Institut für Theoretische Informatik, Algorithmik

Algorithmentechnik

Wintersemester 2008/2009

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.

Klausurergebnisse Nachklausur

  • Klausureinsicht ist möglich am Donnerstag, den 30.04.2009 zwischen 16 Uhr und 17 Uhr in Raum 236 (Informatik-Hauptgebäude 50.34) und am Freitag, den 08.05.2009, zwischen 16 Uhr und 17 Uhr in Raum 301 (Informatik-Hauptgebäude 50.34). Um längere Wartezeiten zu vermeiden, möchten wir Sie bitten innerhalb der unten gelisteten Zeiten zu erscheinen. Bringen Sie bitte Ihren Studentenausweis mit.
Matrikelnummer Uhrzeit
< 1320500 16:00-16:30
> 1320500 16:30-17:00

Falls Sie einen Termin für eine mündliche Nachprüfung benötigen setzen Sie sich bitte mit Dr. Reinhard Bauer in Verbindung.

Klausurergebnisse Hauptklausur

Neueste Meldungen

  • Neue Version des Skripts (Revision 5) online. Änderungen: Kapitel 2.6 überarbeitet und vorläufige Version von Kapitel 9 eingefügt
  • Neue Version des Skripts (Revision 6) online. Änderungen: vorläufige Version von Kapitel 10 eingefügt
  • Für die letzte Übung am 12.02.09 können noch Wünsche/Themenvorschlage/Fragen abgegeben werden. Diese bitte per eMail an Dr. Reinhard Bauer oder direkt im Büro.
  • Das letzte Übungsblatt wird voraussichtlich erst kommende Woche (6. KW) ausgegeben werden.
  • Am Donnerstag, den 05.02.09, findet keine Vorlesung statt.
  • Das letzte Übungsblatt ist online!

Termine

Dienstags Donnerstags
21.10. Vorlesung 23.10. Übung
28.10. Vorlesung 30.10. Vorlesung
4.11. Übung 6.11. Vorlesung
11.11. Vorlesung 13.11. Vorlesung
18.11. Vorlesung 20.11. Übung
25.11. Vorlesung 27.11. Vorlesung
2.12. Vorlesung 4.12. Übung
9.12. Vorlesung 11.12. Vorlesung
16.12. Übung 18.12. Vorlesung
23.12. Vorlesung
8.1. Vorlesung
13.1. Vorlesung 15.1. Übung
20.1. Vorlesung 22.1. Vorlesung
27.1. Vorlesung 29.1. Übung
3.2. Vorlesung 5.2. Vorlesung
10.2. Vorlesung 12.2. Übung

Änderungen vorbehalten!

Skripte und Material

Übungsblätter, Übungsfolien und Musterlösungen

Vorlesungen

Datum Thema Material Literatur
30.10.2008 Anwendungen von Union-Find, Algorithmen für Spannbäume minimalen Gewichts Folien, Skript [CLR01]
23.12.2008 Periodische Fahrpläne Folien

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