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.
Inhalt dieser Lehrveranstaltung sind neuere Entwicklungen in der Algorithmenforschung, deren Einordnung in die Literatur und die Grenzen des Bekannten. Themenblöcke (exemplarisch): - Grundlagen der Komplexitätstheorie (Wiederholung NP-schwere, Reduktionen) - Verfeinerte Komplexitätsanalysen unter Zusatzannahmen, z.B. (starke) Exponentialzeithypothese - Schwere Probleme aus dem Gebiet der Logik (z.B. untere und obere Schranken für das aussagenlogische Erfüllbarkeitsproblem) - Allgemeine algorithmische Techniken (Teilmengenfaltungen, Inklusion-Exklusion, Formulierung als Polynome) und Anwendungen der Techniken (z.B. Steinerbäume) - Ergebnisse zur Nicht-Reduzierbarkeit bestimmter Probleme - Schwere Probleme auf planaren Graphen in subexponentieller Zeit (wenn Zeit ist) - Schwere Geometrische Probleme in subexponentieller Zeit (wenn Zeit ist)
Die Veranstaltung wird in Blockvorlesungen 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.
