Sommersemester 2009
Prof. Dr. (USA) M.Dietzfelbinger

Auswertung Studierendenbefragung

[Mitteilungen] [Termine] [Themen] [Prüfung] [Literatur] [Materialien]

Mitteilungen

Erste Vorlesung: Mittwoch, 08.04.2009, 09:00 Uhr

Übungen beginnen: Dienstag, 14.04.2009; Donnerstag, 16.04.2009; Freitag 24.04.2009

Termine

mündliche Prüfungen EA

• Vorlesungen (Prof. Dr. (USA) M. Dietzfelbinger)
  
• Mittwoch, 9:00-10:30 Uhr, K-Hs 2
  
  
• Übungen (Lucia Draque Penso, Ph. D. (Brown))
• Dienstag (G), 11:00-12:30, HU011
  
• Donnerstag (G), 09:00-10:30, HU011
  
• Freitag (U), 09:00-10:30, HU202
  

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

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

Dokumente zur Vorlesung

Material zur 1. Vorlesung am 08.04.2009 (Stand vom 21.04.2009)

Folien zu Kapitel 1

Folien zu Kapitel 2 Druckversion Blätterversion (korrigiert 20.05.2009, Beweis Folien 75/76)

Folien zu Kapitel 3 ("Greedy-Algorithmen") Druckversion Blätterversion (Stand vom 27.05.2009, 16:00 Uhr (erweitert))

Material zu freien Bäumen

Folien zu Kapitel 3 - Teil 2 Druckversion Blätterversion (Stand vom 17.06.2009)

Folien zu Kapitel 4 Druckversion Blätterversion (Stand vom 08.07.2009, 13:00 Uhr)

Folien zu Kapitel 5 Druckversion Blätterversion (KMP erweitert, 16.07.2009)

Übungsblätter

Übungsblatt 1

Übungsblatt 2

Übungsblatt 3

Übungsblatt 4

Übungsblatt 5

Übungsblatt 6

Übungsblatt 7