|
Dozent:
Prof. Dr. Ernst W. Mayr
|
|
|
Bereich:
4+2 SWS Vorlesung im
Bereich Informatik III (Theoretische Informatik)
Vertiefende Vorlesung
im Gebiet Algorithmen
|
|
|
Zeit und Ort:
Mo 8:30 - 10:00, Hörsaal S1128
Do 8:30 - 10:00, Hörsaal S1128
Beginn: 4. Mai
Ende: 30. Juli
Vorlesungsfrei: 21. Mai (Christi Himmelfahrt)
Pfingstferien: 30. Mai bis einschließlich 3. Juni
Vorlesungsfrei: 11. Juni (Fronleichnam)
|
|
|
Übung:
2 SWS Übung zur Vorlesung
Mi 10h c.t. - 11:45, Raum S2229
Beginn: 20. Mai
Übungsleitung: Stefan Bischof
Übungsschein: Einen Schein erhält, wer
mindestens 40% der Punkte zu den Hausaufgaben erreicht und
erfolgreich an der Semestralklausur teilnimmt.
|
|
|
Hörerkreis:
Studierende im Hauptstudium der Informatik
Studierende mit Nebenfach Informatik
|
|
|
Voraussetzungen:
Stoff des Informatik Grundstudiums
Vorlesung Effiziente Algorithmen und Datenstrukturen I vorteilhaft, aber nicht notwendig.
|
|
|
Empfehlenswert für:
Erweiterte Kenntnisse im Bereich Algorithmen
|
|
|
Inhalt:
- 1.
- Matchings in Graphen
- (a)
- Matchings maximaler Kardinalität in bipartiten Graphen (Forts.)
- (b)
- Matchings maximaler Kardinalität in allgemeinen Graphen (Micali/Vazirani)
- (c)
- Gewichtete Matchings in bipartiten Graphen
- (d)
- Gewichtete Matchings in allgemeinen Graphen
- 2.
- Flüsse in Netzwerken
- (a)
- Flüsse und Schnitte
- (b)
- Der Algorithmus von Dinic
- (c)
- Der Algorithmus von Malhotra, Pramodh Kumar und Maheshwari
- (d)
- Spezielle Anwendungen und Erweiterungen
- i.
- 0-1-Netzwerke
- ii.
- 0-1-Netzwerke vom Typ 1
- iii.
- 0-1 Netzwerke vom Typ 2
- (e)
- Netzwerke mit oberen und unteren Schranken
- (f)
- Push/Relabel Algorithmen
- (g)
- Zusammenhang in Graphen
- (h)
- Min-Cut
- 3.
- LP - Lineare Programmierung
- (a)
- Grundlagen
- (b)
- Gauß-Elimination
- (c)
- Lineare Ungleichungssysteme
- (d)
- Das Farkas-Lemma
- (e)
- Dualität in LP
- (f)
- Strikte Ungleichungen
- (g)
- Complementary Slackness
- (h)
- Der Simplex-Algorithmus
- i.
- Der einfache Simplex-Algorithmus
- ii.
- Dualität
- iii.
- Komplexität des Simplexalgorithmus
- (i)
- Die Ellipsoid-Methode
- i.
- Grundlagen
- ii.
- Khachiyan's Ellipsoid-Algorithmus
- iii.
- Reduktion des generischen LP auf Ax<b
- iv.
- Komplexitätsbetrachtungen
- 4.
- Approximationsalgorithmen für NP-harte Probleme
- (a)
- Grundlagen und Komplexitätsklassen
- (b)
- Beispiele
- i.
- Bin Packing
- ii.
- TSP
- a.
- Die Nearest-Neighbor-Heuristik, Schranken
- b.
- Christofides' Heuristik
- c.
- Weitere Heuristiken für TSP
- (c)
- Zusammenfassung -- Hierarchie von approximativen Komplexitätsklassen
|
|
|
Weiterführende bzw. verwandte Vorlesungen:
Randomisierte Algorithmen
|
|
|
Skript:
Kein Skript.
|
|
|
Literatur:
-
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman:
-
The design and analysis of computer algorithms
Addison-Wesley Publishing Company, Reading, MA, 1976
-
Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin:
-
Network Flows: Theory, Algorithms, and Applications
Prentice Hall, Englewood Cliffs, NJ, 1993
-
Robert Endre Tarjan:
-
Data Structures and Network Algorithms
CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, Philadelphia, PA, 1983
-
Kurt Mehlhorn:
-
Data structures and algorithms 2 : Graph algorithms and NP-Completeness
EATCS Monographs on Theoretical Computer Science, Springer-Verlag, Berlin - Heidelberg - New York - London - Paris - Tokyo - Hong Kong, 1984
-
Christos H. Papadimitriou, Kenneth Steiglitz:
-
Combinatorial optimization : Algorithms and complexity
Prentice-Hall, Englewood Cliffs, NJ, 1982
-
Bjarne Stroustrup
-
The C++ programming language
Third Edition,
Addison-Wesley Publishing Company, Reading, MA, 1997
-
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest:
-
Introduction to algorithms
McGraw-Hill Book Company,
New York - St. Louis - San Francisco - Montreal - Toronto, 1990
-
Alexander Schrijver:
-
Theory of linear and integer programming
John Wiley & Sons,
Chichester - New York - Brisbane - Toronto - Singapore, 1986
|
|
|
Tips zur Vorlesung:
|
|
|
Sprechstunde:
siehe hier
|
|
