Diskrete Mathematik

Grundlage der Informatik

Walter Hower

• Editorial: De Gruyter Oldenbourg
• Año: 2021
• ISBN:
  9783110695670
• Edición: 2
• Categoría: Computer Science
• Categoría: Computer Science General

Diskrete Mathematik zählt zu den Grundlagen der Informatik. Dieses Teilgebiet der Mathematik ermöglicht den Studierenden, diese Grundlagen schnell zu verinnerlichen und den Praxistransfer zu bewerkstelligen.

Vorwort zur 1. Auflage

Die Informatik hat die Mathematik zur Technologie gemacht. Auf der einen Seite nutzt sie mathematische Konzepte in unterschiedlichsten Anwendungen, andererseits bereichert sie die Mathematik durch neue Konzepte und Erkenntnisse. Heute gibt es kaum Teilbereiche der Mathematik, deren Methoden im Zusammenhang mit der Informatik in irgendwelchen technischen Anwendungen oder der wissenschaftlichen Forschung nicht angewendet werden. Unter diesen vielen Mathematikkenntnissen gibt es ein paar Grundbereiche, die für die Kerninformatik unumgänglich sind und mit denen jede Informatikerin und jeder Informatiker vertraut sein muss. Gerade diesen zentralen Themen ist das Lehrbuch von Walter Hower gewidmet.

Die Mathematik zu vermitteln bedeutet, die grundlegenden Konzepte und Begriffe zu bilden und ihre Methoden zu präsentieren. Das Lehrbuch fängt mit der Darstellung von Funktionen und Relationen an, fährt fort mit der Mengenlehre und steigert das Thema zum Konzept von Cantor hinsichtlich des Vergleichs unendlicher Gröβen, der Basis für die Untersuchung der Grenze der Automatisierbarkeit in der Informatik. Das nächste Kapitel, Boolesche Algebra, liefert die Grundlagen der Logik, die für jeden Wissenschaftler unabdingbar sind. Das darauf folgende Kapitel behandelt die korrekte Argumentation in Form von mathematischen Beweisen; hier kommen sowohl der direkte als auch der indirekte Beweis zum Tragen, ebenso die Induktion. Danach folgendes Thema ist den Zähltechniken mit dem Fokus auf der Kombinatorik gewidmet. Das Lehrbuch schlieβt mit der diskreten Wahrscheinlichkeitstheorie.

Das ganze Buch trägt die klare Unterschrift des Autoren, mindestens für diejenigen, die ihn kennen. Dazu gehören die Präzision und Sinn für das Ganze sowie für das Detail. Die Begeisterung des Verfassers für den zu vermittelnden Stoff kann nicht übersehen werden. Begleitet mit dem entsprechenden Tempo und hoher Prägnanz ist es eine ausgezeichnete Quelle für die Vermittlung der Grundlagen der Mathematik für Informatiker.

Juraj Hromkovič

ETH Zürich

0 Einführung

Das vorliegende Buch korrespondierte mal zu meiner gleichnamigen Erst-Semester-Vorlesung, die von 150 englisch-sprachigen Beamer-Folien getragen wurde. Dies bewog mich dazu, auch hier die Terminologie teilweise in Englisch zu fassen ― neben dem „Seiten-Effekt” der einfacheren Erschlieβung der internationalen Standard-Literatur, aus der ich eine kleine Auswahl am Ende aufgelistet habe, einschlieβlich eines Werkes in Französisch, für unsere frankophonen Freunde und Freundinnen

(Manchmal unterschlage ich die weibliche Schreib-Form aus Bequemlichkeit und auch im Hinblick auf’s flüssige Lesen; dass die „Ladies”* mitgemeint sind, ist eine Selbstverständlichkeit.)

Für viele Studierende ist Diskrete Mathematik „hartes Brot”; dieses Buch will helfen, den manchmal abstrakten Formalismus gutmütig aufnehmen zu können. Dazu habe ich einen speziellen Präsentations-Stil entwickelt, der den Stoff

