Randomisierte und approximative Algorithmen

Termine

Art Wann Wo Beginn Dozent
V4 Montag 12:15 - 13:45
Mittwoch 12:15 - 13:45
CP1-HSZ / Hörsaal 3
CP1-HSZ / Hörsaal 3
7. Oktober 2018 Heiko Röglin
Ü2 Donnerstag 10:15 - 11:45
Freitag 10:15 - 11:45
Freitag 12:15 - 13:45
Seminarraum 2.050
Seminarraum 2.050
Seminarraum 2.050
17. Oktober 2018
18. Oktober 2018
18. Oktober 2018
Xianghui Zhong
Anna Großwendt
Anna Großwendt

Inhalt

In dieser Vorlesung werden wir uns mit dem Entwurf und der Analyse von Approximations- und Online-Algorithmen beschäftigen. Zukünftig wird es die Online-Algorithmen nicht mehr als separate Vorlesung geben, sondern die Inhalte werden in diese Vorlesung einfließen.

Datum Inhalt
7. Oktober 1 Einleitung
2 Greedy-Algorithmen
2.1 Vertex Cover
2.2 Set Cover
9. Oktober 2.3 Scheduling auf identischen Maschinen
2.4 Rucksackproblem
14. Oktober 3 Runden und dynamische Programmierung
3.1 Rucksackproblem
16. Oktober 3.2 Scheduling auf identischen Maschinen

Übungen

Literatur

Die Inhalte der Vorlesung basieren auf den beiden Skripten zu Approximationsalgorithmen und Online-Algorithmen.


Page Tools