INHALTE
Effiziente Algorithmen
Mitteilungen
Material
Prüfungsvorbereitung:
Evaluierung:
Skript:
- Kapitel: Divide-and-Conquer [Druckversion], Foliensatz FFT [Druckversion]
- Kapitel: Graphdurchläufe
- Breitensuche [Druckversion]
- Tiefensuche mit Anwendungen [Druckversion | Blätterversion]
- Kapitel: Greedy-Algorithmen: Prinzipien [Druckversion | Blätterversion]
- Kapitel: Greedy-Algorithmen für Graphprobleme [Druckversion | Blätterversion]
Dazu: Notizen zu freien Bäumen [Text] - Kapitel: Dynamische Programmierung [Druckversion| Blätterversion]
Kapitel 5.3: Rucksack [Druckversion | Blätterversion]
Kapitel 5.5: Traveling Salesperson [Druckversion] - Weiterführende Themen:
- Ein Greedy-Algorithmus für das Rucksack-Problem [Druckversion]
- Ein Greedy-Algorithmus für das Set-Cover-Problem (Folien am Ende von Kapitel 3)
Ein randomisierter Algorithmus für das Min-Cut-Problem (Folien am Ende von Kapitel 4)
Übungsblätter:
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 direkt im Zusebau, Raum 1057, abgegeben werden. Bitte dabei angeben, in welcher Übungsgruppe die Lösung vorgerechnet werden soll.
Termine
Verantwortlich: Univ.-Prof. Dr. Martin Dietzfelbinger
Vorlesung | ||
Donnerstag | 13:00 Uhr, LdV-Hs 1 | Prof. M. Dietzfelbinger |
Übungen | ||
Dienstag (U) | 9:00 Uhr, SR HU 202 | M. Aumüller |
Dienstag (G) | 15:00 Uhr, Sr HU 010 | M. Aumüller |
Mittwoch (G) | 13:00 Uhr, Sr HU 204 | M. Aumüller |
Themen
- Divide-and-Conquer
Multiplikation ganzer Zahlen: Algorithmus von Karatsuba-OfmanMatrixmultiplikation: Algorithmus von Strassen
Erinnerung: Mergesort
Master-Theorem
Quicksort: Neue Analyse
Selection in Zeit O(n) –Algorithmus von Blum, Floyd, Pratt, Rivest, Tarjan
Randomisierter Selection-Algorithmus
Schnelle Fourier-Transformation - Durchsuchen und Strukturanalyse von Graphen
Tiefensuche
Erweiterte Tiefensuche mit:
- Kreisfreiheitstest, Finden von Kreisen
- Topologische Sortierung
- Starke Zusammenhangskomponenten
- Tiefensuche in ungerichteten Graphen mit Kreisfreiheitstest
- Greedy-Strategie allgemein
Teilbares Rucksackproblem
Schedulingprobleme
Priority-Queue-Implementierungen: Binäre Heaps
Huffman-Kodierung
Kürzeste Wege 1: Algorithmus von Dijkstra - Minimale Spannbäume: Greedy-Strategie speziell, Hilfsstrukturen
Union-Find-Datenstruktur
MST: Schnitteigenschaft
MST: Algorithmus von Kruskal
MST: Algorithmus von Prim - Dynamische Programmierung
Editierdistanz
Ganzzahliges Rucksackproblem (mit Wiederholungen)
Kürzeste Wege 2: Algorithmus von Floyd-Warshall
Kürzeste Wege 3: Algorithmus von Bellman-Ford
Das Problem des Handlungsreisenden - Weiterführende Themen
Ein Approximationsalgorithmus für das Rucksackproblem
Ein randomisierter Algorithmus zum Finden minimaler Schnitte
Literatur
Neben den Vorlesungsfolien wird empfohlen:
- 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