Inhalt der Vorlesungen

• Freitag, 17. 10. 2014
  • Organisatorisches
  • Einführendes Beispiel: Kuchenteilen
• Montag, 20. 10. 2014
  • Überblick und Ziele der Vorlesung
  • Rechnermodelle: Registermaschine (RAM-Modell)
  • Einheitskostenmaß und logarithmisches Kostenmaß
  • Laufzeitabschätzung im schlimmsten Fall
• Freitag, 24. 10. 2014
  • Registermaschine und Turingmaschine
  • Divide-and-conquer. (bekannte Beispiele: Sortieralgorithmen)
  • Lösung von Rekursionsgleichungen durch fortgesetztes Einsetzen
  • Lösung von Rekursionsgleichungen durch Betrachten des Rekursionsbaums
• Montag, 27. 10. 2014
  • Beispiele für divide-and-conquer: Maximum und Minimum, Karatsuba-Multipikation langer Zahlen
  • Lösung von Rekursionsgleichungen durch Ansatz
  • Das Master-Theorem zur Lösung von Rekursionsgleichungen
• Freitag, 31. 10. 2014
  • Formulierung und Beweis des Master-Theorems (ausführliche Unterlagen zum Beweis, Fassung vom 2.11.)
• Montag, 3. 11. 2014
  • Zählen von Fehlständen (Inversionen)
• Freitag, 7. 10. 2014
  • Mediansuche, Auswahl des k-kleinsten Elements
  • Quickselect, randomizierte Auswahl des Pivotelements
  • Deterministischer Algorithmus nach Blum, Floyd, Pratt, Rivest, Tarjan (1973)
• Montag, 10. 11. 2014
  • Das Rucksackproblem
  • Formulierung mit Variablen
  • Dynamisches Programmieren
  • Was sind die Teilprobleme?
  • Rekursion und Anfangsbedingungen
  • Algorithmus: Systematische Reihenfolge der Teilprobleme
  • Zurückverfolgen der Lösung
  • Darstellung als kürzester Weg in einem Graphen
• Freitag, 14. 11. 2014
  • Beispiel: Gewichtete Intervallauswahl; Darstellung in einem Graphen
  • Das Rundreiseproblem
  • Tabellieren (memoization)
• Montag, 17. 11. 2014
  • Kürzeste Triangulierung eines Polygons (dynamische Programmierung über Intervallen)
  • Isotone Regression, stückweise lineare Funktionen (Unterlagen auf englisch)
• Freitag, 21. 11. 2014
  • Darstellung stückweise linearer Funktionen
  • Optimale binäre Suchbäume
• Montag, 24. 11. 2014
  • Editierabstand, sequence alignment
  • Reduktion auf linearen Speicher
  • Gierige Algorithmen
  • Beispiel: Rucksackproblem
  • Beispiel: Ungewichtete Intervallauswahl
• Freitag, 28. 11. 2014
  • Beispiel: Zerlegung einer Intervallmenge in überlappungsfreie Teilmengen
  • Färbung, Cliquen und unabhängige Mengen in Intervallgraphen
  • Zeitplanung (Scheduling): maximale Verspätung
  • Austauschargument
  • Kürzeste Spannbäume, Algorithmus von Kruskal
• Montag, 1. 12. 2014
  • Kürzeste Wege in Graphen
  • Der Algorithmus von Bellman/Ford/Moore
  • Effiziente Implementierung des Algorithmus von Bellman/Ford/Moore für kürzeste Wege mit einer Warteschlange
• Freitag, 5. 12. 2014
  • Algebraische Wegeprobleme
  • Halbringe
• Montag, 8. 12. 2014
  • Fixed-parameter tractable problems (FPT)
  • Suchbaum
  • Datenreduktion, kernelization
• Freitag, 12. 12. 2014
  • Baumweite
  • Dynamische Programmierung bei Graphen mit beschränkter Baumweite
• Montag, 15. 12. 2014
  • Kürzeste Wege zwischen allen Paaren von Knoten
  • Transformation auf nichtnegative Kantengewichte
  • Der Algorithmus von Floyd/Warshall
• Freitag, 19. 12. 2014
  • Wegeprobleme und Matrizenmultiplikation
  • Vereinfachungen bei idempotenten Halbringen
• Montag, 5. 1. 2015
  • Polynomielle Reduzierbarkeit
  • Die Klassen P und NP
  • Nichtdeterministische Turingmaschinen
• Freitag, 9. 1. 2015
  • Zertifikatskriterium
  • NP-vollständige und NP-schwere Probleme
  • Satz von Cook/Levin: SAT ist NP-vollständig
• Montag, 12. 1. 2015
  • NP-vollstängige Probleme und Reduktionen
  • Unabhängige Knotenmenge
  • Hamiltonkreis in gerichteten Graphen
  • 3-SAT
• Freitag, 16. 1. 2015
  • 3-Färbbarkeit ≤_p planare 3-Färbbarkeit
  • Teilmengensumme, Rucksackproblem
  • Pseudopolynomielle Probleme
• Montag, 19. 1. 2015
  • Stark NP-vollständige Probleme
  • coNP und coNP-Vollständigkeit
  • NP und PSPACE, Landkarte der Komplexitätsklassen
  • Turing-Reduktionen, NP-schwere Berechnungsprobleme
  • Amortisierte Laufzeit
  • Der Algorithmus von Dijkstra mit Fibonacci-Halden
  • Binomialhalden
• Freitag, 23. 1. 2015
  • Fibonacci-Halden
  • Amortisierte Analyse von Fibonacci-Halden
  • Amortisierte Analyse mit einer Potentialfunktion
• Montag, 26. 1. 2015
  • Kürzeste Spannbäume
  • Das UNION-FIND-Problem
  • Vereinigung nach Größe, Vereinigung nach Rang
  • Pfadkompression
  • Analyse des UNION-FIND-Algorithmus nach Seidel und Sharir. Ausarbeitung (PDF-Datei).
  • Werdegang eines Knotens, verallgemeinerte Kompressionsfolge
• Freitag, 30. 1. 2015
  • Beschränkung der Anzahl der Knoten mit großem Rang
  • Zerlegung eines Waldes nach Rang in einen oberen und unteren Wald
• Montag, 2. 2. 2015
  • Die inverse Ackermann-Funktion α(m,n)
  • Langsames Wachstum der inversen Ackermann-Funktion
  • Randomisierte Suchbäume (Balden, treaps)
• Freitag, 6. 2. 2015
  • Geometrische Algorithmen: konvexe Hülle
  • Orientierungstest
  • Reduktion: konvexe Hülle und Sortieren
  • Nächstes Paar
• Montag, 9. 2. 2015
  • Systematisches Durchsuchen von Lösungsbäumen (branch and bound)
  • Beispiel Rucksackproblem mit Knotenauswahl durch Tiefensuche, Breitensuche, größte Schranke, und mit sortierter Eingabe. (Python-Programme b_and_b.py und b_and_b_ipe.py zum Erstellen der Animationen)
  • Heuristiken (lokale Suche, steilster Abstieg, simulated annealing, genetische Algorithmen)
• Freitag, 13. 2. 2015
  • Ausblick: randomisierte Algorithmen, Approximationsalgorithmen, externer Speicher, streaming
  • Approximationsalgorithmen: Rundreiseproblem, Rucksackproblem, PTAS, FPTAS
• Montag, 16. 2. 2015: Klausur