http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

Effiziente Algorithmen SS 2011

Prof. Dr. M. Dietzfelbinger


Mitteilungen

Prüfungsvorbereitung

Fragenkatalog (letzte kleine Korrektur: 3. August 2011)

Prüfungstermine 

Die mündlichen Prüfungen für EA bei Prof. Dietzfelbinger finden am 1., 2., 3. und 4. August 2011 statt. Zur Terminvergabe tragen Sie sich bitte bis zum 22. Juli 2011 im Sekretariat bei Frau Kopp, Informatikgebäude, Raum 305, bzw. ab voraussichtlich 30.06.2011 im Zusebau, Raum 1046, in die Terminliste ein.

Auswertung Studierendenbefragung

Materialien

Materialien

Vorlesungsmaterial

  1. Kapitel:  Divide-and-Conquer Druckversion Blätterversion Stand: 29.04.2011
  2. Kapitel: Graphdurchläufe Druckversion Blätterversion Stand: 13.05.2011
  3. Kapitel: Prinzipien von Greedy-Algorithmen Druckversion Blätterversion Stand: 30.05.2011 (mit Prioritätswarteschlangen)
  4. Kapitel: Greedy-Algorithmen für Graph-Probleme Druckversion Blätterversion Stand: 30.06.2011 (neu: MinCut)
    Dazu: Notizen über freie Bäume.
  5. Kapitel: Dynamische Programmierung Druckversion Blätterversion (Update am 22.07.2011! (Material der letzten Vorlesungsstunde))

Übungsaufgaben

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

 Bonuspunkte

Bonuspunkte 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, abgegeben werden. Bitte dabei angeben, in welcher Übungsgruppe die Lösung vorgerechnet werden soll.

 

Termine

Termine

Vorlesung : Donnerstag, 15:00 - 16:30 Uhr, K-Hs 2

Übungen : Der Übungsbetrieb startet am 20.04.2011.

Dienstag (U)15:00- 16:30 Uhr, Sr HU 011 M. Aumüller
Mittwoch (G)

10:45 - 12:15 Uhr, Sr HU 011

M. Aumüller
Mittwoch (G)13:00 - 14:30 uhr, Sr HU 129M. Aumüller

 

 

Themen

Themen

  1. Divide-and-Conquer
    Multiplikation ganzer Zahlen: Algorithmus von Karatsuba-Ofman
    Matrixmultiplikation: Algorithmus von Strassen
    Erinnerung: Mergesort
    Master-Theorem
    Quicksort: Neue Analyse
    Selection in Zeit O(n) –Algorithmus von Blum, Floyd, Pratt, Rivest, Tarjan
    Randomisierter Selection-Algorithmus
    Schnelle Fourier-Transformation
  2. Durchsuchen und Strukturanalyse von Graphen
    Erinnerung: Breitensuche, Tiefensuche
    Erweiterte Tiefensuche mit:
    • Kreisfreiheitstest, Finden von Kreisen
    • Topologische Sortierung
    • Starke Zusammenhangskomponenten
    • Tiefensuche in ungerichteten Graphen mit Kreisfreiheitstest
  3. Greedy-Strategie allgemein
    Teilbares Rucksackproblem
    Schedulingprobleme
    Kürzeste Wege 1: Algorithmus von Dijkstra
    Priority-Queue-Implementierungen: Binäre Heaps 
    Huffman-Kodierung
    Set Cover
  4. Minimale Spannbäume: Greedy-Strategie speziell, Hilfsstrukturen
    Union-Find-Datenstruktur 
    MST: Schnitteigenschaft
    MST: Algorithmus von Kruskal
    MST: Algorithmus von Prim
    Minimale Schnitte
  5. Dynamische Programmierung
    Editierdistanz
    Matrix-Ketten-Multiplikation
    Ganzzahliges Rucksackproblem
    Kürzeste Wege 2: Algorithmus von Floyd-Warshall, Transitive Hülle
    Kürzeste Wege 3: Algorithmus von Bellman-Ford
    Optimale binäre Suchbäume
  6. Algorithmen für schwere Probleme
    Backtracking
    Branch-and-Bound
    Lokale Suche

Literatur

Literatur

  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 2nd ed., MIT Press, 2001 (auch auf deutsch bei Oldenbourg)
  • S. Dasgupta, C. Papadimitriou, U. Vazirani, Algorithms, McGraw-Hill, 2007
  • V. Heun, Grundlegende Algorithmen, 2. Auflage, Vieweg, 2003
  • J. Kleinberg, E. Tardos, Algorithm Design, Pearson Education, 2005
  • K. Mehlhorn, P. Sanders, Algorithms and Data Structures - The Basic Toolbox, Springer, 2008
  • T. Ottmann, P. Widmayer, Algorithmen und Datenstrukturen, Spektrum Akademischer Verlag, 2002
  • U. Schöning, Algorithmik, Spektrum Akademischer Verlag, 2001
  • 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