 Algorithmen-Animationen
Artikel
Folien
Programme
Themen
und Termine
Übungsblätter
|
Algorithmentheorie
- Typ:
- Kursvorlesung
- Veranstalter:
- PD Dr. Alois Heinz, PD Dr.
Sven Schuierer
- Zeit und Ort:
- Mi 9:50-11:20 (geändert!), Fr 9-11 (14-tägig), Geb. 051, Raum 03-026
-
- Erste Vorlesung: Freitag, 16. 10. 98, 9-11 Uhr
- Übungen:
- Fr 9-11 (14-tägig), Geb. 051, Raum 03-026
- Klausur:
- Fr, 12. 2. 99, 9:00 (s.t.) - 11:00 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.
|