|
Dozent:
Prof. Dr. Sami Khuri
|
|
|
Bereich:
4+2 SWS Vorlesung im
Bereich Informatik III (Theoretische Informatik)
Wahlpflichtvorlesung
im Gebiet Algorithmen
|
|
|
Zeit und Ort:
Di 10:05 - 11:35, Hörsaal 1100
Do 10h c.t. - 12:00, Hörsaal 1100
|
|
|
Prüfung:
Klausur: am 22. Februar, 15:00 bis 17:00, Raum S2229
Arbeitszeit: 120 Minuten
Sprache: Fragen auf englisch, Beantwortung auf deutsch oder english möglich
Erlaubte Hilfsmittel:
ausschließlich ein Blatt DIN A4, auf beiden Seiten beliebig beschrieben,
sowie ein normaler (nicht programmierbarer) Taschenrechner
|
|
|
Übung:
2 SWS Übung zur Vorlesung
Mi 12:30 - 14:00, Hörsaal N1095
Übungsleitung: Thomas Erlebach
Ü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
Die Vorlesung wird auf Englisch gehalten!
|
|
|
Empfehlenswert für:
Grundkenntnisse im Bereich Algorithmen
|
|
|
Inhalt:
Wichtig: Die Vorlesung wird auf Englisch gehalten.
In der Vorlesung werden voraussichtlich folgende Themen
behandet:
- Übersicht
- Wiederholung Maschinenmodelle
- Grundbegriffe
- Komplexitätsmaße
- Höhere Datenstrukturen
- (a,b)-Bäume
- Rot-Schwarz-Bäume
- Wiederholung Binomial heaps
- Fibonacci heaps
- amortisierte Komplexität
- Selbstorganisierende Listen
- Splay trees
- loglogN priority queue
- Selektion
- Selektionsalgorithmus nach BFPRT
- Schönhage-Paterson-Pippenger Median Algorithmus
- 1.5 n untere Schranke für Median
- Minimale Spannbäume
- Grundlagen für Minimale Spannbäume
- Kruskal's Algorithmus
- zwei Algorithmen für MST mit Fibonacci-Heaps
einschl. Analyse
- Kürzeste Pfade
- Grundlagen
- Dijkstra's Algorithmus
- Floyd's Algorithmus für das All-Pairs-Problem
- Min-Plus Matrix-Produkt
- Boolesche Matrixmultiplikation und
Transitive Hülle
- 4-Russen-Algorithmus
- Kürzeste Pfade in allgemeinen Graphen
- All-pairs-shortest-paths in allgemeinen Graphen
- Average-case-Analyse für Transitive Hülle
(Schnorr)
- Zusammenhang von Graphen
- Grundlagen, einfacher Zusammenhang
- Zweifach-Zusammenhangskomponenten
- Starke Zusammenhangskomponenten
- Zweifach-Zusammenhangskomponenten ohne DFS
- Planare Graphen
- Grundlagen
- Charakterisierung planarer Graphen; Rekursive
Charakterisierung der Planarität;
Satz von Kuratowski
- Hopcroft/Tarjan Planaritätstest
- sqr(n)-Separatoren für planare Graphen
|
|
|
Weiterführende bzw. verwandte Vorlesungen:
Effiziente Algorithmen und Datenstrukturen II
|
|
|
Skript:
Eine Vorlesungsmitschrift wird während des Semesters von
Christian Osendorfer erstellt und ist
hier erhältlich.
Skripten aus früheren Semestern gibt es 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
-
Donald E. Knuth:
-
The art of computer programming Vol. 3 : Sorting and searching
Addison-Wesley Publishing Company, Reading MA, 1973
-
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
|
|
|
Sprechstunde:
siehe hier
|
