DAP 2: Was wurde wann gemacht?

Stand 28 von 28 Vorlesungen sind vorüber

Nr.	Datum	Stoff
1	20.04.04	Einleitende Worte zur Vorlesung, anschließend im Skript bis ca. Seite 7 Mitte gekommen, also bis zum Divide-and-Conquer-Algorithmus für das Maxsummenproblem.
2	22.04.04	Von S.7 Mitte bis S. 12 Mitte im Skript, also: divide-and-conquer und dynamische Programmierung für das Maxsummenproblem, Turnierplan für MAXMIN-Problem angegeben und mit der unteren Schranke für die Mindestzahl an Spielen begonnen.
3	27.04.04	Die untere Schranke von ca. (3/2)n für das MAXMIN-Problem beendet. Rechnermodell RAM erklärt, uniformes und logarithmisches Kostenmaß, Beispiel für ein Programm, bei dem die beiden stark verschiedene Werte liefern, (Stichwort: iteriertes Quadrieren). Komplexitätsmaße Laufzeit und Platzbedarf erläutert sowie die "worst-case-Rechenzeit" und die "average-case-Rechenzeit". Das "Addierwerk" als Softwarelösung gezeigt und mit der Analysemethode "Direktes Zählen" analysiert. "Potenzialfunktion" definiert. Im Skript sind das: S. 12 Mitte bis S. 17 Mitte.
4	29.04.04	Mit Hilfe einer "Potenzialfunktion" die average-case-Taktzahl des Addierwerks analysiert. Ebenso die auf das Problem zugeschnittene Analyse vorgestellt. Randomisierte Algorithmen: bei diesen kann man die "durchschnittliche Laufzeit" auch auf die Zufallsentscheidungen beziehen. Größenordnungen ("die Groß-Oh-Notation") definiert und bewiesen, dass n^k = o(2^n). Wieviel größere Problemgrößen kann man bei bestimmten Laufzeiten in "erträglicher" Zeit angehen, wenn unser neuer Rechner 10mal schneller als der alte ist? Im Skript: S.17 Mitte bis 21 unten.
5	04.05.04	Unterschied zwischen polynomiellem/exponentiellem Wachstum betont. Begonnen mit grundlegenden Datenstrukturen: Listen/Arrays. Binäre Suche im geordneten Array als Pseudocode. Korrektheit bewiesen und die Laufzeit analysiert. Lineare Suche/geometrische Suche vorgestellt. Laufzeiten einiger grundlegender Operationen auf Listen/Arrays vorgestellt. Datenstrukturen für Mengen: Bitvektordarstellung und Listendarstellung. Diskutiert, wie man einfache Mengenoperationen entsprechend umsetzen würde. Laufzeiten dieser "analysiert"/angegeben. Begonnen mit wichtigen Graphdefinitionen. Im Skript: Def. 1.7.3 von Seite 20 sowie S. 22 bis S. 28 Mitte (bis zur Graddefinition).
6	06.05.04	Weitere grundlegende Graphdefinitionen: "Weg", "einfacher Weg", "Kreis", "azyklisch", "zusammenhängend", "stark zusammenhängend", "(starke) Zusammenhangskomponenten". Bäume: ungerichtet/gerichtet. Tiefe eines Knotens/eines Baums, "Vater", "Geschwister", "Vorgänger/Nachfolger", "(vollständ.) k-ärer Baum", Anzahl Knoten in diesem gezählt. Durchlaufreihenfolgen Präorder, Postorder, Inorder definiert. Grundlegende DS für Graphen: Inzidenzmatrix, Adjazenmatrix, Adjazenzliste. Vorteile/Nachteile dieser diskutiert. Topologische Sortierung: Motivation, Definition, bewiesen, dass bei kreisfreiem Graphen Knoten mit Ein-/Ausgangsgrad 0 existieren. Grobskizze des Algorithmus für das topologische Sortieren angegeben. Im Skript: S. 28 Mitte bis S. 31 oben sowie die Bäume von S. 33 Mitte bis S 35 oben vorgezogen.
7	11.05.04	Wg. Anfrage noch einmal die starken Zusammenhangskomponenten in gerichteten Graphen erklärt. Korrektheit des Algorithmus für das Topologische Sortieren bewiesen. Implementierung mit Stack vorgestellt. Beispielgraph topologisch sortiert. Laufzeit des Algorithmus als linear analysiert. Mathematischen Hintergrund beleuchtet: Partielle Ordnung definiert, Potenzmenge als Beispiel. Wie kann man partielle Ordnung als Graphen darstellen. Beweis, dass dieser kreisfrei ist und man somit auch partiell geordnete Mengen topologisch sortieren kann. Grundlegende Graphalgorithmen: DFS am Beispiel, erklärt, wie er in T- und B-Kanten einteilt. Pseudocode für DFS auf ungerichteten Graphen vorgestellt. Analyse des Pseudocodes: Laufzeit ist O(n+m), also linear. Begonnen mit dem Beweis, dass jede Kante genau einmal als T- oder B-Kante klassifiziert wird. Im Skript: S. 31 oben bis S. 33 Mitte sowie S. 36 unten bis S. 38 oben.
8	13.05.04	Beweis beendet, dass jede Kante genau einmal klassifiziert wird. BFS-Algorithmus für ungerichtete/gerichtete Graphen in Pseudocode vorgestellt, Beispiel vorgeführt. Anschließend DFS bei gerichteten Graphen erläutert. Genau motiviert, warum man nun 4 Kantenarten hat. Dann erklärt, wie man die Kanten mit Hilfe von num und alpha klassifizieren kann. Pseudocode für DFS auf gerichteten Graphen angegeben. Beispiel vorgeführt und Laufzeit begründet. Eigenschaft: Bei ungerichtetem Graph gilt (wenn man DFS verwendet): Kreis vorhanden genau dann, wenn es eine Back-Kante gibt. Laufzeit O(n+m) bzw. O(n) begründet. Datenstrukturen für Intervalle: Zu unterstützende Operationen angegeben. Einfache Lösungen hinsichtlich Query/Preprocessing-Zeiten analysiert. Segmentbäume definiert. Erklärt, welche Komponenten in den einzelnen Knoten enthalten sind. Tiefe des Baumes als gaussoben(log n) begründet, bewiesen, dass Segmentbaum 2n-1 Knoten hat. Im Skript: S. 38 oben bis S. 42 unten.
9	18.05.04	Segmentbäume: Aufbau des Baums in Linearzeit, Algorithmus für query und update vorgestellt, die Laufzeit von query analysiert: Wann heißen Knoten bündig, wieviele Knoten werden in Bäumen der Tiefe d maximal aufgesucht. Laufzeit von update. Die Laufzeiten mit den trivialen Algorithmen verglichen. Begonnen mit Datenstrukturen für Partitionen (=UNION-FIND). Die trivialen Verfahren vorgestellt (Array / Listen) sowie das "intelligentere", das mit Listen UND Array arbeitet. Beendet mit der Feststellung, dass hierbei die Laufzeit von UNION(A,B) durch die Kardinalität der kleineren Menge bestimmt ist. Im Skript sind das die Seiten 43 oben bis 46 Mitte.
-	20.05.04	Feiertag
10	25.05.04	UNION-FIND: Die Laufzeit der Datenstruktur mit schnellen FINDs analysiert. ('Buchhaltermethode') Beispiel, dass Analyse fast optimal. Datenstruktur für schnelle UNIONs auch mit Pseudocode vorgestellt. ("Baumorientierte Datenstruktur"). Tiefe der auftretenden Bäume analysiert. Daraus ergibt sich die Laufzeit. Pfadkomprimierung erklärt, auch anhand von Pseudocode. Die Laufzeit für die DS mit Pfadkomprimierung angegeben (log* n und Z(n) definiert). Anwendung von UNION-FIND: Spannbäume definiert, das Problem "minimale Spannbäume" erläutert. Beispiele. Algorithmus von Kruskal erklärt und am Beispiel vorgeführt. Begonnen mit dem Beweis seiner Korrektheit: Bewiesen, dass ein *Spannbaum* berechnet wird. Für den Beweis der Minimalität des Spannbaums das entscheidende Lemma erklärt. Begonnen mit dem Beweis des Lemmas. Im Skript sind das: S. 46 Mitte bis S. 51 mitte.
11	27.05.04	Korrektheitsbeweis zum Algorithmus von Kruskal beendet: Lemma über die Erweiterbarkeit von Kantenmengen zu minimalen Spannbäumen. (Siehe auch meine "Ergänzungen" auf der Webseite.) Implementierung mit Hilfe von UNION-FIND-Datenstrukturen erklärt und die Laufzeit analysiert. Begonnen mit Datenstrukturen für boolesche Funktionen: Einfache Bsp. für boolesche Funktionen, Liste von zu unterstützenden Operationen aufgezählt und die jeweiligen Operationen definiert und erklärt: Auswertung, Gleichheitstest, Synthese, Erfüllbarkeitstest, Ersetzung durch Funktionen mit Spezialfall Ersetzung durch Konstanten, Quantifizierung, Minimierung. Pi-OBDDs: "Syntax und Semantik" dieser erklärt. Am Beispiel OBDD für eine Funktion f konstruiert. Im Skript sind das die Seiten: 51 Mitte bis 54 Mitte.
12	01.06.04	Erklärt, wie man die Operationen Auswertung, Ersetzung durch Konstanten, Erfüllbarkeitstest, Minimierung durchführt: Reduktionsregeln Verschmelzungs- und Eliminationsregel erklärt. Satz "OBDD ist minimal genau dann, wenn...". Synthese: Kreuzproduktkonstruktion allgemein beschrieben, dann die auf DFS im Kreuzprodukt-OBDD basierende Synthese, unique-table und computed-table erklärt. (Hierzu gibt es auch einen Aufschrieb unter "Ergänzungen" im Netz.) Pseudo-Code für die Synthese vorgestellt. Die fehlenden Operationen auf OBDDs realisiert. Erklärt, dass man damit bei Synthese gut Operationen für Einfügen und Suchen brauchen kann. Begonnen mit Kapitel "Dynamische Dateien". Erklärt, was man unter Schlüsseln versteht. Im Skript: S. 54 Mitte bis S. 61 oben.
13	03.06.04	Operationen für Dictionaries aufgelistet, Hashing: Universum/Hashfunktion erklärt. Geschlossenes Hashing: Anhand von Geburtstagsparadoxon erklärt, warum man "mit Kollisionen leben muss". Suchen/Einfügen bei Hashing prinzipiell erklärt und die einzelnen Testreihenfolgen für die folgenden Strategien erklärt: Lineares Sondieren, quadratisches Sondieren, multiplikatives Sondieren. Gezeigt, dass beim multiplikativen Sondieren alle Zellen durchlaufen werden. Doppeltes Hashing. Primärkollisionen/Sekundärkollisionen. Am Beispiel klar gemacht, warum bei Linearem Sondieren Cluster entstehen. Analyse für "ideales Hashing" durchgeführt: Die durchschnittliche Anzahl an besuchten Zellen beim Einfügen in Hashtabelle analysiert. Im Skript: S. 61 oben bis 66 Mitte.
14	08.06.04	Formel für Einfügezeiten in Abhängigkeit von der Auslastung. Analyse der erfolgreichen Suche bei geschlossenem Hashing. Dabei den Wert der m-ten Harmonischen Zahl durch ln m abgeschätzt. Methode für die Abschätzung vorgeführt. Offenes Hashing erklärt sowie die Anzahl Vergleiche beim erfolg(reichen/losen) Suchen analysiert. Variante des geschlossenen Hashings mit c Elementen pro Hashwert. Binäre Suchbäume: Korrekte Definition gezeigt sowie häufig gehörte falsche Definition widerlegt. Suchen im Binärbaum/Einfügen/Löschen im Pseudocode bzw. an Beispielen. Begonnen mit der Analyse zur Frage "Wie lange dauert eine Suche im Durchschnitt, wenn wir mit zufälligen Einfügereihenfolgen zufällige Bäume bekommen und dann zufällige Suchanfragen stellen?" Im Skript: S. 66 Mitte bis 69 unten sowie S. 72 ab Zeile 7. Außerdem Skript-Anhang S. 153.
--	10.06.04	Feiertag
15	15.06.04	T(n) analysiert (aus der man die durchschnittliche Suchzeit ermitteln kann.) Rekursionsgleichung aufgestellt. Auf Rekursionsgleichung für eine andere Folge s(n) zurückgeführt, s(n) analysiert. Ergebnis: Durchschnittliche Suchzeit ist ca. 1.386 log n. Begonnen mit 2-3-Bäumen. Definition, Visualisierung. Suchen in diesen. Lemma, dass ihre Tiefe Theta(log n) ist, bewiesen. Einfügealgorithmus vorgestellt (inkl. "Reparaturroutine"). Am konkreten Beispiel diesen vorgeführt. Im Skript: 70 oben bis 75 unten (ohne Seite 72 ab Zeile 7, denn das war ja schon in der letzten Vorlesung dran.)
16	17.06.04	Löschen in 2-3-Bäumen. Algorithmus erklärt und am Beispiel vorgeführt. Laufzeit erklärt. Erwähnt, dass CONCATENATE/SPLIT auch in O(log n) durchführbar sind. Allgemeine B-Bäume motiviert und definiert. Tiefenabschätzung angegeben, Insert/Delete erklärt. Begonnen mit AVL-Bäumen. Definition. Abschätzung für die Tiefe bewiesen. Mit Erklärung der Einfügeoperation begonnen: Wie speichert man den Suchpfad ab. Im Skript: S.75 unten bis S. 85 Mitte - dabei allerdings das Unterkapitel 3.4.5 (CONC und SPLIT bei 2-3-Bäumen) ausgelassen, das damit auch nicht klausurrelevant ist.
17	22.06.04	AVL-Bäume: Operationen Suchen, Einfügen. Dabei die zu benutzenden Rotationen vorgeführt und genau analysiert, wie die Balancegrade zu aktualisieren sind und wann man mit der Aktualisierung stoppen kann bzw. wann nicht. Beispiel für Einfügen bei AVL-Bäumen, anschließend Löschen im AVL-Baum erklärt (inkl. Beispiel) und wie dann die Balancegrade aktualisiert werden müssen und wann die Aktualisierung nach oben hin weiterlaufen muss. Begonnen mit Skiplisten: Suchen und Einfügen beschrieben, beide auch am Beispiel, Im Skript: S. 85 Mitte bis S. 92 Mitte.
18	24.06.04	Löschen in Skiplisten erklärt. CONCATENATE und SPLIT schematisch erklärt. Erwartete Höhe eines neu eingefügten Blocks ausgerechnet, H(n) und Z(n) definiert und den Satz angegeben (inklusive Beweis), der die erwartete Höhe einer Skipliste abschätzt sowie die erwartete Anzahl der Zeiger. Daraus die erwartete Laufzeit von O(log n) hergeleitet. Begonnen mit Sortieren: Allgemeine Definitionen der Begriffe intern/extern, in situ. Im Skript: 91 Mitte bis 96 Mitte.
19	29.06.04	Sortieren: Allgemeine Definitionen der Begriffe (also intern/extern, in situ, stabil etc.). Insertionsort, Analyse des worst case und average case bei Insertionsort. Den average case dabei (siehe Folien) etwas anders bewiesen als im Skript. Mergesort erklärt (Merge und die rekursiven Aufrufe) und Laufzeit analysiert: Laufzeit für Merge begründet und Rekursionsgleichung aufgestellt für die Anzahl der wesentlichen Vergleiche bei Mergesort. Lösung (wie bei Maxsummenproblem) O(n log n). Adaptive Variante, die gerne extern verwendet wird, vorgestellt. Mit Quicksort begonnen: Allgemeine Eigenschaften vorgestellt. Idee des Algorithmus. Gewünschten Effekt der Prozedur "partition" erklärt. Quicksort in der Standardvariante im Pseudocode gezeigt. Begonnen, zu erklären, wie Partition funktioniert: die beiden Invarianten erklärt, die beim Ablauf der Prozedur erhalten bleiben. Im Skript: S. 96 bis 100 unten.
20	01.07.04	Quicksort: Partitionphase, 2 Regeln, die die Invarianten erhalten. Vorgehen, wenn beide nicht anwendbar. Am Beispiel "partition" vorgeführt. Erklärt, warum bei "partition" n-1 Vergleiche. Laufzeitanalyse quicksort: worst case. Zerlegungsstrategie 1 erklärt. Durchschnittliches Verhalten von quicksort: Rekursionsgleichung aufgestellt, gelöst durch Vergleich mit schon bekannter Rekursionsgleichung. Best case analysiert. Zerlegungstrategie 2 erklärt. worst-case davon analysiert, bei average-case nur das Resultat genannt. Zerlegungsstrategie 3 und 4 erklärt und das Ergebnis zu "average case": Nun Durchschnitt über die Zufallsausgänge. Heapsort: Heap definiert. Darstellung als Baum. Heap Creation und Selection erklärt. Reheap erklärt in drei Varianten. Pseudocode für alle Prozeduren. Skript: 101 bis 107 Mitte.
21	06.07.04	Korrektheit von reheap dargelegt. Am Beispiel die Heap Creation Phase vorgeführt. Tiefensumme der Bäume in der Creation und Selection Phase analysiert. Die sich daraus ergebenden worst-case-Laufzeiten erklärt. Genauere Analysen bei den bottom-up-Varianten erklärt bzw. im Endergebnis vorgestellt. Definition von *allgemeinen* Sortierverfahren. Entscheidungsbaum erklärt und am konkreten Beispiel erläutert. Untere Schranken für worst-case und average-case-Vergleichszahl. Bucketsort, verallgemeinerter Bucketsort mit Laufzeit und Korrektheitsbeweis. Verallgemeinerten Bucketsort am Beispiel erläutert. Auswahlproblem: Problem definiert. Im Skript sind das: 107 Mitte bis 113 oben.
22	08.07.04	Auswahlproblem: quickselect beschrieben und die Analyse der durchschnittlichen Laufzeit vorgeführt. Erklärt, wie sich die Rekursionsgleichung für V(n) ergibt. Gezeigt, wie man V(n) nach oben durch 4n abschätzen kann. Sortieren auf Parallelrechnern bzw. auf Parallelrechnermodell: Zunächst untere Schranke 2 log n -O(1), dann Batchermerge und Batchersort erklärt und dabei sehr genau argumentiert, dass Batchermerge korrekt ist. Anschließend die Rekursionsgleichungen für die Anzahl Vergleiche bzw. paralleler Rechenzeit aufgestellt und zu diesen dann die Endergebnisse hingeschrieben, dabei grob skizziert, wie man diese verifizieren kann, wenn man möchte. Anschließend Vergleichsnetzwerke definiert. Im Skript: 113 oben bis 116 unten.
23	13.07.04	Vergleichsnetzwerke und Sortiernetzwerke definiert und bildlich gezeigt, wie man Batchersort als Sortiernetzwerk auffassen kann. Anschließend klar gemacht, dass auf Hardwareebene mit UND/ODER-Operationen Batchersort sehr einfach umzusetzen ist. Begonnen mit Kapitel 5: Entwurfsmethoden für Algorithmen, welche Situationen treten üblicherweise bei Greedyalgorithmen auf. Greedyalgorithmen für Münzwechselproblem, TSP. Dabei jeweils Beispiele gegeben, auf denen der Greedyalgorithmus sehr schlechtes Verhalten an den Tag legt. KP, verallgemeinertes KP: Bewiesen, dass Greedyalgorithmus für das KP beliebig schlecht sein kann, aber auf dem verallgemeinerten KP optimale Lösungen berechnet. Bin Packing Problem definiert und Algorithmen First Fit und Best Fit vorgestellt. Im Skript: 116 unten bis 121 unten.
24	15.07.04	Analyse des "Gütefaktors 2" für die produzierten Lösungen von First Fit und Best Fit. Dynamische Programmierung: Prinzip erklärt und mit einer Reihe von Beispielproblemen begonnen: Rucksackproblem: Bellmansche Optimalitätsgleichung begründet, Laufzeit analysiert, erklärt, wie man nicht nur den optimalen Nutzenwert, sondern auch die optimale Bepackung selbst erhält. Bioinformatik: Das Problem des optimalen Alignments erklärt, Bellmansche Optimalitätsgleichung aufgestellt. Rechenzeit für das Berechnen eines optimalen Alignments "analysiert". Im Skript: 121 unten bis 126 Mitte.
25	20.07.04	APSP: mit Hilfe der dynamischen Programmierung gelöst, Laufzeit analysiert sowie diskutiert, wie man speicherplatzsparend die kürzesten Wege (und nicht nur deren Kosten) berechnet. Algorithmus von Dijkstra: Algorithmus beschrieben, am Beispiel vorgeführt, Korrektheitsbeweis fast komplett. Im Skript: 126 Mitte bis 128 unten.
26	22.07.04	In dieser Vorlesung wurde ich wg. eines auswärtigen Vortrags von Oliver Giel vertreten. Korrektheitsbeweis für den Algorithmus von Dijkstra komplettiert. Implementierungsdetails für den Dijkstra-Algorithmus: Einmal die O(n^2)-Variante, einmal die O(m*log n+n)-Variante, wobei m=|E|. Beschrieben, wie man die V-Werte für die Wege mit berechnet. Branch-and-Bound-Paradigma: allgemeine Bemerkungen sowie die 5 typischen Module beschrieben. Diese dann detailliert am Rucksackproblem-Beispiel erläutert. Schließlich den B&B-Algorithmus an einem konkreten Beispiel vorgeführt. Im Skript sind das: 128 unten bis 134 Mitte. Allerdings wurde ein anderes (kleineres) Beispiel als das im Skript gewählt (siehe "Folien").
27	27.07.04	Analyse der Laufzeit bei rekursivem Algorithmus der Form "a Teilprobleme der Größe n/b, Extraarbeit c*n" durchgeführt. Gezeigt, wie man dann (wenn man mag) auch die Rekursionsgleichung mit Extraterm "+d" lösen kann. Anschließend Strassens Matrixmultiplikationsalgorithmus als einen vorgestellt, wo es zu "7 Teilproblemen der Größe N/4" kommt, und der die Schulmethode schlägt. Anschließend die Analyse von Spielbäumen und das Alpha-Beta-Pruning erklärt. Im Skript: S. 134 Mitte bis 139 oben, wobei ich in der Vorlesung nur auf die Größenordnung der Laufzeit bei Strassen abgehoben habe, nicht so sehr auf die exakte Anzahl an Operationen.
28	29.07.04	Beispiel für Alpha-Beta-Pruning. Anschließend "Klausurvorbereitung". Im Skript: S. 139.