Parametrisierte Algorithmen
| Veranstaltungsnummer | |
| Veranstalter | Prof. Dr. Thomas Schwentick |
| Klassifikation | Proseminar |
| Semester | Sommersemester 2017 |
| Ort und Zeit | |
| Vorbesprechung | wird noch angekündigt |
| Querverbindungen | DAP II, GTI |
| Voraussetzungen | DAP II |
Inhalt
In der Algorithmentheorie wird der Aufwand eines Algorithmus üblicherweise (asymptotisch) im Verhältnis zur Größe seiner Eingaben ausgedrückt. Bei Graphenalgorithmen oft auch in der Anzahl der Knoten des Graphen. Für viele algorithmische Probleme sind in dieser Betrachtungsweise nur Algorithmen mit exponentiellem Zeitaufwand bekannt.
Ein Beispiel hierfür ist das Vertex Cover Problem: Gegeben ein Graph G und eine Zahl k, fragt es, ob es eine Menge M von k Knoten gibt, so dass jede Kante des Graphen einen Knoten in M hat. Interessanterweise gibt es jedoch einen sehr simplen Algorithmus, dessen Aufwand O(n 2^k) ist, wobei n die Anzahl der Knoten des Eingabegraphen ist. Intuitiv ist der Aufwand dieses Algorithmus also "nur" schlecht in k, aber nicht in n. Anders gesagt: für Eingaben mit "kleinem" k lässt sich das Problem effizient lösen.
Solche Parametrisierungen gibt es auch für eine Reihe anderer algorithmischer Probleme. Entsprechende Algorithmen dieser Art wollen wir in dem Proseminar betrachten.
Die Vortragsthemen basieren zum Teil auf dem Buch Invitation to Fixed-Parameter Algorithms von Rolf Niedermeier, zum Teil auf dem Buch Fundamentals of Parameterized Complexity von Rodney G. Downey und Michael R. Fellows. Die dem Buch von Herrn Niedermeier zugrunde liegende Habilitationsschrift finden Sie hier: http://theinf1.informatik.uni-jena.de/~niedermr/publications.html.
Darüber können den Vorträgen weitere Bücher und Originalarbeiten zugrunde liegen.
Suche & Personensuche
Anfahrt & Lageplan
Der Campus der Technischen Universität Dortmund liegt in der Nähe des Autobahnkreuzes Dortmund West, wo die Sauerlandlinie A45 den Ruhrschnellweg B1/A40 kreuzt. Die Abfahrt Dortmund-Eichlinghofen auf der A45 führt zum Campus Süd, die Abfahrt Dortmund-Dorstfeld auf der A40 zum Campus-Nord. An beiden Ausfahrten ist die Universität ausgeschildert.
Direkt auf dem Campus Nord befindet sich die S-Bahn-Station „Dortmund Universität“. Von dort fährt die S-Bahn-Linie S1 im 15- oder 30-Minuten-Takt zum Hauptbahnhof Dortmund und in der Gegenrichtung zum Hauptbahnhof Düsseldorf über Bochum, Essen und Duisburg. Außerdem ist die Universität mit den Buslinien 445, 447 und 462 zu erreichen. Eine Fahrplanauskunft findet sich auf der Homepage des Verkehrsverbundes Rhein-Ruhr, außerdem bieten die DSW21 einen interaktiven Liniennetzplan an.
Zu den Wahrzeichen der TU Dortmund gehört die H-Bahn. Linie 1 verkehrt im 10-Minuten-Takt zwischen Dortmund Eichlinghofen und dem Technologiezentrum über Campus Süd und Dortmund Universität S, Linie 2 pendelt im 5-Minuten-Takt zwischen Campus Nord und Campus Süd. Diese Strecke legt sie in zwei Minuten zurück.
Vom Flughafen Dortmund aus gelangt man mit dem AirportExpress innerhalb von gut 20 Minuten zum Dortmunder Hauptbahnhof und von dort mit der S-Bahn zur Universität. Ein größeres Angebot an internationalen Flugverbindungen bietet der etwa 60 Kilometer entfernte Flughafen Düsseldorf, der direkt mit der S-Bahn vom Bahnhof der Universität zu erreichen ist.