 Hinweise
zur Technik
AOF-FAQ
Übersicht
der Lehrveranstaltung
Informationen
zur Lehrveranstaltung
Unterlagen
zur Vorlesung
Unterlagen
zu den Übungen
Literatur
zur Vorlesung (Handapparat)
Diskussionsforum
Algorithmentheorie
|
Algorithmentheorie
- Typ:
- Kursvorlesung
- Veranstalter:
- Prof. Dr. Thomas Ottmann,
PD Dr. Alois Heinz
- Mitwirkung:
- Dr. Stefan
Edelkamp
- Zeit und Ort:
- Mo 15:30-17:00,
Do 15:30-17:00 (14-täglich), Geb. 101, Raum 00-036
-
- Erste Vorlesung: Montag, 18.10.99, 15:30-17:00 Uhr
- Übungen:
- Do 15:30-17:00 (14-täglich), Geb. 101, Raum 00-036
- Klausur:
- Fr, 17.02.00, 15.30-17.30 Uhr
In dieser Vorlesung werden Algorithmen und Datenstrukturen behandelt,
die in der Vorlesung Informatik II im Grundstudium überhaupt nicht oder
nicht mit der erforderlichen Tiefe behandelt wurden. Dazu gehören u. a.:
- Datenstrukturen: Skip-Listen, randomisierte Suchbäume, Splay
Trees, erweiterte Suchbäume, Tries.
- Polynome und die schnelle Fouriertransformation.
- Algorithmen zur Zeichenkettenverarbeitung (Knuth Morris Pratt,
Boyer Moore u. a.).
- Verschlüsselung und Kodierung von Texten.
- Approximative Verfahren zur Lösung NP-harter Probleme.
Ferner werden die zum Entwurf einer breiten Palette von Algorithmen
benötigten Entwurfsprinzipien herausgearbeitet und an Beispielen
erläutert. Das sind das Divide-and-Conquer-Prinzip, das Greedy-Prinzip,
dynamisches Programmieren, amortisierte Analyse u. a.
Die Vorlesung gehört zum Pflichtkanon der Lehrveranstaltungen für
Studenten des Diplomstudiengangs Informatik im Hauptstudium und eignet
sich auch als weiterführende Lehrveranstaltung für Studenten mit
Nebenfach Informatik und für Lehramtsbewerber.
Zum Verständnis der Vorlesung sind Kenntnisse auf dem Gebiet
Algorithmen und Datenstrukturen im Umfang der Kapitel 1 bis 6 des
Buches
Th. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen,
Bibliographisches Institut, Mannheim, 1993
erforderlich.
Die Vorlesung wird durch Übungen begleitet.
Literatur zur Veranstaltung
- T. Corman, C. Leisserson, R. Rivest.
Introduction to Algorithms. MIT Press, 1990.
|