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