| Datum |
Stoff im Lehrbuch |
Material |
|
25.04.06
| Kap 2.1 (Insertion sort)
|
|
|
27.04.06
| Mergesort, O-Notation, Master-Methode
|
|
|
02.05.06
| Beispiele zur Asymptotik, Matrizenmultiplikation nach Strassen, Heapsort
|
|
|
04.05.06
| Prioritätsschlangen, Quicksort, randomisierter Quicksort, untere Schranke für Sortieren mit Vergleichen
|
|
|
09.05.06
| Obere und untere Schranken für Bestimmung
des Maximums, und des Maximums und Minimums
simultan. Selektion: Problemstellung, Probabilistischer und
deterministischer Algorithmus zur Selektion in erwarteter
bzw. worst-case Linearzeit.
|
|
|
11.05.06
| Dynamische Mengen,
Realisierung durch binäre
Suchbäume. Wdh.: Einfuegen, Loeschen in Binaeren Suchbaeumen, Links- und Rechtsrotation.
Definition Rot-Schwarz-Bäume.
|
Java-Applet, um interaktiv Rot-Schwarz-Bäume zu bauen
|
|
16.05.06
| 2log(n+1) obere Schranke an die Höhe von Rot-Schwarz-Baeumen
Einfügeoperation. Loeschoperation begonnen.
|
|
|
18.05.06
| Loeschen aus Rot-Schwarz Baeumen. AVL-Baeume (nur kursorisch).
B-Baeume. Definition, Suchen, Einfuegen. Das Loeschen aus Rot-Schwarz-Baeumen wurde in der Vorlesung nicht vollstaendig behandelt und ist im Detail weder pruefungs- noch klausurrelevant.
|
|
|
23.05.06
| Loeschen aus B-Baeumen, Rot-Schwarz-Baeume als spezielle B-Baeume. Die Operationen auf B-Baeumen werden in der Vorlesung anders (einfacher) dargestellt als im Lehrbuch. Man findet sie z.B. im Informatikduden. Hashtabellen, Kollisionsbehandlung durch Verkettung, probabilistische Analyse unter der Uniform Hashing Annahme (Gleichverteilung der Zufallsvariablen h(k))
|
|
|
30.05.06
| Hashfunktionen (Divisions-, Multiplikationsmethode), Offene Adressierung (Lineares, Quadratisches Sondieren, Clusterbildung, Double Hashing)
|
|
|
01.06.06
| Probabilistische Analyse der offenen Adressierung: Mittlere Suchdauer bei erfolgreicher/erfolgloser Suche unter der Uniform Hashing Annahme. Neues Kapitel: Allgemeine Entwurfs- und Optimierungsmethoden. Greedy Algorithmen. Greedyalgorithmus zur Auswahl von Aufgaben vorgestellt und korrekt bewiesen. Problemstellung Huffmancodes.
|
|
|
08.06.06
| Huffmanalgorithmus an Besipiel und Pseudocode. Korrekt bewiesen mit der allgemeinen Methode (Invariante: es ist moeglich, die aktuelle partielle Loesung zu einer optimalen Loesung fortzusetzen). Entwurfsmethode Dynamische Programmierung. Einfuehrendes Beispiel: Fibonacci rekursiv, mit Memo-Tabelle, mit dynamischer Programmierung. Anderes Beispiel: Matrix Kettenmultiplikation.
|
|
|
13.06.06
| Laengste gemeinsame Teilfolge und Editierdistanz durch Dynamische Programmierung.
Neues Thema: Amortisierte Komplexitaetsanalyse. Einfuehrendes Beispiel: Queue durch zwei Stacks. Aggregatmethode.
|
|
|
20.06.06
| Bankkontomethode, Potenzialmethode. Neues Thema: Die Union-Find Datenstruktur, Implementierung und Analyse.
|
|
|
22.06.06
| Union-Find Datenstruktur, Implementierung und Analyse. Evtl.: Graphalgorithmen: Breitensuche.
|
|
|
27.06.06
| Graphalgorithmen: Breitensuche zur Berechnung kuerzester Wege.
Tiefensuche mit Zeitstempeln. Klammerungseigenschaft, Klassifikation der Kanten.
|
|
|
29.06.06
| Verwendung der Tiefensuche zur Berechnung einer topologischen Sortierung und der starken Zusammenhangskomponenten (SCCs). Die Beweise sind hier aufgeschrieben. Minimaler Spannbaum, Motivation, Beispiel, Ueberblick Kruskal-Algorithmus.
|
|
|
04.07.06
| Kruskals Algorithmus, Prims Algorithmus. Einfuehrung zu kuerzesten Wegen in gewichteten Graphen. Negative Zyklen, Relaxoperation.
|
|
|
06.07.06
| Algorithmen von Dijkstra, Bellman-Ford. All pairs shortest path mit Matrizenmultiplikation.
|
|
|
11.07.06
| Algorithmus von Floyd-Warshall, Korrektheitsbeweis zu Algorithmus von Dijkstra.
Neues Thema Flussnetzwerke: Motivation, Problemstellung, Definition Fluss, Restnetzwerk.
|
|
|
13.07.06
|
Algorithmus von Ford-Fulkerson, Korrektheitsbeweis mit Max-Flow-Min-Cut Theorem.
Algorithmus von Edmonds-Karp. Naechstes Mal: Laufzeit von Edmonds-Karp, Anwendungen von Flussnetzwerken. Naechstes Thema: Schelle Fouriertransformation.
|
|
|
18.07.06
|
Laufzeit von Edmonds-Karp, Nichttermination von Ford-Fulkerson bei irrationalen Kapazitaeten. Anwendungen von Flussnetzwerken: Bipartites Matching (Buch);
Aufteilung von Bildern in Vorder- und Hintergrund.
Naechstes Mal: Schnelle Fouriertransformation.
|
|
Die Kapitelangaben beziehen sich auf das 
