http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

Effiziente Algorithmen (Master Inf)

Aktuelle Informationen

Die Ankündigung zu den mündlichen Prüfungsterminen finden Sie hier.

Auswertung der Studierendenbefragung

Vorlesungsskript

Beispielprüfungsfragen: [pdf]

  1. Kapitel: Maximierung von Flüssen in Netzwerken [pdf]
    (Update am 4.11., Überarbeitung Abschnitt Sperrflussmethode)
  2. Kapitel: Matchings in bipartiten Graphen [pdf]
    (Update am 25.11., Überarbeitung ungarische Methode)
    (Update am 3.12., Seite 30 aktualisiert)
  3. Kapitel: Amortisierte Analyse [pdf]
  4. Kapitel: Implementierung von Priority Queues [pdf]
  5. Kapitel: Knuth-Morris-Pratt [pdf], Aho-Corasick [pdf],
    Boyer-Moore (Seiten 1-9) [pdf]

Übungsblätter

  1. Übungsblatt [pdf
    Zeichenhilfe Aufgabe 1 [pdf]
    Lösung Aufgabe 1d) von P. Lindner
    Lösung Aufgabe 2 a) & c)
  2. Übungsblatt [pdf]
    Lösung Aufgabe 2
    Lösung Aufgabe 3 von S. Bennecke
  3. Übungsblatt [pdf
  4. Übungsblatt [pdf
  5. Übungsblatt [pdf
  6. Übungsblatt [pdf
    Visualisierung Auktionsmatching [link]
  7. Übungsblatt [pdf]
    Lösung Aufgabe 1 von Matthias Aumüller [pdf]
    Python-Code von L. Pfennig [github]
  8. Übungsblatt [pdf
  9. Übungsblatt [pdf
    Lösung Aufgabe 2 von Matthias Aumüller [pdf]
  10. Übungsblatt [pdf]
    Lösung Aufgabe 1 [pdf]
  11. Übungsblatt [pdf]
    Lösung Aufgabe 1 [pdf]
  12. Übungsblatt [pdf]
  13. Übungsblatt [pdf]

Termine

Vorlesung:

Mittwoch, 11:00 - 12:30 Uhr, LdV-Hs 2, Univ.-Prof. M. Dietzfelbinger

Übungen:

Mittwoch, 15:00 - 16:30 Uhr, Sr HU 010, S. Walzer

Freitag, 15:00 - 16:30 Uhr, Sr HU 201, S. Walzer

Am 13.1. und 15.1. entfällt die Übung!

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