Sommersemester 2010
Prof. Dr. M.Dietzfelbinger

Mitteilungen

Erste Vorlesung:  Donnerstag, den 8. April 2010

Übungen beginnen: Mittwoch, den 7. April 2010

Mündliche Prüfungen: 29., 30. Juli, 17., 18. und 19. August, 21.,22.,23. September -- Näheres hier!

Die Vorlesung am 27.05.2010 entfällt!

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
  

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
   
   

Änderungen vorbehalten

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.  

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

Materialien und Übungsblätter

Folien zur Vorlesung:

Folien zu Kapitel 1 Druckversion Blätterversion Stand: 15.04.2010

Folien zu Kapitel 2 Druckversion Blätterversion Stand: 02.05.2010

Folien zu Kapitel 3 Druckversion Blätterversion Stand: 20.05.2010

Folien zu Kapitel 4 Druckversion Blätterversion Stand: 14.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) [Musterlösung Aufgabe 1]

Übungsblatt 4 (Abgabe bis 19.05.2010, 10 Uhr) [Kommentare]

Übungsblatt 5 (Abgabe bis 01.06.2010, 15 Uhr) [Huffmann-Text]

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

Übungsblatt 7 (Abgabe bis 05.07.2010, 15 Uhr) Änderung: Aufgabe 2 ist abgeändert und jetzt auch lösbar! Diese kann nun bis 06.07.2010, 14 Uhr eingereicht werden.