Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
teaching:ws1920:vl-randalgo [2019/11/29 10:52]
grosswendt [Übungen]
teaching:ws1920:vl-randalgo [2020/02/18 12:14] (current)
roeglin [Prüfungen]
Line 4: Line 4:
  
 ^Art ^Wann ^Wo ^Beginn ^Dozent^ ^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 | +|V4 | Montag 12:15 - 13:45 \\ Mittwoch 12:15 - 13:45 | CP1-HSZ / Hörsaal 3 \\ CP1-HSZ / Hörsaal 3  | 7. Oktober ​2019   | 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 |+|Ü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 ​2019 \\ 18. Oktober ​2019 \\ 18. Oktober ​2019| Xianghui Zhong \\ Anna Großwendt \\ Anna Großwendt |
  
 ===== Inhalt ===== ===== Inhalt =====
Line 12: Line 12:
  
 ^Datum ^Inhalt^ ^Datum ^Inhalt^
-|7. Oktober ​| **Approximationsalgorithmen**\\ 1 Einleitung \\ 2 Greedy-Algorithmen\\ 2.1 Vertex Cover\\ 2.2 Set Cover |+| |**Approximationsalgorithmen**
 +|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 | |9. Oktober | 2.3 Scheduling auf identischen Maschinen\\ 2.4 Rucksackproblem |
 |14. Oktober | 3 Runden und dynamische Programmierung\\ 3.1 Rucksackproblem | |14. Oktober | 3 Runden und dynamische Programmierung\\ 3.1 Rucksackproblem |
Line 19: Line 20:
 |23. Oktober | 4.1 Grundlagen der Wahrscheinlichkeitsrechnung\\ 4.2 Zufallsvariablen und Erwartungswerte | |23. Oktober | 4.1 Grundlagen der Wahrscheinlichkeitsrechnung\\ 4.2 Zufallsvariablen und Erwartungswerte |
 |28. Oktober | 4.3 Max-SAT | |28. Oktober | 4.3 Max-SAT |
-|30. Oktober | 4.3 Max-SAT(Fortsetzung)\\ 5 Lineare Programmierung und Runden\\ 5.1 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) | |4. November | 5.1 Max-SAT (Fortsetzung) |
 |6. November | 5.2 Facility Location ohne Kapazitäten | |6. November | 5.2 Facility Location ohne Kapazitäten |
Line 25: Line 26:
 |13. November | 5.3 Scheduling auf allgemeinen Maschinen (Fortsetzung) | |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| |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|+| |**Online-Algorithmen**
 +|20. November | 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| |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| |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 | |2. Dezember |2.2.4 Untere Schranke für randomisierte Online-Algorithmen |
 +|9. Dezember|3 Das k-Server-Problem\\ 3.1 Einführende Bemerkungen\\ 3.1.1 Der Greedy-Algorithmus\\ 3.2 Untere Schranke für deterministische Algorithmen| 
 +|11. Dezember|3.3 Das k-Server-Problem auf Linien und Bäumen\\ 3.3.1 Analyse des DC-Algorithmus auf der Linie\\ 3.3.2 Analyse des DC-Algorithmus auf Bäumen| 
 +|18. Dezember| 3.3.3 Anwendungen des DC-Algorithmus\\ 4 Approximation von Metriken\\ 4.1 Approximation durch Baummetriken\\ 4.1.1 Hierarchische Partitionen und Baummetriken| 
 +|8. Januar| 4.1.1 Hierarchische Partitionen und Baummetriken\\ 4.1.2 Erzeugung von hierarchischen Partitionen\\ 4.1.3 Analyse des Streckungsfaktors| 
 +|13. Januar| 4.1.3 Analyse des Streckungsfaktors (Fortsetzung)\\ 4.2 Anwendung auf das k-Server-Problem\\ 6.2 Maschinen mit Geschwindigkeiten| 
 +| |**Approximationsalgorithmen**| 
 +|15. Januar| 8 Primal-Duale Algorithmen\\ 8.1 Duale Lineare Programme| 
 +|20. Januar| 8.2 Set Cover\\ 8.3 Feedback Vertex Set| 
 +|22. Januar| 8.3 Feedback Vertex Set (Fortsetzung)| 
 +|27. Januar| 8.4 Das Kürzeste-Wege-Problem|
  
 ===== Übungen ===== ===== Übungen =====
Line 41: Line 52:
   * {{:​teaching:​ws1920:​blatt7.pdf|Übungsblatt 7}} (Besprechung in KW 48)   * {{:​teaching:​ws1920:​blatt7.pdf|Übungsblatt 7}} (Besprechung in KW 48)
   * {{:​teaching:​ws1920:​blatt8.pdf|Übungsblatt 8}} (Besprechung in KW 49)   * {{:​teaching:​ws1920:​blatt8.pdf|Übungsblatt 8}} (Besprechung in KW 49)
 +  * {{:​teaching:​ws1920:​blatt9.pdf|Übungsblatt 9}} (Besprechung in KW 50) 
 +  * {{:​teaching:​ws1920:​blatt10.pdf|Übungsblatt 10}} (Besprechung in KW 51) 
 +  * {{:​teaching:​ws1920:​blatt11.pdf|Übungsblatt 11}} (Besprechung in KW 2)
 +  * {{:​teaching:​ws1920:​blatt12.pdf|Übungsblatt 12}} (Besprechung in KW 3)
  
 ===== Prüfungen ===== ===== Prüfungen =====
  
-Die mündlichen Prüfungen ​werden am 30Januar sowie am 4. und 6. Februar ​2020 stattfinden. Bitte wenden Sie sich an [[staff:​christianeandrade|Frau Andrade]] zur Vereinbarung eines Prüfungstermins.+Die Nachprüfungen ​werden am 24März 2020 stattfinden. Bitte wenden Sie sich bis zum 14. März 2020 an [[staff:​christianeandrade|Frau Andrade]] zur Vereinbarung eines Prüfungstermins.
 ===== Literatur ===== ===== Literatur =====
 Die Inhalte der Vorlesung basieren auf den beiden Skripten zu [[http://​www.roeglin.org/​teaching/​Skripte/​Approximationsalgorithmen.pdf|Approximationsalgorithmen]] und [[http://​www.roeglin.org/​teaching/​Skripte/​OnlineAlgorithmen.pdf|Online-Algorithmen]]. Die Inhalte der Vorlesung basieren auf den beiden Skripten zu [[http://​www.roeglin.org/​teaching/​Skripte/​Approximationsalgorithmen.pdf|Approximationsalgorithmen]] und [[http://​www.roeglin.org/​teaching/​Skripte/​OnlineAlgorithmen.pdf|Online-Algorithmen]].
  
  

Page Tools