Seminar über Algorithmen WS 2016
LVR-Nr: | 150 528 |
---|---|
Veranstaltung: | Seminar über Algorithmen Di 10.15 - 11.45 Uhr, NA 1/64 |
Dozentin: | Maike Buchin |
News
- Die Sitzung geplant für den 6.12. wird auf den 13.12. um 8:30 Uhr in NA 1/64 verschoben
- Alle Termine ab dem 22.11. wurden um eine Woche nach hinten verschoben
- Vorbesprechung am 20.7. um 14 Uhr (s.t.) in NA 1/64
Kommentar
In diesem Seminar betrachten wir parametrisierte Algorithmen. Viele wichtige algorithmische Probleme sind NP-schwer, was heisst, dass es vermutlich keine effizienten Algorithmen für diese Probleme gibt. Parametrisierte Algorithmen nutzen die Struktur typischer Eingaben, um diese Probleme dennoch effizient zu lösen. Ihre Laufzeit ist polynomiell in der Eingabegröße und exponentiell in einem Parameter. Parametrisierte Algorithmen sind praktisch relevant, da sie effiziente Algorithmen für kleine Parameter liefern. Im Seminar werden verschiedene Techniken zum Entwurf von parametrisierten Algorithmen vorgestellt und an verschiedenen Problemen demonstriert.
Voraussetzungen
Voraussetzung zur Teilnahme an dem Seminar sind Kenntnisse in Algorithmik wie sie etwa in der Vorlesung ``Effiziente Algorithmen'' vermittelt werden.
Literatur
Das Seminar orientiert sich an den folgenden Büchern:
- ``Parameterized Algorithms'' von Marek Cygan et al.
- ``Invitation to Fixed-Parameter Algorithms'' von Rolf Niedermeyer
Das Buch von Cygan et al. ist verfügbar auf der Webseite: http://parameterized-algorithms.mimuw.edu.pl/ Ebenfalls gab es 2014 eine Summer School veranstaltet von den Autoren mit weiteren Materialien: http://fptschool.mimuw.edu.pl/
Zeitplan
Kapitelangaben beziehen sich auf das Buch von Cygan et al.
- Kernelization (Kap. 2.1 bis 2.3) am 15.11.16 von Jan Wrona
- Bounded Search Trees (Kap. 3.1 bis 3.3) am 29.11.16 von Leonie Selbach
- Iterative Compression (Kap. 4 ausser 4.3.2) am 13.12.16 von Felix von der Heide
- Fixed Parameter Intractibility (Kap. 13.1 bis 13.3) am 13.12.16 von Niklas Troost
- Important Seperators (Kap. 8.1 bis 8.3) am 20.12.16 von Jan Götte