Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

Approximationsalgorithmen (Wintersemester 2018/19)

Beschreibung

Viele Fragestellung aus der Praxis sind nicht direkt Entscheidungsprobleme, wie sie in der klassischen Komplexitätstheorie meist betrachtet werden, sondern es stellt sich vielmehr die Frage nach der Berechnung einer besten aus einer Menge vieler Lösungen. Auch wenn das Auffinden einer besten Lösung meist schwierig ist, so lassen sich für viele Probleme zumindest gute Lösungen effizient berechnen mit Hilfe sogenannter Approximationsalgorithmen. Dabei wird eine Garantie für die Qualität der berechneten Lösung in Form einer beweisbaren Güte, einer Art maximaler Abweichung von der besten Lösung, angegeben. In dieser Vorlesung werden grundlegende Konzepte und gängige Techniken vorgestellt, um einerseits Approximationsalgorithmen zu entwickeln und andererseits Grenzen dieser algorithmischen Lösungsmethodik zu untersuchen.

Voraussetzungen

Die Vorlesung richtet sich an Master-Studierende, die Interesse am Entwurf und der Analyse von Algorithmen haben. Es gibt keine formalen Voraussetzungen, um diese Vorlesung zu belegen.

Leistungserfassung

Es werden regelmäßig Hausaufgaben gestellt, von deren erfolgreicher Bearbeitung die Zulassung zur Prüfung abhängt. Die Prüfung wird in mündlicher Form stattfinden.

Termine

Wöchentlich dienstags um 13:30 in A 2.1 und mittwochs um 11 Uhr in A 1.2. Beginn in der ersten Vorlesungswoche.