http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

Effiziente Algorithmen II (Univ.-Prof. M. Dietzfelbinger)

Mitteilungen

Die Termine für die mündlichen Prüfungen finden Sie hier.

Die Freitagsübung findet ab dem vierten Übungsblatt im Sr Hu 201 statt.

Material

Prüfungsvorbereitung: Liste mit Beispielfragen [pdf]

Vorlesungsskript:

  1. Kapitel: Maximierung von Flüssen in Netzwerken [pdf] (Aktualisierung am 7.11., 20 Uhr)
  2. Kapitel: Matchings in bipartiten Graphen [pdf] (Aktualisierung am 14.11., 15 Uhr. Änderungen auf Seite 9.)
    Korrektur zur Vorlesung am 21.11. [pdf]
  3. Kapitel: Amortisierte Analyse [pdf]
  4. Kapitel: Priority Queues
    1. Binomial-Heaps [pdf] (Aktualisierung am 10.1., 15 Uhr)
    2. Fibonacci-Heaps [pdf]
  5. Kapitel: Textalgorithmen
    1. Knuth-Morris-Pratt [pdf] (Achtung: Erneute Aktualisierung am 24.1., 15 Uhr)

Übungsunterlagen:

  1. Übungsblatt (Zeichenhilfe für Aufgabe 1)
    Beispiel für Nicht-Terminierung der FF-Methode [pdf]
  2. Übungsblatt
  3. Übungsblatt 
  4. Übungsblatt 
  5. Übungsblatt 
  6. Übungsblatt
  7. Übungsblatt 

Ergebnis der Vorlesungsevaluierung: pdf

Termine

Vorlesung:

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

 Übungen: (Jede zweite Woche, Leitung: M. Aumüller)

  • Mittwoch, 9:00 - 10:30, Sr H 1520a (ungerade Kalenderwochen)
  • Freitag, 15:00 - 16:30, Sr Hu 201 (gerade Kalenderwochen)

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

Bonuspunktesystem

Bonuspunkte gibt es 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 oder direkt im Zusebau Raum 1057. Bitte dabei angeben, in welcher Übungsgruppe die Lösung vorgerechnet werden soll.

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