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

Grundlegende Algorithmen (WS 02/03)

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

• Bereich:
  3+2 SWS Vorlesung im Bachelorstudium Informatik (Pflichtvorlesung)
  3+2 SWS Vorlesung im Aufbaustudium Informatik (Pflichtvorlesung)
  

• Zeit und Ort:
  Mi 10:15 - 11:45, Hörsaal MW0350
  Do 10:15 - 11:00, Hörsaal MI 00.06.011 (Hörsaal 3) (Achtung: Raumänderung!)

• Übung:
  2 SWS Übung zur Vorlesung
  Di 14:15 - 15:45, Hörsaal PH HS1
  Übungsleitung: Thomas Bayer
  

• Hörerkreis:
  Studierende im Bachelorstudium Informatik
  Studierende im Aufbaustudium Informatik
  

• Voraussetzungen:
  Elementare Grundkenntnisse in Informatik

• Empfehlenswert für:
  Grundkenntnisse im Bereich Algorithmen

• Informationene:
  Info-Blatt 1 (vom 16.10.2002)

• Inhalt (geplant):
  
  • Grundlagen
    Maschinenmodelle, Komplexitätsmaße, Asymptotik
  • Sortieren
    Insertion-Sort, Merge-Sort, Heap-Sort, Quick-Sort, untere Schranken für Sortierprobleme, Bucket-Sort
  • Selektieren
    Quick-Select, BFPRT
  • Suchen
    Hashing, binäre Suchbäume, AVL-Bäume, Tries
  • Graphalgorithmen
    Traversieren von Graphen, Kürzeste-Wege-Algorithmen, minimale Spannbäume
  • Textalgorithmen
    Knuth-Morris-Pratt, Boyer-Moore, Tries für Texte, Datenkompression
  • Arithmetische Probleme
    Euklidischer Algorithmus, schnelle Fourier-Transformation
  • Heuristische und approximative Algorithmen
  • Algorithmen für das Erfüllbarkeitsproblem

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

• Skript:
  Kein Skript.

• Literatur:
  Die Vorlesung folgt in wesentlichen Teilen dem Buch:
  • Volker Heun.
    Grundlegende Algorithmen: Einführung in den Entwurf und die Analyse effizienter Algorithmen.
    Vieweg, Braunschweig-Wiesbaden, 2000.

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

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

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

• Sprechstunde:
  nach Vereinbarung