RUB » LMI » Lehre » Seminar über Algorithmen WS 2016

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