|
Logik in der Informatik
Prof. Dr. Martin Grohe |
 Institut für Informatik |
Daniel Schenkel und Torsten Bosse haben netterweise ihre Vorlesungsmitschrift ins Netz gestellt.
Zahlreiche wichtige algorithmische Probleme sind zwar komplexitätstheoretisch schwer, etwa NP-schwer, müssen aber in der Praxis dennoch gelöst werden. Dass dies gelingen kann, liegt daran, dass die in der Praxis vorkommenden Instanzen oft eine recht "einfache Struktur" aufweisen. Versucht man zu verstehen, was "einfache Struktur" hier bedeutet, so stößt man häufig auf Begriffe wie "baumartige" oder "hierarchisch strukturierte" Instanzen. Baumzerlegungen von Graphen geben eine natürliche Präzisierung solcher intuitiver Begriffe. Sie spielen eine wichtige Rolle sowohl in der Graphentheorie als auch in der Algorithmik. Insbesondere lassen sich sehr viele NP-schwere algorithmischen Probleme effizient auf Instanzen mit guten Baumzerlegungen lösen.
Diese Vorlesung ist eine Einführung in die Theorie der Baumzerlegungen und verwandter Zerlegungen und in ihre algorithmischen Anwendungen. Dabei sollen sowohl die graphentheoretischen Grundlagen als auch die algorithmischen Techniken vermittelt werden.
Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungen und gelegentlich ergänzende Bemerkungen.
Ergänzend zu den Vorlesungen finden 2-stündige Übungen statt.
Es gibt regelmäßig Übungsaufgaben, deren erfolgreiche Bearbeitung (mindestens 40% der Punkte) Voraussetzung für den Scheinerwerb und die Zulassung zur Prüfung ist.
Zu Beginn der Semesterferien finden mündliche Prüfungen statt. Für die Zulassung zur Prüfung müssen mindestens 40% der Punkte in den Übungsaufgaben erworben werden.
Zum Thema der Vorlesung gibt es derzeit noch keine Lehrbücher oder Monographien. Verweise auf die Fachliteratur werden im Laufe der Vorlesung gegeben.
Das letzte Kapitel des Buchs Graph Theory von Reinhard Diestel, (3. Auflage, Springer Verlag 2005) gibt eine Einführung in die graphentheoretischen Grundbegriffe, deckt aber nur eine kleinen Teil der Vorlesung ab und spart insbesondere algorithmische Aspekte aus.
Das Skript zu einer Vorlesung Einbettungen und Minoren von Graphen, die ich im Wintersemester 1999/2000 an der Universität Freiburg gehalten habe, enthält ebenfalls Teile dieser Vorlesung. Achtung: Ich habe das Skript nicht mehr überarbeitet oder korrigiert, es enthält sicherlich einige Fehler.
Hier finden Sie eine Implementierung der in der Vorlesung vorgestelleten Algorithmen zum Berechnen von Baumzerlegungen in Python.