Algorithmen II
Wintersemester 2013/2014
Allgemeines
- Dozentin: Prof. Dr. Dorothea Wagner
- Termine: Wöchentlich: Dienstags 15:45–17:15 Uhr (HS Neue Chemie) und Donnerstags 15:45–17:15 Uhr (Gerthsen)
- Betreuung: Thomas Bläsius, Benjamin Niedermann
- Klausur: Termine
Thema
Die Vorlesung Algorithmentechnik vertieft die wichtigsten Teilgebiete der Algorithmik. Dazu gehören Graphenalgorithmen, Algorithmische Geometrie, Algebraische Algorithmen, Kombinatorische Optimierung sowie fortgeschrittene Datenstrukturen. Es werden verschiedene methodische Richtungen vertieft, z.B. randomisierte Algorithmen, Approximationsalgorithmen, parallele Algorithmen, Online-Algorithmen und Algorithm Engineering.
Klausur
Sonderfälle Anmeldung für Nachklausur
- In allen Fällen gilt: Die Anmeldung ist nur bis zum 09. September möglich.
- Schülerstudenten: Sie können sich mit einem formlosen Schreiben anmelden (unterschrieben im Sekretariat abgeben).
Hauptklausur
- Termine für die Einsicht stehen auf der Ergebnisliste.
- Die Ergebnisse sind da. Außerdem gibt es jeweils einen Aushang (mit Matrikelnummer) im Foyer und vor unserem Sekretariat.
- Die Hauptklausur findet am 24.02.2014 um 14:00 Uhr statt (siehe Termine)
- Die Bearbeitungszeit beträgt 2 Stunden.
- Die Anmeldung zur Klausur ist bis zum 17. Februar über https://studium.kit.edu/ möglich.
- Hörsaaleinteilung: Liste
- Die Klausur wird über mehrere Hörsäle verteilt geschrieben. Nach Anmeldeschluss wird bekannt gegeben wer in welchem Hörsaal schreibt.
- Die Aufgaben werden alle auf Deutsch gestellt.
Nachklausur
- Termine für die Einsicht stehen auf der Ergebnisliste.
- Es gibt eine zusätzliche Einsicht am Freitag den 17. Oktober von 14:00 Uhr bis 15:00 Uhr in Raum 301.
- Die Ergebnisse sind da. Außerdem gibt es jeweils einen Aushang (mit Matrikelnummer) im Foyer und vor unserem Sekretariat.
- Die Nachklausur findet am 16.09.2014 um 11:00 Uhr statt (siehe Termine).
- Die Bearbeitungszeit beträgt 2 Stunden.
- Die Anmeldung zur Klausur ist bis zum 09. September über https://studium.kit.edu/ möglich.
- Hörsaaleinteilung: Liste
- Die Klausur findet im Hörsaal am Fasanengarten statt.
Wörterbuch
In der Klausur darf man ein eigenes Wörterbuch verwenden. Das Wörterbuch darf keine Veränderungen zum Originaldruck aufweisen! (z.B. Notizen jeglicher Form.)
Die Wörterbücher müssen spätestens bis zum 12. September 11 Uhr bei den Übungsleitern (Raum 309 bzw. Raum 316) oder im Sekretariat des Lehrstuhls (Raum 321) abgeben werden. Sie werden in der Klausur dann wieder ausgeteilt. Um eine korrekte Zuordnung zu gewährleisten, bitte einen Zettel mit Name und Matrikelnummer einlegen! Wir behalten uns das Recht vor, gegebenfalls Wörterbücher nicht zur Klausur zu zulassen.
Alte Algorithmen II Klausuren
Alte Algorithmentechnik Klausuren
Achtung: Zum einen stimmt der Stoff nicht ganz überein, zum anderen waren die Klausuren 1-stündig.
Neuste Meldungen
10. Oktober
Eine weitere Klausureinsicht findet am 17. Oktober in Raum 301 von 14:00 Uhr bis 15:00 Uhr statt.
10. September
Die Hörsaaleinteilung für die Klausur am 16. September ist nun online: Hörsaaleinteilung. Falls ihr euch für die Klausur angemeldet habt, bitte überprüft ob ihr auch in der Liste eingetragen seid. Falls ihr wider Erwarten nicht in der Liste eingetragen seid, dann schreibt bitte eine Mail an uns Übungsleiter.
07. August
Die Anmeldung zur Nachklausur, die am 16.09.2014 stattfindet, ist freigeschalten. Anmeldeschluss ist der 09.09.2014. Nach dem 09.09.2014 ist eine Anmeldung zur Nachklausur nicht mehr möglich!
20. Februar
Die Hörsaaleinteilung für die Klausur am 24. Februar ist nun online: Hörsaaleinteilung. Falls ihr euch für die Klausur angemeldet habt, bitte überprüft ob ihr auch in der Liste eingetragen seid. Falls ihr wider Erwarten nicht in der Liste eingetragen seid, dann schreibt bitte eine Mail an uns Übungsleiter.
5. Dezember
Die Anmeldung zur Hauptklausur, die am 24.02.2014 stattfindet, ist nun freigeschalten. Anmeldeschluss ist der 17.02.2014. Nach dem 17.02.2014 ist eine Anmeldung zur Hauptklausur nicht mehr möglich!
20. August:
Vorläufige Vorlesungs- und Übungstermine online.
Vorlesungs-/Übungstermine
| Dienstags | Donnerstags | ||
|---|---|---|---|
| 22.10. | Vorlesung | 24.10. | Vorlesung |
| 29.10. | Übung | 31.10. | Vorlesung |
| 05.11. | Vorlesung | 07.11. | Vorlesung |
| 12.11. | Übung | 14.11. | Vorlesung |
| 19.11. | Vorlesung | 21.11. | Vorlesung |
| 26.11. | Übung | 28.11. | Vorlesung |
| 03.12. | Vorlesung | 05.12. | Übung |
| 10.12. | Vorlesung | 12.12. | Vorlesung |
| 17.12. | Übung | 19.12. | Vorlesung |
| Weihnachtsferien | |||
| 07.01. | Vorlesung | 09.01. | Übung |
| 14.01. | Vorlesung | 16.01. | Vorlesung |
| 21.01. | Übung | 23.01. | Vorlesung |
| 28.01. | Vorlesung | 30.01. | Vorlesung |
| 04.02. | Übung | 06.02. | Vorlesung |
| 11.02. | Vorlesung | 13.02. | vsl. Fragestunde u. Wiederholung |
Änderungen vorbehalten!
Skripte, Folien, Übungsblätter und hilfreiches Material
Die Vorlesung basiert überwiegend auf folgenden Skripten:
- Algorithmen II (WS 11/12) Course Notes aus der Vorlesung Algorithmen II gehalten von Prof. Peter Sanders im Wintersemester 11/12 (siehe Forum).
Folien:
| Termin | Inhalt | Skript | Referenz | Folien |
|---|---|---|---|---|
| 22.10. | Einführung | – | Vorlesung1 | |
| 24.10. | Flussprobleme | Algorithmentechnik, Kapitel 4 | Vorlesung2 | |
| 29.10. | Besprechung ÜB1 | Übung1 | ||
| 31.10. | Flussprobleme | Algorithmentechnik, Kapitel 4 | Vorlesung3 | |
| 05.11. | Fluss mit Kosten & Matchings | Vorlesung4 | ||
| 07.11. | Minimale Schnitte | Algorithmentechnik, Kapitel 3 | Vorlesung5 | |
| 12.11. | Besprechung ÜB2 | Übung2 | ||
| 14.11. | Kreisbasen, Matroide & Greedy Algorithmen | Algorithmentechnik, Kapitel 5 & 2.6 | Vorlesung6 | |
| 19.11. | Kreisbasen, Algorithmus von Horton, Algorithmus von de Pina | Algorithmentechnik, Kapitel 5 & 2.6 | [Hor87, Kav04] | Vorlesung7 |
| 21.11. | Randomisierte Algorithmen | Algorithmentechnik, Kapitel 8 | [KS97] | Vorlesung8 |
| 26.11. | Besprechung ÜB3 | Übung3 | ||
| 28.11. | Randomisierte Algorithmen, MaxCut | Algorithmentechnik, Kapitel 8 | [GW95] | Vorlesung9 |
| 03.12. | Algorithmische Geometrie | Entwurf & Analyse, Kapitel 6.1 & 6.2 | Vorlesung10 | |
| 05.12. | Besprechung ÜB4 | Übung4 | ||
| 10.12. | Algorithmische Geometrie: Konvexe Hülle | Entwurf & Analyse, Kapitel 6.3 | Vorlesung11 | |
| 12.12. | String-Matching | Entwurf & Analyse, Kapitel 7 | Vorlesung12 | |
| 17.12. | Besprechung ÜB5 | Übung5 | ||
| 19.12. | String-Matching: Suffixbäume | Algorithmen II (WS 13/14) Course Notes | Vorlesung13 | |
| 07.01. | Approximierende Algorithmen | TGI-Skript, Kapitel 4.7 | Vorlesung14 | |
| 09.01. | Besprechung ÜB6 | Übung6 | ||
| 14.01. | Approximierende Algorithmen | Algorithmentechnik, Kapitel 7.1 & 7.2 | [DS13] | Vorlesung15 |
| 16.01. | Approximierende Algorithmen | Algorithmentechnik, Kapitel 7.3 | Vorlesung16 | |
| 21.01. | Besprechung ÜB7 | Übung7 | ||
| 23.01. | Parametrisierte Algorithmen | Algorithmentechnik, Kapitel 10 | Vorlesung17 | |
| 28.01. | Parametrisierte Algorithmen | Vorlesung18 | ||
| 30.01. | Online Algorithmen | Algorithmen II (WS 11/12) Course Notes, Kapitel 13 | Vorlesung19 | |
| 04.02. | Besprechung ÜB8 | Übung8 | ||
| 06.02. | Parallele Algorithmen | Algorithmentechnik, Kapitel 9 | Vorlesung20 | |
| 11.02. | Algorithmen für externen Speicher | Algorithmen II (WS 11/12) Course Notes, Kapitel 7 | Vorlesung21 | |
| 13.02. | Wiederholung | Zusammenfassung |
Übungsblätter:
| Ausgabe | Besprechung | Blatt |
|---|---|---|
| 22.10. | 29.10. | Übungsblatt1 |
| 29.10. | 12.11. | Übungsblatt2 |
| 12.11. | 26.11. | Übungsblatt3 |
| 26.11. | 05.12. | Übungsblatt4 |
| 05.11. | 17.12. | Übungsblatt5 |
| 17.12. | 09.01. | Übungsblatt6 |
| 09.01. | 21.01. | Übungsblatt7 |
| 21.01. | 04.02. | Übungsblatt8 |
Weitere hilfreiche Materialien:
Literatur
| Index | Literatur |
|---|---|
| [CLR01] | T. H. Cormen, C. E. Leiserson, R. L. Rivest u.a. Introduction to Algorithms / Algorithmen -- eine Einführung. MIT Press, 1990-2001 / Oldenburg 2004. |
| [OW90] | Thomas Ottmann und Peter Widmayer. Algorithmen und Datenstrukturen. Spektrum, Akad. Verl., 1990-2002. |
| [Tar83] | Robert E. Tarjan. Data structures and network algorithms. Society for Industrial and Applied Mathematics, 1983. |
| [BCKO08] | M. de Berg, O. Cheong, M. van Kreveld, M. Overmars: Computational Geometry, 3rd ed., Springer-Verlag, 2008. |
| [S01] | Uwe Schöning. Algorithmik. Spektrum Akademischer Verlag, 2001. |
| [B05] | Norbert Blum. Algorithmen und Datenstrukturen. Oldenbourg Verlag, 2004. |
| [A99] | Giorgio Ausiello et al. Complexity and Approximation. Springer Verlag, 1999. |
| [H01] | Juraj Hromkovic. Algorithmics for Hard Problems. Springer Verlag, 2001. |
| [O98] | Thomas Ottmann. Prinzipien des Algorithmenentwurfs. Spektrum Akademischer Verlag, 1998. |
| [Hor87] | J. D. Horton A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM Journal on Computing Vol. 16, Issue 2, 1987. |
| [KS97] | David Karger und Clifford Stein, A new approach to the minimum cut problem, J. ACM, 1997. |
| [Kav04] | T. Kavitha, K. Mehlhorn, D. Michail, K. Paluch. A faster algorithm for Minimum Cycle Basis of graphs. Proc. ICALP 2004, Turku, Finland, 2004. |
| [V04] | Berthold Vöcking. Crashkurs Lineare Programmierung. Vorlesungsnotizen, 2004. |
| [D05] | Reinhard Diestel. Graph Theory. Springer-Verlag, 2005. |
| [P03] | Leon Peeters. Cyclic Railway Timetable Optimization. Dissertation, 2003. |
| [DF99] | R. G. Downey, M. R. Fellows, Parameterized Complexity. Springer, 1999. |
| [S02] | Alexander Schrijver, On the history of the transportation and maximum flow problems. Mathematical Prorgamming, 2002. |
| [MG07] | Jiří Matoušek und Bernd Gärtner, Understanding and Using Linear Programming, Springer, 2007. |
| [GW95] | Michel Goemans und David Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming, J. ACM, 1995. |
| [DS13] | György Dósa und Jiri Sgall, First Fit bin packing: A tight analysis, STACS 2013. |