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

Grundlegende Algorithmen (WS 05/06)

• Dozent:
  Dr. Jens Ernst

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

• Zeit und Ort:
  Mi. 11:00 - 11:45, Hörsaal MW 1801
  Fr. 12:00 - 13:30, Hörsaal MI HS 2
  

• Übung:
  2 SWS Übung zur Vorlesung
  Übungsleitung: Johannes Nowak
  

• Hörerkreis:
  Studierende im Bachelorstudium Informatik
  

• Voraussetzungen:
  Elementare Grundkenntnisse in Informatik

• Empfehlenswert für:
  Grundkenntnisse im Bereich Algorithmen, Bioinformatik

• Informationen:
  

  Informationsblatt (pdf)

• Inhalt (vorläufige Planung):
  
  • Einführung
    Einführendes Beispiel: Fibonacci-Zahlen
    Das Modell der Registermaschine (RAM)
    Zeit- und Platzkomplexität
    Landau-Symbole
  • Sortieralgorithmen
    Selection Sort
    Insertion Sort
    Merge Sort
    Heap Sort
    Quick Sort
    Untere Schranken für Sortieren
    
  • Suchen
    Lineare, binäre, exponentielle Suche
    Binäre Suchbäume
    AVL-Bäume
    (a,b)-Bäume
    
  • Graphalgorithmen
    Begriffe der Graphentheorie
    Speicherung von Graphen
    Traversieren von Graphen
    Kürzeste-Wege-Algorithmen
    
  • Textalgorithmen
    Suchen in Texten
    Vergleichen von Texten bzw. Sequence Alignment
    Weiterhin geplant:
  • Algorithmen zur Datenkompression
    Huffman-Encoding, Lempel-Ziv-Algorithmus, Kompression von Bilddaten

  Änderungen an dieser Planung werden noch bekanntgegeben.

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

• Klausurtermine und Ergebnismitteilungen:
  
  Midterm/Mittelklausur: Freitag, 09.12.2005 zum Termin der Vorlesung, d.h. 12:00 - 13:30 im Hörsaal HS2
  (Hilfsmittel: Ein eigenhändig, per Hand, beidseitig beschriebenes Din A4-Blatt beliebigen Inhalts)
  
  Final/Endklausur: Freitag, 10.02.2006 zum Termin der Vorlesung, d.h. 12:00 - 13:30 im Hörsaal HS2
  (Hilfsmittel: Ein eigenhändig, per Hand, beidseitig beschriebenes Din A4-Blatt beliebigen Inhalts)
  Klausureinsicht: Mittwoch, 01.03.2006, 11:00, Raum MI 03.09.043 (I14)
  
  Wiederholungsklausur: Zur Teilnahme melden Sie sich bitte bis zum 20.03.2006 bei der Übungsleitung an.
  Termin und Form der Prüfung (mündlich/schriftlich) der Prüfung werden nach Ablauf der Anmeldefrist an
  dieser Stelle bekanntgegeben.
  
  
• Skript:
  Kein Skript, ausgenommen:
  1. Vorlesung (ppt)
  KMP-Algorithmus aus der vorletzten Vorlesung (pdf)

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

  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