Institut für Theoretische Informatik, Algorithmik

Algorithmentechnik

Allgemeines

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.

Neueste Meldungen

  • Klausureinsicht: Mi, 03.05.06, 14:00-16:00, SR 301 im Infobau
  • 20. Apr.:Klausurergebnisse der 2. Klausur hängen in Gebäude 50.34 im Foyer und im dritten Stock aus
  • 10. Jan.: Neuigkeiten zum Programmierprojekt

Termine

Di Do
25.10. Vorlesung 27.10. Vorlesung
1.11. Feiertag 3.11. Vorlesung
8.11. Vorlesung 10.11. Übung
15.11. Vorlesung 17.11. Vorlesung
22.11. Vorlesung 24.11. Übung
29.11. Vorlesung 1.12. Vorlesung
6.12. Vorlesung 8.12. Übung
13.12. Vorlesung 15.12. Vorlesung
20.12. Vorlesung 22.12. Übung
10.1. Vorlesung 12.1. Vorlesung
17.1. Vorlesung 19.1. Übung
24.1. Vorlesung 26.1. Vorlesung
31.1. Vorlesung 2.2. Übung
7.2. Vorlesung 9.2. Vorlesung
14.2. Vorlesung 16.2. Übung

Änderungen vorbehalten!

Folien und Skripte

Übungen

Es wird alle 14 Tage ein Übungsblatt geben. Die Lösungen der Aufgaben wird in der Übung vorgestellt. Zudem werden dort ausgewählte Themen der Vorlesung nochmals vertieft. Die Teilnehmer können per Abstimmung auf die in der Übung behandelten Themen Einfluss nehmen. Übungsblätter können abgegeben werden, und werden dann auch korrigiert.

Klausur

  • Zweite Klausur vom 18.04.06, und Lösung
  • Klausurergebnisse der zweiten Klausur (Schnitt 3,32; Schnitt Bestandene: 2,84)
PunkteNoteAnzahl
39 1 7
37 1,3 3
34 1,7 1
32 2 2
30 2,3 5
27 2,7 3
25 3 5
23 3,3 1
20 3,7 11
18 4 11
<18 5 14
  • Erste Klausur vom 09.03.06, und Lösung
  • Klausurergebnisse der ersten Klausur (Schnitt 3,23; Schnitt bestandene 2,78)
PunkteNoteAnzahl
36 1 6
34 1,3 4
31 1,7 4
29 2 6
27 2,3 5
24 2,7 8
22 3 5
20 3,3 12
17 3,7 14
15 4 7
<15 5 18

Abstimmung

Welches Thema aus der Vorlesung hat Ihnen am besten gefallen?

Grundlagen    7    4,61 %
Union-Find    13    8,55 %
Heaps    24    15,79 %
MSTs    14    9,21 %
Schnitte    3    1,97 %
Flussprobleme    17    11,18 %
Kreisbasen    48    31,58 %
Lineare Programmierung    10    6,58 %
Approximierende Algorithmen    3    1,97 %
Randomisierte Algorithmen    13    8,55 %

Stimmen gesamt: 152


Welches Thema aus der Vorlesung hat Ihnen am wenigsten gefallen?

Grundlagen    6    4,05 %
Union-Find    13    8,78 %
Heaps    9    6,08 %
MSTs    14    9,46 %
Schnitte    7    4,73 %
Flussprobleme    8    5,41 %
Kreisbasen    38    25,68 %
Lineare Programmierung    18    12,16 %
Approximierende Algorithmen    21    14,19 %
Randomisierte Algorithmen    14    9,46 %

Stimmen gesamt: 148

FIXME Frühere Abstimmungen

Vorlesungen

