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/10/09 08:27]
roeglin
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^
 +| |**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:​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 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