http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

EA II

Effiziente Algorithmen II - WS 2010

Prof. Dr. M. Dietzfelbinger

Materialien und Übungsblätter

Materialien und Übungsblätter

Prüfungsvorbereitung

Beispiele für Prüfungsfragen [pdf]

Vorlesungsmaterial

Kapitel 1:

  1. Definitionen Flüsse [pdf] (kleine Änderungen im Vergleich zur Vorlesung)
  2. Notizen zur 2. Vorlesung [pdf]
  3. Algorithmen zur Sperrflussmethode [pdf] (Vorsicht: Zeile 3 FB-Sperrfluss dazugekommen)
  4. Notizen zur Sperrflussberechnung [pdf]

Kapitel 2:

  1. Algorithmus: Ungarische Methode [pdf]

Kapitel 4:

  1. Algorithmen für Binomial-Heaps [pdf]
  2. Fibonacci-Heaps [pdf]

Kapitel 5:

  1. Knuth-Morris-Pratt-Algorithmus [pdf]
  2. Aho-Corasick-Algorithmus [pdf]
    [Aktualisierung am 24.01.2010, AC-Preprocessing Zeile 1 und 10]
  3. Boyer-Moore-Algorithmus [pdf]

Übungsmaterial

Hinweise zum Abgabesystem unter Mitteilungen. Abgabe ist nicht Pflicht!

Übungsblatt 1 (Abgabe bis 20.10.2010, 18 Uhr) [Zeichenhilfe für Aufgabe 1]

Übungsblatt 2 (Abgabe bis 04.11.2010, 12 Uhr) [Zusatzaufgaben für Interessierte]

Übungsblatt 3 (Abgabe bis 18.11.2010, 12 Uhr)

Übungsblatt 4 (Abgabe bis 02.12.2010, 12 Uhr)

Übungsblatt 5 (Abgabe bis 16.12.2010, 12 Uhr) [Muster Aufgabe 4 & 5]

Übungsblatt 6 (Abgabe bis 13.01.2011, 12 Uhr)

Übungsblatt 7 (Abgabe bis 27.01.2011, 12 Uhr) [Muster Aufgabe 2]

Termine

Termine

Vorlesung:

Dienstag, 9:00 Uhr, Sr Oe 117

Übungen:

Die erste Übung findet am 21.10.2010 statt.

TagZeitRaumMitarbeiter
Mittwoch (U)9:00 UhrSr H 1520aM. Aumüller
Donnerstag (G)17:00 UhrSr HU 011M. Aumüller

 

 

Inhalte und Literatur

Inhalte und Literatur

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
  6. Online-Algorithmen: Caching

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

Mitteilungen

Mitteilungen

 

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 im Briefkasten AFS/KTEA, Blechhaus zweiter Stock, abgegeben werden. Bitte dabei angeben, in welcher Übungsgruppe die Lösung vorgerechnet werden soll.

 

Auswertung Studierendenbefragung