Dozent: Manuel Bodirsky
Termine
Beginn der Vorlesung: 18.04.2007.| VL | Mittwoch | 11:15 - 12:45 | RUD 25, 3’011 | Manuel Bodirsky |
|---|---|---|---|---|
| Freitag | 11:15 - 12:45 | RUD 26, 1’305 | Manuel Bodirsky | |
| UE | Freitag | 09:30 - 11:00 | RUD 26, 1’305 | Stefan Kirchner |
| Sprechzeit | nach Absprache | (RUD 25, 3.414) | Manuel Bodirsky |
Zuordnung
- Hauptstudium, Halbkurs
- Theoretische Informatik
Inhalte und Lernziele
Die Veranstaltung behandelt fortgeschrittene Fragestellungen aus der algorithmischen Graphentheorie. Die ausgewählten Themen führen die Vorlesung auf möglichst einfachem Weg zu aktuellen Forschungsfragen und berühmten offenen Problemen in den jeweiligen Gebieten. Behandelt werden unter anderem:- Algorithmen für zufällige Graphen,
- das Graphisomorphieproblem,
- Graphhomomorphismen und Constraint Satisfaction,
- Ramsey Theorie, und
- unendliche Graphen und Anwendungen.
Voraussetzungen
- Grundstudium
- Die Kenntnis des ersten Teils der Vorlesung ist wünschenswert, aber nicht notwendig.
Übungen
Leiter: Stefan KirchnerDen Stoff der Vorlesung können Sie nur verstehen, wenn Sie sich aktiv damit beschäftigen. Die Übungen werden Sie dabei unterstützen. Jeden Mittwoch gibt es ein neues Übungsblatt, das in der Vorlesung verteilt wird. Die Lösungen werden in der darauffolgenden Woche am Ende der Vorlesung abgegeben, und am Freitag in der Übung besprochen. Die Übungen sollten in Zweiergruppen bearbeitet werden.
- Übungsblatt 1 - Abgabe 25.4.2007
- Übungsblatt 2 - Abgabe 2.5.2007
- Übungsblatt 3 - Abgabe 9.5.2007
- Übungsblatt 4 - Abgabe 16.5.2007
- Übungsblatt 5 - Abgabe 23.5.2007
- Übungsblatt 6 - Abgabe 30.5.2007
- Übungsblatt 7 - Abgabe 6.6.2007
- Übungsblatt 8 - Abgabe 13.6.2007
- Übungsblatt 9 - Abgabe 20.6.2007
- Übungsblatt 10 - Abgabe 4.7.2007
- Übungsblatt 11 - Abgabe 11.7.2007
- Übungsblatt 12 - Abgabe 18.7.2007
Skript und Folien
Hinweise auf Fehler, Kritik und Verbesserungsvorschlaege sind herzlich willkommen, bitte an den Kursleiter richten!Zum ersten Teil der Vorlesung, "The H-coloring problem", gibt es ein Skript (ergaenzend zur Vorlesung, in Englisch). Das Skript ist hier verfuegbar in in Pdf.
Zum zweiten Teil sind die Vorlesungsfolien in Pdf hier verfuegbar.
Literatur
- , Graphentheorie, 3. Auflage, Springer 2005. Dieses hervorragende Buch ist kostenlos auf dieser Seite verfügbar.
- , Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and its Applications, 2004
- , Einführung in Graphen und Algorithmen
- , Understanding and Using Linear Programming, Springer Verlag, 2007
- , Graphen und Algorithmen 1
- , Graphen und Algorithmen 2
