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