Fakultät für Informatik
-
Technische Universität München
Lehrstuhl für
Effiziente Algorithmen
Effiziente Algorithmen und Datenstrukturen II (SS 05)
Dozent:
Dr. Sven Kosub
Bereich:
4+2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
Vertiefende Vorlesung im Gebiet Algorithmen
Zeit und Ort:
Dienstag, 10:15-11:45, Hörsaal MI 00.04.011 (Hörsaal 2)
Freitag, 12:00-13:30, Hörsaal MI 00.04.011 (Hörsaal 2)
Übung:
2 SWS Übung zur Vorlesung
Mittwoch, 10:15-11:45, Hörsaal MI 00.13.009A (Multimedia-Hörsaal)
Übungsleitung:
Stefan Eckhardt
Schein:
Einen Schein erhält, wer mindestens 40% der Punkte zu den Hausaufgaben erreicht und erfolgreich an der mündlichen Prüfung 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:
Behandelte Themen:
Graphenalgorithmen
Datenstrukturen für Graphen
Erreichbarkeitsprobleme
Zweifacher Zusammenhang
Starker Zusammenhang
Transitive Hülle
Minimale Spannbäume
Algorithmus von Kruskal
Algorithmus von Prim und Jarnik
Algorithmus von Boruvka
Algorithmus von Chazelle
Algorithmen für Flüsse und Matchings
Flüsse und Schnitte
Maximaler Fluss
Max-Flow, Min-Cut Theorem
Algorithmus von Ford und Fulkerson
Algorithmus von Edmonds und Karp
Maximale Matchings
Flüsse mit minimalen Kosten
Lineare Programmierung
Standardformulierungen
Simplex-Algorithmus
Grundlagen
Formaler Simplex-Algorithmus
Terminierung
Optimalität und Dualität
Initialisierung
Vorlesungszusammenfassung:
[PostScript]
[PDF]
Weiterführende bzw. verwandte Vorlesungen:
Internet-Algorithmik
Skript:
Kein Skript.
(Private Vorlesungsmitschrift:
Martin von Gagern
)
Literatur:
Die Inhalte der Vorlesung werden in wesentlichen Teilen durch folgende Bücher und Artikel abgedeckt:
Bernard Chazelle.
A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity.
Journal of the ACM, 47(6):1028-1047, 2000.
Thomas H. Cormen, Charles E. Leiserson, Ron L. Rivest, Clifford Stein.
Introduction to Algorithms.
2. Auflage, The MIT Press, Cambridge, MA, 2001.
Michael T. Goodrich, Roberto Tamassia.
Algorithm Design: Foundations, Analysis, and Internet Examples.
John Wiley & Sons, Inc., 2002.
Christos H. Papadimitriou, Kenneth Steiglitz.
Combinatorial optimization: Algorithms and complexity.
Prentice-Hall, Englewood Cliffs, NJ, 1982.
Uwe Schöning.
Algorithmik.
Spektrum Akademischer Verlag, Heidelberg, 2001.
Steven S. Skiena.
The Algorithm Design Manual.
Springer-Verlag, New York, 1998.
Robert E. Tarjan.
Data Structures and Network Algorithms.
CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, Philadelphia, PA, 1983.
Sprechstunde:
siehe hier
Letzte Änderung:
Sven Kosub
am 18.08.2005