Inhalt

Für viele wichtige Probleme in der Informatik ist derzeit kein effizienter (d.h. polynomieller) Algorithmus bekannt. Ein prominentes Beispiel ist das Problem des Handlungsreisenden, bei dem es darum geht eine kürzeste Rundreise zu finden, die eine vorgegebene Menge von Stationen besucht. In dieser Vorlesung beschäftigen wir uns mit Entwurfs- und Analysetechniken für Algorithmen, die zwar im schlechtesten Fall exponentielle Laufzeit besitzen können, aber dennoch nachweisbar schneller als naheliegende Brute-Force-Ansätze sind.

Schlüsselwörter: Exakte Exponentialzeit-Algorithmen; parameterisierte Algorithmen.

Lernziele

Am Ende dieses Kurses sollen die Teilnehmer in der Lage sein, einfache exakte Algorithmen zu entwickeln oder zu analysieren. Außerdem sollen sie grundlegende Entwurfstechniken, wie beispielsweise Branching, dynamische Programmierung, Inclusion-Exclusion, Measure & Conquer, Kernelisierung und Suchbäume mit begrenzter Tiefe verstehen und anwenden können.

Prüfung

Die Note wird durch eine mündliche Pfüfung am Ende des Semesters bestimmt. Wer bei den Übungen mindestens 50% der Punkte erreicht, bekommt bei einer bestandenen Prüfung einen Notenbonus von 0,3 Notenpunkten.

Literatur

• Parameterized Algorithms.
  Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh.  Springer International Publishing 2015.
• https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf
• Exact Exponential Algorithms.
  Fedor V. Fomin and Dieter Kratsch. Springer-Verlag Berlin Heidelberg 2010.
  http://www.ii.uib.no/~fomin/BookEA/BookEA.pdf