hoffentlich schmackhaft darbietet. (Natürlich ist Vieles längst nicht so dramatisch wie hier und da zugespitzt, erst recht nicht für uns Insider; ich adressier’s ja hauptsächlich an Informatik/Mathe-Interessierte und Studierende in der Eingangs-Phase ― ok, auch an Fach-Kolleg*en, die dieses Büchlein empfehlen mögen.

Somit sollte sich das vorliegende Teil auch „stand-alone” nutzen lassen, ohne interaktives Erlebnis im Hörsaal oder synchroner Online-Session. Meine Studierenden mögen mir nachsehen, dass ich längst nicht alle Schenkel-Klopfer in den Text einstreuen konnte; trotz vorliegendem Skript-Buch jedoch wird’s in der Vorlesung nicht langweilig. Wie bei manchem Smiley: Da bleibt nicht nur kein Auge trocken (Bemerkung für den „inner circle”).

Der Aufbau hier läuft nicht zwingend entlang einer historischen Schiene oder einer womöglich sonst üblichen Reihenfolge gehorchend; er dient lediglich einem gewissen Pragmatismus. Hier und da wird mit einem erst später präzisierten Begriff vorgegriffen und Menschen-Verstand zugeschaltet (ohne an Genauigkeit verlieren zu wollen); ein hoch-axiomatisch eingefärbtes Werk für die werdende Mathematikerin war nicht geplant. Bei der Themen-Auswahl lieβ ich mich vom Bedarf für ein Informatik-Studium leiten. Gerade dort muss peinlichst auf eine saubere Notation geachtet werden ― dies einzuüben sollte mit diesem Buch gelingen.

Im grundlegenden ersten Kapitel beginnen wir mit den natürlichen Zahlen, führen Funktionen ein und beleuchten die Welt der Relationen. Im zweiten Kapitel legen wir die Grundlagen der Mengen-Lehre, stellen weiterführende Begriffe vor, präsentieren innewohnende Gesetzmäβigkeiten und räsonieren über die Gröβen-Ordnung sowohl endlicher als auch unendlicher Mengen. (Diese Betrachtung der Unendlichkeit bereitet den Boden für ein intuitiveres Verständnis der Unberechenbarkeit in der Theoretischen Informatik.) Das dritte Kapitel behandelt die Boolesche Algebra. Begrifflichkeiten und Gesetze werden dargelegt sowie die entsprechenden Werte-Tafeln aufgestellt; interessant zu erwähnen sind die Formeln für die Anzahl möglicher Belegungen und Funktionen. Das vierte Kapitel beherbergt die gängigsten Beweis-Prinzipien. Dargeboten werden die Induktion sowohl auf natürlichen Zahlen als auch auf Zeichen-Ketten sowie der direkte und der indirekte Beweis. Mit dem fünften Kapitel geht’s dann auf die Achterbahn

der Zähl-Techniken. Hier finden sich Summen-, Produkt- und Quotienten-Regel ebenso ein wie das Schubfach-Prinzip und der Mechanismus des Ein-/Ausschlusses. Die dort folgende Rekurrenz-Relation lässt sich als Kreativitäts-Werkzeug einsetzen, um bei einer Zähl-Aufgabe auf eine geschlossene Formel hoffen zu dürfen. Es kommen noch Reihenfolge- und Auswahl-Problem-Lösungen an die Reihe, mitsamt Permutations- und Binomial-Koeffizienten. Als Schmankerl biete ich zusätzlich die Stirling-Zahlen erster und zweiter Art, also Zyklus- bzw. Teilmengen-Zahlen, und die Bell-Zahlen an. Das sechste Kapitel mit der allgemeinen und bedingten Wahrscheinlichkeits-Theorie (einschlieβlich des obligatorischen Ziegen-Problems

) liefert den Show-down.

Es ist ein recht handliches Exemplar geworden; dies sollte Sie/dich dazu verführen, das Buch gerne zu nutzen. Trotz des übersichtlichen Umfangs, vielleicht gerade wegen der Mühe, prägnant und ohne unnötigen Ballast formulieren zu wollen, war es ein kleines Stück Arbeit. Auf diesem Weg dahin haben mich einige mir wohlgesonnene Geister begleitet. Selbstredend sind meine Eltern zu nennen, von denen wenigstens meine Mutter das End-Produkt im wahrsten Sinne des Wortes noch sehen möge.¹ Meine Mathematik-Lehrer/innen (und die -Professoren im Informatik-Studium an der Uni Kaiserslautern) haben natürlich fachlichen Anteil, ohne deren Esprit ich es nicht bis zu diesem Werk gebracht hätte; Robert Kirsch, dem ich dieses Buch ebenfalls widme, hätte es sicher gern noch erlebt. Im privaten Bereich profitiere ich, auch emotional, stark von meiner Familie; meine drei Girlies tragen immer motivierend bei. Nicht ganz unerwähnt lassen möchte ich die professionelle Umgebung, in der man zumindest nicht behindert werden sollte; dieses Umfeld ist mir derzeit vergönnt. Mein Dank gilt auch meinem Fach-Kollegen Juraj Hromkovič, der sich freundlicherweise die Zeit nahm, das Vorwort der Erst-Auflage zu übernehmen. Meine Studierenden, mit denen ich ja schon einiges durchmache²

taten ein Übriges: sie wollen die gesprochenen Sätze fixiert haben und dieses Traktat als Souvenir ― voilà!

Spätestens zum Ende hin schlägt die Stunde des Verlags. Mein Dank geht an’s gesamte Lektorats-Team für die Koordination des Projekts sowie an die Truppe im

Steinbruch für die damals sehr hilfreiche Herstellung meiner handgezeichneten Vorlagen.

So ist es vollbracht; viel Spaβ mit Diskrete Mathematik ― Grundlage der Informatik !

1 Grundstock

Wir beginnen ganz harmlos mit den Grundlagen des Gebiets. Fundamental sind sicher die Peano-Axiome zusammen mit der Menge der natürlichen Zahlen; dies ist...