|
Dozent:
Prof. Dr. Angelika Steger
|
|
|
Bereich:
4 SWS Vorlesung im
Bereich Informatik III (Theoretische Informatik)
Vertiefende Vorlesung
im Gebiet Algorithmen
|
|
|
Zeit und Ort:
Di 10h s.t. - 12:00, Hörsaal 1260
Do 11h s.t. - 12:45, Hörsaal 2770
|
|
|
Übung:
2 SWS Übung zur Vorlesung
Di 12h s.t. - 13:30, Raum N0815.
Übungsleitung: Thomas Schickinger
Übungsschein: Einen Schein erhält, wer
wer aktiv an den Übungen teilnimmt (Vorrechnen an der Tafel) und eine
Abschlußprüfung erfolgreich absolviert (mündlich, außer bei sehr vielen
Interessenten)
|
|
|
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:
- Matchingprobleme
- Flußprobleme
- Lineare Programmierung
- Ganzzahlige Optimierung
- Polynomielle Approximationsalgorithmen
- Untere Schranken
|
|
|
Weiterführende bzw. verwandte Vorlesungen:
|
|
|
Skript:
Folien zur Vorlesung:
|
|
|
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
-
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest:
-
Introduction to Algorithms
The MIT Press, 2. Auflage, 2001
|
|
|
Sprechstunde:
siehe hier
|
|
