Elemente der diskreten Mathematik

1 - Vorwort [Seite 5]
2 - 1 Elementare Zahlentheorie [Seite 13]
2.1 - 1.1 Einführung [Seite 13]
2.1.1 - 1.1.1 Von natürlichen zu komplexen Zahlen [Seite 13]
2.1.2 - 1.1.2 Von Halbgruppen zu Körpern [Seite 14]
2.2 - 1.2 Der euklidische Algorithmus [Seite 15]
2.3 - 1.3 Der Fundamentalsatz der Arithmetik [Seite 17]
2.4 - 1.4 Modulare Arithmetik [Seite 18]
2.5 - 1.5 Anwendungen der modularen Arithmetik [Seite 20]
2.5.1 - 1.5.1 Bits und Bytes [Seite 20]
2.5.2 - 1.5.2 Fehlererkennung bei Artikelnummern [Seite 21]
2.6 - 1.6 Der chinesische Restsatz [Seite 21]
2.7 - 1.7 Ein erster Primzahltest nach Fermat [Seite 24]
2.8 - 1.8 Die schnelle Exponentiation [Seite 25]
2.9 - 1.9 Verschlüsselung mit dem RSA-Verfahren [Seite 27]
2.10 - 1.10 Die Euler'sche phi-Funktion [Seite 29]
2.11 - 1.11 Fibonacci-Zahlen [Seite 33]
2.12 - 1.12 Laufzeitanalyse des euklidischen Algorithmus [Seite 37]
2.13 - Aufgaben [Seite 38]
2.14 - Zusammenfassung [Seite 42]
3 - 2 Einige nützliche Abschätzungen [Seite 44]
3.1 - 2.1 Das Wachstum der Fakultät [Seite 44]
3.2 - 2.2 Das Wachstum der Binomialkoeffizienten [Seite 45]
3.3 - 2.3 Das Wachstum des kleinsten gemeinsamen Vielfachen [Seite 17]
3.4 - 2.4 Aussagen zur Primzahldichte [Seite 51]
3.5 - 2.5 Das Bertrand'sche Postulat [Seite 53]
3.6 - Aufgaben [Seite 55]
3.7 - Zusammenfassung [Seite 56]
4 - 3 Diskrete Wahrscheinlichkeitsrechnung [Seite 57]
4.1 - 3.1 Wahrscheinlichkeitsräume und Erwartungswerte [Seite 57]
4.2 - 3.2 Die Jensen'sche Ungleichung [Seite 61]
4.3 - 3.3 Das Geburtstagsparadoxon [Seite 62]
4.4 - Aufgaben [Seite 63]
4.5 - Zusammenfassung [Seite 65]
5 - 4 Kombinatorik [Seite 66]
5.1 - 4.1 Abzählende Kombinatorik [Seite 66]
5.2 - 4.2 Binomialkoeffizienten [Seite 68]
5.3 - 4.3 Durchschnittsanalyse von Bubble-Sort [Seite 80]
5.4 - 4.4 Das Prinzip von Inklusion und Exklusion [Seite 81]
5.5 - 4.5 Rencontres-Zahlen [Seite 84]
5.6 - 4.6 Stirling-Zahlen [Seite 85]
5.6.1 - 4.6.1 Die Stirling-Zahlen zweiter Art [Seite 86]
5.6.2 - 4.6.2 Die Stirling-Zahlen erster Art [Seite 90]
5.7 - 4.7 Bell-Zahlen [Seite 94]
5.8 - 4.8 Partitionszahlen [Seite 95]
5.9 - 4.9 Catalan-Zahlen [Seite 98]
5.9.1 - 4.9.1 Dyck-Wörter und Catalan-Zahlen [Seite 98]
5.9.2 - 4.9.2 Binärbäume und Catalan-Zahlen [Seite 100]
5.10 - 4.10 Die mittlere Höhe binärer Suchbäume [Seite 102]
5.11 - Aufgaben [Seite 104]
5.12 - Zusammenfassung [Seite 108]
6 - 5 Erzeugende Funktionen [Seite 111]
6.1 - 5.1 Gewöhnliche erzeugende Funktionen [Seite 111]
6.1.1 - 5.1.1 Fibonacci-Zahlen [Seite 112]
6.1.2 - 5.1.2 Catalan-Zahlen [Seite 113]
6.1.3 - 5.1.3 Stirling-Zahlen zweiter Art [Seite 114]
6.1.4 - 5.1.4 Partitionszahlen [Seite 114]
6.1.5 - 5.1.5 Das Wachstum der Partitionszahlen [Seite 118]
6.1.6 - 5.1.6 Der Pentagonalzahlensatz [Seite 119]
6.2 - 5.2 Exponentielle erzeugende Funktionen [Seite 123]
6.2.1 - 5.2.1 Stirling-Zahlen erster Art [Seite 124]
6.2.2 - 5.2.2 Bell-Zahlen [Seite 125]
6.3 - Aufgaben [Seite 125]
6.4 - Zusammenfassung [Seite 127]
7 - 6 Graphentheorie [Seite 129]
7.1 - 6.1 Grundbegriffe [Seite 129]
7.2 - 6.2 Eulerkreise und Hamiltonkreise [Seite 135]
7.3 - 6.3 Bäume [Seite 138]
7.4 - 6.4 Die Cayley-Formel [Seite 140]
7.5 - 6.5 Der Heiratssatz [Seite 142]
7.6 - 6.6 Stabile Heirat [Seite 143]
7.7 - 6.7 Der Satz von Menger [Seite 146]
7.8 - 6.8 Maximale Flüsse [Seite 147]
7.8.1 - 6.8.1 Der Satz von Ford und Fulkerson [Seite 148]
7.8.2 - 6.8.2 Residualgraphen und Verbesserungspfade [Seite 151]
7.8.3 - 6.8.3 Der Algorithmus von Dinitz [Seite 153]
7.9 - 6.9 Planare Graphen [Seite 156]
7.9.1 - 6.9.1 Die Eulerformel [Seite 158]
7.9.2 - 6.9.2 Färbungen von planaren Graphen [Seite 160]
7.9.3 - 6.9.3 Planare Separatoren [Seite 161]
7.10 - 6.10 Der Satz von Ramsey [Seite 164]
7.11 - Aufgaben [Seite 168]
7.12 - Zusammenfassung [Seite 171]
8 - 7 Ordnungsstrukturen und Verbände [Seite 173]
8.1 - 7.1 Halbordnungen [Seite 173]
8.2 - 7.2 Vollständige Halbordnungen [Seite 177]
8.3 - 7.3 Denotationale Semantik [Seite 178]
8.4 - 7.4 Kleinste Fixpunkte für monotone Abbildungen [Seite 181]
8.5 - 7.5 Verbände [Seite 183]
8.6 - 7.6 Vollständige Verbände [Seite 185]
8.7 - 7.7 Modulare und distributive Verbände [Seite 186]
8.8 - 7.8 Boolesche Verbände [Seite 191]
8.9 - 7.9 Boolesche Ringe [Seite 193]
8.10 - 7.10 Der allgemeine Darstellungssatz von Stone [Seite 195]
8.11 - Aufgaben [Seite 199]
8.12 - Zusammenfassung [Seite 200]
9 - 8 Boolesche Funktionen und Schaltkreise [Seite 202]
9.1 - 8.1 Shannons obere Schranke für die Anzahl der Gatter [Seite 204]
9.2 - 8.2 Die untere Schranke von Shannon [Seite 205]
9.3 - 8.3 Die obere Schranke von Lupanov [Seite 208]
10 - A Grundlagen [Seite 211]
10.1 - A.1 Mengen, Relationen und Abbildungen [Seite 211]
10.2 - A.2 Die O-Notation [Seite 212]
11 - B Lösungen der Aufgaben [Seite 214]
12 - Literaturverzeichnis [Seite 245]
13 - Symbolverzeichnis [Seite 247]
14 - Index [Seite 251]