| |
| |
Algorithmen und Datenstrukturen
| 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).
| | 23, 24 Einf, 24.3
|---|
| 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.
|
Martin Hofmann
Last modified: Wed Jul 15 16:05:01 CEST 2009
|
|
|
|