Table of Contents

Fachprojekt Algorithm Engineering (Wintersemester 2012/2013)

Veranstalter Prof. Dr. Petra Mutzel
Modul INF-BSc-267 (Informatik, Angewandte Informatik)
Veranstaltungsart Fachprojekt
Veranstaltungsnummer TBA
SWS 4

Inhalt und Themen

Algorithm Engineering beinhaltet das Design von Algorithmen, ihre theoretische Analyse, die Implementierung, sowie die experimentelle Evaluation am Rechner. Dabei liegt der Schwerpunkt auf anwendungsrelevanten Problemen.

In diesem Fachprojekt liegt der Fokus auf dem klassischen Steinerbaumproblem (STP, Steiner tree problem):

Für einen gegebenen Graphen $G=(V,E)$ mit Kantenkosten $c:E\rightarrow \mathbb{N}$ und einer Menge an speziellen Knoten $T \subseteq V$, den sogenannten Terminalen, wird ein Teilgraph $G_T =(V_T, E_T)$ von $G$ gesucht, der alle Terminale miteinander verbindet und minimale Kosten $c(E_T) = \sum_{e \in E_T} c_e$ hat.

Das STP ist ein NP-vollständiges, kombinatorisches Optimierungsproblem, welches gut durch mathematische Programmierung (z.B. Branch & Cut) exakt gelöst werden kann. Für die Praxis ist es wichtig, die gegebenen Instanzen durch Preprocessing zu bearbeiten, um die Graphgröße zu reduzieren. Für das STP gibt es einige Preprocessing-Methoden, die einen Graphen extrem verkleinern können und die Lösbarkeit enorm verbessern.

In diesem Fachprojekt sollen unterschiedliche Preprocessing-Methoden für das Steinerbaumproblem implementiert werden. Anschließend sollen diese experimentell untersucht und deren Performanz verglichen werden.

Die Studierenden arbeiten dabei in Teams mit Gruppengröße $\le 3$. Es wird einen regelmäßigen Termin in der Woche für alle geben, bei dem Zwischenergebnisse, Aufgaben oder Probleme besprochen werden. Der Termin wird dienstags, 14-18 Uhr sein.

Die Implementierung wird in C++ erfolgen und verwendet das OGDF (Open Graph Drawing Framework).

Anmeldung

Die Anmeldung ist bis zum 05.06. verfügbar und können Sie hier finden.

Termine

Das regelmäßige Treffen findet jeden Dienstag, 14.00-18.00 Uhr statt; im Besprechungsraum 202 oder im Rechnerpool 204 (jeweils OH14).

Das erste Treffen ist am 09.10. um 14:15 Uhr im Raum 202, OH 14. Die folgenden Termine stehen noch nicht fest.

Inhalt Datum Uhrzeit Raum Details
Vorbesprechung und Themenvergabe 09.10.2012 14:15 Uhr OH14, Raum 202
Vorstellung der Planung TBA 14:00 Uhr OH14, Raum 202 je Gruppe ca. 10-15 min Präsentation
Fortschrittspräsentation TBA 14:00 Uhr OH14, Raum 202 je Gruppe ca. 20-25 min Präsentation
Abschlusspräsentation TBA 14:00 Uhr OH14, Raum 202 je Gruppe ca. 25 min Präsentation der Ergebnisse

Ansprechpartner

Bei Fragen zu dieser Veranstaltung wenden Sie sich bitte an Prof. Petra Mutzel oder Bernd Zey.