Sidebar
This is an old revision of the document!
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 |
| 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 |
Übungen
- Übungsblatt 1 (Besprechung in KW 42)
- Übungsblatt 2 (Besprechung in KW 43)
- Übungsblatt 3 (Besprechung in KW 44)
- Übungsblatt 4 (Besprechung in KW 45)
- Übungsblatt 5 (Besprechung in KW 46)
Literatur
Die Inhalte der Vorlesung basieren auf den beiden Skripten zu Approximationsalgorithmen und Online-Algorithmen.