Vorlesung

Effiziente Algorithmen

Hartmut Klauck

SS 2006

Termine:

Vorlesung: Di 14 - 16, Magnus HS; Do 12 - 14, Magnus HS

Übung: Mi 14-16 SR 307 (D. Brendel)

Inhalt:

Der Entwurf und die Analyse von Datenstrukturen und effizienten sequentiellen Algorithmen werden beschrieben. Die einzelnen Themengebiete sind:

· Graphalgorithmen

· Randomisierte Algorithmen,

· Approximationsalgorithmen,

· Datenstrukturen mit guter amortisierter Laufzeit,

Vorkenntnisse:

Die Vorlesung setzt den Besuch der Veranstaltungen Theoretische Informatik 1 und 2 voraus.

Scheinerwerb:

Erfolgreiche Teilnahme an den Übungen

Vorlesungen:

18.4.: .pps , .pdf, .ps [Einleitung, Breitensuche, Tiefensuche, Kürzeste Weg in ungewichteten Graphen]
20.4.: .pps , .pdf, .ps  [Kürzeste Wege: Dijkstra, Bellman-Ford]
25.4.: .pps , .pdf, .ps  [Bellman-Ford, Floyd-Warshall]
27.4.: .pps , .pdf, .ps  [Distanzberechnung per Matrixmultiplikation]
2.5.: .pps , .pdf, .ps  [Kürzeste Wege per Matrixmultiplikation, Randomisierte Algorithmen]
4.5.: .pps , .pdf, .ps  [Randomisierter Algorithmus für Boolesches Matrixprodukt mit Zeugen]
9.5.: .pps , .pdf, .ps  [Approximation der paarweisen Distanzen in gerichteten, gewichteten Graphen]
11.5.: .pps , .pdf, .ps  [APSP vs. Matrixmultiplikation, Vorbereitung Approximation APSP in ung. Graphen/Dominating Sets]
16.5.: .pps , .pdf, .ps  [2-Approximation von APSP]
18.5.: .pps , .pdf, .ps  [3-Approximation von APSP in fast Linearzeit]
23.5.: .pps , .pdf, .ps  [Spannbäume: Kruskal/Prim, Union-Find]
30.5.: .pps , .pdf, .ps  [Spannbäume: randomisierte Linearzeitberechnung/Boruvka]
1.6.: .pps , .pdf, .ps  [Spannbäume: Theorem zum randomisierten Algo., Verifizierung in Linearzeit]
6.6.: .pps , .pdf, .ps  [Flussnetzwerke, Ford Fulkerson]
8.6.: .pps , .pdf, .ps  [Max-Flow Min-Cut Theorem, Laufzeit Edmonds Karp, Matching]
13.6.: .pps , .pdf, .ps  [Dinic Algorithmus, Min Cuts]
22.6.: .pps , .pdf, .ps  [Matching, Randomisierter Algorithmus Min Cut]
27.6.: .pps , .pdf, .ps  [Randomisierter Alg. Min Cut: Korrektheit, Binomische Heaps]
29.6.: .pps , .pdf, .ps  [Amortisierte Analyse, Fibonacci Heaps]
4.7.: .pps , .pdf, .ps  [Fibonacci Heaps]
6.7.: .pps , .pdf, .ps  [Lineares Programmieren, Simplex]
11.7.: .pps , .pdf, .ps  [Simplex]
13.7.: .pps , .pdf, .ps  [Lineare Integer Programme, Semidefinite Programme, Lovasz Theta Funktion, Approximation von Vertex Cover]
18.7.: .pps , .pdf, .ps  [Approximation per Zufall, per LP Relaxation und Set Cover]
20.7.: .pps , .pdf, .ps  [Set Cover via LP Relaxation, TSP, Max Cut Approx. durch semidefinite Programmierung]

Übungsblätter:

Ausgabe und Abgabe jeweils Di.

20.4: .ps
27.4: .ps Musterlösung
4.5: .ps
11.5: .ps
18.5: .ps
30.5: .ps
6.6: .ps
13.6: .ps
20.6: .ps
27.6: .ps
4.7 : .ps
11.7: .ps

Literatur:

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, Cambridge University Press, 2001;

Deutsche Ausgabe bei Oldenbourg.
R. Motwani, P. Raghavan: Randomized Algorithms, Cambridge University Press, 1995.

Jon Kleinberg, Eva Tardos: Algorithm Design, Pearson 2006.

Sonstige Links:

Survey über Kürzeste Pfade
Stretch-Algorithmen
Spannbaumverifikation

---

24.7.2006,   Hartmut Klauck