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
Last revision Both sides next revision
teaching:ws1920:vl-randalgo [2019/10/14 15:49]
zhong [Übungen]
teaching:ws1920:vl-randalgo [2020/02/18 12:13]
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^
 +| |**Approximationsalgorithmen**|
 |7. Oktober | 1 Einleitung \\ 2 Greedy-Algorithmen\\ 2.1 Vertex Cover\\ 2.2 Set Cover | |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 |
 +|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|
 +| |**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|
 +|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 |
 +|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 =====
- 
-Bitte melden Sie sich zur Teilnahme an den Übungen bis zum 11.10.2019 (23:59 Uhr) über das elektronische Tutorienvergabesystem der Universität Bonn ([[https://​puma.cs.uni-bonn.de/​]]) an. 
  
   * {{:​teaching:​ws1920:​approxblatt1.pdf|Übungsblatt 1}} (Besprechung in KW 42)   * {{:​teaching:​ws1920:​approxblatt1.pdf|Übungsblatt 1}} (Besprechung in KW 42)
   * {{:​teaching:​ws1920:​approxblatt2.pdf|Übungsblatt 2}} (Besprechung in KW 43)   * {{:​teaching:​ws1920:​approxblatt2.pdf|Übungsblatt 2}} (Besprechung in KW 43)
 +  * {{:​teaching:​ws1920:​approxblatt3.pdf|Übungsblatt 3}} (Besprechung in KW 44)
 +  * {{:​teaching:​ws1920:​approxblatt4.pdf|Übungsblatt 4}} (Besprechung in KW 45)
 +  * {{:​teaching:​ws1920:​approxblatt5.pdf|Übungsblatt 5}} (Besprechung in KW 46)
 +  * {{:​teaching:​ws1920:​approxblatt6.pdf|Übungsblatt 6}} (Besprechung in KW 47)
 +  * {{:​teaching:​ws1920:​blatt7.pdf|Übungsblatt 7}} (Besprechung in KW 48)
 +  * {{:​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 =====
 +
 +Die Nachprüfungen werden am 24. März 2020 stattfinden. Bitte wenden Sie sich 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