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 (SS 99)


* Dozent:
Prof. Dr. Ernst W. Mayr
Volker Heun

* Bereich:
3+2 SWS Vorlesung im Aufbaustudium Informatik
Pflichtvorlesung

* Zeit und Ort:
Mi 8:30 - 10:00, Hörsaal 1260 (nur am 5.5)
Di 8:30 - 10:00, Hörsaal 0220 (ab 11.5.)
Mi 12h c.t. - 13:00, Hörsaal 2760
Beginn: 5. Mai
Ende: 28. Juli

* Übung:
2 SWS Übung zur Vorlesung
Mi 15h c.t. - 16:45, Raum S2225
Übungsleitung: Michal Mnuk
Übungsschein: Einen Schein erhält, wer erfolgreich an der Semestralprüfung teilnimmt. Voraussetzung für die Teilnahme ist das Vortragen einer Lösung der gestellten Aufgaben in der Übung.

!NEW! Die Scheinvergabe erfolgt durch eine mündliche Prüfung voraussichtlich im Oktober.
Zur besseren Planung und Koordinierung werden alle Teilnehmer gebeten, sich für die Semestralprüfung anzumelden. Hierfür genügt eine Email an mnuk@in.tum.de mit folgende Informationen:

  • Name, Vorname
  • Matrikelnummer
  • Geburtsdatum
  • Email-Adresse
* Hörerkreis:
Studierende im Aufbaustudium Informatik

* Voraussetzungen:
Elementare Grundkenntnisse in Informatik

* Empfehlenswert für:
Grundkenntnisse im Bereich Algorithmen

* Inhalt:
  • Grundlagen
    Maschinenmodelle, Komplexitätsmaße
  • Sortieren
    Merge-Sort, Heap-Sort, Quick-Sort, Bucket-Sort-Sort, untere Schranken für Sortierprobleme
  • Selektieren
    BFPRT-Algorithmus, Randomisierter Median-Algorithmus
  • Suchen
    Hashing, Suchbäume, Suchen in Texten
  • Elementare Graphalgorithmen
    Traversieren von Graphen, Transitive Hülle, kürzeste Wege Algorithmen, minimale Spannbäume
  • Arithmetische Probleme
    Euklidischer Algorithmus, Multiplikation ganzer Zahlen, ...

* 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


mayr@informatik.tu-muenchen.de