Vorlesungsinhalt
Wir werden die im Grundstudium gewonnenen Kenntnisse über den Entwurf und die Analyse von Algorithmen vertiefen und erweitern. Voraussetzungen sind die Vorlesungen "Datenstrukturen, Algorithmen und Programmierung" und "Grundlagen der Theoretischen Informatik" sowie Interesse an der Anwendung mathematischer Methoden. Der Inhalt der Vorlesung ist ein Mix aus klassischen Resultaten und hochaktuellen Forschungsergebnissen.
- Flussalgorithmen (3 Wochen)
Algorithmus von Ford und Fulkerson (Beschreibung und Analyse)
Anwendungsbeispiel: Matching in bipartiten Graphen
Algorithmus von Edmonds und Karp (Beschreibung und Analyse)
Forward-Backward Propagation (Beschreibung und Analyse)
- Kurze Einführung in Lineare Optimierung (ca. 1-2 Wochen)
Lineare Programme (Definition und Erläuterung)
Simplex Algorithmus (Geometrische Interpretation, Laufzeit)
Polynomielle Laufzeitschranke der Ellipsoid Methode
Integer Lineare Programme
Beispielanwendungen
- Randomisierte Algorithmen (ca. 3 Wochen)
Algorithmus SeideLP für LPs kleiner Dimension
Karger's Mincut-Algorithmus
Bälle und Kisten (max. Last, Anzahl leerer Kisten, etc.)
Routing (durch Multicomm. Flow und random. Runden mit Chernoff Schranke)
- Approximationsalgorithmen (4 Wochen)
Vertex-Cover und Set-Cover
TSP (Nichtapproximierbarkeit im allg. Fall, 3/2-Approx. für metrisches TSP)
Approximationsschemata (Definition, FPAS für Rucksack, Strong NP-Hardness)
PAS für Maschinen-Scheduling (für identische Maschinen)
2-Approximation für Maschinen-Scheduling (für allgemeine Maschinen)
- Online-Algorithmen (ca. 1-2 Wochen)
Competitive-Analyse (Definition)
Paging (deterministisch und randomisiert)
Potentialfunktionsmethode
(Wegen der zahlreichen Feiertage stehen uns nur 12-13 Wochen zur Verfügung.)
Die Algorithmen und Analysen werden möglichst anschaulich präsentiert, ohne auf
eine formale Darstellung zu verzichten. Neben dem Skript zur
Vorlesung gibt es Literaturhinweise zu den einzelnen Teilgebieten. Die Literatur
wird im Semesterhandapparat und teilweise im Internet zur Verfügung gestellt.
zum Skript