http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

Effiziente Algorithmen

Aktuelle Informationen

Die mündlichen Prüfungstermine finden Sie hier.

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

In einer aktuellen Ausgabe der Fachzeitschrift "Communications of the ACM" wird ein interessanter Überblick über Flussalgorithmen gegeben. Artikel und Video sind unter http://dl.acm.org/citation.cfm?doid=2628036 (vermutlich nur aus dem Netz der TU Ilmenau frei) verfügbar.

Auswertung der Studierendenevaluierung (Vorlesung): pdf

Auswertung der Studierendenevaluierung (Uebung): pdf

Vorlesungsskript

Beispielprüfungsfragen: pdf

  1. Kapitel: Maximierung von Flüssen in Netzwerken [pdf]
  2. Kapitel: Matchings in bipartiten Graphen [pdf]
    Visualisierung Auktions-Matching [link]
  3. Kapitel: Amortisierte Analyse [pdf]
  4. Kapitel: Priority-Queues [pdf]
  5. Kapitel: Textalgorithmen
    • Knuth-Morris-Pratt [pdf]
    • Aho-Corasick [pdf]
    • Boyer-Moore [pdf]

Übungsblätter

  1. Übungsblatt [pdf
  2. Übungsblatt [pdf]  Wegen Krankheit entfallen.
  3. Übungsblatt [pdf
  4. Übungsblatt [pdf
  5. Übungsblatt [pdf
  6. Übungsblatt [pdf
  7. Übungsblatt [pdf
  8. Übungsblatt [pdf
  9. Übungsblatt [pdf
  10. Übungsblatt [pdf]
  11. Übungsblatt [pdf
  12. Übungsblatt [pdf
  13. Übungsblatt [pdf
  14. Übungsblatt [pdf]

Termine

Vorlesung Univ.-Prof. M. Dietzfelbinger

Mittwoch, 11:00 - 12:30 Uhr, LdV-Hs 2

 

Übung: M. Aumüller

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

Freitag, 15:00 - 16:30 Uhr, 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