Elemente der diskreten Mathematik (eBook)

lt;!doctype html public "-//w3c//dtd html 4.0 transitional//en">

Volker Diekert und Manfred Kufleitner, Universität Stuttgart; Gerhard Rosenberger, Universität Hamburg.

Volker Diekert and Manfred Kufleitner, University of Stuttgart, Germany; Gerhard Rosenberger, University of Hamburg, Germany.

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