Institut für Theoretische Informatik, Algorithmik

Algorithmen II

Wintersemester 2013/2014

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 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

Wintersemester 12/13 Klausur Lösung
Wintersemester 12/13 Klausur Lösung

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

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!

uebung3.pdf

Skripte, Folien, Übungsblätter und hilfreiches Material

Die Vorlesung basiert überwiegend auf folgenden Skripten:

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.