Das Standardwerk über Diskrete Mathematik in deutscher Sprache. 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 etwa die Hälfte der Übungen. Das Buch eignet sich für Lehrveranstaltungen im Bereich Diskrete Mathematik, Kombinatorik, Graphen und Algorithmen.
Abzählung: Grundlagen - Summation - Erzeugende Funktionen - Muster - Asymptotische Analyse - Graphen und Algorithmen: Graphen - Bäume - Matchings und Netzwerke - Suchen und Sortieren - Allgemeine Optimierungsmethoden - Algebraische Systeme: Boolesche Algebren - Modulare Arithmetik - Codierung - Kryptographie - Lineare Optimierung - Lösungen zu ausgewählten Übungen.
/ AUS DEM INHALT: / / /
Vorwort v
Teil I: Abzählung 1
1 Grundlagen 3
1.1 Elementare Zählprinzipien 3
1.2 Die fundamentalen Zählkoeffizienten 6
1.3 Permutationen 10
1.4 Rekursionen 13
1.5 Diskrete Wahrscheinlichkeitsrechnung 18
1.6 Existenzaussagen 24
Übungen 27
2 Summation 35
2.1 Direkte Methoden 35
2.2 Differenzenrechnung 39
2.3 Inversion 45
2.4 Inklusion-Exklusion 48
Übungen 53
3 Erzeugende Funktionen 57
3.1 Definition und Beispiele 57
3.2 Lösung von Rekursionen 58
3.3 Erzeugende Funktionen vorn Exponentialtyp 65
Übungen 67
4 Abzählung von Mustern 73
4.1 Symmetrien 73
4.2 Problemstellung 75
4.3 Muster und Zyklenindikator 77
4.4 Der Satz von Polya 79
Übungen 85
5 Asymptotische Analyse 89
5.1 Wachstum von Funktionen 89
5.2 Größenordnung von Rekursionen 93
5.3 Laufzeit von Algorithmen 96
Übungen 98
Literatur zu Teil I 102
Teil II : Graphen und Algorithmen 103
6 Graphen 105
6.1 Definition und Beispiele 105
6.2 Darstellung von Graphen 109
6.3 Wege und Kreise 112
6.4 Gerichtete Graphen 115
Übungen 118
7 Bäume 123
7.1 Begriff und Charakterisierung 123
7.2 Breadth-First und Depth-First Suche 126
7.3 Minimale aufspannende Bäume 128
7.4 Kürzeste Wege in Graphen 131
Übungen 133
8 Matchings und Netzwerke 137
8.1 Matchings in bipartiten Graphen 137
8.2 Konstruktion von optimalen Matchings 141
8.3 Flüsse in Netzwerken 147
8.4 Eulersche Graphen, das Traveling Salesman-Problem 153
8.5 Die Komplexitätsklassen P und NP 161
Übungen 163
9 Suchen und Sortieren 169
9.1 Suchprobleme und Entscheidungsbäume 169
9.2 Der Hauptsatz der Suchtheorie 172
9.3 Sortieren von Listen 178
9.4 Binäre Suchbäume 184
Übungen 190
10 Allgemeine Optimierungsmethoden 195
10.1 Backtrack 195
10.2 Dynamisches Programmieren 199
10.3 Der Greedy-Algorithmus 206
Übungen 209
Literatur zu Teil II 212
Teil III: Algebraische Systeme 213
11 Boolesche Algebren 215
11.1 Definition und Eigenschaften 215
11.2 Aussagenlogik und Boolesche Funktionen 217
11.3 Logische Netze 221
11.4 Boolesche Verbände, Ordnungen, Hypergraphen 225
Übungen 231
12 Modulare Arithmetik 235
12.1 Rechnen mit Kongruenzen 235
12.2 Endliche Körper 237
12.3 Lateinische Quadrate 239
12.4 Kombinatorische Designs 243
Übungen 250
13 Codierung 255
13.1 Problemstellung 255
13.2 Quellencodierung 256
13.3 Entdecken und Korrigieren von Fehlern 258
13.4 Lineare Codes 262
13.5 Zyklische Codes 267
Übungen 270
14 Kryptographie 275
14.1 Kryptosysteme 275
14.2 Lineare Schieberegister 278
14.3 Öffentliche Schlüsselsysteme 284
14.4 Zero-Knowledge-Protokolle 288
Übungen 291
15 Lineare Optimierung 295
15.1 Beispiele und Definitionen 295
15.2 Dualität 297
15.3 Der Hauptsatz der linearen Optimierung 302
15.4 Zulässige Lösungen und optimale Lösungen 307
15.5 Der Simplexalgorithmus 311
15.6 Ganzzahlige lineare Optimierung 318
Übungen 320
Literatur zu Teil III 323
Lösungen zu ausgewählten Übungen 325
Sachwortverzeichnis 351