| Nr. | Datum | Stoff |
| 1 | 22.04.03 | Im Skript bis S. 7 Mitte gekommen. (Der triviale/normale Algorithmus für das Maxsummenproblem, mit dem Divide-and-Conquer-Algorithmus begonnen.) |
| 2 | 24.04.03 | Von S.7 Mitte bis S. 11 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 | 29.04.03 | Zu Beginn (noch mal) den Pseudocode zum
Divide-and-conquer-Algorithmus für das Maxsummenproblem aufgelegt.
Die untere Schranke von ca. (3/2)n für das MAXMIN-Problem beendet.
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?
Unterschied polynomiell/exponentiell, begonnen mit dem
Rechnermodell RAM. Im Skript sind das: S. 11, S. 17 Mitte bis 20 unten, Seite 12. (Die Reihenfolge in der Vorlesung ist gegenüber dem Skript wg. des Übungszettels leicht geändert). |
| - | 01.05.03 | Maifeiertag |
| 4 | 06.05.03 | RAM-Modell 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 den
Analysemethoden "Direktes Zählen" und "Potenzialfunktionen"
die average-case-Taktzahl des Addierwerks analysiert. Das heißt im Skript: S. 13, 14, 15, 16 plus das Beispiel "Iteriertes Quadrieren", das nicht im Skript enthalten ist, zu dem aber ein Aufschrieb unter dem Link "Begleitmaterial" abrufbar ist. |
| 5 | 08.05.03 | Die letzte Analysemethode für das Addierwerk vorgestellt (via Bitflips),
diskutiert, wie bei randomisierten Algorithmen die Laufzeit definiert ist.
Grundlegende Datenstrukturen: Arrays, Listen: welche Laufzeiten haben
verschiedene Operationen auf ihnen? Binäre Suche ausführlich in Pseudocode
vorgestellt und Korrektheit/Laufzeit analysiert. (Siehe auch
den Aufschrieb unter "Zusätzliches Material").
Geometrische Suche skizziert. Begonnen mit den Definitionen
von ungerichteten und gerichteten Graphen, Grad, Ingrad, Outgrad, etc. Im Skript sind das: S.21-26 Mitte sowie die erste Hälfte von Seite 35. --Ich habe die Definition von Graphen vorgezogen, weil ich denke, dass man die "topologische Sortierung" (die in der nächsten Vorlesung an der Reihe ist) mit Hilfe von Graphen besser verstehen kann. |
| 6 | 13.05.03 | Definitionen beendet: "Kreise", "azyklisch", "kreisfrei", Motivation
für topologisches Sortieren. Bewiesen, dass in kreisfreiem Graphen
immer Knoten mit Eingangsgrad 0 und Knoten mit
Ausgangsgrad 0 existieren, dass
Knoten mit Eingangsgrad 0 in topologischer Sortierung vorne stehen können,
daraus den Algorithmus Topsort (siehe auch Begleitmaterial) abgeleitet.
Algorithmus am Beispiel vorgeführt sowie seine Laufzeit analysiert.
Mathematischen Hintergrund beleuchtet: vollständige/partielle Ordnung,
Beispiele für diese gegeben, erklärt, wie man diese als gerichteten
Graphen umsetzen kann.
Definitionen: Bäume gerichtet/ungerichtet, "Blatt", "innerer Knoten", "Tiefe
eines Knotens", "Tiefe eines Baumes".
Im Skript sind das die Seiten 26 Mitte bis 30 Mitte sowie S. 31 unten
bis 32 "ein Drittel".
Wer genau hinschaut, wird feststellen, dass der TopSort-Algorithmus
dort im Prinzip genau so funktioniert, wie der in der Vorlesung
vorgestellte, a(i) entspricht dort dem "indeg(i)" aus der Vorlesung und die "minimalen Elemente" der Ordnung sind die Elemente mit Eingangsgrad 0 im gerichteten Graphen. |
| 7 | 15.05.03 | Definitionen k-ärer Baum, vollständiger k-ärer Baum, Anzahl
Knoten in diesem analysiert, Implementierung von Bäumen auf
dem Rechner, Durchlaufreihenfolgen Prä-/Post-/Inorder erklärt,
Datenstrukturen für allgemeine Graphen: Inzidenz-/Adjazenzmatrix,
Adjazenzliste, Def. der Äquivalenzrelationen, die
für Definition der (starken)
Zusammenhangskomponenten gebraucht werden. Tiefendurchlauf (DFS)
in algorithmischer Notation und an Beispiel erklärt: Einteilung
der Kanten in Tree-/Backkanten. Im Skript sind das: S: 32-37 oben. Dabei wurden aber nur einige, nicht alle, der Datenstrukturen für die Baumimplementierung (S.33) angesprochen. |
| 8 | 20.05.03 | Analyse Laufzeit ungerichtetes DFS, gezeigt, dass jede Kante
genau einmal klassifiziert wird. BFS-Algorithmus im gerichteten
Fall skizziert.
DFS für gerichtete Graphen: Rahmenprogramm sowie die
4 Fälle "C, F, T, B" für die Kanteneinteilung beschrieben.
Beispiel gerechnet. Kreistest für ungerichtete Graphen via
"B ungleich leere Mege". Datenstrukturen für Mengen skizziert:
Bitvektordarstellung, Listendarstellung und wie man z.B.
Vereinigung darauf realisiert.
Begonnen mit "Datenstrukturen für Intervalle": die trivialen
Implementierungen hinsichtlich Laufzeit/Platzbedarf analysiert,
begonnen mit Segmentbäumen.
Im Skript sind das: (Mengen von S. 30/31 nachgeholt), 37-41 Mitte. |
| 9 | 22.05.03 | Segmentbäume: Definition, Aufbau des Baums in Linearzeit, Algorithmus
für query und update vorgestellt, die Laufzeit von query und update
analysiert, 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 41 bis 45 Mitte. |
| 10 | 27.05.03 | Mit der Buchhaltermethode bewiesen, dass
Laufzeit O(nlogn + m) bei UNION-FIND mit Arrays und Listen.
Baumorientierte Datenstruktur vorgestellt sowie Laufzeit
von O(n +mlogn) bewiesen, dann Pfadkomprimierung erklärt.
Jeweils eine einfache Implementierung dieser Datenstrukturen
in algorithmischer Notation vorgeführt.
Das Ergebnis über die Laufzeit bei Pfadkomprimierung
(mit der Funktion log^* n) genannt.
Begonnen mit Datenstrukturen für boolesche Funktionen: Bsp.
für einfache boolesche Funktionen genannt, warum stellt man
boolesche Funktionen nicht als Mengen dar (Stichwort f-1(1))?
Begonnen mit einer Auflistung von Operationen, die eine Darstellung
von booleschen Funktionen unterstützen soll: 1) Auswertung bis
5) Ersetzung durch boolesche Funktionen. Im Skript sind das: Seite 45 Mitte bis Seite 48 Mitte. (Die zusätzlichen Folien erscheinen noch unter Extramaterial). |
| -- | 29.05.03 | Feiertag |
| 11 | 03.06.03 | Operationen Ersetzung durch Funktionen/Konstanten, wie erreicht
man ersteres durch zweites? Operation Quantifizierung, Operation Minimierung
erklärt. OBDD-Definition: Syntax und Semantik, Bsp.-OBDD für die
Funktion "Anzahl Einsen durch 3 teilbar".
Gezeigt, wie die einzelnen Operationen aus der Wunschliste auf OBDDs
realisiert werden können: Auswertung, Ersetzung, Erfüllbarkeit, Minimierung,
die Kreuzproduktkonstruktion für die Synthese vorgeführt, auch am Beispiel.
Im Skript sind das die Seiten: 48 Mitte bis 52 unten, dabei das Modell "Schaltkreis" auf S. 49 ausgelassen. Die Realisierung der Syntheseoperation mit "computed-table" und "unique-table" wird in der nächsten Vorlesung vorgestellt. |
| 12 | 05.06.03 | Synthese beendet: Dabei die Implementierung mit unique-table und computed-table erklärt. (Siehe Extraaufschrieb). Begonnen mit dem Kapitel "Dynamische Dateien": Was heißt "Schlüssel", welche Operationen soll ein Dictionary unterstützen. Begonnen mit Hashing. Was ist eine Hashfunktion, was ist das Universum, Forderungen an eine Hashfunktion, begonnen mit "geschlossenem Hashing". Kollisionen: Wie das "Geburtstagsparadoxon" zeigt, warum wir mit Kollisionen auch schon bei wenigen Daten umgehen müssen. Wie sieht die Kollisionsbehandlung aus: insert und search in algorithmischer Notation (unter Benutzung der Testfunktionen test_i), lineare Sondierung und quadratische Sondierung erklärt, auch am Beispiel vorgeführt, multiplikatives Sondieren definiert und die Aussage erwähnt, dass alle Elemente von 0 bis M-1 bei dieser durchlaufen werden. Beweis dazu in der nächsten Vorlesung. |
| 13 | 10.06.03 |
Beweis zur multiplik. Sondierung. Beispiel zu multiplik. Sondierung.
Doppeltes Hashing, Primär- und Sekundärkollisionen definiert,
bei linearer Sondierung am Beispiel gezeigt, dass diese zu Clustering
führen. Ideales Hashing erklärt, die durchschnittliche Anzahl an
besuchten Zellen für Einfügen und erfolgreiche Suche analysiert
(dabei Abschätzung für die harmonischen Zahlen aus dem Anhang vorgeführt).
Variante von geschlossenem Hashing, offenes Hashing. Analyse
der Vergleiche bei erfolgloser und erfolgreicher Suche mit
offenem Hashing. Das sind S. 56 Mitte bis S. 59 Mitte im Skript sowie S. 145 Mitte bis 145 Ende (im Anhang). |
| 14 | 12.06.03 | Definition Suchbäume, Operationen Einfügen, Suchen, Löschen in
diesen erklärt, Einfügen und Suchen dabei auch mit "Pseudocode".
Beispiele vorgeführt. Dann: Analyse der
durchschnittlichen Suchlaufzeit in einem zufällig entstandenen
Suchbaum: T(Pi) definiert und erklärt, T(n) definiert und erklärt:
T(n)/n ist die durchschnittliche Suchzeit, Rekursionsgleichung
für T(n) aufgestellt und exakt analysiert. Fazit gezogen:
Suche in einem zufälligen Baum dauert durchschnittlich ca.
1.386 log n, was nicht viel schlechter ist als die durchschnittliche
Suchzeit im vollständig ausgeglichenen Baum. Im Skript: S. 59 Mitte bis S.65 oben. |
| 15 | 17.06.03 |
2-3-Bäume: Definition, anschauliche Skizze dazu, Beweis, dass Tiefe zwischen ca.
0.63 log n und log n liegt, Suche in 2-3-Baum beschrieben,
Einfügen in 2-3-Baum erklärt, anschließend Beispiel Einfügen, dann
Löschen in 2-3-Baum erklärt, gefolgt von Beispiel, in dem gelöscht wird.
CONCATENATE und SPLIT bei 2-3-Bäumen ausgelassen, (das ist also auch nicht
klausurrelevant). Definition von B-Bäumen (auch bekannt
als Bayer-Bäume). Im Skript entspricht das den Seiten 65-72 oben sowie 74 Mitte bis 75 oben. Dabei habe ich bei der Erklärung der Operationen aber auf die Skizzen aus dem Anhang, S. 146 bis 149 zurückgegriffen, weil diese meiner Meinung nach ein wenig anschaulicher sind. |
| -- | 19.06.03 | Feiertag |
| 16 | 24.06.03 | Operationen Einfügen und Löschen auf allgemeinen B-Bäumen erläutert.
Begonnen mit AVL-Bäumen. Definition.
Analyse, dass ihre Tiefe durch ca. 1.44 log n beschränkt ist.
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. Im Skript: S. 74 Mitte bis 79 unten. |
| 17 | 26.06.03 |
Beispiel für Einfügen bei AVL-Bäumen, anschließend Löschen im AVL-Baum
erklärt 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, anschließend Löschen, CONCATENATE und SPLIT
schematisch erklärt. Erwartete Höhe eines neu eingefügten Blocks
ausgerechnet, H(n) und Z(n) definiert und mit dem
Satz/Beweis begonnen, der
die erwartete Höhe einer Skipliste abschätzt sowie
die erwartete Anzahl der Zeiger. Im Skript: 79 unten bis 85 Mitte. |
| 18 | 01.07.03 | In dieser Vorlesung wurde ich wegen eines auswärtigen
Vortrags von Oliver Giel vertreten.
Inhalt der Vorlesung: Analyse der Skiplisten beendet. Begonnen mit Sortieren:
Allgemeine Definitionen der Begriffe (also intern/extern, in situ, stabil etc.).
Insertionsort, Analyse des worst case und
average case bei Insertionsort. Mergesort erklärt und analysiert.
Im Skript: S. 85 Mitte bis 92 Mitte. |
| 19 | 03.07.03 | Quicksort: Rahmenprogramm in algorithm. Notation, Partition erklärt und
in algorithm. Notation, Beispiel für Ablauf von Partition/Quicksort vorgeführt,
Analyse worst-case-Laufzeit, best-case-Laufzeit skizziert,
die vier Zerlegungsstrategien vorgestellt, average-case-Analyse für Strategie
1 durchgeführt, worst-case-Laufzeit für Strategie 2 und average-case-Analyse für
Strategie 2: die Rekursionsgleichung aufgestellt und begründet, wie sie sich
ergibt. Diese dann aber nicht gelöst, sondern nur das Endergebnis, also
die Lösung genannt.
Im Skript: 92 Mitte bis 96 oben. |
| 20 | 08.07.03 | Average-case-Aussage zu Zerlegungsstrategien 3 und 4.
Heapsort: Definition Heap, Sichtweise des Arrays als Baum,
Heap Creation Phase, Heap Selection Phase, reheap als
Pseudocode. Vorgestellt in den Varianten "klassisch" bzw.
"Pfadsuche mit binärer Suche" und "Pfadsuche mit linearer Suche".
Aussage über worst-case Laufzeiten bei den Varianten.
Begonnen mit Unterkapitel "Untere Schranken für allgemeine
Sortierverfahren": Definition von *allgemeinen* Sortierverfahren.
Im Skript: 96 oben-100 unten. |
| 21 | 10.07.03 | Untere Schranken für worst-case und average-case-Vergleichszahl
beendet. Bucketsort, verallgemeinerter Bucketsort.
Auswahlproblem: quickselect beschrieben und mit der Analyse begonnen:
Erklärt, wie sich die Rekursionsgleichung für V(n) ergibt.
Ausrechnen dieser in der nächsten Vorlesung.
Im Skript: 100 unten-104 unten. |
| 22 | 15.07.03 | Abschätzung der erwarteten Laufzeit 4n bei quickselect beendet.
Sortieren auf Parallelrechnern: 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. Rechenzeit auf Parallelrechnern aufgestellt
und zu diesen dann die Endergebnisse hingeschrieben, dabei grob skizziert,
wie man diese verifizieren kann, wenn man möchte.
Anschließend Sortiernetzwerke definiert und bildlich skizziert,
wie man Batchersort als Sortiernetzwerk auffassen kann.
Begonnen mit Kapitel 5: Entwurfsmethoden für Algorithmen,
welche Situationen treten üblicherweise bei Greedyalgorithmen auf. Im Skript sind das: S. 105 oben bis 109 unten. |
| 23 | 17.07.03 |
Greedyalgorithmen für Münzwechselproblem, TSP, KP, verallgemeinertes KP,
Bin Packing Problem (First Fit und Best Fit) jeweils analysiert bzw.
Beispiele gegeben, bei denen die produzierte Lösung beliebig
schlecht ist. Minimale Spannbäume definiert, Algorithmus von Kruskal
beschrieben und mit dem Beweis begonnen, dass dieser immer
optimale Lösungen berechnet.
Im Skript sind das: S. 109 unten bis 114 Mitte.
|
| 24 | 22.07.03 |
Algorithmus von Kruskal: Korrektheitsbeweis beendet. Implementierung mit UNION-FIND
diskutiert. 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.
Im Skript sind das: S. 114 Mitte bis S. 118 Mitte.
|
| 25 | 24.07.03 |
Bioinformatik: Rechenzeit "analysiert". 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
komplett.
Im Skript sind das: S. 118 Mitte bis 121 oben.
|
| 26 | 29.07.03 |
Implementierungsdetails für den Dijkstra-Algorithmus:
Einmal die O(n^2)-Variante, einmal die O(m*log 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: 121 oben bis 126 Mitte, dabei aber ein anderes (kleineres) Beispiel als das im Skript gewählt (siehe "Folien"). |
| 27 | 31.07.03 |
Analyse der Laufzeit bei rekursivem Algorithmus der Form
"a Teilprobleme der Größe n/b, Extraarbeit c*n" durchgeführt.
Anschließend Strassens Matrixmultiplikationsalgorithmus als
einen vorgestellt, wo es zu "7 Teilproblemen der Größe N/4"
kommt, und der die Schulmethode schlägt. Der Stoff von heute im Skript: S. 126 Mitte bis S. 129, wobei ich in der Vorlesung nur auf die Größenordnung der Laufzeit abgehoben habe, nicht so sehr auf die exakte Anzahl an Operationen. Den Rest der Vorlesung habe ich für Fragen zum gesamten Stoff/zur Klausur zur Verfügung gestellt. |