Vorlesung: Fortgeschrittene Algorithmen und Datenstrukturen
Koordinaten
mittwochs, 9.15 - 10.45, Hörsaal 7
Aktuelles
Programmier-Aufgaben zu Sortiernetzen.
Scheine
Sie sollten sich mit den Aufgaben beschäftigen
und Ihre Überlegungen jeweils zur nächsten Vorlesung mitbringen.
Normalerweise beginne ich die Vorlesung mit einer Wiederholung,
während der wir auch über Lösungen der Aufgaben sprechen.
Von Zeit zu Zeit sollten Sie Ihre Lösungen schriftlich ausarbeiten
und zur Korrektur abgeben, oder während der Aufgabenbesprechung
einen Kurzvortrag halten.
Für wenigstens eine solche Leistung erhalten Sie am Semesterende
einen Schein.
Optimum Sorting
Abschnitten 5.3 von Knuth: The Art Of Computer Programming, Band 3.
Forschungsaufgaben:
- Sortiere 13 Elemente mit 33 Vergleichen.
- 22 Elemente lassen sich nicht mit 70 Vergleichen sortieren.
Übungsaufgaben: Finde den Median von x Elementen mit y Vergleichen:
- x = 5, y = 6
- x = 7, y = 10
- x = 9, y = 14
Programme zum Rechnen mit Halbordnungen.
Zu Suchbäumen
In der Vorlesung vom 1. 12. haben wir einen
Gastvortrag:
Herr Dr. Ralf Hinze
(Uni Bonn) spricht über die Konstruktion von Rot-Schwarz-Bäumen.
Weitere Aufgaben zu Suchbäumen und Heaps.
Über den Zusammenhang von (a,b)- und Rot-Schwarz-Bäumen
biete ich ein
Diplom-Thema an.
Herr Ch. Biemann wies mich darauf hin,
daß der in der Vorlesung behauptete Zusammenhang
zwischen AVL- und (2,3)-Bäumen nicht immer besteht.
Siehe dazu diesen Text.
Aufgabe: Mit (2,4)-Bäumen klappt es aber.
Implementierungen von Finite Maps
finden Sie hier.
Aufgaben zu Priority Queues
sind hier.
Material
Es gibt bereits genügend
- gut ausgearbeitete Lehrbücher und Skripte sowie
- Übersichtsdarstellungen aktueller Forschungen,
deswegen beschränkt sich
der hier vorliegende Begleittext zur Vorlesung
auf mehr oder weniger ausführlich kommentierte Verweise auf die Literatur,
gewürzt mit passenden Übungsaufgaben.
Weiterhin gebe ich einige
Haskell-Programme an.
Sie sollten diese Texte (obwohl sie meist ausführbar sind)
weniger als Implementierung denn als Spezifikation
von Algorithmen verstehen. Sie müssen überhaupt nicht
Haskell programmieren können, aber Sie sollten üben,
die Programme als Gleichungssysteme zu lesen,
und diese auch korrekt umzuformen.
Wenns Sies denn doch mal probieren wollen:
am einfachsten laufen die Sachen unter dem Haskell-Interpreter
hugs.
Beispiel:
$ hugs -u Skew.hs
> build [9,1,8,2,7,3] :: Bin Int
http://www.informatik.uni-leipzig.de/~joe/
mailto:joe@informatik.uni-leipzig.de