Die Termine für die mündlichen Prüfungen finden Sie hier!

Prüfungsvorbereitung:

Beispiel-Prüfungsfragen

 Evaluierung:

Evaluierung

Skript:

1. Kapitel: Divide-and-Conquer [Druckversion], Foliensatz FFT [Druckversion]
2. Kapitel: Graphdurchläufe
   1. Breitensuche  [Druckversion]
   2. Tiefensuche mit Anwendungen [Druckversion | Blätterversion] 
3. Kapitel: Greedy-Algorithmen: Prinzipien [Druckversion | Blätterversion] 
4. Kapitel: Greedy-Algorithmen für Graphprobleme [Druckversion | Blätterversion]
   Dazu: Notizen zu freien Bäumen [Text]
5. Kapitel: Dynamische Programmierung [Druckversion| Blätterversion]
   Kapitel 5.3: Rucksack [Druckversion | Blätterversion]
   Kapitel 5.5: Traveling Salesperson [Druckversion]
6. 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:

1. Übungsblatt 
2. Übungsblatt
3. Übungsblatt 
4. Übungsblatt 
5. Übungsblatt
6. Übungsblatt

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.

Verantwortlich: Univ.-Prof. Dr. Martin Dietzfelbinger

1. Divide-and-Conquer
   Multiplikation ganzer Zahlen: Algorithmus von Karatsuba-Ofman
   Matrixmultiplikation: 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
2. Durchsuchen und Strukturanalyse von Graphen
   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
   Priority-Queue-Implementierungen: Binäre Heaps 
   Huffman-Kodierung
   Kürzeste Wege 1: Algorithmus von Dijkstra
4. Minimale Spannbäume: Greedy-Strategie speziell, Hilfsstrukturen
   Union-Find-Datenstruktur 
   MST: Schnitteigenschaft
   MST: Algorithmus von Kruskal
   MST: Algorithmus von Prim
5. 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
6. Weiterführende Themen
   Ein Approximationsalgorithmus für das Rucksackproblem
   Ein randomisierter Algorithmus zum Finden minimaler Schnitte

Neben den Vorlesungsfolien wird empfohlen: