|
Dozent:
Prof. Dr. Ernst W. Mayr
|
|
|
Bereich:
4+2 SWS Vorlesung im
Bereich Informatik III (Theoretische Informatik)
Wahlpflichtvorlesung
im Gebiet Algorithmen
|
|
|
Zeit und Ort:
Mi 8:30 - 10:00, Hörsaal 2750
Do 10h c.t. - 11:45, Hörsaal 2750
Beginn: 5. November
Weihnachtsferien: 23. Dez mit 7. Jan
|
|
|
Übung:
2 SWS Übung zur Vorlesung
Mo 8:30 - 10:00, Hörsaal N1070
Beginn: 10. November
Übungsleitung: Stefan Bischof
|
|
|
Hörerkreis:
Studierende im Hauptstudium der Informatik
Studierende mit Nebenfach Informatik
|
|
|
Voraussetzungen:
Stoff des Informatik Grundstudiums
|
|
|
Empfehlenswert für:
Grundkenntnisse im Bereich Algorithmen
|
|
|
Inhalt:
In der Vorlesung wurden folgende Themen behandet:
- 0.
- Übersicht und Wiederholung
- (a)
- Was sind kombinatorische Algorithmen?
- (b)
- Maschinenmodelle
- (c)
- Komplexitätsmaße
- i.
- Berechnungsmodi
- ii.
- Ressourcen
- iii.
- Arten der Berechnung (worst-case, average, etc.)
- iv.
- Kostenmodelle (uniform vs. logarithmisch)
- v.
- Rekursionsgleichungen
- a.
- Multiplikatoren
- b.
- Charakteristisches Polynom
- c.
- Erzeugendenfunktionen
- d.
- Transformation des Definitions- bzw. Wertebereichs
- vi.
- Literaturhinweise
- 1.
- Höhere Datenstrukturen
- (a)
- Grundlegende Operationen
- (b)
- Suchbäume, balanzierte Bäume
- i.
- Höhenbalanzierte Suchbäume
- a.
- (a,b)-Bäume
- b.
- Rot-Schwarz-Bäume
- c.
- AVL-Bäume
- ii.
- Gewichtsbalancierte Bäume (kurz, Verweis auf Literatur)
- iii.
- Hashing (Verweis auf Literatur)
- (c)
- Priority Queues (Vorrangwarteschlangen)
- i.
- Wiederholung
- a.
- Binomialbäume
- b.
- Binomial Queues
- ii.
- Fibonacci-Heaps
- a.
- Das amortisierte Kostenmodell
- b.
- Datenstruktur Fibonacci-Heaps
- c.
- Implementierung der Operationen
- d.
- Amortisierte Analyse von Fibonacci-Heaps
- iii.
- Eine O(loglog n) Priority Queue
- (d)
- Sich selbst organisierende Datenstrukturen
- i.
- Selbstorganisierende lineare Listen
- ii.
- Splay-Trees als Suchbäume
- a.
- Einleitung
- b.
- Die Splay-Operation
- c.
- Amortisierte Kostenanalyse der Splay-Operation
- d.
- Wörterbuch-Operationen in Splay-Trees
- e.
- Weitere Arten von Datenstrukturen
- 2.
- Selektion
- (a)
- Einleitung
- (b)
- Der Algorithmus von Blum-Floyd-Pratt-Rivest-Tarjan
- (c)
- Der Median-Algorithmus von Schönhage-Paterson-Pippenger
- (d)
- Eine untere Schranke für das Median-Problem
- (e)
- Eine bessere untere Schranke für Selektion
- 3.
- Minimale Spannbäume
- (a)
- Grundlagen
- (b)
- Kruskal's Algorithmus
- (c)
- Prim's Algorithmus, erste Variante
- (d)
- Prim's Algorithmus, zweite Variante
- (e)
- Weitere Algorithmen für Minimale Spannbäume
- 4.
- Kürzeste Pfade
- (a)
- Grundlagen
- (b)
- Dijkstra's Algorithmus
- (c)
- Dijkstra's Algorithmus mit Radix-Heaps
- (d)
- Floyd's Algorithmus für das All-Pairs-Shortest-Path-Problem
- (e)
- Min-Plus-Produkt und -Transitive Hülle
- (f)
- Boolesche Matrixmultiplikation und Transitive Hülle
- (g)
- Der ``4-Russen''-Algorithmus
- (h)
- Transitive Hülle und DFS
- (i)
- Ein schnellerer Algorithmus für das All-pairs-shortest-distance-Problem
- (j)
- Transitive Hülle in linearer erwarteter Zeit
- (k)
- Strassen's Algorithmus für Matrix-Multiplikation
- 5.
- Matchings in Graphen
- (a)
- Grundlagen
- (b)
- Matchings maximaler Kardinalität in bipartiten Graphen
|
|
|
Weiterführende bzw. verwandte Vorlesungen:
Effiziente Algorithmen und Datenstrukturen II
Randomisierte Algorithmen
|
|
|
Skript:
Ein Skript
wird derzeit begleitend zur Vorlesung
von Martin Stumpf, Thomas Schöpf,
Martin Hans und Guido Wimmel erstellt.
Für den Abschnitt
Höhere Datenstrukturen
gibt es eine Ausarbeitung dieses Teils der Vorlesung vom
WS94/95.
|
|
|
Literatur:
-
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman:
-
The design and analysis of computer algorithms
Addison-Wesley Publishing Company, Reading MA, 1974
Weitere Informationen
-
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
Weitere Informationen
-
Donald E. Knuth:
-
The art of computer programming Vol. 3: Sorting and searching
Addison-Wesley Publishing Company, Reading MA, 1973
Weitere Informationen
-
Kurt Mehlhorn:
-
Data structures and algorithms 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 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
Weitere Informationen
-
Robert Endre Tarjan:
-
Data Structures and Network Algorithms
CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, Philadelphia, PA, 1983
|
|
|
Tips zur Vorlesung:
Nützliche Software
Lewis Carroll: Lawn Tennis Tournaments. Der erste
bekannte Selektions-Algorithmus.
|
|
|
Sprechstunde:
siehe hier
|
|
