Diekert / Kufleitner / Rosenberger Elemente der diskreten Mathematik

Zahlen und Zählen, Graphen und Verbände
1. Auflage 2013
ISBN: 978-3-11-027816-3
Verlag: De Gruyter
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Deutsch, 259 Seiten

Reihe: De Gruyter Studium

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.

Zielgruppe

Bachelorstudierende, Dozenten; Akademische Bibliotheken

Autoren/Hrsg.

Diekert, Volker

Kufleitner, Manfred

Rosenberger, Gerhard

Fachgebiete

• Mathematik | Informatik Mathematik Algebra Zahlentheorie
• Mathematik | Informatik Mathematik Operations Research Graphentheorie
• Mathematik | Informatik Mathematik Mathematik Allgemein Diskrete Mathematik, Kombinatorik

Inhaltsverzeichnis

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

Über Autor(innen)

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.