Algorithmentechnik

Wintersemester 2009/2010

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.

Nachklausur

  • Die Nachklausur fand statt am Freitag, 16. April 2010 um 16:00 Uhr.

Mündliche Nachprüfung

Falls Sie einen Termin für eine mündliche Nachprüfung benötigen, setzen Sie sich bitte mit Thomas Pajor in Verbindung.

Hauptklausur

  • Die Hauptklausur fand statt am 1. März 2010 um 9:00 Uhr.

Neuste Meldungen

7. Mai:
Die Noten der Nachklausur haben sich aufgrund der Klausureinsicht geändert (betrifft auch Studierende, die nicht in der Klausureinsicht waren). Eine upgedatete Fassung der Notenliste wurde unter Nachklausur veröffentlicht.

12. April:
Anmeldeliste für die Nachklausur online. Bitte überprüfen Sie wiederrum, ob Sie auf der Anmeldeliste stehen. Eine Teilnahme an der Klausur für Studierende, die nicht auf der Anmeldeliste verzeichnet sind, ist ausgeschlossen.

24. März:
Die Hauptklausur sowohl mit alsauch ohne Lösung sind jetzt zum Download verfügbar.

23. Februar:
Anmeldeliste und Hinweise zum Ablauf der Hauptklausur sind online. Bitte überprüfen Sie unbedingt, ob Sie auf der Anmeldeliste verzeichnet sind. Eine Teilnahme an der Klausur für Studierende, die nicht auf der Anmeldeliste stehen, ist ausgeschlossen.

18. Februar:
Anmerkung zum Skript, S.153 ff: Die Existenz eines Suchbaums für VERTEX COVER in O(nk + (1.342^k) k^2) setzt einen zusammenhängenden Graphen voraus, da sonst nicht ausgeschlossen werden kann, dass eine Verzweigung (1,4) mehrfach pro Pfad auftritt.

16. Februar:
Lösungsvorschläge zu Blatt 8 sind jetzt online.

12. Februar:
Diplom-Mathe-Studenten, die die Algorithmentechnik im Vordiplom als Nebenfach-Prüfung schreiben möchten, müssen sich bei Herrn Stefan Kühnlein (Mathefakultät) anmelden.
Diplom-Mathe-Studenten, die die Algorithmentechnik im Hauptdiplom als Nebenfach-Prüfung schreiben möchten, brauchen eine Zulassung (gelber DINA4-Zettel), der bei uns im Infobau abgegeben werden kann.

In letzterem Fall gab es etwas Verwirrung, die dazu führte, dass wir nicht wussten, ob wir jene Zulassungszettel annehmen dürfen. Daher nahmen manche von Euch einen unnötigen Weg zu Herrn Kühnlein auf sich. Dafür bitten wir um Entschuldigung!

09. Februar:
Weitere Informationen zu den in der Übung vorgestellten Hiwi-Stellen gibt's hier.

08. Jänner:
Vorlesungsfolien zur Vorlesung über Lineares Programmieren vom 7. Jänner 2010 sind online.

14. Dezember:
In den letzten beiden Zeichnungen des Gegenbeispiels zu Aufgabe 2, Blatt 3, befanden sich bis eben Vorzeichenfehler in den Flussangaben zwischen den Knoten 1,2,3 und 4. Diese sind nun korrigiert. Bitte entschuldigen Sie diese Unachtsamkeit!

29. Oktober:
Der Vorlesungstermin am 12.11.2009 fällt aus. Es wird empfohlen an der Eröffnungsfeier des KIT-Schwerpunkt COMMputation teilzunehmen.

26. Oktober:
Diskussionsforum aktiviert. Falls ihr also Fragen habt, könnt ihr diese dort gerne an uns stellen.

16. Oktober:
Vorläufige Version des Vorlesungsskripts online (basierend auf WS 08/09). Möglicherweise werden neue Revisionen des Skripts im Verlauf des Semesters veröffentlicht die Verbesserungen und Korrekturen enthalten.

6. Oktober:
Vorläufige Vorlesungs- und Übungstermine online. Bitte beachten Sie außerdem, dass an den Terminen 12.11.2009 und 26.11.2009 die jeweilige Veranstaltung im Gaede Hörsaal stattfindet.

Skripte und Material

Übung:

Hinweise zu den Blättern:

  • Allgemein:
    Sollten Sie Fragen zur Korrektur der Übungsblätter haben, wenden Sie sich an die Übungsleiter oder direkt an den Korrektor (Jonathan Rollin) unter algotech@n-ten.de
  • Blatt 2:
    Sie können bei Aufgabe 2d) davon ausgehen, dass sich ein minimaler Spannbaum in Zeit O(|V|²) berechnen lässt (zum Beispiel über den Algorithmus von Prim mit Fibonacci-Heaps), bzw. einen minimalen Spannbaum als gegeben voraussetzen.
  • Blatt 3:
    Ein Gegenbeispiel zur in der Übung vorgeschlagenen (vermeintlich alternativen) Vorgehensweise zur Bestimmung eines minimalen Schnitts auf Basis eines Max-Flows (berechnet mit Preflow-Push-Algo) (Problem 2), steht hier (korrigiert) bereit. (Alte Version mit Vorzeichenfehler: Achtung: Vorzeichenfehler!)

Vergangene Algorithmentechnik-Vorlesungen:

Klausuren

Voraussichtliche Klausurtermine:

  • Hauptklausur: 1. März 2010
  • Nachklausur: 16. April 2010

Verbindlich sind die Termine auf der offiziellen Klausurseite.

Vorlesungs-/Übungstermine

Dienstags Donnerstags
20.10. Vorlesung 22.10. Vorlesung / Übung
27.10. Vorlesung 29.10. Vorlesung
3.11. Vorlesung 5.11. Übung
10.11. Vorlesung 12.11. Termin fällt aus.
Eröffnungsfeier KIT-Schwerpunkt COMMputation
17.11. Vorlesung 19.11. Übung
24.11. Vorlesung 26.11. Vorlesung
Achtung: Verlerung in Gaede-Hörsaal
1.12. Vorlesung 3.12. Übung
8.12. Vorlesung 10.12. Vorlesung
15.12. Vorlesung 17.12. Übung
22.12. Vorlesung
7.1. Vorlesung
12.1. Übung 14.1. Vorlesung
19.1. Vorlesung 21.1. Übung
26.1. Vorlesung 28.1. Vorlesung
2.2. Vorlesung 4.2. Übung
9.2. Vorlesung 11.2. Vorlesung

Änderungen vorbehalten!

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

Die Journalveröffentlichungen [Hor87] und [Kav04] sind aus dem Netz der Universität zugänglich.