Effiziente Algorithmen und Datenstrukturen I (WS 2000/2001)

Effiziente Algorithmen und Datenstrukturen I (WS 2000/2001)

Dozent:
Prof. Dr. Javier Esparza

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

Zeit und Ort:
Di 11h c.t. - 13h, Hörsaal N1070
Do 10h c.t. - 12h, Hörsaal 1100

Sprechstunde:
Do 13:15h - 14:15h und nach Vereinbarung

Übung:
2 SWS Zentralübung zur Vorlesung
Übungsschein: Einen Schein erhält, wer mindestens 40% der Punkte der Kontrollhausaufgaben erreicht und erfolgreich an der Semestralprüfung teilnimmt.
Welche Hausaufgaben Kontrollhausaufgaben sind, wird vorher bekannt gegeben.

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

Voraussetzungen:
Stoff des Informatik Grundstudiums

Empfehlenswert für:
Grundkenntnisse im Bereich Algorithmen

Inhalt:

Ü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

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

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 (Skript von WS 98/99).

Folien

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
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

Javier Esparza