|
Logik in der Informatik
Prof. Dr. Martin Grohe |
 Institut für Informatik |
Die erste Vorlesung findet am Dienstag, dem 12.4. statt.
Viele Probleme von großer praktischer Bedeutung erweisen sich als NP-schwer; für sie sind keine effizienten Algorithmen bekannt. In der Praxis wird zu ihrer Lösung daher meist auf heuristische Verfahren zurückgegriffen, die zwar oftmals ausreichend gute Laufzeiten bzw. Lösungen liefern, aber leider meist schwer durchschaubar sind und keine garantierten Aussagen über ihre Leistungsgüte erlauben. Ein möglicher Ausweg kann in der Betrachtung von parametrischer Komplexität bestehen: Bei vielen NP-schweren Problemen lässt sich die scheinbar inhärente "kombinatorische Explosion" auf einen kleinen Teil der Eingabe, einen so genannten Parameter beschränken. Dies führt zu dem Konzept der parametrischen Algorithmen, welche eine sinnvolle Alternative zu heuristischen Methoden darstellen können.
In der Vorlesung werden einige Methoden zur Entwicklung effizienter parametrischer Algorithmen vorgestellt. Außerdem werden wir uns mit der so genannten parametrischen Komplexitätstheorie beschäftigen, um die Grenzen parametrischer Algorithmen aufzeigen zu können.
Das folgende Inhaltsverzeichnis wird im Laufe der Vorlesung noch ergänzt und möglicherweise verändert.
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 wird regelmäßig Übungsaufgaben geben, 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.
Die Vorlesung orientiert sich an folgendem Buch, das voraussichtlich Ende 2005 erscheinen wird. Das Manuskript wird den Studenten im Laufe der Vorlesung zur Verfügung gestellt.
| [FG] | J. Flum, M. Grohe, Parameterized Complexity Theory. |
Desweiteren seien empfohlen:
| [DF] | R. Downey and M. Fellows, Parameterized Complexity. Springer, 1999. |
| [N] | R. Niedermeier, An Invitation to Fixed-Parameter Algorithms. Habilitationsschrift an der Universität Tübingen, 2002. |