Differences
This shows you the differences between two versions of the page.
|
teaching:fp_ae-2012 [2012-05-31 09:49] |
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. | ||
| - | 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 [[staff:mutzel|Prof. Petra Mutzel]] oder [[staff:zey|Bernd Zey]]. | ||