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