Diskrete Mathematik, SS 2016/17
Termine
| Course: |
Wednesday, 10:15 - 11:45 Uhr, Geomatikum H3, |
Friday, 08:15 - 09:45 Uhr, Geomatikum H3 |
| Exercises: |
Wednesday, 14:15 - 15:45 Uhr, Geomatikum 241, |
Friday, 10:15 - 11:45 Uhr, Geomatikum 142 |
| No lecture on 12.04. |
| First Exercise Session on 19.04. |
Exercises
There is an exercise sheet (approximately) every week. The exercises are (usually) due to Friday before the lecture (and in any case stated on each exercise sheet). You can work on the exercises in pairs. To participate in the final exam, you are expected to collect 50% of the exercises (in total). In general, you might be asked to present your solutions during the exercise sessions. The exercise sheets will be uploaded here, as well as in StiNe.
Prerequisites
Parts of the course are based on basic notions of Linear Algebra, Analytic Geometry and Analysis. Basic knowledge on these topics is recommended, but not a must.
Content
We follow the german version of the book Diskrete Mathematik – Eine Entdeckungsreise of Matoušek and Nešetřil. There are multiple copies of it in the library.
Lectures:
| 05.04. | Eine Sammlung von Problemen
|
| 07.04. | Relationen, spezielle Relationen
|
| 19.04. | Ordnungen, Lineare Ordnungen, Hasse-Diagramme, Existenz linearer Erweiterung
|
| 21.04. | Einbettungen partieller Ordnungen, Ketten und Antiketten, Länge und Weite eines Posets, Erdös-Szekeres-Lemma |
| 26.04. | Anzahl von Abbildungen und Teilmengen, Permutationen, Binomialkoeffizienten, Binomialsatz |
| 28.04. | Näherungen, Landau-Notation, Abschätzungen der Fakultät und der Binomialkoeffizienten |
| 03.05. | Anzahl der Lösungen einer Gleichung, Inklusion-Exklusion, Fixpunktfreie Permutationen |
| 05.05. | Graphen, Isomorphie, Zusammengang, Teilgraphen, Abstand, Adjazenzmatrix |
| 10.05. | Gradfolgen eines Graphen, Eulersche Graphen |
| 12.05. | 2-zusammenhang, Ohrenzerlegung, Satz von Mantel (eine Richtung) |
| 17.05. | Satz von Mantel (Rückrichtung), Bäume und Charakterisierungen |
| 19.05. | Isomorphismen von Bäumen, Aufspannende Bäume und Algorithmen |
| 24.05. | Minimal Aufspannende Bäume, Algorithmen von Kruskal und Jarnik |
| 26.05. | Sperner-Lemma und Brouwerscher Fixpunktsatz (Aussage), das HEX-Spiel, Satz von Sperner (Anfang) |
| 31.05. | Satz von Sperner (zwei Beweise) |
| 02.06. | K_2,2-freie Graphen, Cauchy-Schwarzsche-Ungleichung, Erster Beweis der Cayley-Formel |
| 14.06. | Beweis der Cayley-Formel mit Determinanten |
| 16.06. | Endliche Projektive Ebenen, Definition und Eigenschaften |
| 23.06. | Existenz Projektiver Ebenen, Orthogonale lateinische Quadrate, Kombinatorische Anwendungen |
| 28.06. | Zählargumente, Endliche Wahrscheinlichkeitsräume, Zufallsfolgen, Zufällige Permutationen |
| 30.06. | Zufallsgraphen, Zufallsvariable und Erwartungswert |
| 05.07. | Probabilistische Anwendungen: Grosse bipartite Teilgraphen, Satz von Turan, Schnittpunkte auf der Ebene |
| 07.07. | Erzeugende Funktionen, Polynone und Potenzreihen |
| 12.07. | Fibonnacci-Zahlen, Homogene lineare Rekursionen, Abzählen binärer Bäume |
| 14.07. | Würfeln, Züfallswege, Zahlpartitionen |
|
