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

Grundlegende Algorithmen (WS 03/04)

• Dozent:
  Dr. Jens Ernst

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

• Zeit und Ort:
  Do. 08:30 - 10:00, Physik HS 3
  Fr. 10:15 - 11:00, Raum MI 00.04.011
  

• Übung:
  2 SWS Übung zur Vorlesung
  Di 16:15 - 17:45, Raum MI 00.04.011
  Übungsleitung: Jan Griebsch
  

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

• Voraussetzungen:
  Elementare Grundkenntnisse in Informatik

• Empfehlenswert für:
  Grundkenntnisse im Bereich Algorithmen

• Inhalt:
  
  • 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ü Sortieren
    
  Weiterhin geplant:
  • Suchen
    Hashing, binäre Suchbäume, AVL-Bäume, Tries
  • Graphalgorithmen
    Traversieren von Graphen, Kürzeste-Wege-Algorithmen, minimale Spannbäume
  • Textalgorithmen
    Suchen in Texten, Vergleichen von Texten (Edit-Distanzen)
  • Arithmetische Probleme
    Euklidischer Algorithmus, schnelle Fourier-Transformation
  • Algorithmen zur Datenkompression
    Huffman-Encoding, Lempel-Ziv-Algorithmus
  • Heuristische und approximative Algorithmen

  Änderungen an dieser Planung werden noch bekanntgegeben

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

• Klausurtermine und Ergebnismitteilungen:
  
  Midterm: Freitag, 12.12.2003, 15:00-18:00, MI HS1
  • Midterm
  • Lösungsvorschlag
  
  Semestrale: Montag, 16.02.2004, 15:00, Raum MW2001; Die Bearbeitungszeit beträgt 90 Minuten.
  Klausureinsicht: Donnerstag, 26.02.04, 12:30, Raum 03.11.018
  
  Wiederholungsklausur: Mittwoch, 21.04.2004, 15:00 - 18:00, Hörsaal CH21010 (Hans-Fischer-Hörsaal, Chemie);
  Nur für zur Semestrale zugelassene Teilnehmer.
  Der Prüfungsstoff umfasst alle während des Semesters in der Vorlesung und in der Übung behandelten Inhalte.
  Das einzige zugelassene Hilfsmittel ist ein beidseitig handbeschriebenes Din A4-Blatt mit beliebigem Inhalt.
  Eventuelle Fragen zur Nachholklausur richten Sie bitte sämtlich an Herrn Jan Griebsch.
  Klausureinsicht: Freitag, 07.05.04, 10:00-10:30, Raum 03.11.018
  

• Skript:
  Kein Skript.

• Vorlesung 1 (Powerpoint)
• RAM-Beispielprogramm (2.Vorlesung, ps)
• RAM-Beispielprogramm (2.Vorlesung, pdf)
• Theoretical Computer Science Cheat Sheet (von Steve Seiden, ACM Press, NY)
• 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