Diskrete Mathematik
Andreas M. Hinz
Universität München
Sommersemester 2006
Inhalt
Die Diskrete Mathematik beschäftigt sich mit endlichen Strukturen. Insbesondere seit der Einführung leistungsfähiger Rechenanlagen bildet sie einen neben der kontinuierlichen Mathematik (Analysis) wichtigen, eigenständigen Ast der modernen Mathematik mit Anwendungen in Modellierung und Informatik. Die Vorlesung sollte eine elementare Einführung in die drei Hauptzweige Kombinatorik, Graphentheorie und Algorithmik geben. Das Leitmotiv bildete der "Turm von Hanoi", ein mathematisches Spiel anhand dessen Beispiels viele der wichtigsten Begriffsbildungen erläutert und studiert werden konnten.
Literatur
Zur Einstimmung:
1. A. Beutelspacher, M.-A. Zschiegner, Diskrete Mathematik für Einsteiger, 2. Auflage, Vieweg, Wiesbaden, 2004.
2. M. Nitzsche, Graphen für Einsteiger, 2. Auflage, Vieweg, Wiesbaden, 2005.
3. A. P. Barth, Algorithmik für Einsteiger, Vieweg, Wiesbaden, 2003.
4. A. M. Hinz, Der Turm von Hanoi, mathe-lmu.de 4(2001), 20-25.
Eine ausführliche, kommentierte Literaturliste liegt mittlerweile vor.
Übungsblätter und korrigierte Lösungen (Abgabe in der Vorlesung oder im Übungskasten) liegen von nun an aus feuerpolizeilichen Gründen (nicht meine Erfindung!) in einem Kasten rechts von den Übungskästen aus.
Skripten zu Kapitel 0 und den Abschnitten 3, 4 und 6 liegen vor.
Die Übungsblätter finden Sie unter
Aufgaben.
Hier finden Sie Teil 1 und hier Teil 2 der Vorlesung.
Es wurde behandelt:
Kapitel 0. Einleitende Beispiele
Kapitel 1. Kombinatorik
1. Das Schubfachprinzip
2. Die natürlichen Zahlen
2.0. Ursprung der natürlichen Zahlen
2.1. Die Chinesischen Ringe
2.2. Quadratfreie Folgen
2.3. Vollständige Induktion
2.4. Metrische Räume
Kapitel 2. Graphen
3. Grundbegriffe über Graphen
4. Bäume
4.1. Grundlegende Eigenschaften von Bäumen
4.2. Aufspannende Bäume und eine weitere Charakterisierung von Bäumen
4.3. Minimale aufspannende Bäume
4.4. Wurzelbäume und indizierte Bäume
4.4.1. Wurzelbäme
4.4.2. Indizierte Bäume
4.4.3. Anmutige Bäume
5. Der Turm von Hanoi
5.0. Die Legende
5.1. Die Lösung
5.2. Analyse der Lösung
5.3. Rückkehr zu quadratfreien Folgen
5.4. Rückkehr zu Graphen
5.5. Metrische Eigenschaften der Hanoi-Graphen T^n
5.5.1. Die Lösung für P_1
5.5.2. Diskussion der Lösung für P_1
5.5.3. Die Lösung für P_2
Kapitel 3. Algorithmen
6. Hanoi-Graphen zu höheren Basen
6.0. Des Teufels Nadel
6.1. Höhere Basen
6.1.1. Planarität
6.1.2. Färbungen
6.1.3. Metrische Eigenschaften von Q^n
6.2. Dijkstras Algorithmus
Die Scheine können ab jetzt bei mir (Raum 245) abgeholt werden,
ab Anfang September dann im Prüfungssekretariat.
Herr Maximilian Mair wird gebeten, einen Übungsschein auszufüllen.
A. M. Hinz, Andreas.Hinz@mathematik.uni-muenchen.de, 2008-02-06