Stand (21.07.2005): 27 von 27 Vorlesungen sind vorüber
| Nr. | Datum | Stoff |
| 1 | 11.04.05 | Einleitung, Beginn grundlegende Graphalgorithmen:
Erinnerung an DFS gerichtet/ungerichtet,
Zusammenhangskomponenten (ZSHK) etc.
Neu: Definition starke ZSHK. Definition Strukturgraph.
Effizienten Algorithmus zur Berechnung der starken ZSHK
angegeben. Am Beispiel vorgeführt.
Im Semesteranfangsskript: S. 1 bis 7 oben. |
| 2 | 14.04.05 |
Beweis, dass der vorgestellte Algorithmus tatsächlich
die starken ZSHK berechnet. Skizziert: Wie man
2-SAT damit entscheiden kann.
Definition von Zweizusammenhangskomponenten (ZZK),
Begriffe "Schnittpunkt", "zweifach zusammenhängend",
ZZK. Beispiel vorgeführt.
Lemma "Zwei ZZK haben höchstens einen Knoten gemeinsam und wenn,
dann ist dieser ein Schnittpunkt."
Beweis von Teil a) des Lemmas beendet.
Im Semesteranfangsskript: S. 7 oben bis 10 oben. |
| 3 | 18.04.05 |
Beweis des Lemmas, Teil b) beendet. Definition lowpt,
Charakterisierung eines Schnittpunkts via lowpt angegeben
und bewiesen, andere Charakterisierung von lowpt angegeben.
Algorithmus BICON vorgestellt, erklärt, warum man *Kanten*mengen
ausgibt. Gezeigt, dass BICON in Zeit O(n+m) die
ZZK berechnet. Beweis *fast* beendet.
Im Semesteranfangsskript: S. 10 oben bis 15 oben/Mitte. |
| 4 | 21.04.05 |
Beweis zu BICON beendet. Transitiven Abschluss definiert,
gezeigt, wie man ihn auf ungerichteten Graphen
(ein Algorithmus mit Laufzeit O(n*n))
und auf gerichteten Graphen (zwei Algorithmen
mit Laufzeiten O(n*n*n) bzw. O(M(n)*log n))
berechnen kann.
Kürzeste Wege: Die verschiedenen Problemtypen aufgezählt
und resümiert, welche Ergebnisse schon bekannt sind
aus DAP2.
Dynamischen Programmierungsansatz für Problem 3 mit
negativen Kantenkosten, aber ohne negative Kreise.
Begonnen mit der Vorstellung eines Algorithmus für
das ungewichtete Kürzeste-Wege-Problem
(berechne alle Distanzen). A^* erläutert sowie
erklärt, wie man es berechnet.
Im Semesteranfangsskript: S. 15 oben/Mitte bis 19 Mitte. (Dabei den Algorithmus von Dijkstra aber nicht im Detail wiederholt und die Definition des Durchmessers auf später verschoben.) |
| 5 | 25.04.05 | Beziehungen zwischen den Distanzen in G und G^* bewiesen.
(Zwischen D(i,j) und D^*(i,j).)
Ein Lemma vorgestellt, mit Hilfe dessen man die Paritäten
der D(i,j)-Werte berechnen kann.
Gezeigt, wie man die Zahlen, die man für die Paritäten benötigt,
mit Hilfe einer Matrixmultiplikation erhalten kann. (S=A*D^*).
Durchmesser definiert, gezeigt, dass pro Rekursionsaufruf
der Durchmesser halbiert wird und daher die Laufzeit O(M(n)*log n)
ist. (Durchmesser ist maximal n-1 für zusammenhängende Graphen.)
MINCUT-Problem definiert, einige der benutzten Begriffe definiert
und Beispiele für MINCUT gezeichnet.
Im Semesteranfangsskript: S. 19 Mitte bis S. 22 Mitte. |
| 6 | 28.04.05 |
Q-S-MINCUT-Problem definiert. "Kontraktion"
zweier Knoten in einem *gewichteten* Graphen erklärt.
Erklärt, dass man nur die beiden Fälle "Q und S im minimalen
Schnitt auf der gleichen Seite/ auf verschiedenen Seiten" betrachten
muss. Ergibt einen iterativen Algorithmus, wenn man einen minimalen
Q-S-Schnitt berechnen kann.
Algorithmus "Irgendein minimaler Q-S-Schnitt" erklärt, am
Beispiel vorgeführt und gezeigt, dass der Schnitt "S auf einer
Seite, alle anderen Knoten gegenüber" ein minimaler Q-S-Schnitt ist.
(Beweis im Detail: Aktive Knoten erklärt sowie die entscheidende Aussage
für diese....).
Geschlossen mit einer pseudocodeartigen Beschreibung des gesamten
MINCUT-Algorithmus, der den Algorithmus "Irgendein..."
als Subroutine verwendet.
Im Semesteranfangsskript: S. 22 Mitte bis S. 26 Mitte. |
| 7 | 02.05.05 |
Die Laufzeit von "Irgendein minimaler Q-S-Schnitt"
analysiert. Zwei Implementierungen vorgestellt und erklärt, wie die
Laufzeiten sich ergeben.
Die schnellste Implementierung (mit Fib.-Heaps) als
dritte Implementierung nur erwähnt.
Laufzeit von MINCUT insgesamt daraus abgeleitet.
Begonnen mit dem Kapitel "Beispiele für die Analyse von Algorithmen".
UNION-FIND-Datenstrukturen: Gezeigt, wie man die
amortisierte Laufzeit der Datenstruktur mit Arrays und Listen
mit Hilfe einer Potenzialfunktion zu O(n log n) analysieren kann.
Begonnen mit der Analyse der zweiten Datenstruktur für UNION-FIND,
bei der die UNIONs geringe Laufzeit haben:
Bäume ohne und mit Pfadkomprimierung.
Gezeigt, dass Bäume der Tiefe h bei UNION-FIND mindestens 2 hoch h
Elemente besitzen und dass daraus eine Laufzeit von O( log n) pro
FIND maximal folgt.
Die Folge U_i^ohne und U_i^mit erklärt.
Rang eines Elements definiert.
Rangwachstumseigenschaft definiert und
begonnen mit dem Beweis, dass diese in *allen*
Datenstrukturen U_i^mit gilt.
Im Semesteranfangsskript: S. 26 Mitte bis S. 33 unten. (Aber: Die Details der Implementierung mit Hilfe eines "vater"-Arrays, die ja aus DAP2 bekannt sind, nicht noch einmal erklärt. Diese stehen ja im Skript nur aus Gründen der Vollständigkeit. ) |
| - | 05.05.05 | Feiertag |
| 8 | 09.05.05 |
Beweis beendet, dass die Rangwachstumseigenschaft in allen
Bäumen gilt. Funktion F(i) und deren "Umkehrfunktion" log^*(n)
definiert. Beweis, dass die amortisierte Laufzeit O((m+n)*log^*(n))
ist: Ranggruppen definiert, Konten definiert, Kosten verteilt.
Kosten in den einzelnen Konten abgeschätzt, summiert.
String Matching: Problemdefinition, triviale Implementierung
mit Laufzeit O(m*n), erklärt, wieso man dabei sparen kann -
Zusammenhang zu endlichen Automaten aufgezeigt.
Motivation des Algorithmus von Knuth, Morris, Pratt
begonnen.
Im Semesteranfangsskript: S. 34 oben bis S. 37 oben. |
| 9 | 12.05.05 |
Bedeutung der Fehlerkantenfunktion F(.) erklärt und an
mehreren Beispielen veranschaulicht. Algorithmus
"String Matching" von Knuth, Morris, Pratt vorgestellt,
lineare Laufzeit auf zwei Weisen bewiesen. (Anschaulich und mit
Potenzialfunktion.)
Zur Berechnung der F-Werte den Begriff "Präfixmatch" definiert,
erklärt, wie man diesen induktiv ermitteln kann,
Algorithmus zur F-Berechnung angegeben.
Lineare Laufzeit bewiesen.
Begonnen mit Kapitel "Approximationsalgorithmen":
Definition von "Güte", "Approximationsschema",
"polynomiellem Approximationsschema (PTAS)",
"voll polynomiellem Approximationsschema (FPTAS)",
das Problem "Vertex Cover" definiert.
Im Semesteranfangsskript: S. 37 oben bis S. 42 Mitte. |
| - | 16.05.05 | Feiertag |
| 10 | 19.05.05 |
Approximationsalgorithmus für Vertex Cover. Güte 2 bewiesen.
worst-case-Beispiel. Set-Cover-Problem definiert.
Erläutert, wieso es Verallgemeinerung von Vertex Cover ist.
Komplexitätstheoretische untere Schranke für die Approximationsgüte
von Set Cover genannt. Greedy-Algorithmus vorgestellt.
Am Beispiel vorgeführt.
Bewiesen, dass die Güte H(n) <= 1+ln n ist.
Beispielinstanz angegeben, wo der Greedy-Algorithmus fast um
den Faktor H(n) schlechter als das Optimum ist.
Im Semesteranfangsskript: S. 42 Mitte bis 46 oben. (Der vorgeführte Beweis zur Güte befindet sich im aktualisierten Skript.) |
| 11 | 23.05.05 |
TSP definiert, metrisches TSP. Fakten zu Eulerkreis
genannt. Minimaler Spannbaum liefert untere Schranke
für TSP, Umbau eines Eulerkreises zu Tour,
Algorithmus mit Güte 2 vorgestellt und Güte 2 bewiesen.
Algorithmus von Christofides erklärt und Güte 3/2
bewiesen. Ein voll (echt) polynomielles Approximationsschema
für das Rucksackproblem: Algorithmus erklärt, der kleine
Laufzeit hat, wenn die Nutzenwerte der Objekte klein sind.
FPTAS-Algorithmus angegeben und mit der Analyse begonnen:
Auswirkung der Gaußklammer.
Im Semesteranfangsskript: S. 46 oben bis S. 49 Mitte. |
| - | 26.05.05 | Feiertag |
| 12 | 30.05.05 |
Bewiesen, dass der vorgestellte FPTAS für das Rucksackproblem
tatsächlich eine (1+epsilon)-Approximation berechnet.
Problem Makespan definiert. Algorithmus Least-Loaded
erklärt und Güte 2 nachgewiesen. Beispiel, wo Algorithmus
nicht besser als Güte 2.
Algorithmus LPT vorgestellt und detailliert bewiesen, dass
die Güte 4/3 ist, insbesondere den Umbau eines optimalen
Schedules.
Begonnen mit der Vorstellung eines PTAS für das Makespan-Problem:
Darstellung der Auslastung einer Maschine durch einen Vektor.
Im Semesteranfangsskript: S. 49 Mitte bis 52 unten. (Besser: 50 Mitte bis 55 unten im aktualisierten Skript.) |
| 13 | 02.06.05 |
Bewiesen, dass man den Spezialfall von Makespan Scheduling
mit konstanter Anzahl verschiedener Jobgrößen in Polynomialzeit
lösen kann.
Den PTAS für Makespan Scheduling erklärt, bewiesen, dass
es überhaupt ein PTAS ist.
Begonnen mit dem Kapitel "Randomisierte Algorithmen".
MC/LV erklärt. Kleine Auffrischung von Resultaten
aus der Wahrscheinlichkeitstheorie.
Darstellung von randomisierten Algorithmen durch
Bäume. Die erwartete Laufzeit eines
einfachen Münzwurf"algorithmus" analysiert.
Im Semesteranfangsskript: S. 52 unten bis 59 Mitte. (Besser: 55 Mitte bis 61 Mitte im aktualisierten Skript.) |
| 14 | 06.06.05 |
Weitere einfache Analysen: Einfacher
Münzwurfalgorithmus, einfacher Lottoalgorithmus.
Die Probleme MAXSAT und MAX-k-SAT definiert.
Einen einfachen Algorithmus für MAXSAT analysiert.
Exemplarisch gezeigt, wie die Methode der Derandomisierung
mit Potenzialfunktion funktioniert.
Einen weiteren Approximationsalgorithmus für MAXSAT
vorgestellt: Exkurs in lineare Programme, Formulierung
von MAXSAT als mathematisches Programm, Relaxation
in ein lineares Programm. Randomisiertes Runden definiert.
Lemma angegeben, das Aussage darüber trifft, mit welcher
W'keit eine Klausel erfüllt ist, wenn wir mit der optimalen
Lösung aus dem LP runden.
Den Beweis des Lemmas fast beendet.
Im Semesteranfangsskript: S. 59 Mitte bis 66 Mitte. |
| 15 | 09.06.05 |
Beweis des "LP-Lemmas" beendet. Gezeigt, dass man daraus
direkt einen Algorithmus bekommt, der mindestens
0.632*OPT viele Klauseln erfüllt. (Im Erwartungswert).
Algorithmus MIX vorgestellt.
Bewiesen, dass dieser mindestens 0.75*OPT viele Klauseln im
Erwartungswert erfüllt.
MINCUT-Problem: Algorithmus "Randomisierte Kontraktion"
erklärt. Bewiesen, dass er Erfolgsw'keit mindestens
Omega(1/n^2) hat.
Angeschaut, wie man durch Iteration die Erfolgsw'keit verbessern könnte.
Anderen Ansatz gewählt: Motiviert, warum FastCut besser ist.
Algorithmus FastCut erklärt. Rekursionsgleichung für die Laufzeit
hingeschrieben und begründet, gezeigt, wie man diese
sauber analysieren kann. FAZIT: Laufzeit von FastCut ist O(n^2*log n)
Im Semesteranfangsskript: S. 66 Mitte bis 76 oben, dabei aber ausgelassen: a) Den einfachen Algorithmus für MAXCUT (S. 68) b) Den technischen Beweis (S.75), dass die Rekursionstiefe durch 2*n*log n+7 beschränkt ist. |
| 16 | 13.06.05 | Die Erfolgswahrscheinlichkeit von FASTCUT analysiert. Gezeigt, wie man diese nun durch Wiederholung noch stark verbessern kann. Random Walks anhand eines einfachen "Teilchenbeispiels" eingeführt. Die erwartete Laufzeit analysiert, bis Teilchen an Position 0 angekommen ist. Gezeigt, wie man die Analyse für 2SAT verwenden kann. Dabei sowohl "Algorithmus A" als auch "Algorithmus B" betrachtet. Gezeigt, wie man die Erfolgsw'keiten amplifizieren kann. 3-SAT-Algorithmen: Entropiefunktion H eingeführt, angegeben, wie man mit dieser gut Binomialkoeffizienten abschätzen kann. 3-SAT-Algorithmus RandomWalk(a) angegeben. Mit seiner Analyse begonnen: Betrachte Kette, in der wir mit W'keit mindestens 1/3 nach links gehen. Lemma, das angibt, dass die Erfolgsw'keit im Wesentlichen (1/2)^(Hammingdistanz(a,a^*)) ist: Aussage angegeben, mit dem Beweis begonnen. Im Semesteranfangsskript: S. 76 oben bis S. 83 oben. |
| 17 | 16.06.05 |
Beispiel für Ablauf des 3-SAT-Algorithmus.
Beweis beendet, dass die Erfolgsw'keit im
Wesentlichen (1/2)^(Hammingdistanz(a,a^*)) ist.
RandomWalk(0...0);RandomWalk(1...1) analysiert.
Startbelegung *zufällig* initialisiert, Erfolgsw'keit
davon analysiert.
Idee erklärt, wie man mit besserer Initialisierung
schneller werden kann. Unabhängige Klauseln
definiert, neue Erfolgsw'keit analysiert.
Neuen Algorithmus vorgestellt (mit 2SAT arbeitend),
der bei wenigen unabhängigen Klauseln erfolgreich ist.
Gezeigt, dass der bessere von beiden Algorithmen
Erfolgsw'keit mindestens 1.330258^(-n) hat.
Im Semesteranfangsskript: S. 83 oben bis S. 87 unten. |
| 18 | 20.06.05 |
Motivation randomisierte Suchheuristiken.
Grobe Skizze evolutionärer Algorithmen.
Definition von X(f), der Zeit bis zur Optimierung.
(1+1)EA definiert und diskutiert.
f-basierte Partitionen definiert. Erklärt, wie man
f-basierte Partitionen benutzen kann, um E[Xf] abzuschätzen.
Optimierungslaufzeit auf ONEMAX mit Hilfe von f-basierter Partition
analysiert. Unimodale Funktionen definiert und Schranke
für diese definiert. Lineare Funktionen definiert,
Analyse der Optimierungszeit.
Im Semesteranfangsskript: S. 88 oben bis S. 92 Mitte. |
| 19 | 23.06.05 |
Methode für die Analyse der Optimierungszeit bei linearen Funktionen
auf Polynome vom Grad k verallgemeinert. Kapitel
(1+1)EA beendet.
Flüsse in Netzwerken. Definitionen: Netzwerk, Fluss in Netzwerk,
Wert des Flusses, maximaler Fluss. Anwendung: Matchings in bipartiten
Graphen. (Zum Vergleich Greedyalgorithmus vorgestellt und
"analysiert".)
Algorithmen zur Berechnung maximaler Flüsse:
Definition Restgraph, FV-Weg.
Im Skript: 92 Mitte bis 98 unten. |
| 20 | 27.06.05 | Beschrieben, wie man mit FV-Weg den Fluss vergrößern kann.
Algorithmus von Ford und Fulkerson: Markierungsalgorithmus
erklärt. Laufzeit von Ford und Fulkerson als O(B*(n+e)) analysiert.
Satz MAXFLOW = MINCUT bewiesen und verwendet zum Korrektheitsbeweis
des Algorithmus von Ford und Fulkerson. Ein Beispiel angegeben,
wo der Algorithmus tatsächlich exponentielle Laufzeit in
der Eingabelänge haben kann.
"Exkurs Distanzen in Graphen": gezeigt, wie Hinzufügen bestimmter
Kanten die Distanzen unverändert lässt.
Im Skript: Seite 98 unten bis 103 unten. |
| 21 | 30.06.05 |
Teil b) des Distanzlemmas bewiesen. Algorithmus von Dinic:
Niveaunetzwerk definiert. "Kante saturiert" definiert, Sperrfluss definiert.
Backtracking-Algorithmus zur Berechnung eines Sperrflusses vorgestellt
und Laufzeit O(n*e) bewiesen.
Algorithmus von Dinic: Max. n-fache Sperrflussberechnung.
Bewiesen, dass jedes Mal die Distanz mindestens 1 größer wird.
Im Skript: Seite 103 unten bis Seite 106 unten. |
| 22 | 04.07.05 | Sperrflussberechnung nach Malhotra, Kumar, Maheshwari.
Potenzial definiert, Algorithmen Forward und Backward
erklärt. Algorithmus Forward-Backward-Propagation erklärt.
Laufzeit O(n*n) bewiesen.
Algorithmenfamilie von Goldberg und Tarjan:
e(v) definiert, Preflow definiert.
Lemma: Aktive Knoten haben im Restgraphen einen
Weg zur Quelle. Bewiesen.
"Gültige Knotenmarkierung" definiert und motiviert.
Definition "Kante wählbar".
Lemma: Wenn Preflow gültige Markierung d hat, dann gibt
es keinen Weg von Q nach S.
Im Skript: Seite 107 oben bis Seite 110 Mitte. |
| 23 | 07.07.05 |
Generischen Preflow-Push-Algorithmus erklärt.
Definition saturierende Push-Operation.
Gezeigt, dass d stets eine gültige Markierung bleibt und
durch Relabel um mind. 1 wächst.
Beweis, dass bei STOPP ein maximaler Fluss vorliegt.
Beweis für die Rechenzeit begonnen: d(v)<= 2n-1 für alle v.
Beweis, dass es maximal 2n*n Relabel-Aufrufe gibt.
Zahl saturierender Push-Operationen durch O(n*e) abgeschätzt.
Begonnen mit dem Beweis, dass es maximal O(n*n*e) nicht-saturierende
Push-Operationen gibt: Potenzialfunktion definiert, Verhalten bei
nicht-saturierendem Push betrachtet.
Im Skript: Seite 110 Mitte bis Seite 112 Mitte. |
| 24 | 11.07.05 | Bewiesen, dass es höchstens O(n*n*e) nicht-saturierende Pushoperationen
gibt. Gezeigt, wie man schnell an anwendbare Basisoperationen kommt:
Generischer Algorithmus Push/Relabel. Gezeigt, dass Relabel
an passender Stelle anwendbar ist. Laufzeit analysiert.
FIFO-Strategie vorgestellt und analysiert: Laufzeit O(n*n*n) bewiesen.
Highest Selection Rule erwähnt.
Im Skript: Seite 112 Mitte bis 115 unten. |
| 25 | 14.07.05 |
Begonnen mit Kapitel "Effizienter Primzahltest".
RSA als Public-Key-Kryptosystem vorgestellt.
Algorithmen für effizientes Potenzieren vorgestellt
und Laufzeit analysiert.
Effizienter ggT-Algorithmus mit Laufzeitanalyse.
Effizienter Inversen-Algorithmus mit Laufzeitanalyse.
Begonnen mit dem Korrektheitsbeweis der Inversenberechnung.
Im Skript: Seite 116 oben bis 121 Mitte/unten. |
| 26 | 18.07.05 |
Gezeigt, dass Berechnung von phi(n) für n=p*q
polynomialzeitäquivalent ist zur Faktorisierung von n.
Beweis zur Inversenberechnung beendet.
Zahlentheoretische Definitionen: Ordnung, quadratischer Rest,
erzeugendes Element, etc.
Carmichael-Funktion definiert, Rechenregeln dafür.
Beweis, dass die Hälfte der Zahlen modulo p quadratischer Rest ist.
Carmichaelzahlen definiert, Charakterisierung der Carmichaelzahlen.
Jacobi-Symbol definiert.
Im Skript: Seite 121 Mitte/unten bis 124 Mitte. (Zusätzlich Seite 122 Mitte aus dem aktualisierten Skript.) |
| 27 | 21.07.05 |
Rechenregeln für das Jacobi-Symbol gelistet.
Daraus Algorithmus zur effizienten Berechnung hergeleitet.
Laufzeit analysiert.
Chinesischen Restsatz angegeben, aber nicht bewiesen.
Algorithmus von Solovay und Strassen vorgestellt.
Die entscheidende Eigenschaft, die dabei verwendet wird,
hervorgehoben.
Die Eigenschaft für Primzahlen bewiesen, bei den Nichtprimzahlen
den Beweis aus Zeitgründen nur ansatzweise skizziert.
Einfaches Beispiel für den Algorithmus gerechnet.
Im Skript: 124 Mitte bis 130 oben, dabei aber ein paar Beweisdetails ausgelassen (s.o.). |