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

Grundlagen: Algorithmen und Datenstrukturen (SS 07)

• Dozent:
  Prof. Dr. Christian Scheideler

  Sprechstunde: Do 16-17 Uhr, FMI 03.09.044.
  

• Modul: IN0007

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

• Zeit und Ort:
  Dienstag, 11:15-12:45, Hörsaal MW 1801
  Mittwoch, 13:15-14:00, Hörsaal MI 00.02.001 (Hörsaal 1)
  

• Übung:
  1 SWS Übung zur Vorlesung (in Tutorgruppen)
  Übungsleitung: Sylvia Pott, Hanjo Täubig

• Klausuren
  
  • Mittelklausur: Di 29.05. 11:15 Uhr
  • Endklausur: Di 24.07. 14:00 Uhr (Nachnamen mit A-Li in MW 0001, Lo-Z in MW 2001)
  • Nachholklausur: Di 09.10. 14:00-16:00 Uhr in MW 0001 (geändert!)
    (Wer für Mittel-/Endklausur nicht zugelassen war, muss bis 15.9.07 das Wiederholungsblatt lösen und dabei mindestens 50% der Punkte erreichen.)

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

• 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: (kann nur uni-intern oder über VPN-Client geladen werden)
  Der Inhalt der Vorlesung orientiert sich an folgendem Manuskript:

  K. Mehlhorn, P. Sanders: Algorithms and Data Structures - The Basic Toolbox

  Kreiszeichnen: Kreise.pdf

• Folien: (können nur uni-intern oder über VPN-Client geladen werden)
  
  • Kapitel 2.6-2.7 in ppt und pdf (Stand vom 23. Mai)
  • Kapitel 3.1-3.2 in ppt und pdf (Stand vom 9. Mai)
  • Kapitel 3.3-3.5 in ppt und pdf (Stand vom 21. Mai)
  • Kapitel 4 in ppt und pdf (Stand vom 17. Juli)
  • Kapitel 5 in ppt und pdf (Stand vom 17. Juli)
  • Kapitel 6 in ppt und pdf (Stand vom 17. Juli)
  • Kapitel 7 in ppt und pdf (Stand vom 17. Juli)
  • Kapitel 8 in ppt und pdf (Stand vom 17. Juli)
  • Kapitel 9 in ppt und pdf (Stand vom 17. Juli)
  • Kapitel 10 in ppt und pdf (Stand vom 17. Juli)
  • Kapitel 11 in ppt und pdf (Stand vom 17. Juli)
  • Kapitel 12 in ppt und pdf (Stand vom 17. Juli)

• Literatur:
  Vertiefendes und ergänzendes Material zur Vorlesung findet sich in:
  • 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.

  • 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