Algorithmen und Datenstrukturen

Zeitplan

23, 24 Einf, 24.3
Datum Stoff Material
21.04.09 Insertion sort 2.1
23.04.09 Merge sort, O-Notation (auch Theta,Omega,o,omega), O-Notation bei Induktionsbeweisen. 2.3.1, 3.1
28.04.09 Hauptsatz der Master Methode, Heapsort mit Analyse 4.3, 6.1-6.4
30.04.09 Wdh. Heapsort, Prioritaetsschlange, Quicksort, Randomized Quicksort. Wdh naechstesmal. 6.5, 7.1-7.3, Aufgabe 7-2
05.05.09 Wdh. Randomized Quicksort, Vergleichskomplexitaet, Maximum und Minimum, Selektionsaufgabe. 8.1, 9.1, Aufgabe 9.1-2, 9.2, 9.3
12.05.09 Binaere Suchbaeume, Wdh. Grundoperationen, Rotationen. AVL-Baeume, B-Baeume. Rot-Schwarz-Baeume als spezielle B-Baeume. 12.1-12.3, 18.1-18.3, 13.1
14.05.09 Wdh. AVL-Baeume. Groesse (Balanciertheit) der Rot-Schwarz-Baeume Einfuegen und Loeschen in Rot-Schwarz-Baeumen. Hashtabellen: Direkte Adressierung Lemma 13.1, 13.3., 13.4, Kap 11 (Einleitung)
19.05.09 Hashtabellen. Direkte Adressierung, Kollisionsaufloesung durch Verkettung, Divisionsmethode, Multiplikationsmethode. Offene Adressierung, Lineares u. Quadratisches Sondieren, Uniform Hashing Annahme, Mittlere Suchdauer bei erfolgloser Suche. Kap 11
26.05.09 Mittlere Suchdauer bei erfolgreicher Suche. Zusammenfassung Hashing. Einfuehrung Kap IV (Allg Entwurfs u Optimierungsmethoden). Greedy Algorithmen (wir weichen hier etwas vom Buch ab): Einfaches Auswahlproblem, Steinitzscher Austauschsatz, Def. Praefixcode, Huffman Algorithmus, Verifikation noch nicht. 16.1, 16.3
28.05.09 Wdh. Greedy, Korrektheit des Huffman Algorithmus, Dynamische Programmierung: Matrix Kettenmultiplikation, laengste gem Teilfolge, Zusammenfassung dyn. Prog. Kap. 15 Einf., 15.2, 15.4
04.06.09 Probeklausur
09.06.09 Amortisierte Komplexitaet, Definition, Methoden, Beispiele. Union-Find mit union-by-rank und Pfadkompression. Letztere wird naechstes Mal wiederholt.
16.06.09 Wdh.\ Pfadkompression. Herleitung der amortisierten Komplexit"at f"ur Union-Find mit Pfadkompression.

Graphentheorie: Adjazenzlisten, Inzidenzmatrix, Breitensuche.

22.1
23.06.09 Wdh.\ Breitensuche, Korrektheit der B., Tiefensuche, topologische Sortierung, Zerlegung in starke Zusammenhangskomponenten. 22.22-22.5
25.06.09 Wdh.\ Zerlegung in SCC. Korrektheit des Algorithmus fuer SCCs. Minimale Spannbaeume. Grundalgorithmus, sichere Kanten. Prims Algorithmus. 22.5 23
30.06.09 Wdh.\ sichere Kanten, Prims Algorithmus. Korrektheit von Prims Algorithmus, Kruskals Algorithmus. Grundlegende Definitionen zu kuerzesten Wegen. Dijkstra Algorithmus (Korrektheit & Wdh naechstesmal).
02.07.09 Hinweis auf Erratum in Korrektheit des Algorithmus fuer SCCs. Korrektheit des Dijkstra Algorithmus. Bellman-Ford Algorithmus mit Korrektheit. All pairs shortest path mit dynamischer Programmierung, Matrizenmultiplikation und Algorithmus von Floyd-Warshall. Wdh naechstesmal.
09.07.09 Fluesse in Netzwerken. Problemstellung, Restnetzwerk, Erweiterungspfad, Max-Flow-Min-Cut Theorem, Ford-Fulkerson Methode.
14.07.09 Algorithmus von Edmonds-Karp mit Korrektheit. Maximale bipartite Matchings als Anwendung von Fluessen in Netzwerken. ***ENDE***

Wdh.: Abschaetzungen fuer erwartete Suchdauer bei uniform Hashing. Korrektheit von Greedy-Algorithmen. Union-Find mit Pfadkompression.

Die Kapitelangaben beziehen sich auf das Lehrbuch zur Vorlesung.


Valid HTML 4.01!
Martin Hofmann
Last modified: Wed Jul 15 16:05:01 CEST 2009
Valid CSS!