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

Grundlagen: Algorithmen und Datenstrukturen (SS 06)

Wiederholungsklausur am 11.10.2006, 9:30-11:30, MW 2001
(Informationen zu Zulassung und Klausurstoff siehe Info-Blatt 4)

• Dozent:
  Dr. Sven Kosub

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

• Zeit und Ort:
  Dienstag, 11:30-13:00, Hörsaal MW 1801
  Mittwoch, 13:10-13:55, Hörsaal MI 00.02.001 (Hörsaal 1)
  

• Übung:
  1 SWS Übung zur Vorlesung (in Tutorgruppen)
  Übungsleitung: Matthias Baumgart
  

• Hörerkreis:
  Studierende im Bachelorstudium Informatik
  Studierende im Bachelorstudium Bioinformatik
  Studierende im Bachelorstudium Wirtschaftsinformatik
  

• ECTS: 5 Punkte

• Voraussetzungen:
  Elementare Grundkenntnisse in Informatik

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

• Informationen:
  Elementare Begriffe und Schreibweisen
  Info-Blatt 1 (vom 25.04.2006)
  Info-Blatt 2 (vom 24.05.2006; geändert am 30.05.06)
  Info-Blatt 3 (vom 11.07.2006)
  Info-Blatt 4 (vom 14.09.2006; geändert am 9.10.06)

• Inhalt:
  1. Konzepte und Methoden der Algorithmenanalyse
     1. Entwurfsprinzipien für Algorithmen
     2. Beurteilungsmethoden für Algorithmen
        1. Experimentelle Analyse
        2. Theoretische oder asymptotische Analyse
     3. Asymptotisches Verhalten von Funktionen
     4. Komplexitätsmaße und -arten
        1. Was ist die Eingabegröße?
        2. Was ist die Laufzeit?
        3. Welche Art Beziehung zwischen Eingabe und Laufzeit?
     5. Amortisationsanalyse
     1. Aggregatmethode
     2. Bankkontomethode
     3. Potenzialmethode
     4. Dynamische Arrays

  2. Elementare Datenstrukturen
     1. Stacks und Queues
     2. Vektoren, Listen und Sequenzen
     3. Bäume
     1. Definitionen
     2. Baumtraversierung
     3. Implementierungen von Bäumen
     4. Priority Queues und Heaps
     1. Definitionen
     2. Sortieren mit Priority Queues
     3. PQ-Implementierung mit Heaps
     4. Bottom-Up Heap-Konstruktion
     5. Wörterbücher und Hashing
     1. Definitionen
     2. Hashfunktion
     3. Strategien zur Kollisionsauflösung
     4. Universelles Hashing

  3. Suchbäume
     1. Binäre Suchbäume
     2. AVL-Bäume
     3. (a,b)-Bäume

  4. Sortieralgorithmen
     1. MergeSort
     2. Eine untere Schranke für vergleichsbasiertes Sortieren

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

• Skript:
  Kein Skript.

• Literatur:
  Die Vorlesung folgt in weiten Teilen dem Buch:
  • Michael T. Goodrich, Roberto Tamassia.
    Algorithm Design: Foundations, Analysis, and Internet Examples.
    John Wiley & Sons, Inc., Hoboken, NJ, 2002.

  • Volker Heun.
    Grundlegende Algorithmen: Einführung in den Entwurf und die Analyse effizienter Algorithmen.
    2. Auflage, 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.

  • Jon Kleinberg, Eva Tardos.
    Algorithm Design.
    Pearson Education, Boston, MA, 2005.

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

  • Robert Sedgewick.
    Algorithmen in Java. Teil 1-4.
    3., überarbeitete Auflage, Pearson Education, München, 2003.

  Zur Diskussion von Entwurfsprinzipien implementierbarer Algorithmen:

  • Karsten Weihe.
    A Software Engineering Perspective on Algorithmics.
    ACM Computing Surveys, 33(1), 89-134, 2001.

• Sprechstunde:
  nach Vereinbarung