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:20 - 11:50, Hörsaal MW0350
  Do 10:15 - 11:00, Hörsaal MI 00.06.011 (Hörsaal 3)

• Ü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

• Informationen:
  Elementare Begriffe und Schreibweisen
  Info-Blatt 1 (vom 16.10.2002)
  Info-Blatt 2 (vom 21.11.2002)
  Info-Blatt 3 (vom 16.01.2003)

• Inhalt:
  1. Grundlagen
     1. Beispiel: Fibonacci-Zahlen
        1. Rekrusive Berechnung
        2. Iterative Berechnung
     2. Grundlegende Konzepte
        1. Registermaschinen (RAM)
        2. Komplexitätsmaße
        3. Asymptotisches verhalten von Funktionen
  2. Sortieren
     1. Elementare Sortierverfahren
        1. Sortieren durch Auswahl
        2. Sortieren durch Einfügen
     2. Sortieren durch Mischen
        1. Rekursives Sortieren durch Mischen
        2. Iteratives Sortieren durch Mischen
     3. HeapSort
     4. QuickSort
     5. Untere Schranken für vergleichsbasiertes Sortieren
  3. Selektieren
     1. QuickSelect
     2. BFPRT-Algorithmus
  4. Suchen
     1. Ausnutzung von Sortierung
        1. Lineare Suche
        2. Binäre Suche
     2. Hashing
        1. Hashfunktionen
        2. Strategien zur Kollisionsauflösung
        3. Universelles Hashing
     3. Binäre Suchbäume
     4. AVL-Bäume
     5. (a,b)-Bäume
  5. Texte
     1. Der Knuth-Morris-Pratt-Algorithmus
     2. Der Boyer-Moore-Algorithmus
     3. Datenkompression
        1. Die Huffman-Kodierung
        2. Der Lempel-Ziv-Welch-Algorithmus

• Vorlesungszusammenfassung
  

• 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