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

Effiziente Algorithmen und Datenstrukturen II (SS 06)

• Dozent:
  Prof. Dr. Christian Scheideler

• Bereich:
  4+2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
  Vertiefende Vorlesung im Gebiet Algorithmen

• Zeit und Ort:
  Mittwoch, 14:15-15:45, Hörsaal MI HS 3
  Freitag, 12:00-13:30, Hörsaal MI HS 2

• Übung:
  2 SWS Übung zur Vorlesung
  Übungsleitung: N.N.

• Schein:
  Einen Schein erhält, wer mindestens 40% der Punkte zu den Hausaufgaben erreicht und erfolgreich an der mündlichen Prüfung teilnimmt.

• Hörerkreis:
  Studierende im Hauptstudium der Informatik
  Studierende mit Nebenfach Informatik

• Voraussetzungen:
  Stoff des Informatik Grundstudiums
  Vorlesung Effiziente Algorithmen und Datenstrukturen I vorteilhaft, aber nicht notwendig.

• Empfehlenswert für:
  Erweiterte Kenntnisse im Bereich Algorithmen

• Inhalt:
  1. Algorithmen für Flüsse und Matchings
  1. Flüsse und Schnitte
  2. Maximaler Fluss
  1. Max-Flow Min-Cut Theorem
  2. Algorithmus von Ford und Fulkerson
  3. Algorithmus von Edmonds und Karp
  4. Algorithmus von Goldberg
  3. Maximale Matchings
  4. Flüsse mit minimalen Kosten
  2. String und Pattern Matching
  1. Naives Matching
  2. Matching von Worten
  3. Matching regulärer Ausdrücke
  3. Textkompression
  1. Shannon-Fano Codes
  2. Huffman Codes
  3. Arithmetische Codes
  4. Lempel-Ziv Codes
  4. Lineare Optimierung
  1. Standardformulierungen
  2. Dualitätssatz der linearen Programmierung
  3. Simplex-Algorithmus
  4. Polynomialzeit-Algorithmen
  5. Approximationsalgorithmen
  1. Randomisierte Approximationsalgorithmen
  2. Lineare Optimierung und Approximationsalgorithmen

• Weiterführende bzw. verwandte Vorlesungen:
  Internet-Algorithmik
  

• Skript:
  
  • Algorithmen für maximale Flüsse (in Postscript und pdf)
    (aus dem Skript "Algorithms" von Sariel Har-Peled)
  • Sting- und Pattern-Matching (in Postscript und pdf)
    (basierend auf dem Buch "Algorithms on Strings, Trees, and Sequences" von Dan Gusfield und dem Skript "Information Retrieval" von Peter Becker)
  • Datenkomprimierung (in Postscript und pdf)
    (teilweise basierend auf dem Skript "Data Compression" von Peter Bro Miltersen)
  • Lineare Optimierung (in Postscript und pdf)
    (basierend auf dem Skript "Optimierung und OR" von Michael Jünger)
  • Techniken für randomisierte Approximationsalgorithmen (in Postscript und pdf)
    (aus dem Skript "Approximationsalgorithmen" von Rolf Wanka)
  • Lineare Optimierung und Approximationsalgorithmen (in Postscript und pdf)
    (aus dem Skript "Approximationsalgorithmen" von Rolf Wanka)
  • Online Algorithmen (in pdf)
    (aus dem Skript "Online Algorithmen" von Susanne Albers)

• Literatur:
  Die Inhalte der Vorlesung werden in wesentlichen Teilen durch folgende Bücher und Artikel abgedeckt:
  1. Thomas H. Cormen, Charles E. Leiserson, Ron L. Rivest, Clifford Stein.
     Introduction to Algorithms.
     2. Auflage, The MIT Press, Cambridge, MA, 2001.

  2. Michael T. Goodrich, Roberto Tamassia.
     Algorithm Design: Foundations, Analysis, and Internet Examples.
     John Wiley & Sons, Inc., 2002.

  3. Christos H. Papadimitriou, Kenneth Steiglitz.
     Combinatorial optimization: Algorithms and complexity.
     Prentice-Hall, Englewood Cliffs, NJ, 1982.

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

  5. Steven S. Skiena.
     The Algorithm Design Manual.
     Springer-Verlag, New York, 1998.

  6. Robert E. Tarjan.
     Data Structures and Network Algorithms.
     CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, Philadelphia, PA, 1983.

• Sprechstunde:
  siehe hier