|
Logik in der Informatik
Prof. Dr. Martin Grohe |
|
An dieser Stelle finden Sie im Laufe der Vorlesung aktuelle Mitteilungen.
Viele in der Praxis relevante Probleme sind NP-schwer, so dass für sie keine schnellen Lösungen zu erwarten sind. Das entbindet natürlich nicht von dem Wunsch oder der Notwendigkeit, sie trotzdem zu lösen. Einen Ansatzpunkt hierfür bilden parametrische Algorithmen: Die kombinatorische Explosion wird auf einen Teil der Eingabe, den Parameter, beschränkt. Bei kleinem Parameter ist die Laufzeit dann womöglich akzeptabel.
Das gelingt jedoch nicht für alle Probleme. Die parametrische Komplexitätstheorie bietet einen Rahmen, in dem manche parametrisierte Probleme, analog zur NP-Schwere, als parametrisch schwer ausgewiesen werden können.
In der Vorlesung werden wir uns mit beiden Seiten befassen.
Die einzelnen Kapitel des Skripts werden im Laufe der Vorlesung hier erscheinen.
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.
Die Vorlesung orientiert sich vor allem an folgendem Buch:
| [FG] | Jörg Flum und Martin Grohe: Parameterized Complexity Theory. Springer, 2006. |
| [DF] | R. G. Downey und M. R. Fellows: Parameterized Complexity. Springer, 1999. |
| [N] | Rolf Niedermeier: Invitation to Fixed-Parameter Algorithms. Habilitationsschrift, Universität Tübingen, 2002. |
| [Na] | Rolf Niedermeier: Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006. |