Datum Thema Material Literatur
25.10. Worst-case- und Average-case-Laufzeit Kurzskript [CLR01]
27.10. Untere Schranke für Laufzeiten, Amortisierte Analyse, Rekursionsabschätzungen SkriptAlt (6.3, 2, 1) [CLR01]
3.11. Master Theorem, Select, Union Find SkriptAlt (1.3.2, 3.1) [S01, CLR01]
8.11. Union Find Laufzeitbeweis SkriptAlt (3.1) [CLR01]
15.11. Union Find Anwendungen SkriptAlt (3.2) [CLR01]
17.11. Priority Queues und Heaps [CLR01]
22.11. Minimale aufspannende Bäume SkriptAlt (4) [CLR01]
29.11. MSTs SkriptAlt (4) [CLR01]
1.12. Greedy Verfahren und Matroide SkriptAlt (4) [CLR01]
6.12. Schnitte in Graphen SkriptAlt (5) [CLR01]
13.12. Flussprobleme: Max-Flow Min-Cut, Algorithmen von Ford/Fulkerson, Edmonds/Karp, Goldberg/Tarjan Flusskapitel, Vorlesungsfolien Teil 1 [CLR01, Tar83]
15.12. Flussprobleme: Goldberg/Tarjan und Anwendungsbeispiel Flusskapitel, Vorlesungsfolien Teil 2 [CLR01, Tar83]
20.12. Periodische Fahrpläne und Kreise in Graphen Vorlesungsfolien
10.1. Kreisbasen: Einführung und Algorithmus von Horton Neues Skript, Kapitel 5.1 bis 5.3 [Deo04, Bol98, Hor87]
12.1. Kreisbasen: Algorithmen von Horton und de Pina Neues Skript, Kapitel 5.3 und 5.4 [Hor87, dP95, Kav04]
17.1. Kreisbasen: Simple MCB Neues Skript, Kapitel 5.4 [Kav04]
24.1. Kreisbasen: Zertifikate; Lineare Programme Neues Skript, Kapitel 5.5 und Kapitel 6 [Kav04] und [CLR01, V04]
26.1. Geometrische Repräsentation von LPs Neues Skript Kapitel 6 [CLR01, V04]
31.1. Approximationsalgorithmen, PAS Neues Skript Kapitel 7 [CLR01, A99]
7.2. Approximationsalgorithmen, APAS, FPAS Neues Skript Kapitel 7 [CLR01, A99]
14.2. Randomisierte Algorithmen Neues Skript Kapitel 8 [CLR01, A99]

Programmierprojekt

In disem Programmierprojekt soll der Algorithmus von Goldberg und Tarjan (und möglicherweise weitere Algorithmen) implementiert und visualisiert werden. Die Teilnahme ist freiwillig. Die besten Lösungen werden vorgestellt und möglicherweise auf dem „visualization contest“ einer Konferenz eingesetzt und/oder als „Algorithmus der Woche“ im Rahmen des Informatikjahrs veröffentlicht.

  • Demo anschauen: zip entpacken und README-Datei lesen (Java3d erforderlich).
  • Der Goldberg-Tarjan-Algorithmus soll mit Java implementiert werden und auf einem DirectedGraph-Objekt operieren. Der Algorithmus soll folgende Funktionen unterstützen (Interface „StepwiseAlgorithm“):
    • public void init(String filename);
      Initialisieren des Algorithmus und Übergabe der .graphml-Datei.
    • public void nextStep();
      Einen Schritt im Algorithmus durchführen (also einen Push oder Relabel).
    • public void previousStep();
      Einen Schritt zurück.
    • public boolean finished();
      True wenn der Algorithmus fertig ist.
    • public boolean atStart();
      True wenn der Algorithmus am Anfang ist.
  • Dreidimensionale Visualisierung der Schritte des Algorithmus auf dem Graphen mit Hilfe von Java3d. Dazu müssen zusätzlich folgende Funktionen unterstützt werden (interface „Scene3DProvider“):
    • public Vector3d getStartPosition();
      Startpunkt der Kamera
    • public BranchGroup getChild();
      Gibt den Wurzelknoten der Java3d-Szene zurück.
  • Dazu wird von uns ein Frontend zur Navigation durch den Graphen zur Verfügung gestellt.

Es kann in Teams gearbeitet werden und sollte schlank und sauber programmiert werden. Deadline für die Abgabe ist der 9. Februar. Wir bitten schon vorher um eine kurze Rückmeldung mit evtl. Fragen damit wir eine Vorstellung von der Anzahl möglicher Teilnehmer haben.

Referenzen:

  • Archiv mit den notwendigen Bibliotheken und Demoimplementation einer Breitensuche (zip). Für Hinweise zur Ausführung und Implementation bitte die README-Datei im Archiv lesen!
  • Java3d (Homepage und API).
  • Jung Graphenbibliothek (Homepage und API).
  • Eine andere Bibliothek zur Visualisierung von Algorithmen: jGABL, unter anderem mit einer Implementation von Goldberg-Tarjan.

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.