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.

Neuste Meldungen

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

Übungsblatt Übungsfolien Lösungsvorschläge
- 22.10 -
Übungsblatt 1 05.11 zu Blatt 1
Übungsblatt 2
Bitte untenstehende Hinweise beachten 		19.11 zu Blatt 2
Übungsblatt 3 - -

Hinweise zu den Blättern:

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

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