Projektgruppe (Hauptstudium)
Projektgruppe Effiziente Approximationsalgorithmen: Implementation und Analyse
Prof. Dr. Marek Karpinski
Dr. Mathias Hauptmann
Johannes Langguth
Für die Lösung kombinatorischer Optimierungsprobleme erweisen sich sequentielle Algorithmen trotz polynomieller Laufzeit häufig als ungeeignet. Für sehr große Instanzen, wie sie heutzutage in den Anwendungen auftreten, ist selbst quadratische Laufzeit inakzeptabel. Darüberhinaus sind die meisten auftretenden Probleme nicht exakt schnell (d.h. in Polynomzeit) lösbar (falls nicht P=NP gilt). Drei Ansätze schaffen Abhilfe: Approximative Algorithmen berechnen Lösungen, die mit Garantie nicht viel schlechter als das Optimum sind. Parallele Algorithmen laufen verteilt auf mehreren Prozessoren und bewirken oft eine erhebliche (d.h. fast exponentielle) Beschleunigung. Randomisierte Algorithmen sind zufallsgesteuert, die Fehlerwahrscheinlichkeit kann beliebig klein gemacht werden. In vielen Fällen werden diese Ansätze kombiniert eingesetzt. Im Rahmen dieser Projektgruppe entwickeln, implementieren und untersuchen wir Approximationsalgorithmen zur Lösung in der Praxis relevanter Probleme aus der Kombinatorischen Optimierung. Dabei wird schrittweise eine umfangreiche Programmbibliothek zur kombinatorischen Optimierung aufgebaut. Derzeitige Themen sind u.a.: Netzwerk-Routingprobleme (Steinerbaumproblem, Zero Skew Trees etc.), Bisektionsprobleme, algorithmische Genomanalyse (Sorting by Reversals). Für die Arbeit in der Projektgruppe stehen zwei modern ausgestattete Labore der Abteilung V zur Verfügung.
Interessenten wenden sich bitte an Mathias Hauptmann (N332, Tel. 4319) oder Johannes Langguth (N322, Tel. 4129)
| Zeit, Ort | n.Vereinb. |
| Vorbesprechung | n.Vereinb. |
| Teilnehmerzahl | 12 |
| Vortragsmodus | Implementierung einzeln oder in Kleingruppen, regelmäßige Präsentation und Diskussion der Arbeitsergebnisse. |
| Voraussetzungen | Vordiplom in Informatik bzw. Mathematik, Interesse an algorithmischen und mathematischen Fragestellungen (insbesondere an Diskreter Optimierung), Grundkenntnisse in C, C++ oder Java. | | Nachfolgeveranstaltungen | Seminar: "Randomisierte und Approximative Algorithmen: Entwurf und Analyse". Die Projektgruppe bietet einen Einstieg in eine weitergehende Beschäftigung mit der Materie im Rahmen von Diplomarbeiten. |
| Bereich (alte DPO) | A |
| Bereich (neue DPO) | A |
| Email-Kontakt | hauptman@cs.uni-bonn.de langguth@cs.uni-bonn.de |
|
Übersicht: alle Semester
Projektgruppe Fehlerresistente Übertragungssysteme
Diplomandenseminar Algorithmische Geometrie und Bewegungsplanung