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