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 Approximationsalgorithmen
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 4.3 Max-SAT(Fortsetzung)
5 Lineare Programmierung und Runden
5.1 Max-SAT
4. November 5.1 Max-SAT (Fortsetzung)
6. November 5.2 Facility Location ohne Kapazitäten
11. November 5.2 Facility Location ohne Kapazitäten (Fortsetzung)
5.3 Scheduling auf allgemeinen Maschinen
13. November 5.3 Scheduling auf allgemeinen Maschinen (Fortsetzung)
18. November 6 Semidefinite Programmierung und Runden
6.1 Semidefinite Programmierung
6.2 Maximum-Cut Problem
20. November Online-Algorithmen
1 Einleitung
2 Paging
2.1 Deterministische Algorithmen
2.1.1 Markierungsalgorithmen
25. November 2.1.2 Untere Schranken
2.2 Randomisierte Algorithmen
2.2.1 Potentialfunktionen
27. November 2.2.2 Analyse von RANDOM
2.2.3 Analyse von MARK
2. Dezember 2.2.4 Untere Schranke für randomisierte Online-Algorithmen

Übungen

Prüfungen

Die mündlichen Prüfungen werden am 30. Januar sowie am 4. und 6. Februar 2020 stattfinden. Bitte wenden Sie sich an Frau Andrade zur Vereinbarung eines Prüfungstermins.

Literatur

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


Page Tools