Dozent: Amin Coja-Oghlan
Termine
Beginn der Vorlesung: 19.10.2004| VL | Dienstag | 09:00 - 11:00 | (RUD 26, 1.306) |
|---|---|---|---|
| Donnerstag | 09:00 - 11:00 | (RUD 26, 1.306) | |
| UE | Dienstag | 11:00 - 13:00 | (RUD 26, 1.306) Manuel Bodirsky |
| PR | (semesterbegleitend) | Martin Thimm | |
| Sprechzeiten | Mittwoch | 14:00 - 15:00 | (RUD 25, 3.410) Manuel Bodirsky |
| Donnerstag | 14:00 - 15:00 | (RUD 26, 3.415) Amin Coja-Oghlan | |
Zuordnung
- Hauptstudium, 1. Teil eines Kurses
- Theoretische Informatik
Inhalte und Lernziele
Ein Graph besteht aus einer Menge von Knoten, von denen einige durch Kanten verbunden sind. Hier sind Beispiele für Graphen:
 |
 |
 |
| Der "Petersen Graph" | Ein Baum | Der "Heawood Graph" |
Mit Hilfe dieser relativ einfachen Struktur lassen sich viele fundamentale Probleme modellieren und mittels geeigneter Graphenalgorithmen auch effizient lösen, wie beispielsweise
- wie findet man den kürzesten Weg von einem Ort zu einem anderen?
- wie färbt man eine Landkarte mit möglichst wenigen Farben so, dass benachbarte Länder verschiedene Farben erhalten?
- wie plant man eine Rundreise durch n Städte so, dass die insgesamt zürckgelegte Strecke mölichst kurz wird?
- ...
Besonders interessant ist die Art und Weise, in der algorithmische Probleme strukturelle Fragen über Graphen aufwerfen, deren Beantwortung dann zu verbesserten Algorithmen führt.
Folgende Themen sollen im Wintersemester behandelt werden:- Grundlagen
- Zusammenhang
- Flüsse
- Matchings
- Eulersche/Hamiltonsche Graphen
- Das Traveling-Salesman-Problem
- Färbungen
- Planarität
- Minimal spannende Bäume
Übungen
Leiter: Manuel Bodirsky
Den Stoff der Vorlesung können Sie nur verstehen, wenn Sie sich
aktiv damit beschäftigen. Die Übungen werden Sie dabei
unterstützen. Jeden Dienstag gibt es ein neues Übungsblatt.
Die Lösungen werden in der darauffolgenden Woche am Ende der
Vorlesung abgegeben, und gleich besprochen. In der nächsten
Woche werden die korrigierten Übungen zurückgegeben, und bei
Bedarf können sie dann nochmal besprochen werden.
Um die Vorlesung zu bestehen, benötigen Sie 50% der erreichbaren
Punkte für die Übungen. Ausserdem ist die erfolgreiche
Teilnahme am dazugehörenden Programmierpraktikum notwendig, das am
Ende des Semesters stattfindet. Die Übungen sollten in Zweier-
oder Dreiergruppen bearbeitet
werden.
- Übungsblatt 1 - Abgabe 26.10.2004
- Übungsblatt 2 - Abgabe 2.11.2004
- Übungsblatt 3 - Abgabe 9.11.2004
- Übungsblatt 4 - Abgabe 16.11.2004
- Übungsblatt 5 - Abgabe 23.11.2004
- Übungsblatt 6 - Abgabe 30.11.2004
- Übungsblatt 7 - Abgabe 7.12.2004
- Übungsblatt 8 - Abgabe 14.12.2004
- Übungsblatt 9 - Abgabe 4.1.2005
- Übungsblatt 10 - Abgabe 11.1.2005
- Übungsblatt 11 - Abgabe 18.1.2005
- Übungsblatt 12 - Abgabe 25.1.2005
- Übungsblatt 13 - Abgabe 1.2.2005
- Übungsblatt 14 - Abgabe 8.2.2005
- Übungsblatt 15 - Serie 15 wird das letzte Übungsblatt zu dieser Vorlesung. Abgabe 15.2.2005.
Links
Programmierpraktikum
Prüfung
Die Prüfungen finden am 24.2. und am 3.3.2005 statt. Zur Teilnahme an der Prüfung ist es notwendig, bis zum 31.1. das Anmeldeformular in der Vorlesung abzugeben.
Empfohlene Literatur
- , Graphen und Algorithmen 1
- , Einführung in Graphen und Algorithmen
- , Graphentheorie, Springer Verlag, 2000
- , Introduction to Graph Theory, Prentice Hall, 1996
English