Vorlesungsinhalt
Schwerpunkt der Veranstaltung sind der Entwurf und die Analyse
von effiziente Algorithmen. Komplexitätstheoretische
Gesichtspunkte werden nur am Rande behandelt. Im kommenden
Wintersemester wird eine Vorlesung unter demselben Namen aber mit
umgekehrtem Schwerpunkt von Ingo Wegener angeboten.
Wir werden die im Grundstudium gewonnenen Kenntnisse über
den Entwurf und die Analyse von Algorithmen vertiefen und erweitern.
Voraussetzungen sind die Grundstudiumsveranstaltungen "Datenstrukturen,
Algorithmen und Programmierung" sowie "Grundbegriffe der Theoretischen
Informatik". Die Themenauswahl orientiert sich an der praktischen
Relevanz der vorgestellten Algorithmen und Analysemethoden. Im
Einzelnen widmen wir uns den folgenden Themen.
- Maximaler Fluss (2 Wochen)
Algorithmus von Ford und Fulkerson
Verbesserung von Edmonds und Karp
Sperrflüsse & Forward-Backward Propagation
- Maximum Matchings (1 Woche)
Gewichtete und ungewichtete Matchingprobleme
Maximum Matchings in bipartiten Graphen (Hopcroft und Karp)
- Chrashkurs Lineare
Programmierung (1-2 Wochen)
Simplex und Ellipsoid-Methode
Ganzzahligkeit, Unimodularität
- Randomisierte Algorithmen (ca. 2-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 (2-3 Wochen)
Vertex-Cover und Set-Cover
TSP und metrisches TSP
Approximationsschemata, starke NP-Härte
Makespan-Scheduling
- Online-Algorithmen (ca. 1-2 Wochen)
Competitive-Analyse (Definition und Erläuterung)
Paging (deterministische und randomisierte Verfahren)
Ressourcenaugmentierung
- Algorithmen
für zahlentheoretische Probleme
(1-2 Wochen)
Kryptographische Systeme (RSA)
Grundlagen wie z.B. der Chinesische Restklassensatz
Berechnung von Potenzen, Inversen, und ggTs
Randomisierter Primzahltest (Solovay und Strassen)
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 soweit möglich auch im Internet
zur
Verfügung gestellt.