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
english

Effiziente Algorithmen und Datenstrukturen (WS 98/99)


* Dozent:
Prof. Dr. Ernst W. Mayr

* Bereich:
4+2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
Wahlpflichtvorlesung im Gebiet Algorithmen

* Zeit und Ort:
Mo 8:30 - 10:00, Hörsaal S1128
Mi 8:30 - 10:00, Hörsaal S1128
Beginn: 2. November

* Übung:
2 SWS Übung zur Vorlesung
Donnerstag 8:30 - 10:00, Raum 1260
Übungsleitung: Jens Ernst
Übungsschein: Einen Schein erhält, wer mindestens 40% der Punkte zu den Hausaufgaben erreicht und erfolgreich an der Semestralklausur teilnimmt.

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

* Voraussetzungen:
Stoff des Informatik Grundstudiums

* Empfehlenswert:
Grundkenntnisse im Bereich Algorithmen

* Inhalt:
0.
Übersicht und Wiederholung
(a)
Ein einleitendes Beispiel
(b)
Übersicht
(c)
Maschinenmodelle
(d)
Komplexitätsmaße
(e)
Rekursionsgleichungen
i.
Motivierung
ii.
Lösungsansätze
a.
Raten + Verifizieren
b.
Mutiplikationsmethode
c.
Charakteristische Polynome
d.
Erzeugendenfunktionen
e.
Transformationen des Definitions- und Wertebereichs
1.
Höhere Datenstrukturen
(a)
Grundlegende Operationen, Einordnung
(b)
Balancierte allgemeine Suchbäume
i.
(a,b)-Bäume
ii.
Rot-Schwarz-Bäume
(c)
Binäre Suchbäume
i.
Natürliche Binäre Suchbäume
ii.
Balancierte binäre Suchbäume/AVL-Bäume
(d)
Hashing
i.
Grundlagen
ii.
Chaining-Verfahren
iii.
Hashing mit offener Adressierung (linear probing, quadratic probing, double hashing)
iv.
Universelles Hashing
v.
Perfektes Hashing
(e)
Priority Queues
i.
Binomial Queues
ii.
Fibonacci Heaps
a.
Die Datenstruktur und Operationen
b.
Amortisierte Kostenanalyse
(f)
Sich selbst organisierende Datenstrukturen
i.
Sich selbst organisierende Listen
ii.
Sich selbst organisierende Binary Heaps
iii.
Splay-Trees (als Suchbäume)
a.
Historie
b.
Die Splay-Operation
c.
Amortisierte Komplexitätsanalyse
d.
Wörterbuchoperationen in Splay-Trees
e.
Weitere Datenstrukturen
(g)
Radix-basierte Datenstrukturen
i.
Buckets
ii.
2-Level-Buckets
iii.
van Emde Boas Priority Queues
iv.
Radix Heaps
(h)
Union-Find Datenstrukturen
i.
Motivation
ii.
In-trees
iii.
Verbesserte Heuristiken
a.
Gewichtete Vereinigung
b.
Pfadkompression
c.
Pfadkompression mit gewichteter Vereinigung
d.
Erweiterungen und Varianten
2.
Grundlegende Algorithmen
(a)
Selektieren und Sortieren
i.
Einleitung
ii.
Der BFPRT-Algorithmus für Selektion
iii.
Ein randomisierter Median-Algorithmus
iv.
Eine (erste) untere Schranke für die Medianbestimmung
v.
Eine bessere untere Schranke für den Median
vi.
Untere Schranke für (vergleichsbasierte) Sortieralgorithmen
vii.
Bucket Sort im Schnitt
viii.
(Die Komplexität von) Quicksort
(b)
Elementare Graphenalgorithmen
(c)
Minimale Spannbäume
i.
Grundlagen
ii.
Kruskal's Algorithmus
iii.
Prim's Algorithmus, erste Variante
iv.
Prim's Algorithmus, zweite Variante
(d)
Kürzeste Pfade
i.
Grundlagen
ii.
Single-Source
a.
Dijkstra's Algorithmus
b.
Dijkstra's Algorithmus mit Radix-Heaps
c.
Der Algorithmus von Bellman-Ford
iii.
Floyd's Algorithmus für das All-Pairs-Shortest-Path Problem
iv.
Digraphen mit negativen Kantengewichten
a.
Grundsätzliches
b.
Modifikation des Bellman-Ford Algorithmus
c.
Modifikation von Floyd's Algorithmus
d.
Der Algorithmus von Johnson -- Rekalibrierung
v.
Zusammenfassung
vi.
Transitive Hülle
a.
Min-Plus-Matrix-Produkt und Min-Plus-Transitive Hülle
b.
Boolesche Matrixmultiplikation und Transitive Hülle
c.
Der 4-Russen-Algorithmus für Boolesche Matrixmultiplikation

* Weiterführende bzw. verwandte Vorlesungen:
Effiziente Algorithmen und Datenstrukturen II
Randomisierte Algorithmen

* Skript:
Siehe unter Skripten.

* 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 Publishing Company, Reading MA, 1973
Dexter C. Kozen:
The design and analysis of algorithms
Texts and Monographs in Computer Science, Springer-Verlag, Berlin - Heidelberg - New York - London - Paris - Tokyo - Hong Kong, 1991
Udi Manber:
Introduction to algorithms - A creative approach
Addison-Wesley Publishing Company, Reading MA, 1989
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
Thomas Ottmann, Peter Widmayer
Algorithmen und Datenstrukturen
Reihe Informatik, Band 70, 3. Auflage, Spektrum Akademischer Verlag, 1996
Online-Version: hier
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
McGraw-Hill Book Company, New York - St. Louis - San Francisco - Montreal - Toronto, 1990
Bjarne Stroustrup
The C++ programming language
Third Edition, Addison-Wesley Publishing Company, Reading, MA, 1997
Robert Endre Tarjan:
Data Structures and Network Algorithms
CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, Philadelphia, PA, 1983

* Tips zur Vorlesung:

The Collection of Computer Science Bibliographies

LEABIB

Nützliche Software

Lewis Carroll: Lawn Tennis Tournaments. Der erste bekannte Selektions-Algorithmus.

* Sprechstunde:
siehe hier


mayr@informatik.tu-muenchen.de