LEA
Fakultät für Informatik der Technischen Universität München
Lehrstuhl für Effiziente Algorithmen
Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Algorithmen und Datenstrukturen - Effiziente Algorithmen I (WS94/95)


* Dozent:
Ernst W. Mayr

* Bereich:
4 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)

* Zeit und Ort:
Mi 08:30 - 10:00, Hörsaal S1128
Do 10:00 - 12:00, Hörsaal 1100

* Übung:
2 SWS Übung zur Vorlesung
Di 16:00 - 18:00, Raum S0144
Übungsleitung: Hans Stadtherr
Übungsschein: Klausur

* Hörerkreis:
Studierende im Hauptstudium Informatik
Studierende mit Nebenfach Informatik

* Voraussetzungen:
Stoff des Informatik-Grundstudiums

* Inhalt:
  1. Übersicht
    1. Wiederholung Maschinenmodelle
    2. Grundbegriffe
    3. Komplexitätsmaße
  2. Höhere Datenstrukturen
    1. (a,b)-Bäume
    2. Rot-Schwarz-Bäume
    3. Wiederholung Binomial heaps
    4. Fibonacci heaps
    5. amortisierte Komplexität
    6. Selbstorganisierende Listen
    7. Splay trees
    8. loglogN priority queue
  3. Selektion
    1. Selektionsalgorithmus nach BFPRT
    2. Schönhage-Paterson-Pippenger Median Algorithmus
    3. 1.5 n untere Schranke für Median
  4. Minimale Spannbäume
    1. Grundlagen für Minimale Spannbäume
    2. Kruskal's Algorithmus
    3. zwei Algorithmen für MST mit Fibonacci-Heaps einschl. Analyse
  5. Kürzeste Pfade
    1. Grundlagen
    2. Dijkstra's Algorithmus
    3. Floyd's Algorithmus für das All-Pairs-Problem
    4. Min-Plus Matrix-Produkt
    5. Boolesche Matrixmultiplikation und Transitive Hülle
    6. 4-Russen-Algorithmus
    7. Kürzeste Pfade in allgemeinen Graphen
    8. All-pairs-shortest-paths in allgemeinen Graphen
    9. Average-case-Analyse für Transitive Hülle (Schnorr)
  6. Zusammenhang von Graphen
    1. Grundlagen, einfacher Zusammenhang
    2. Zweifach-Zusammenhangskomponenten
    3. Starke Zusammenhangskomponenten
    4. Zweifach-Zusammenhangskomponenten ohne DFS
  7. Planare Graphen
    1. Grundlagen
    2. Charakterisierung planarer Graphen; Rekursive Charakterisierung der Planarität; Satz von Kuratowski
    3. Hopcroft/Tarjan Planaritätstest
    4. sqr(n)-Separatoren für planare Graphen

* Weiterführende bzw. vertiefende Vorlesungen:
Algorithmen und Datenstrukturen - Effiziente Algorithmen II

* Skript:
In Vorbereitung.

* Literatur:
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman
The design and analysis of computer algorithms
Addison-Wesley Publishing Company, Reading MA, 1976
Donald E. Knuth
The art of computer programming Vol. 3 : Sorting and searching
Addison-Wesley Publiching Company, Reading MA, 1973
Kurt Mehlhorn
Data structures and algoprithms 1 : Sorting and searching
EATCS Monographs on Theoretical Computer Science, Springer-Verlag, Berlin - Heidelberg - New York - London - Paris - Tokyo - Hong Kong, 1984
Kurt Mehlhorn
Data structures and algoprithms 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
Combinatorical optimization : Algorithms and complexity
Prentice-Hall, Englewood Cliffs, NJ, 1982
Bjarne Stroustrup
The C++ programming language
Addison-Wesly Publishing Company, Reading, MA, 1986

* Sprechstunde:
siehe hier


mayr@informatik.tu-muenchen.de