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

Effiziente Algorithmen und Datenstrukturen I
(WS 03/04)

Ergebnisse der Klausur hängen im Glaskasten am Lehrstuhl

Klausureinsicht: Freitag, 20.02.2004, 10.00-11.00 Uhr in Raum MI 03.09.011

• Dozent:
  Prof. Dr. Ernst W. Mayr,
  Dr. Sven Kosub

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

• Zeit und Ort:
  Dienstag, 8:15-9:45, Hörsaal CH 21010 (Hans-Fischer-Hörsaal)
  Freitag, 13:00-15:00, Hörsaal MW 0001 (Gustav-Niemann-Hörsaal)

• Übung:
  2 SWS Übung zur Vorlesung
  Montags, 16:00 - 17:30 Uhr, Raum MI 00.04.011 (HS 2)
  Dienstags, 14:15 - 15:45 Uhr, Raum MI 00.13.009A (Multimedia-Hörsaal)
  Übungsleitung: Moritz G. Maaß, Stefan Eckhardt
  

• Schein:
  Einen Übungsschein erhält, wer erfolgreich an den Klausuren (Mittel- und Endklausur) teilnimmt.

• Klausuren:
  Mittelklausur: Mittwoch, 17.12.2003, 17:00-19:00, MI 00.02.001 (Hörsaal 1)
  Endklausur: Mittwoch, 11.02.2003, 18:00-20:00, MI 00.02.001 (Hörsaal 1)

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

• Voraussetzungen:
  Stoff des Informatik Grundstudiums

• Empfehlenswert für:
  Grundkenntnisse im Bereich Algorithmen

• Inhalt:
  1. Konzepte und Methoden der Algorithmenanalyse
     1. Theorie und Experiment
     2. Komplexitätsmaße und Komplexitätsarten
     3. Amortisationsanalyse
     4. Analyse randomisierter Algorithmen

  2. Grundlegende Datenstrukturen
     1. Stacks und Queues
     2. Bäume
     3. Priority Queues und Heaps
     4. Wörterbücher und Hashing

  3. Suchbäume und Skiplisten
     1. Binäre Suchbäume
     2. AVL-Bäume
     3. (a,b)-Bäume
     4. Splay Trees
     5. Skiplisten

  4. Sortieren und Selektieren in Mengen
     1. MergeSort
     2. Untere Schranken für vergleichsbasiertes Sortieren
     3. Binomial Queues und Fibonacci-Heaps
     4. Mengen und Union-Find-Strukturen
     5. Selektionsalgorithmen

  5. Graphenalgorithmen
     1. Datenstrukturen für Graphen
     2. Graphentraversierung
     3. Erreichbarkeitsprobleme
     4. Kürzeste Pfade
     5. Minimale Spannbäume

• Weiterführende bzw. verwandte Vorlesungen:
  Effiziente Algorithmen und Datenstrukturen II
  Internet-Algorithmik

• Skript:
  Siehe unter Skripten.

• Literatur:
  Die Vorlesung folgt in wesentlichen Teilen dem Buch:
  • Michael T. Goodrich, Roberto Tamassia.
    Algorithm Design: Foundations, Analysis, and Internet Examples.
    John Wiley & Sons, Inc., 2002.

  Ergänzendes und vertiefendes Material zur Vorlesung findet sich in:
  • Thomas H. Cormen, Charles E. Leiserson, Ron L. Rivest, Clifford Stein.
    Introduction to Algorithms.
    2. Auflage, The MIT Press, Cambridge, MA, 2001.

  • Volker Heun.
    Grundlegende Algorithmen: Einführung in den Entwurf und die Analyse effizienter Algorithmen.
    2. Auflage, Vieweg, Braunschweig-Wiesbaden, 2003.

  • Donald E. Knuth.
    The Art of Computer Programming: Fundamental Algorithms.
    3. Auflage, Addison-Wesley, Reading, MA, 1997.

  • Donald E. Knuth.
    The Art of Computer Programming: Sorting and Searching.
    2. Auflage, Addison-Wesley, Reading, MA, 1997.

  • Uwe Schöning.
    Algorithmik.
    Spektrum Akademischer Verlag, Heidelberg, 2001.

  • Robert Sedgewick.
    Algorithmen.
    2. Auflage, Pearson Education, München, 2002.

• Sprechstunde:
  siehe hier