Hier werde ich meine Mitschriften zur Vorlesung “Höhere Algorithmik” im Wintersemester 2008/2009 der Allgemeinheit zu Verfügung stellen.

1. Vorlesung: Einführung in Algorithmen und Effizienz anhand von ein paar Sortieralgorithmen.
2. Vorlesung: Fortsetzung von der vorhergehenden Stunde.
3. Vorlesung: Wir haben mit Berechnungsmodellen angefangen, im speziellen mit Turinmaschinen und RAMs.
4. Vorlesung: Weiter im Text mit Berechnungsmodellen und wie man sie vergleichen kann. Und noch ein paar Bemerkungen zum Suchen und Sortieren
5. Vorlesung: Nachdem wir uns zu Ende über das Suchen und Sortieren Gedanken gemacht haben, haben wir mit dem Auswahlproblem angefangen.
6. Vorlesung: Wir haben uns ein deterministisches Auswahlverfahren angeguckt und dann mit Binärsuche und als Verbesserung dazu die Interpolationssuche angeschaut.
7. Vorlesung: Wir haben die Suchverfahren mit der Quadratischen Binärsuche abgeschlossen.
8. Vorlesung: Das neue Kaptiel heißt Datenstrukturen. Wir widmen uns dem Wörterbuchproblem und gucken uns sortierte Arrays, Hashing, binäre Suchbäume, AVL-Bäume und BB[α]-Böume an.
9. Vorlesung: Weiter mit dem Wörterbuchproblem und (a,b)-Bäumen, Rot-Schwarz-Bäumen und schlussendlich Tries. Optimale binäre Suchbäume wurden angerissen, damit geht es nächstes mal weiter.
10. Vorlesung: Es ging weiter mit den optimalen Suchbäumen. Wir haben zum Aufbau von solchen Bäumen einen Algorithmus kennengelernt.
11. Vorlesung: Abschließend zu optimalen Suchbäumen haben wir den Algorithmus analysiert und gesehen, wie man ihn optimieren kann. Dann haben wir mit dem Vereinige-Finde-Problem (oder auch Union-Find) angefangen.
12. Vorlesung: Wir haben Union-Find analysiert und per Pfadkompression weiter verbessert.
13. Vorlesung. Es wurde mit Graphen angefangen. Nach vielen Definitionen ging es auch kurz um Travsersierungen und topologisches Sortieren. Danke an Gero, der mir seine Tafelbilder zu Verfügung gestellt hat.
14. Vorlesung: Wir haben angeguckt, wie man mit dem Algorithmus von Kruskal minimal spannende Bäume baut und wie Dijkstra kürzeste Wege findet.
15. Vorlesung: Wir haben uns mit dem Floyd-Warshall-Algorithmus beschäftigt, der das All-Pairs-Shortest-Path-Problem löst.
16. Vorlesung: Nach den Wegproblemen folgen nun die Flüsse in Netzen. Wir haben den Ford-Fulkerson-Algorithmus kennen gelernt, der den maximalen Fluss berechnet.
17. Vorlesung: Weiter mit Ford-Fulkerson.
18. Vorlesung: Zuende mit Ford-Fulkerson und dann gleich noch Edmonds-Karp hinterher, der ein wenig anders als Ford-Fulkerson funktioniert.
19. Vorlesung: Als letztes zum Thema Graphen haben wir uns das bipartite Matching angeschaut. Das neue Kapitel ist nun String Matching.
20. Vorlesung: String Matching haben wir fortgeführt und und den Algorithmus von Knuth-Morris-Pratt weiter angeschaut. Und dann dazu auch noch Suffixbäume.
21. Vorlesung: Wir haben das Kapitel String Matching abgeschlossen und mit NP-Vollsändigkeit angefangen.
22. Vorlesung: Wir haben uns die Klassen P und NP angeschaut und definiert, was polynomzeit Reduktion ist.
23. Vorlesung: Wir haben definiert, was NP-schwer und NP vollständig bedeutet und gezeigt, dass CSAT (Schaltkreiserfüllbarkeit) ein NP vollständiges Problem ist.
24. Vorlesung: Wir haben uns weitere NP vollständige Probleme angeschaut. Es kam SAT …
25. Vorlesung: … 3-SAT, CLIQUE …
26. Vorlesung: … UK (Unabhängige Knotenmenge), ÜK  (überdeckende Knotenmenge), SUBSET-SUM und GHK (gerichteter Hamiltonscher Kreis).
27. Vorlesung:  Wir haben uns andere Komplexitätsklassen angeschaut. Darunter waren Co-NP, PSPACE und EXPTIME.
28. Vorlesung: Approximationsalgorithmen heißt das neue Kapitel. wir widmen uns zunächst Delta-TSP mit der Baumheuristik.
29. Vorlesung: Wir lernen die Christofides-Heuristik für Delta-TSP kennen und zeigen, warum das normale TSP nicht approximierbar ist.
30. Vorlesung: Wir lernen einen PTAS (polynomial time approx scheme) für SUBSET-SUM kennen.

Anmerkung: Die letzten drei Vorlesungen sind noch nicht überarbeitet! Aber da sicherlich einige schon jetzt reinschauen wollen um für die Klausur zu lernen, stelle ich es schon online. Ich versuche aber noch vor Freitag meine Notizen durchzugehen und zu überarbeiten. Ich wünsche schonmal allen viel Erfolg beim Lernen und vor allem bei der Klausur!

Edit (12.02.09, 15.00): Nun sind auch die letzten drei Vorlesungen überarbeitet!

Download Höhere Algorithmik Mitschrift