This is an old revision of the document!
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 |
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 |
21. Oktober | 3.2 Scheduling auf identischen Maschinen (Fortsetzung) 4 Randomisierte Approximationsalgorithmen |
23. Oktober | 4.1 Grundlagen der Wahrscheinlichkeitsrechnung 4.2 Zufallsvariablen und Erwartungswerte |
28. Oktober | 4.3 Max-SAT |
30. Oktober | 5 Lineare Programmierung und Runden 5.1 Max-SAT |
Die Inhalte der Vorlesung basieren auf den beiden Skripten zu Approximationsalgorithmen und Online-Algorithmen.