Algorithmentheorie
- Typ:
- Kursvorlesung
- Veranstalter:
- PD Dr. Alois
Heinz, PD Dr. Sven
Schuierer
- Mitwirkung:
- Bernd
Zupancic
- Zeit und Ort:
- Mo 11-13, Mi 11-13 (14-täglich), Geb. 101, Raum
00-036
- Erste Vorlesung: Montag, 16.10.00, 11-13 Uhr
- Übungen:
- Mi 11-13 (14-täglich); Geb. 101, Raum 00-036 und
Geb. 51, Raum 03-026
- Erste Übung: Montag 30.10.2000. Geb. 101, Raum 00-036
(P. Stiegeler) und Geb. 101, Raum 00-026 (S. Kupferschmid)
- Danach finden die Übungen Mittwochs statt. Beginn
der Mittwochs-Übungen: 15.11.2000.
- Für die Rechnerübungen und zum Abspielen der
AOF-Vorträge steht der Linux-Pool Geb. 51 Raum 00-030
wöchentlich Montags und Mittwochs von 11- 17
Uhr zur Verfügung..
- Klausur:
- Die Teilnehmer der Klausur können ihre Klausur am
Freitag den 16.03.2001 um 10 Uhr im Raum 02-026 (Gebäude
051) einsehen. Das Ergebnis
der Klausur ist online abrufbar.
- Verlosung und Fragebogenaktion:
-
Herzlichen Dank an alle, die an der Fragebogenaktion teilgenommen
haben. Der Gewinner der Verlosung des Buchgutscheins im
Wert von 50 DM steht fest: M. Sumner. Herzlichen Glückwunsch!
-
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. xvii+696
Seiten, 3. Auflage, Spektrum Verlag, Heidelberg, 1996
erforderlich.
Die Vorlesung wird durch Übungen begleitet.
Literatur zur Veranstaltung
- T. Corman, C. Leisserson, R. Rivest. Introduction to Algorithms.
MIT Press, 1990.
- Th. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen. xvii+696
Seiten, 3. Auflage, Spektrum Verlag, Heidelberg, 1996
- Th. Ottmann: Prinzipien des Algorithmenentwurfs. Multimediales Buch
mit Beiträgen von A. Brüggemann-Klein, J. Eckerle, A. Heinz, R. Klein,
K. Mehlhorn,Th. Roos, S. Schuierer, P. Widmayer, Spektrum Akademischer
Verlag, Bd. 244, Dezember 1997
- Aufgezeichnete AOF-Vorträge der Vorlesung
WS 1999/2000. Erhältlich als CDROM bei J. Lienhard
(Geb. 82, Raum 00-030, Zeit: 9-11 Uhr). Die Vorträge
können auch online
im Linux-Pool angeschaut werden.
|
