|
Dozent:
Prof. Dr. Angelika Steger
|
|
|
Bereich:
4+2 SWS Vorlesung im
Bereich Informatik III (Theoretische Informatik)
Wahlpflichtvorlesung
im Gebiet Algorithmen
|
|
|
Zeit und Ort:
Di 10h c.t. - 11:45, Hörsaal N1179 Achtung:
am 6.11 noch in N1070
Do 10h c.t. - 11:45, Hörsaal N1189
Beginn: 16. Oktober
|
|
|
Übung:
2 SWS Übung zur Vorlesung
Di 13:30 - 15:00, Hörsaal N1080
Übungsleitung: Ingo Rohloff
Ü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 für:
Grundkenntnisse im Bereich Algorithmen
|
|
|
Inhalt:
In der Vorlesung werden voraussichtlich folgende Themen
behandelt:
- Grundlagen
- Ein Beispiel
- Analyse von Algorithmen
- Amortisierte Analyse
- Höhere Datenstrukturen
- Wiederholung: (a,b)-Bäume, AVL-Bäume
- Splay Trees
- Fibonacci Heaps
- k-level Buckets
- Radix Heaps
- Sortieren und Selektieren
- Analyse von QuickSort
- BucketSort
- Selektionsalgorithmus nach BFPRT
- Untere Schranke für Median
- Graphalgorithmen I
- Das kürzeste Wege Problem
- Transitive Hülle
- Ausgewählte Verfahren
- Matrizenmultiplikation nach Strassen
- String Matching
- Suffix Trees
- FFT
- Approximationsalgorithmen
- Knapsack
- Binpacking
- TSP
- MaxSat
|
|
|
Weiterführende bzw. verwandte Vorlesungen:
Effiziente Algorithmen und Datenstrukturen II
Randomisierte Algorithmen
|
|
|
Skript:
Skript von 1996/97. Siehe hier.
|
|
|
Literatur:
-
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman:
-
The design and analysis of computer algorithms
Addison-Wesley Publishing Company, Reading MA, 1976
-
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest:
-
Introduction to Algorithms
The MIT Press, 2. Auflage, 2001
-
Volker Heun:
-
Grundlegende Algorithmen
Vieweg Verlag, 2000
(Hörerscheine für dieses Buch können bei Frau Sterl, Zi. S1430, abgeholt
werden.)
-
Donald E. Knuth:
-
The art of computer programming Vol. 3 : Sorting and searching
Addison-Wesley Publishing Company, Reading MA, 1973
-
Thomas Ottmann, Peter Widmayer:
-
Algorithmen und Datenstrukturen
Spektrum, Akad. Verlag, 3. Auflage, 1996
-
Christos H. Papadimitriou, Kenneth Steiglitz:
-
Combinatorial optimization : Algorithms and complexity
Dover Publications, 1998
-
Uwe Schöning:
-
Algorithmik
Spektrum, Akad. Verlag, 2001
|
|
|
Sprechstunde:
siehe hier
|
|
