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