http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

Effiziente Algorithmen

Sommersemester 2010

Prof. Dr. M. Dietzfelbinger

Materialien

Materialien

Folien zur Vorlesung:

Folien zu Kapitel 1 Druckversion Blätterversion Stand: 15.04.2010

Folien zu Kapitel 2  Druckversion Blätterversion Stand:30.4.2010

Folien zu Kapitel 3  Druckversion Blätterversion  Stand: 06.05.2010

Folien zu Kapitel 4  Druckversion Blätterversion Stand: 17.06.2010

Folien zu Kapitel 5 Druckversion  Blätterversion Stand: 01.07. 2010

Zusatz zu Kapitel 5 Folien Stand: 08.07. 2010

Folien zu Kapitel 6 Druckversion  Blätterversion Stand: 15.07. 2010


Übungsblätter

Übungsblatt 1

Übungsblatt 2 (Abgabe bis 21.04.2010, 10 Uhr)

Übungsblatt 3 (Abgabe bis 05.05.2010 , 10 Uhr)

Übungsblatt 4  (Abgabe bis 19.05.2010, 10 Uhr) 

Übungsblatt 5  (Abgabe bis 01.06.2010, 15 Uhr) 

Übungsblatt 6 (Abgabe bis 21.06.2010, 15 Uhr) (Zusatz zur Selbstkontrolle) (4a)

Übungsblatt 7 (Abgabe bis 05.07. 2010, 15 Uhr)

Themen

Themen

  1. Divide-and-Conquer
    Multiplikation ganzer Zahlen: Algorithmus von Karatsuba-Ofman
    Matrixmultiplikation: Algorithmus von Strassen
    Erinnerung: Mergesort
    Selection in Zeit O(n) –Algorithmus von Blum, Floyd, Pratt, Rivest, Tarjan
    Rekurrenz(un)gleichungen: Das Master-Theorem
  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
    Huffman-Kodierung
  4. Minimale Spannbäume: Greedy-Strategie speziell, Hilfsstrukturen
    Union-Find-Datenstruktur 
    MST: Schnitteigenschaft
    MST: Algorithmus von Kruskal
    Priority-Queue mittels binärer Heaps
    MST: Algorithmus von Prim
  5. Dynamische Programmierung
    Editierdistanz
    Matrix-Ketten-Multiplikation
    Kürzeste Wege 2: Algorithmus von Floyd-Warshall, Transitive Hülle
    Kürzeste Wege 3: Algorithmus von Bellman-Ford
  6. Textalgorithmen: Teilwortsuche
    Knuth-Morris-Pratt-Algorithmus
    Rabin-Karp-Algorithmus
  7. Flüsse in Netzwerken
    Das Problem „Maximaler Fluss in Netzwerk“
    Algorithmus von Ford-Fulkerson
    Max-Flow-Min-Cut-Theorem

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

Termine

Termine

  • Vorlesungen (Prof. Dr. M. Dietzfelbinger)
          
    Donnerstag, 15:00-16:30 Uhr, HU-Hs

  • Übungen (M. Aumüller):

    Dienstag (U), 15:00-16:30, Sr HU 201
    Mittwoch (G), 10:45-12:15, Sr HU 011
    Mittwoch (G), 13:00-14:30, Sr HU 129

Bonuspunkte

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

 


Auswertung Studierendenbefragung