Fakultät für Informatik der Technischen Universität München Lehrstuhl für Effiziente Algorithmen

Effiziente Algorithmen und Datenstrukturen I
(WS 02/03)

• Dozent:
  Prof. Dr. Ernst W. Mayr

• Bereich:
  4+2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
  Wahlpflichtvorlesung im Gebiet Algorithmen

• Zeit und Ort:
  

  Di 8:30 - 10:00, Hörsaal PH HS1
  Fr 11:15 - 12:45, Hörsaal PH HS1

• Übung:
  2 SWS Übung zur Vorlesung
  Mo 15h s.t. - 17:00, Hörsaal PH HS1
  Übungsleitung: Klaus Holzapfel
  

• Schein:
  Einen Übungsschein erhält, wer
  • mindestens 40% der Punkte zu den Hausaufgaben erreicht und
  • erfolgreich an den Klausuren (Mittel- und Endklausur) teilnimmt.

• Klausur:
  Es finden zwei Klausuren (Midterm und Final) statt:

  Termine:		Midterm:	Mo 9. Dez 2002	15:00 Uhr
  		Final:	Mo 3. Feb 2003	15:00 Uhr
  Gewichtung:		50% Midterm, 50% Final
  Hilfsmittel:		Ein DIN A4 Blatt, handgeschrieben (Original keine Kopien)

• Hörerkreis:
  Studierende im Hauptstudium der Informatik
  Studierende mit Nebenfach Informatik

• Voraussetzungen:
  Stoff des Informatik Grundstudiums

• Empfehlenswert für:
  Grundkenntnisse im Bereich Algorithmen

• Inhalt:
  In der Vorlesung wurden folgende Themen behandelt (ausführliche Gliederung)
  1. Einleitung
     1. Kombinatorische Probleme
     2. Maschinenmodelle
     3. Komplexitätsmaße
     4. Rekursionsgleichungen (in Übung)
  2. Höhere Datenstrukturen
     1. Grundlegende Operationen
     2. Suchbäume, höhenbalancierte Bäume
     3. Prioritätswarteschlangen
     4. Union-Find-Strukturen
  3. Grundlegende Algorithmen
     1. Selektion und Sortieren
     2. Minimale Spannbäume
     3. Kürzeste Wege/Pfade
     4. Transitive Hülle
     5. Matchings in Graphen

• Weiterführende bzw. verwandte Vorlesungen:
  Effiziente Algorithmen und Datenstrukturen II
  Randomisierte Algorithmen

• Skript:
  Siehe unter Skripten.

• 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 and Charles E. Leiserson and R.L. Rivest:

  Introduction to algorithms
  McGraw-Hill, 1990

  Donald E. Knuth:

  The art of computer programming Vol. 3 : Sorting and searching
  Addison-Wesley Publishing Company, Reading MA, 1973

  Kurt Mehlhorn:

  Data structures and algorithms 1 : Sorting and searching
  EATCS Monographs on Theoretical Computer Science, Springer-Verlag, Berlin - Heidelberg - New York - London - Paris - Tokyo - Hong Kong, 1984

  Kurt Mehlhorn:

  Data structures and algorithms 2 : Graph algorithms and NP-Completeness
  EATCS Monographs on Theoretical Computer Science, Springer-Verlag, Berlin - Heidelberg - New York - London - Paris - Tokyo - Hong Kong, 1984

  T. Ottmann and P. Widmayer:

  Algorithmen und Datenstrukturen
  B.I. Wissenschaftsverlag, Mannheim, 1990

  Christos H. Papadimitriou, Kenneth Steiglitz:

  Combinatorial optimization : Algorithms and complexity
  Prentice-Hall, Englewood Cliffs, NJ, 1982

• Sprechstunde:
  siehe hier