Fakultät für Informatik - Technische Universität München Lehrstuhl für Effiziente Algorithmen

Effiziente Algorithmen und Datenstrukturen I
(WS 04/05)

• Dozent:
  Dr. Sven Kosub

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

• Zeit und Ort:
  Montag, 8:30-10:00, Hörsaal MW 1801
  Freitag, 8:30-10:00, Hörsaal MW 1801
  

• Übung:
  2 SWS Übung zur Vorlesung
  Freitag, 15:00-16:30, Raum MI 00.04.011 (HS 2)
  Übungsleitung: Stefan Eckhardt
  

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

• Klausuren:
  Mittelklausur: Freitag, 17.12.2004, 15:00-17:00
  Endklausur: Freitag, 11.02.2005, 15:00-17:00

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

• Voraussetzungen:
  Stoff des Informatik Grundstudiums

• Empfehlenswert für:
  Grundkenntnisse im Bereich Algorithmen

• Inhalt:

  Behandelte Themen:

  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. Analyse von QuickSort
  2. Selektionsalgorithmen
  3. Höhere Heap-Strukturen: Binomial Queues
  4. Höhere Heap-Strukturen: Fibonacci-Heaps
  5. Höhere Heap-Strukturen: Soft Heaps
  6. Mengen und Union-Find-Strukturen
  5. Graphenalgorithmen
  1. Kürzeste Wege

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

• Skript:
  Siehe unter Skripten.
  (Aktuelle private Vorlesungsmitschrift: Benjamin Gufler)

• 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