Current Semester (SeSe 2023)
Bachelor
- Algorithmen und Berechnungskomplexität II
Sidebar
Randomisierte und approximative Algorithmen
Termine
| Art | Wann | Wo | Beginn | Dozent(in) |
|---|---|---|---|---|
| V4 | Montag 10:15 - 11:45 Mittwoch 10:15 - 11:45 | AVZ III / HS 2 AVZ III / HS 2 | 8. Oktober 2018 | Heiko Röglin |
| Ü2 | Dienstag 12:15 - 13:45 Mittwoch 16:15 - 17:45 Donnerstag 12:15 - 14:45 | Seminarraum 2.050 Seminarraum 2.050 Seminarraum 2.050 | 16. Oktober 2018 | Andreas Tönnis Andreas Tönnis Alexander Göke |
Inhalt
In dieser Vorlesung werden wir uns mit dem Entwurf und der Analyse von Approximationsalgorithmen beschäftigen.
| Datum | Inhalt |
|---|---|
| 16. Oktober | 1 Einleitung 2 Greedy-Algorithmen |
| 18. Oktober | 2 Greedy-Algorithmen |
| 23. Oktober | 3 Runden und dynamische Programmierung 3.1 Rucksackproblem |
| 25. Oktober | 3.2 Scheduling auf identischen Maschinen |
| 30. Oktober | 3.2 Scheduling auf identischen Maschinen (Fortsetzung) |
| 6. November | 4 Randomisierte Approximationsalgorithmen 4.1 Grundlagen der Wahrscheinlichkeitsrechnung |
| 8. November | 4.2 Zufallsvariablen und Erwartungswerte |
| 13. November | 4.3 Max-SAT |
| 15. November | 4.3 Max-SAT (Fortsetzung) 5 Traveling-Salesman-Problem 5.1 Allgemeines TSP 5.2 Metrisches TSP |
| 20. November | 5.3 Euklidisches TSP |
| 22. November | 5.3 Euklidisches TSP (Fortsetzung) |
| 27. November | 5.3 Euklidisches TSP (Fortsetzung) |
| 29. November | 6 Lineare Programmierung und Runden 6.1 Max-SAT |
| 4. Dezember | 6.1 Max-SAT (Fortsetzung) |
| 11. Dezember | 6.2 Facility Location ohne Kapazitäten |
| 13. Dezember | 6.2 Facility Location ohne Kapazitäten (Fortsetzung) |
| 18. Dezember | 6.3 k-Median Problem |
| 20. Dezember | 6.3 k-Median Problem (Fortsetzung) |
| 8. Januar | 6.4 Scheduling auf allgemeinen Maschinen |
| 10. Januar | 6.4 Scheduling auf allgemeinen Maschinen (Fortsetzung) 7 Semidefinite Programmierung und Runden 7.1 Semidefinite Programmierung |
| 15. Januar | 7.1 Semidefinite Programmierung (Fortsetzung) 7.2 Maximum-Cut Problem |
| 17. Januar | 7.3 Max-2SAT 7.4 Correlation Clustering |
| 22. Januar | 7.4 Correlation Clustering (Fortsetzung) 8 Untere Schranken für Approximierbarkeit 8.1 Reduktionen von NP-schweren Problemen |
| 24. Januar | 8.2 Reduktionen mithilfe des PCP-Theorems |
Übungsblätter
- Übungsblatt 1 (Besprechung in KW 43)
- Übungsblatt 2 (Besprechung in KW 44)
- Übungsblatt 3 (Besprechung in KW 45)
- Übungsblatt 4 (Besprechung in KW 46)
- Übungsblatt 5 (Besprechung in KW 47)
- Übungsblatt 6 (Besprechung in KW 48)
- Übungsblatt 7 (Besprechung in KW 49)
- Übungsblatt 8 (Besprechung in KW 50)
- Übungsblatt 9 (Besprechung in KW 51)
- Übungsblatt 10 (Besprechung in KW 3)
- Übungsblatt 11 (Besprechung in KW 4)
Prüfungen
Die Nachprüfungen werden am 26. März stattfinden. Bitte melden Sie sich möglichst bald bei Frau Andrade, um einen Prüfungstermin zu vereinbaren.
Literatur
Die Inhalte der Vorlesung finden sich in diesem Skript, das im Laufe des Semesters noch erweitert wird.