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.
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 fuÌr die Kerninformatik unumgaÌ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 praÌsentieren. Das Lehrbuch faÌngt mit der Darstellung von Funktionen und Relationen an, faÌhrt fort mit der Mengenlehre und steigert das Thema zum Konzept von Cantor hinsichtlich des Vergleichs unendlicher GroÌÎČen, der Basis fuÌr die Untersuchung der Grenze der Automatisierbarkeit in der Informatik. Das naÌchste Kapitel, Boolesche Algebra, liefert die Grundlagen der Logik, die fuÌ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 ZaÌhltechniken mit dem Fokus auf der Kombinatorik gewidmet. Das Lehrbuch schlieÎČt mit der diskreten Wahrscheinlichkeitstheorie.
Das ganze Buch traÌgt die klare Unterschrift des Autoren, mindestens fuÌr diejenigen, die ihn kennen. Dazu gehoÌren die PraÌzision und Sinn fuÌr das Ganze sowie fuÌr das Detail. Die Begeisterung des Verfassers fuÌr den zu vermittelnden Stoff kann nicht uÌbersehen werden. Begleitet mit dem entsprechenden Tempo und hoher PraÌgnanz ist es eine ausgezeichnete Quelle fuÌr die Vermittlung der Grundlagen der Mathematik fuÌr Informatiker.
Juraj HromkovicÌ
ETH ZuÌrich
0âEinfuÌ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 FranzoÌsisch, fuÌr unsere frankophonen Freunde und Freundinnen
(Manchmal unterschlage ich die weibliche Schreib-Form aus Bequemlichkeit und auch im Hinblick aufâs fluÌssige Lesen; dass die âLadiesâ* mitgemeint sind, ist eine SelbstverstaÌndlichkeit.)
FuÌr viele Studierende ist Diskrete Mathematik âhartes Brotâ; dieses Buch will helfen, den manchmal abstrakten Formalismus gutmuÌtig aufnehmen zu koÌnnen. Dazu habe ich einen speziellen PraÌsentations-Stil entwickelt, der den Stoff
hoffentlich schmackhaft darbietet. (NatuÌrlich ist Vieles laÌngst nicht so dramatisch wie hier und da zugespitzt, erst recht nicht fuÌr uns Insider; ich adressierâs ja hauptsaÌchlich an Informatik/Mathe-Interessierte und Studierende in der Eingangs-Phase â ok, auch an Fach-Kolleg*en, die dieses BuÌchlein empfehlen moÌgen.
Somit sollte sich das vorliegende Teil auch âstand-aloneâ nutzen lassen, ohne interaktives Erlebnis im HoÌrsaal oder synchroner Online-Session. Meine Studierenden moÌgen mir nachsehen, dass ich laÌ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 fuÌr den âinner circleâ).
Der Aufbau hier laÌuft nicht zwingend entlang einer historischen Schiene oder einer womoÌglich sonst uÌblichen Reihenfolge gehorchend; er dient lediglich einem gewissen Pragmatismus. Hier und da wird mit einem erst spaÌter praÌzisierten Begriff vorgegriffen und Menschen-Verstand zugeschaltet (ohne an Genauigkeit verlieren zu wollen); ein hoch-axiomatisch eingefaÌrbtes Werk fuÌr die werdende Mathematikerin war nicht geplant. Bei der Themen-Auswahl lieÎČ ich mich vom Bedarf fuÌr ein Informatik-Studium leiten. Gerade dort muss peinlichst auf eine saubere Notation geachtet werden â dies einzuuÌben sollte mit diesem Buch gelingen.
Im grundlegenden ersten Kapitel beginnen wir mit den natuÌrlichen Zahlen, fuÌhren Funktionen ein und beleuchten die Welt der Relationen. Im zweiten Kapitel legen wir die Grundlagen der Mengen-Lehre, stellen weiterfuÌhrende Begriffe vor, praÌsentieren innewohnende GesetzmaÌÎČigkeiten und raÌsonieren uÌber die GroÌÎČen-Ordnung sowohl endlicher als auch unendlicher Mengen. (Diese Betrachtung der Unendlichkeit bereitet den Boden fuÌr ein intuitiveres VerstaÌ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 erwaÌhnen sind die Formeln fuÌr die Anzahl moÌglicher Belegungen und Funktionen. Das vierte Kapitel beherbergt die gaÌngigsten Beweis-Prinzipien. Dargeboten werden die Induktion sowohl auf natuÌrlichen Zahlen als auch auf Zeichen-Ketten sowie der direkte und der indirekte Beweis. Mit dem fuÌnften Kapitel gehtâs dann auf die Achterbahn
der ZaÌ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 laÌsst sich als KreativitaÌts-Werkzeug einsetzen, um bei einer ZaÌhl-Aufgabe auf eine geschlossene Formel hoffen zu duÌrfen. Es kommen noch Reihenfolge- und Auswahl-Problem-LoÌsungen an die Reihe, mitsamt Permutations- und Binomial-Koeffizienten. Als Schmankerl biete ich zusaÌ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 verfuÌhren, das Buch gerne zu nutzen. Trotz des uÌbersichtlichen Umfangs, vielleicht gerade wegen der MuÌhe, praÌgnant und ohne unnoÌtigen Ballast formulieren zu wollen, war es ein kleines StuÌ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 moÌge.1 Meine Mathematik-Lehrer/innen (und die -Professoren im Informatik-Studium an der Uni Kaiserslautern) haben natuÌrlich fachlichen Anteil, ohne deren Esprit ich es nicht bis zu diesem Werk gebracht haÌtte; Robert Kirsch, dem ich dieses Buch ebenfalls widme, haÌ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 unerwaÌhnt lassen moÌchte ich die professionelle Umgebung, in der man zumindest nicht behindert werden sollte; dieses Umfeld ist mir derzeit vergoÌnnt. Mein Dank gilt auch meinem Fach-Kollegen Juraj HromkovicÌ, der sich freundlicherweise die Zeit nahm, das Vorwort der Erst-Auflage zu uÌbernehmen. Meine Studierenden, mit denen ich ja schon einiges durchmache2
taten ein UÌbriges: sie wollen die gesprochenen SaÌtze fixiert haben und dieses Traktat als Souvenir â voilaÌ!
SpaÌtestens zum Ende hin schlaÌgt die Stunde des Verlags. Mein Dank geht anâs gesamte Lektorats-Team fuÌr die Koordination des Projekts sowie an die Truppe im
Steinbruch fuÌ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 natuÌrlichen Zahlen; dies ist...
