Weitere Informationen finden Sie auf der Homepage des Seminars

Anmeldung: Alle Plätze sind bereits vergeben.
Neue Anmeldungen tragen wir auf eine Warteliste ein. Wer trotzdem sein Glück versuchen will, kann sich an Thomas Schlechte: schlechte@zib.de und Marco Blanco: blanco@zib.de wenden und zur Vorbesprechung kommen.

Termine:
Eine Vorbesprechung zum Seminar mit Vergabe von Seminarthemen findet statt am
Freitag, dem 18. Oktober 2013, um 09:30 Uhr im Hörsaal 1005 am Konrad-Zuse-Zentrum.

Ein Termin mit Kurzvorträgen von jeweils 5 Minuten Dauer findet voraussichtlich statt am
Donnerstag, dem 12. Dezember 2013, ab 14:00 Uhr im Hörsaal R 1005 am Konrad-Zuse-Zentrum.

Das Seminar wird als Blockseminar voraussichtlich am
Donnerstag/Freitag, dem 13./14.02.2013 am Konrad-Zuse-Zentrum. durchgeführt. ( Lageplan). close

Inhalt: In diesem gemischten Bachleor/Master-Seminar für Studenten der FU und TU werden grundlegende und aktuelle Forschungsartikel zur Lösung des Kürzeste-Wege-Problems behandelt. Das kürzeste-Wege-Problem (Shortest Path Problem) ist ein klassisches Problem der diskreten Optimierung und theoretischen Informatik. Fundamental ist der Dijkstra-Algorithmus mit polynomialer Laufzeit (Komplexitätsklasse P). Heutzutage wird versucht, durch Preprocessingtechniken die zugrundeliegenden riesigen Graphen so zu verändern, dass anschließend kürzeste Wege viel schneller als mit dem klassichen Dijkstra-Algorithmus gefunden werden können. Diese Algorithmen werden z.B. bei der Straßenroutenplanung intensiv verwendet. Anderseits gibt es Algorithmen, die schwierigere Varianten des Shortest Path Problems behandeln, zum Beispiel das "Resource Constrained Shortest Path" oder das kürzeste Wege Problem mit verbotenen Subpfaden. In diesem Seminar werden zentrale Artikel der kombinatorischen Optimierung behandelt, die starken Einfluss auf die aktuelle Forschung und Entwicklung von kürzeste-Wege-Algorithmen haben.

Voraussetzungen: Grundkenntnisse in Graphen- und Netzwerkalgorithmen sowie kombinatorischer Optimierung. Für einige fortgeschrittene Themen sind Kenntnisse in linearer und ganzzahliger Optimierung notwendig. close