Institut für Theoretische Informatik, Algorithmik

Algorithmen II

Wintersemester 2012/2013

Allgemeines

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.

Wintersemester 09/10 Klausur Lösung
Wintersemester 09/10 Klausur Lösung
Wintersemester 08/09 Klausur Lösung
Wintersemester 08/09 Klausur Lösung
Wintersemester 06/07 Klausur Lösung
Wintersemester 06/07 Klausur Lösung
Wintersemester 05/06 Klausur Lösung
Wintersemester 05/06 Klausur Lösung

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 01.11. 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:

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.