Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage aktuellen Entwicklungen in der Forschung zu Algorithmen und Komplexität zu folgen, aufbauend auf dem bestehenden Wissen zu Algorithmen und Datenstrukturen und anknüpfend an die Komplexitätstheorie und verschiedene Anwendungsgebiete (z.B. Netzwerkdesign, geometrische Probleme, Algorithmen auf planaren Graphen). Die Studierenden können

    - Begriffe und grundlegende Problemstellungen aus der Vorlesung erklären;
    - verfeinerte Komplexitätsannahmen und Folgerungen daraus formal beschreiben und intuitiv erklären;
    - Algorithmen für ausgewählte schwere Probleme intuitiv und formal beschreiben, analysieren und über deren Eigenschaften Beweise führen;
    - mithilfe der Techniken aus der Vorlesung eigene Algorithmen für unbekannte algorithmische Probleme entwerfen und analysieren;
    - die Grenzen aktueller Forschungsergebnisse in Algorithmen und Komplexität beschreiben und erklären;
    - aktuelle Forschungsergebnisse erarbeiten und einordnen.

Im WS2024 konzentriert sich die Lehrveranstaltung auf Approximationsalgorithmen basierend auf lokaler Suche.

Inhalt dieser Lehrveranstaltung sind neuere Entwicklungen in der Algorithmenforschung, deren Einordnung in die Literatur und die Grenzen des Bekannten. 

Im WS2024 konzentriert sich die Lehrveranstaltung auf Approximationsalgorithmen basierend auf lokaler Suche. Zu den Themen gehören z. B. Suchkomplexitätsklassen, theoretische Analyse lokaler Suchalgorithmen im Hinblick auf untere und obere Garantiegrenzen für Lösungsqualität und Laufzeit. Zu den behandelten Problemen gehören unter anderem Max-Cut und Traveling Salesman Problem.

Die Veranstaltung wird in Vorlesungen abgehalten, die Themen zum Stand der Forschung in Algorithmen und Komplexität abdecken. Sie finden in einem Seminar-ähnlichen Rahmen statt und sind interaktiv, d.h. von den Studierenden wird erwartet, sich an Diskussionen im Plenum zu beteiligen. Jede Technik die im Kurs eingeführt wird, wird an mehreren Beispielen gezeigt.

Die Note ergibt sich aus einer kurzen muendlichen Pruefung ueber die Themen aus der Vorlesung. Die Studierenden duerfen ein Schwerpunktthema fuer die Pruefung auswaehlen. Insbesondere kann die Pruefung auch in Form von einer Praesentation einer aktuellen Forschungsarbeit aus dem Themengebiet der Vorlesung erfolgen.