http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

Effiziente Algorithmen II

Mitteilungen

Die mündlichen Prüfungstermine finden Sie hier.

Materialien

Prüfungsvorbereitung:

  • Liste mit Beispielfragen [pdf]

Vorlesungsskript:

  1. Kapitel: Maximierung von Flüssen in Netzwerken [pdf
  2. Kapitel: Matchings in bipartiten Graphen [pdf]
  3. Kapitel: Amortisierte Analyse [pdf]
  4. Kapitel: Binomial-Heaps und Fibonacci-Heaps [pdf]
  5. Kapitel: Textsuche [pdf]

Übungsblätter:

  1. Übung [pdf
  2. Übung [pdf
  3. Übung [pdf
  4. Übung [pdf]  
  5. Übung [pdf]  
  6. Übung [pdf]  (Visualisierung Auktions-Matching)
  7. Übung [pdf]  
  8. Übung [pdf
  9. Übung [pdf
  10. Übung [pdf]
  11. Übung [pdf
  12. Übung [pdf]

Termine

Vorlesung:Prof. M. Dietzfelbinger

Mittwoch, 11:00 - 12:30, LdV-Hs 1

Übungen: M. Aumüller

Mittwoch, 15:00 - 16:30, Sr HU 010

Freitag, 15:00 - 16:30, Sr HU 201

Bonuspunktesystem

Bonuspunkte gibt es ab dem zweiten Übungsblatt für das korrekte Vorrechnen einer markierten Übungsaufgabe (maximal zwei pro Person, 1/3 einer Notenstufe jeweils, keine automatische Verbesserung von 5,0 auf 4,0). Lösungsvorschlag muss bis zum im jeweiligen Übungsblatt genannten Zeitpunkt per E-Mail an Martin Aumüller gesendet oder direkt im Zusebau Raum 1057 abgegeben werden. Bitte dabei angeben, in welcher Übungsgruppe die Lösung vorgerechnet werden soll.

Inhalt

  1. Flüsse in Netzwerken
  2. Matching-Algorithmen und andere Anwendungen von Flussalgorithmen
  3. Amortisierte Analyse
  4. Binomial-Heaps und Fibonacci-Heaps
  5. String-Matching

Literatur

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, MIT Press, 2009
  • S. Dasgupta, C. Papadimitriou, U. Vazirani, Algorithms, McGraw-Hill, 2007
  • T. Ottmann, P. Widmayer, Algorithmen und Datenstrukturen, Spektrum Akademischer Verlag, 2002
  • R. Sedgewick, Algorithms, Addison-Wesley, 2002 (auch C-, C++, Java-Versionen, auch auf deutsch bei Pearson) R. Sedgewick, Algorithms, Part 5: Graph Algorithms, Addison-Wesley, 2003
  • J. Kleinberg, E. Tardos, Algorithm Design, Pearson Education, 2005
  • Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin: Network Flows, Prentice Hall, 1993
  • Sven O. Krumke, H. Noltemeier: Graphentheoretische Konzepte und Algorithmen, Teubner, 2005
  • M. Crochemore, W. Rytter: Jewels of Stringology, World Scientific, 2003