http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

Effiziente Algorithmen

Mitteilungen

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

 

 

Material

Prüfungsvorbereitung:

Beispiel-Prüfungsfragen

 Evaluierung:

Evaluierung

Skript:

  1. Kapitel: Divide-and-Conquer [Druckversion], Foliensatz FFT [Druckversion]
  2. Kapitel: Graphdurchläufe
    1. Breitensuche  [Druckversion]
    2. Tiefensuche mit Anwendungen [Druckversion | Blätterversion
  3. Kapitel: Greedy-Algorithmen: Prinzipien [Druckversion | Blätterversion
  4. Kapitel: Greedy-Algorithmen für Graphprobleme [Druckversion | Blätterversion]
    Dazu: Notizen zu freien Bäumen [Text]
  5. Kapitel: Dynamische Programmierung [Druckversion| Blätterversion]
    Kapitel 5.3: Rucksack [Druckversion | Blätterversion]
    Kapitel 5.5: Traveling Salesperson [Druckversion]
  6. Weiterführende Themen:
    • Ein Greedy-Algorithmus für das Rucksack-Problem [Druckversion]
    • Ein Greedy-Algorithmus für das Set-Cover-Problem (Folien am Ende von Kapitel 3)
    • Ein randomisierter Algorithmus für das Min-Cut-Problem (Folien am Ende von Kapitel 4)

     

Übungsblätter:

  1. Übungsblatt 
  2. Übungsblatt
  3. Übungsblatt 
  4. Übungsblatt 
  5. Übungsblatt
  6. Übungsblatt

 

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
Donnerstag13:00 Uhr, LdV-Hs 1Prof. M. Dietzfelbinger
Übungen
Dienstag (U)9:00 Uhr, SR HU 202M. Aumüller
Dienstag (G)15:00 Uhr, Sr HU 010M. Aumüller
Mittwoch (G)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