Algorithmen II
Wintersemester 2012/2013
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
- Hörsaaleinteilung für die Klausur am 1. März: Liste
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 Klausuranmeldung
- Informationswirte: Bitte im Studienbüro anmelden. Dort werden Sie entweder direkt ins System eingetragen oder bekommen einen blauen Schein, den Sie bei uns im Sekretariat abgeben müssen.
- Schülerstudenten: Sie können sich mit einem formlosen Schreiben anmelden (unterschrieben im Sekretariat abgeben).
- In allen Fällen gilt: Die Anmeldung ist nur bis zum 22. Februar möglich.
Hauptklausur
- Termine für die Einsicht stehen auf der Ergebnisliste.
- Die Ergebnisse sind da. Außerdem gibt es jeweils einen Aushang im Foyer und vor unserem Sekretariat.
- Da die Hauptklausur vorbei ist, hier die Klausur, sowie die Musterlösung.
- Die Hauptklausur findet am 01.03.2013 um 11:00 Uhr statt (siehe Termine)
- Die Bearbeitungszeit beträgt 2 Stunden.
- Die Anmeldung zur Klausur ist bis zum 22. 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.
Nachklausur
- Mündliche Nachprüfungen: Zur mündlichen Nachprüfung kann man sich bis zum 31.10.13 bei Lilian Beckert anmelden.
- Termine für die Einsicht stehen auf der Ergebnisliste.
- Die Ergebnisse sind da. Außerdem gibt es jeweils einen Aushang im Foyer und vor unserem Sekretariat.
- Hier die Nachklausur, sowie die Musterlösung.
- Hörsaaleinteilung: Liste
- Die Nachklausur findet am 02.10.2013 um 14:00 Uhr statt (siehe Termine).
- Die Bearbeitungszeit beträgt 2 Stunden.
Hinweis: Die Gastvorträge vom 18.12.2012 sind nicht klausurrelevant.
Alte Algorithmentechnik Klausuren
Achtung: Zum einen stimmt der Stoff nicht ganz überein, zum anderen waren die Klausuren 1-stündig.
Neuste Meldungen
01. März:
Die Hauptklausur inklusive Musterlösung ist nun online.
25. Februar:
Die Hörsaaleinteilung für die Klausur am 1. März 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.
24. Januar:
Die Anmeldung zur Klausur ist nun freigeschalten! Eine Anmeldung zur Klausur ist bis zum 22. Februar über https://studium.kit.edu/ möglich.
24. Januar:
Das Übungsblatt 7 wurde um zwei Aufgaben erweitert.
25. Oktober:
Folien für dritte Vorlesung und erste Übung sind online.
16. Oktober:
Folien für erste und zweite Vorlesung sowie erstes Übungsblatt sind online.
15. Oktober:
Skripte, hilfreiche Materialien und Literaturhinweise sind nun online.
4. September:
Vorläufige Vorlesungs- und Übungstermine online.
Vorlesungs-/Übungstermine
| Dienstags | Donnerstags | ||
|---|---|---|---|
| 16.10. | Vorlesung | 18.10. | Vorlesung |
| 23.10. | Vorlesung | 25.10. | Übung |
| 30.10. | Vorlesung | | Feiertag |
| 06.11. | Vorlesung | 08.11. | Vorlesung |
| 13.11. | Übung | 15.11. | Vorlesung |
| 20.11. | Vorlesung | 22.11. | Vorlesung |
| 27.11. | Übung | 29.11. | Vorlesung |
| 04.12. | Vorlesung | 06.12. | Vorlesung |
| 11.12. | Übung | 13.12. | Vorlesung |
| 18.12. | Vorlesung | 20.12. | Übung |
| Weihnachtsferien | |||
| 08.01. | Vorlesung | 10.01. | Vorlesung |
| 15.01. | Vorlesung | 17.01. | Vorlesung |
| 22.01. | Übung | 24.01. | Vorlesung |
| 29.01. | Vorlesung | 31.01. | Vorlesung |
| 05.02. | Übung | 07.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 letztjährigen Vorlesung Algorithmen II gehalten von Prof. Peter Sanders (siehe Forum).
Folien:
| Termin | Inhalt | Skript | Folien |
|---|---|---|---|
| 16.10. | Einführung | – | Vorlesung1 |
| 18.10. | Flussprobleme | Algorithmentechnik, Kapitel 4 | Vorlesung2 |
| 23.10. | Flussprobleme | Algorithmentechnik, Kapitel 4 | Vorlesung3 |
| 25.10. | Besprechung ÜB1 | Übung1 | |
| 30.10. | Fluss mit Kosten & Matchings | Vorlesung4 | |
| 06.11. | Minimale Schnitte | Algorithmentechnik, Kapitel 3 | Vorlesung5 |
| 06.11. | Kreisbasen, Matroide & Greedy Algorithmen | Algorithmentechnik, Kapitel 5 & 2.6 | Vorlesung6 |
| 13.11. | Besprechung ÜB2 | Übung2 | |
| 15.11. | Kreisbasen, Algorithmus von Horton, Algorithmus von de Pina | Algorithmentechnik, Kapitel 5 & 2.6 | Vorlesung7 |
| 20.11. | Randomisierte Algorithmen | Algorithmentechnik, Kapitel 8 | Vorlesung8 |
| 22.11. | Randomisierte Algorithmen, MaxCut | Algorithmentechnik, Kapitel 8 | Vorlesung9 |
| 27.11. | Besprechung ÜB3 | Übung3 | |
| 29.11. | Algorithmische Geometrie: Grundlagen | Entwurf & Analyse, Kapitel 6.1 & 6.2 | Vorlesung10 |
| 04.12. | Algorithmische Geometrie: Konvexe Hülle | Entwurf & Analyse, Kapitel 6.3 | Vorlesung11 |
| 06.12. | String-Matching | Entwurf & Analyse, Kapitel 7 | Vorlesung12 |
| 11.12. | Besprechung ÜB4 | Übung4 | |
| 13.12. | String-Matching: Suffixbäume | Algorithmen II (WS 11/12) Course Notes | Vorlesung13 |
| 18.12. | Gastvorträge | Kartogramme, Färbung planare Graphen | |
| 20.12. | Besprechung ÜB5 | Übung5 | |
| 08.01. | Approximierende Algorithmen | Algorithmentechnik, Kapitel 7.1 & 7.2 | Vorlesung15 |
| 10.01. | Approximierende Algorithmen | Algorithmentechnik, Kapitel 7.3 | Vorlesung16 |
| 15.01. | Parametrisierte Algorithmen | Algorithmentechnik, Kapitel 10 | Vorlesung17 |
| 17.01. | Parametrisierte Algorithmen | Vorlesung18 | |
| 22.01. | Besprechung ÜB6 | Übung6 | |
| 24.01. | Online Algorithmen | Algorithmen II (WS 11/12) Course Notes, Kapitel 13 | Vorlesung19 |
| 29.01. | Parallele Algorithmen | Algorithmentechnik, Kapitel 9 | Vorlesung20 |
| 31.01. | Algorithmen für externen Speicher | Algorithmen II (WS 11/12) Course Notes, Kapitel 7 | Vorlesung21 |
| 05.02. | Besprechung ÜB7 | Übung7 | |
| 08.02. | Wiederholung | Zusammenfassung |
Übungsblätter:
| Ausgabe | Besprechung | Blatt |
|---|---|---|
| 16.10. | 25.10. | Übungsblatt1 |
| 30.10. | 13.11. | Übungsblatt2 |
| 13.11. | 27.11. | Übungsblatt3 |
| 29.11. | 11.12. | Übungsblatt4 |
| 12.12. | 20.12. | Übungsblatt5 |
| 14.01. | 22.01. | Übungsblatt6 |
| 22.01. | 05.02. | Übungsblatt7 |
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. |
| [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. |