http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

Effiziente Algorithmen II (Prof. Dr. Martin Dietzfelbinger)

Material

Prüfungsvorbereitung:

Fragebogen mit Beispielfragen [pdf]

Vorlesungsunterlagen:

  1. Kapitel: Flussalgorithmen [pdf]
  2. Kapitel: Matchings in bipartiten Graphen [pdf
  3. Kapitel: Amortisierte Analyse [pdf
  4. Kapitel: Notizen zu Fibonacci-Heaps [pdf]
  5. Kapitel: Textsuche
    • Knuth-Morris-Pratt-Algorithmus [pdf]
    • Aho-Corasick-Algorithmus [pdf]
    • Boyer-Moore-Algorithmus [pdf]

Übungsblätter:

  1. Übungsblatt [pdf]
  2. Übungsblatt [pdf
  3. Übungsblatt [pdf
  4. Übungsblatt [pdf
  5. Übungsblatt [pdf]
  6. Übungsblatt [pdf
  7. Übungsblatt [pdf

Evaluation:

Auswertung der Vorlesung [pdf]

Termine

Prüfungstermine:

Die mündlichen Prüfungen finden vom 16. - 17. Februar 2012 und vom 28. - 30. März 2012 statt. Zur Terminvergabe tragen Sie sich bitte bis zum 3. Februar 2012 im Sekretariat bei Frau Kopp, Zusebau, Raum 1046, in die Terminliste ein.

Vorlesung:

  • Dienstag, 09:00-10:30, LdV-Hs 1

Übung (jede zweite Woche, Leitung: Martin Aumüller):

  • Mittwoch (ungerade Wochen), 09:00-10:30, Sr H 1520a
  • Freitag (gerade Wochen), 15:00-16:30, Sr H 1520a

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