LEA
Fakultät für Informatik der Technischen Universität München
Lehrstuhl für Effiziente Algorithmen
Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München
english

Grundlegende Algorithmen (SS97)


* 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


heun@informatik.tu-muenchen.de