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

Auswertung Studierendenbefragung

[Mitteilungen] [Inhalte] [Termine] [Scheinerhalt] [Literatur] [Materialien]

Mitteilungen

Ausweichtermin für die Übung am 21. Mai 2008 (Dies Academicus):

Donnerstag, den 22. Mai 2008 7:00 - 8:30 Uhr, Sr HU 211/212

Termine

mündliche Prüfungen EA

• Vorlesungen (Prof. Dr. (USA) M. Dietzfelbinger)
  
• Dienstag, 9:00-10:30 Uhr, K-Hs
  
  
• Übungen (U. Schellbach)
• Mittwoch (G), 13:00-14:30, Sr Oe 305
  
• Mittwoch (U), 15:00-16:30, Sr H 211/212
• Freitag (U), 13:00-14:30, H1510
  

Themen

1. Divide-and-Conquer
   Multiplikation ganzer Zahlen: Algorithmus von Karatsuba-Ofman
   Matrixmultiplikation: Algorithmus von Strassen
   Erinnerung: Mergesort
   Quicksort
   Selection in Zeit O(n) –Algorithmus von Blum, Floyd, Pratt, Rivest, Tarjan
   Rekurrenz(un)gleichungen
   
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
   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
• 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

Folien zur Vorlesung vom 01.04.2008 Druckversion Blätterversion

Folien zur Vorlesung vom 08.04.2008 Druckversion Blätterversion

Folien zur Vorlesung vom 15.04.2008 Druckversion Blätterversion Teil 2 Druckversion Blätterversion

Folien zur Vorlesung vom 22.04.2008 Druckversion Blätterversion

Folien zur Vorlesung vom 29.04.2008 Druckversion Blätterversion

Folien zur Vorlesung vom 06.05.2008 Druckversion Blätterversion

Ergänzung: Beweis des Fundamentallemmas für freie Bäume

Folien zur Vorlesung vom 13.05.2008 Druckversion Blätterversion

Folien zur Vorlesung vom 20.05.2008, Druckversion Blätterversion korrigierte Version (Algo'en von Dijkstra und Jarnik/Prim)

Folien zur Vorlesung vom 27.05.2008 Druckversion

Folien zur Vorlesung vom 03.06.2008 Druckversion Blätterversion

Folien zur Vorlesung vom 10.06.2008 Druckversion Blätterversion (Wichtig: Folien 13+15 korrigiert, 11.06.2008)

Folien zur Vorlesung vom 24.06.2008 Druckversion Blätterversion

Übungsblätter

Übungsblatt 1 (3.4.08, 11.00Uhr)

Übungsblatt 2

Übungsblatt 3

Übungsblatt 4

Übungsblatt 5

Übungsblatt 6

Übungsblatt 7

Folien zu Übungen

Folien zur 1. Übung

Folien zur 2. Übung

Folien zur 4. Übung

Folien zur 6. Übung

Folien zur 7. Übung