Diskrete Mathematik

Vor 50 Jahren gab es den Begriff "Diskrete Mathematik" nicht, und er ist auch heute im deutschen Sprachraum keineswegs gebräuchlich. Vorlesungen dazu werden nicht überall und schon gar nicht mit einem einheitlichen Themenkatalog angeboten (im Gegensatz zum Beispiel zu den USA, wo sie seit langem einen festen Platz haben). Die Mathematiker verstehen unter Diskreter Mathematik meist Kombinatorik oder Graphentheorie, die Informatiker Diskrete Strukturen oder Boolesche Algebren. Das Hauptanliegen dieses Buches ist daher, solch einen Themenkatalog zu präsentieren, der alle Grundlagen für ein weiterführendes Studium enthält. Die Diskrete Mathematik beschäftigt sich vor allem mit endlichen Mengen. Was kann man in endlichen Mengen studieren? Als allererstes kann man sie abzählen, dies ist das klassische Thema der Kombinatorik - in Teil I werden wir die wich tigsten Ideen und Methoden zur Abzählung kennenlernen. Auf endlichen Mengen ist je nach Aufgabenstellung meist eine einfache Struktur in Form von Relationen gegeben, von denen die anwendungsreichsten die Graphen sind. Diese Aspekte fas sen wir in Teil II unter dem Titel Graphen und Algorithmen zusammen. Und schließlich existiert auf endlichen Mengen oft eine algebraische Struktur (oder man kann eine solche auf natürliche Weise erklären). Algebraische Systeme sind der Inhalt von Teil III. Diese drei Gesichtspunkte bilden den roten Faden des Buches. Ein weiterer Aspekt, der die Darstellung durchgehend prägt, betrifft den Begriff der Optimierung.

Das Buch ist das erste umfassende Lehrbuch über Diskrete Mathematik in deutscher Sprache. Es besteht aus drei Teilen: Abzählung, Graphen und Algorithmen, Algebraische Systeme, die weitgehend unabhängig voneinander gelesen werden können. Jeder Teil schließt mit einer Literaturliste für ein weiterführendes Studium. Großer Wert wird auf die Übungen gelegt, die etwa ein Viertel des Textes ausmachen. Die Übungen sind nach Schwierigkeitsgrad gegliedert, im Anhang findet man Lösungen für ausgewählte Übungen. Vorausgesetzt werden nur Vertrautheit mit mathematischen Grundbegriffen sowie Grundkenntnisse in Analysis und Linearer Algebra, wie sie überlicherweise im 1. Semester erworben werden. Das Buch eignet sich für Lehrveranstaltungen im Bereich Diskrete Mathematik, Kombinatorik, Graphen und Algorithmen.

Autorentext

Prof. Dr. Martin Aigner ist an der FU Berlin tätig.

Klappentext

Großer Wert wird auf die Übungen gelegt, die etwa ein Viertel des Textes ausmachen. Das Buch eignet sich für Lehrveranstaltungen im Bereich Diskrete Mathematik, Kombinatorik, Graphen und Algorithmen.

Inhalt
I: Abzählung.- 1 Grundlagen.- 2 Summation.- 3 Erzeugende Funktionen.- 4 Asymptotische Analyse.- Literatur zu Teil I.- II: Graphen und Algorithmen.- 5 Graphen.- 6 Bäume.- 7 Matchings und Netzwerke.- 8 Suchen und Sortieren.- 9 Allgemeine Optimierungsmethoden.- Literatur zu Teil II.- III: Algebraische Systeme.- 10 Boolesche Algebren.- 11 Modulare Arithmetik.- 12 Codes und Kryptographie.- 13 Lineare Optimierung.- Literatur zu Teil III.- Lösungen zu ausgewählten Übungen.- Sachwortverzeichnis.