Elemente der diskreten Mathematik
Description
Die Grundidee des vorliegenden Lehrbuchs ist, wesentliche Elemente der diskreten Mathematik zu vermitteln, um die modernen Entwicklungen im Informationszeitalter kompetent mathematisch beurteilen zu können. Hierzu gehören das Verständnis von Graphen, das Rechnen mit großen Zahlen und das Rechnen modulo n . Die Autoren beginnen mit einer Darstellung der elementaren Zahlentheorie. Insbesondere wird die Verschlüsselung mit dem RSA-Verfahren erläutert. Danach werden Abschätzungen behandelt, die unerlässlich sind, wenn man Objekte zählen oder Laufzeiten wichtiger Algorithmen verstehen möchte. Diverse in der Praxis vollkommen zuverlässige Algorithmen nehmen den Zufall zu Hilfe, um überhaupt zu einem Ergebnis zu kommen. Daher darf ein Kapitel zur diskreten Wahrscheinlichkeit nicht fehlen. Danach begibt sich der Leser ins Zentrum der diskreten Mathematik. Es werden Kombinatorik, erzeugende Funktionen und Graphentheorie behandelt. Zum Abschluss widmen sich die Autoren Ordnungsstrukturen und Verbänden sowie booleschen Funktionen und Schaltkreisen.
Das Buch ergänzt und vertieft Grundlagen und zeigt mögliche Anwendungen auf. Es werden aber auch Themen behandelt, die über den Standardstoff hinaus gehen. Einen hohen Stellenwert nehmen Aufgaben und Lösungen ein. Für alle wichtigen Aussagen geben die Autoren vollständige Beweise an. Am Ende eines jeden Kapitels sind kurze Kapitelzusammenfassungen als Lern- und Merkhilfe hinzugefügt.
Das benötigte Vorwissen ist gering. Die behandelten Grundlagen sind keine bloßen Aneinanderreihungen von Definitionen und elementaren Zusammenhängen. Das Buch vermittelt ein tieferes Verständnis für die behandelten mathematischen Zusammenhänge und stellt Wissen, Techniken und Denkweisen vor, welche den Leser in die Lage versetzen, selbstständig mathematische Probleme zu lösen.
More details
Other editions
Additional editions
Persons
Content
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]
