Differences
This shows you the differences between two versions of the page.
teaching:fp_ae-2012 [2012-05-31 09:48] |
teaching:fp_ae-2012 [2015-09-11 13:21] |
||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== Fachprojekt Algorithm Engineering (Wintersemester 2012/2013) ====== | ||
- | | Veranstalter | [[staff:mutzel|Prof. Dr. Petra Mutzel]] | | ||
- | | Modul | [[http://www.cs.uni-dortmund.de/nps/de/Studium/Proseminare_Seminare_Praktika_Fachprojekte_Projektgruppen/Fachprojekte/Fachprojekte/INF-BSc-267.pdf|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 [[http://www.ogdf.net|OGDF]] (Open Graph Drawing Framework). | ||
- | |||
- | |||
- | ===== Anmeldung ===== | ||
- | |||
- | Die Anmeldung ist bis zum 05.06. verfügbar und können Sie [[http://evaluation.tu-dortmund.de/evasys/indexstud.php|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. | ||
- | |||
- | | Vorbesprechung und Themenvergabe | 09.10.2012 | 14:15 Uhr | OH14, Raum 202 | | | ||
- | | 1. Treffen: 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 [[staff:mutzel|Prof. Petra Mutzel]] oder [[staff:zey|Bernd Zey]]. |