Für viele wichtige Probleme in der Informatik ist derzeit kein effizienter (d.h. polynomieller) Algorithmus bekannt. Ein prominentes Beispiel ist das Traveling Salesperson Problem, 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 deutlich schneller als naheliegende Brute-Force-Ansätze sind [ Illustration ]. Unser Ziel ist dabei stets das Berechnen von optimalen Lösungen, weshalb solche Algorithmen auch als exakte Algorithmen bezeichnet werden, um sie von Approximationsalgorithmen und Heuristiken abzugrenzen. Ein wichtiges (und relativ junges) Teilgebiet der exakten Algorithmik ist die Festparameterberechenbarkeit, die ebenfalls in der Vorlesung behandelt wird. Dabei geht es um den Entwurf von exakten Algorithmen, die nachweislich effizient sind, sofern die Probleminstanzen eine geeignete Struktur aufweisen.

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