Instituts-Logo Logik in der Informatik
Prof. Dr. Martin Grohe
Humboldt-Logo

Vorlesung Parametrische Algorithmen und Komplexitätstheorie

Aktuelles  Einführung  Inhalt  Logbuch  Vorlesung  Übungen  Aufgaben  Prüfung Literatur

Aktuelles

An dieser Stelle finden Sie im Laufe der Vorlesung aktuelle Mitteilungen.


Einführung

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.


Inhalt

Die einzelnen Kapitel des Skripts werden im Laufe der Vorlesung hier erscheinen.

  1. Klassen parametrisierter Probleme
  2. Die Methode der beschränkten Suchbäume
  3. Die Klasse W[P]
  4. Kernelisierungen
  5. Die Klassen W[1] und W[2]
  6. Baumweite und verwandte Techniken


Logbuch

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungen und gelegentlich ergänzende Bemerkungen.


Informationen zum Vorlesungsbetrieb

Zeiten und Raum
Montags und Mittwochs 9-11 Uhr im Erwin-Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'303
 
Dozent
Dr. Mark Weyer

Übungen

Ergänzend zu den Vorlesungen finden 2-stündige Übungen statt.

Zeit und Raum
Montags 11-13 Uhr im Erwin-Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'303
 
Übungsleiter
Dipl.-Inf. Magdalena Grüber

Übungsaufgaben

Es gibt regelmäßig Übungsaufgaben, deren erfolgreiche Bearbeitung (mindestens 40% der Punkte) Voraussetzung für den Scheinerwerb und die Zulassung zur Prüfung ist.


Prüfung

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.


Literatur

Die Vorlesung orientiert sich vor allem an folgendem Buch:
[FG] Jörg Flum und Martin Grohe: Parameterized Complexity Theory. Springer, 2006.
Als Ergänzung seien auch noch folgende Bücher genannt:
[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.


Mark Weyer