Praktikum: Algorithm Engineering
Allgemeines
Aktuelles
- Einführung in wissenschaftliches Schreiben/LaTeX: 2. Februar, 9.45 in -119 (Infobau); Folien
- Abschlusspräsentationen: 9. Februar, 9.45 in -119 (Infobau)
- Erste Abgabe der Ausarbeitung: 16. Februar
- Abgabe der Ausarbeitung: 9. März
- Aktuelle Materialien incl. APIs von AlgoVis3D, log4j und JUnit
- Materialien zu den Themen
Inhalt: Visualisierung von Algorithmen für planare Graphen
Ein planarer Graph ist ein Graph, der in der Ebene gezeichnet werden, ohne dass die Kanten sich kreuzen. Planare Graphen haben viele schöne Eigenschaften, die benutzt werden können um für zahlreiche Probleme besonders einfache, schnelle und schöne Algorithmen zu entwerfen. Oft können sogar Probleme, die auf allgemeinen Graphen (NP-)schwer sind auf planaren Graphen sehr effizient gelöst werden.
Einige dieser Probleme und Algorithmen zu ihrer Lösung wurden in der Vorlesung „Algorithmen für Planare Graphen“ im vergangenen Sommersemester vorgestellt. In diesem Praktikum sollen nun solche Algorithmen implementiert werden. Der Besuch der Vorlesung ist hilfreich, aber keine Voraussetzung zum erfolgreichen Besuch des Praktikums.
Ein Schwerpunkt der Vorlesung liegt nicht nur auf der effizienten Implementierung der Algorithmen, sondern auch in ihrer Visualisierung. Mit Hilfe einer am Institut entwickelten Bibliothek, die auf Java3D aufsetzt, sollen die verschiedene Algorithmen visualisiert werden. Wie dies genau geschieht, bleibt der Kreativität der Teilnehmer überlassen.
Ablauf
Nach ein paar gemeinsamen Terminen mit einführendem Charakter und einigen Aufwärmaufgaben wird jeweils eine große Aufgabe von einem Team von etwa 3 Personen bearbeitet. Ziel ist sowohl eine effiziente und „schöne“ Implementierung als auch eine für das Verständnis des Algorithmus hilfreiche Visualisierung. Kurz vor Weihnachten wird jede Gruppe in einer Kurzpräsentation ihre bisherige Arbeit vorstellen. Am Ende ist eine schriftliche Ausarbeitung zu erstellen und die Ergebnisse in einer Abschlusspräsentation vorgestellt.
Themen und Literatur
Praktikumsarbeiten
| Thema | Verfasser | Texte |
| Planar-Separator-Theorem | Dirk Achenbach, Thomas Pajor, Jonida Saqe | Ausarbeitung,Triangulierung |
| Menger-Algorithmus | Florian Böhl, Simon Friedberger, Boris Groß-Hardt | Ausarbeitung |
Material
Praktikum
- Beispiel einer Visualisierung zum Push-Relabel-Algorithmus von Goldberg und Tarjan für maximale Flüsse: Flow-Commander (Java WebStart).
- Skript zur Vorlesung Algorithmen für planare Graphen.
- Folien der Vorbesprechung [ pdf]
- Nullte Übungsaufgabe [ pdf]
- Folien der ersten Übung [ pdf]
- Erste Übungsaufgabe [ pdf]
- Folien der zweiten Übung [ pdf]
- Zweite Übungsaufgabe [ pdf]
- Folien der dritten Übung [ pdf]
- Folien zur Einführung in wiss. Schreiben/LaTeX [Folien ]
Programmierung
- Graphdateiformat GraphML
- AlgoVis3D Information und Download
- jungX [ API ]
LaTeX
- Einstiegshilfe und Konventionen fachgerechten Schreibens: Materialien
- Praktikumsarbeiten früherer Semester: SoSe 2004, WiSe 05/06
- Eine der besten Latex-Distributionen für Windows: MiKTeX