http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

Effiziente Algorithmen

Mitteilungen

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

Die mündlichen Prüfungen für Effiziente Algorithmen finden vom 30.07. - 31.07.2012 und vom 17.09. - 21.09.2012 statt. Zur Terminvergabe tragen Sie sich bitte bis zum 16. Juli 2012 im Sekretariat bei Frau Kopp, Zusebau, Raum 1046, in die Terminliste ein. Bitte melden Sie sich zuerst im Prüfungsamt (Thoska) für die Prüfung an. Vorher ist keine Terminvergabe möglich!

Evaluierung: Vorlesung | Übung

Material

Prüfungsvorbereitung:

  • Fragebogen mit Beispielfragen [pdf]

Skript:

  1. Kapitel: Divide-and-Conquer-Algorithmen [pdf]
  2. Kapitel: Graphdurchläufe und -strukuranalyse [pdf]
  3. Kapitel: Greedy-Algorithmen [pdf]
  4. Kapitel: Greedy-Algorithmen für Graphprobleme [pdf]
  5. Kapitel: Dynamische Programmierung [pdf
  6. Kapitel: Weiterführende Themen [pdf]

Vorlesungsnotizen:

  • 05.04. Organisatorisches, Karatsuba-Multiplikation, Strassen-Matrixmultiplikation [pdf]
  • 12.04. Mergesort, Master-Theorem, Quicksort, Quickselect [pdf]  
    (Analyse QuickSelect [pdf])
  • 19.04. BFPRT, schnelle Fourier-Transformation [pdf]
  • 26.04. Tiefensuche, Kreisfreiheitstest, Topologische Sortierung [pdf]
  • 03.05. Starke Zusammenhangskomponenten, DFS in ungerichteten Graphen [pdf]
  • 03.05. Greedy-Algorithmen -- einführende Beispiele [pdf]
  • 10.05. Huffman-Algorithmus, Priority Queues [pdf]
  • 24.05. Der Algorithmus von Dijkstra [pdf]
  • 07.06. Minimale Spannbäume: Algorithmen von Jarnik/Prim bzw. Kruskal [pdf]
    (Für besonders Interessierte: Weiterführende Notizen über Bäume [pdf])
  • 14.06. Union-Find [pdf] Zusatz: Zusammenfassung Pfadkompression [pdf]
  • 21.06. Editierdistanz [pdf | Java-Code
  • 28.06. Kürzeste Wege mit DP: Floyd-Warshall und Bellman-Ford [pdf | Java-Code
  • 05.07. Weitere Beispiele DP: Rucksackproblem, TSP [pdf]
  • 12.07. Ausblick: 0-1-Rucksackproblem mit Greedy-Strategie, minimale Schnitte [pdf]

Übungsunterlagen:

  1. Übungsblatt [pdf
  2. Übungsblatt [pdf]
  3. Übungsblatt [pdf]
  4. Übungsblatt [pdf]
  5. Übungsblatt [pdf] (Dienstag, 5.6.), 5. Übungsblatt [pdf] (Mittwoch, 20.6.)
  6. Übungsblatt [pdf]

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

Verantwortlich: Univ.-Prof. Dr. Martin Dietzfelbinger. Vorlesung wird von Dipl.-Inf. Martin Aumüller vertreten.

Vorlesung
Donnerstag15:00 Uhr, K-Hs 2M. Aumüller
Übungen
Dienstag (U)15:00 Uhr, Sr HU 011M. Aumüller
Mittwoch (U)10:45 Uhr, Sr HU 011M. Aumüller
Mittwoch (U)13:00 Uhr, Sr HU 204M. Aumüller

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
    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
    Priority-Queue-Implementierungen: Binäre Heaps 
    Huffman-Kodierung
    Kürzeste Wege 1: Algorithmus von Dijkstra
  4. Minimale Spannbäume: Greedy-Strategie speziell, Hilfsstrukturen
    Union-Find-Datenstruktur 
    MST: Schnitteigenschaft
    MST: Algorithmus von Kruskal
    MST: Algorithmus von Prim
  5. Dynamische Programmierung
    Editierdistanz
    Ganzzahliges Rucksackproblem (mit Wiederholungen)
    Kürzeste Wege 2: Algorithmus von Floyd-Warshall
    Kürzeste Wege 3: Algorithmus von Bellman-Ford
    Das Problem des Handlungsreisenden
  6. Weiterführende Themen
    Ein Approximationsalgorithmus für das Rucksackproblem
    Ein randomisierter Algorithmus zum Finden minimaler Schnitte

Literatur

Neben den Vorlesungsfolien wird empfohlen:

  • 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