Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

Approximationsalgorithmen

MSc Lecture - Winter 2020/21

Diese Lehrveranstaltung wird digital durchgeführt. Deshalb ist es wichtig, dass sich alle Teilnehmenden bis zum 01.11.2020 im Moodle des Kurses einschreiben. Falls es Probleme bei dieser Registrierung über moodle gibt, schreibt mir eine email an katrin.casel(at)hpi.de. Beachte, dass dieser Termin von der allgemeinen Einschreibefrist abweicht und die Registrierung zusätzlich zur normalen Einschreibung über das Studienreferat erfolgt. Im Moodle wird zeitnah der Zoom-Link für die erste Vorlesungseinheit veröffentlicht, die am 02.11.2020 um 13:30 Uhr stattfindet.

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 montags und mittwochs um 13:30. Beginn in der ersten Vorlesungswoche.