|
Dozenten:
Prof. Dr. Ernst W. Mayr
Volker Heun
|
|
|
Bereich:
3 SWS Vorlesung
Pflichtvorlesung für Studenten des Aufbaustudiums
|
|
|
Zeit und Ort:
Di 12:15 - 13:00, Hörsaal 2750
Fr 09:15 - 10:45, Hörsaal N1070
Beginn: 2. Mai
|
|
|
Übung:
2 SWS Übung zur Vorlesung
Mi 8:30 - 10:00, Raum S2229
Übungsleitung:
Ulla Koppenhagen
Übungsschein:
Der Schein für die Vorlesung wird nach einer erfolgreichen
mündlichen Prüfung erteilt.
Termin ist voraussichtlich Dienstag, der 14.Oktober 1997,
vormittags.
Genaueres wird durch Aushang am schwarzen Brett vor dem Raum S2223
bekanntgegeben.
Um zur mündlichen Prüfung zugelassen zu werden, sind die
Übungen regelmäßig zu besuchen und dort mindestens
eine der gestellten Übungsaufgaben selbständig
vorzutragen.
|
|
|
Hörerkreis:
Studierende im Aufbaustudium Informatik
Studierende aller Studienrichtungen mit Interesse an effizienten
Algorithmen
|
|
|
Voraussetzungen:
Elementare Grundkenntnisse der Informatik
(wie z.B. die Vorlesungen Einführung in die Informatik I
und III)
|
|
|
Inhalt:
In dieser Vorlesung sollen an Hand der am meist benötigten
Algorithmen sowohl die allgemeinen Entwurfsmethodiken für
effiziente Algorithmen als auch die am meist verwendeten
Datenstrukturen vorgestellt werden. Im einzelnen wird sich die Vorlesung
wie folgt gliedern:
- Sortieralgorithmen
Bubble-Sort, Merge-Sort, Heap-Sort, Quick-Sort, Radix-Sort,
Median-Algorithmen, untere Schranken für Sortierprobleme
- Suchen
Hashing, Suchbäume, Suchen in Texten
- Elementare Graphalgorithmen
Traversieren von Graphen, Transitive Hülle, kürzeste
Wege Algorithmen, minimale Spannbäume
- Algorithmen für arithmetische Probleme
Multiplikation ganzer Zahlen, Matrizenmultiplikation,
Optimale Klammerung von Matrizenprodukten
|
|
|
Skript:
Das Skript ist leider nicht mehr verfügbar, da es als
Buch erschienen ist.
|
|
|
Literatur:
-
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman:
-
The Design and Analysis of Computer Algorithms
Addison-Wesley Publishing Company: Reading (MA), 1976
-
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest:
-
Introduction to Algorithms
The MIT Press, 1990
-
Thomas Ottmann, Peter Widmayer:
-
Algorithmen und Datenstrukturen
Bibliographisches Institut, Reihe Informatik, Band 70,1990
-
Donald E. Knuth
-
The art of computer programming Vol. 3 : Sorting and
searching
Addison-Wesley Publiching Company, Reading MA, 1973
-
Kurt Melhorn
-
Data structures and algoprithms 1 : Sorting and searching
EATCS Monographs on Theoretical Computer Science, Springer-Verlag,
1984
-
|
|
|
Sprechstunde:
siehe hier
|
|
