Algorithmentechnik

• Dozentin: Prof. Dr. Dorothea Wagner
• Betreuer: Dr. rer. nat. Robert Görke, Dipl.-Math. Steffen Mecke
• Vorlesung: Wöchentlich dienstags 15.45-17.15 und 14-täglich donnerstags 15.45-17.15 im HMU
  vom 25.10.2005 bis 16.02.2006
• Übung: 14-täglich donnerstags 15.45-17.15 im HMU
  
• Klausur: i3v

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.

• 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

Änderungen vorbehalten!

• Skript zur Vorlesung Revision 4 (vorläufig endgültige Version), Changelog
• Skript zur Vorlesung "Entwurf und Analyse von Algorithmen", entspricht nicht dem Vorlesungsskript.
• Kapitel zu Maximalen Flüssen, Randomisierte Algorithmen, Approximationsalgorithmenn
• Kurzskripte zur Wiederholung wichtiger Begriffe: Algorithmen und ihre Laufzeit, Begriffe zu Graphen, Die Komplexitätsklassen //P, NP// und //NPC//

1. Übungsblatt und Musterlösung
2. Übungsblatt und Musterlösung und Übungsfolien
3. Übungsblatt und Musterlösung und Übungsfolien
4. Übungsblatt und Musterlösung
5. Übungsblatt und Musterlösung
6. Übungsblatt Teil A, Teil B und Übungsfolien und Bemerkung zu Lemma 5.12 und Musterlösung
7. Übungsblatt und Übungsfolien und Musterlösung

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.

• Zweite Klausur vom 18.04.06, und Lösung
• Klausurergebnisse der zweiten Klausur (Schnitt 3,32; Schnitt Bestandene: 2,84)

• Erste Klausur vom 09.03.06, und Lösung
• Klausurergebnisse der ersten Klausur (Schnitt 3,23; Schnitt bestandene 2,78)

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

Frühere Abstimmungen

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.