Logbuch Effiziente Algorithmen - Sommer 2019
18.07.2019:
Berechnung eines maximum Matchings in allgemeinen Graphen
G mit n Knoten und m Kanten, Matching M maximum ⇔ M hat
keinen augmentierenden Pfad, augmentierende Pfade und ungerade
Kreise, Kontraktion von ungeraden Kreisen (Blüte, engl blossom)
Vervollständigung von augmentierenden Pfaden, Edmonds
Blossom-Algorithmus, Korrektheit, Laufzeit O(n2(n+m)).
- Notizen Flüsse und Matchings, Abschnitt 2.2
16.07.2019:
Beispiel Preflow-Push Algorithmus. Matching: perfekt, maximum,
maximal. Berechnung eines maximum Matchings in bipartiten Graphen
G=(A ∪ B, E) mit n Knoten und m Kanten, Flussnetzwerk,
Äquivalenz integraler Flüsse zu Matchings, Berechnung
mit Ford-Fulkerson-Algorithmus in Zeit O(nm). Charakterisierung
von Graphen mit perfekten
Matchings (Hall, König, Egervary,...), entweder perfektes
Matching oder eine Menge X ⊆ A mit |X| > |Γ(X)|.
- Notizen Flüsse und Matchings, Abschnitt 2.1
11.07.2019:
Preflows, Überschuss, Labellings, Kompatibilität (Abstiegsbedingung
im Residualnetzwerk). Fluß mit kompatiblem Labelling ist
maximal. Preflow-Push Algorithmus, verwaltet kompatible
Preflows und Labellings, erreicht Abbau von Überschüssen. Korrektheit, Laufzeit: Anzahl
Relabels höchstens 2n2 (maximale Höhe eines Knotens), Anzahl saturierender
Pushs höchstens 2nm (Höhenänderung um
mind. 2 vor nächstem saturierenden Push auf gleicher Kante), Anzahl nicht-saturierender Pushs höchstens 4n2m (Potenzialanalyse).
- Notizen Flüsse und Matchings, Abschnitt 1.2
09.07.2019:
Maximale Flüsse, Definitionen zu Flussnetzwerk, Fluss, Wert des
Flusses, s-t-Schnitt, Kapazität des Schnittes,
Residualnetzwerk, augmentierende Pfade. Ford-Fulkerson
Algorithmus, Korrektheit, Max-Flow-Min-Cut Theorem, Laufzeit, stark
polynomielle Laufzeit mit Edmonds-Karp Variante.
- Notizen Flüsse und Matchings, Abschnitte 1 und 1.1
04.07.2019:
Erzeugung von Random und Pseudo-Random Bitsequenzen,
statistische Tests, Generatoren, Existenz von einem
effizienten Pseudo-Random Generator unabhängig
von der Streckung, Verbindung zu P-NP, Blum-Micali
Generator, Multiplikative Gruppe modulo n, Generatoren
- Notizen Pseudo-Random Generatoren
- Skript, Abschnitt 4.1
02.07.2019:
Random Sampling, Beispiel: Closest-Pair, Gittereinteilung,
Schätzung μ der kleinsten Distanz: Zufällige Wahl eines
Punktes, Reduzierung der Punktmenge; Anwendung eines Gitters mit
Schätzwert μ. Yao-Prinzip, Intuition mit 2-Spieler-Modell
(Algorithmusdesigner vs. Instanzwahl-Gegner), Anwendung auf das
Paging Problem, jeder randomisierte Paging-Algorithmus bei
Cachegröße k hat Wettbewerbsfaktor mindestens Hk.
- Folien Randomisierte Algorithmen 2, Seiten 6-10
- Notizen Randomisierte Algorithmen 2, Seiten R73-R78, Y1-Y9
- Skript, Abschnitte 2.3.1 und 6.2
- Der schnellste deterministische Algorithmus für Closest-Pair läuft wie vermutet in Zeit O(n log n), hier eine suboptimale Version und hier die verbesserte Version, mit Code und Analyse.
27.06.2019:
Probabilistische Methode, für welche Zahlen n und k gibt es einen Graphen mit n Knoten,
ohne Kk und ohne Kk als
Subgraph? Probabilistische Methode zeigt Existenz für k ≥ 2log2 n. Byzantine Agreement, randomisierter Algorithmus für t < n/8 illoyale Generäle, erwartete Laufzeit O(1)
- Folien Randomisierte Algorithmen 2, Seiten 1-5
- Notizen Randomisierte Algorithmen 2, Seiten R56-R70
- Skript, Abschnitte 2.4 und 2.6.
25.06.2019:
Splay-Bäume, Operation Splay(x) rotiert immer das größte Element ≤ x an die Wurzel, Splay(x) als Basis für Insert(x),
Lookup(x) und Remove(x), Rechts- und Linksrotationen und Anwendung in der Splay-Operation, Definition der Potenzialfunktion,
amortisierte Kosten für eine Zick-Zick-Operation (Zick-Zack analog) und eine Zick-Operation, amortisierte Kosten einer
Splay-Operation in O(log n), Dynamic Optimality Conjecture, Probabilistische Methode.
- Folien Online Algorithmen 2, Seiten 21-26
- Skript, Abschnitt 9.2.
18.06.2019:
Fibonacci-Heaps, Wiederholung Insert (in O(1)) und DeleteMin mit Aufräumen (in O(log m)),
DecreaseKey mit Cascading Cuts, amortisierte Laufzeit O(1), Fibonacci-Eigenschaft der verbleibenden Bäume,
Dijkstra's Algorithmus, Laufzeit mit binären und Fibonacci-Heaps.
Splay-Bäume, Operation Splay(x) rotiert immer das größte Element ≤ x an die Wurzel, Splay(x) als Basis für Insert(x),
Lookup(x) und Remove(x), Rechts- und Linksrotationen und Anwendung in der Splay-Operation, Definition der Potenzialfunktion.
- Notizen Online Algorithmen 2, Seiten OA49-OA61
- Folien Online Algorithmen 2, Seiten 18-25
- Skript, Abschnitt 9.3, 9.2 (bis Seite 131).
13.06.2019:
Binomische Bäume, binomische Heaps, Operationen mit amortisierten
Laufzeiten: Insert durch Vereinigung von Bäumen (in O(1)),
DeleteMin druch Abtrennen der Wurzel
und Vereinigung von Bäumen (in O(log m)), DecreaseKey durch repair_up
wie bei binären Heaps (in O(log m)), Delete = DecreaseKey +
DeleteMin. Fibonacci-Bäume, Fibonacci-Heaps, triviales
Insert (in O(1)), DeleteMin mit Aufräumen (in O(log m)),
DecreaseKey mit Cascading Cuts.
- Notizen Online Algorithmen 2, Seiten OA40-OA55
- Folien Online Algorithmen 2, Seiten 13-20
- Skript, Abschnitt 9.3.
11.06.2019:
Amortisierte Laufzeitanalyse, Buchhalter-Argument und
Potenzialfunktion, Beispiele: Paging mit Flush-When-Full,
Bitzähler, Hashtabelle mit dynamischer
Größenanpassung. Wiederholung Heaps, binomische Bäume.
- Notizen Online Algorithmen 2, Seiten OA23-OA41
- Folien Online Algorithmen 2, Seiten 8-12
- Skript, Abschnitte 9, 9.1, 9.3 (bis Seite 137).
06.06.2019:
Auswahl von Experten, n Experten, JA/NEIN Entscheidungen, jeder Experte macht eine Empfehlung, minimiere Fehlentscheidungen,
Optimum ist Anzahl Fehler des besten Experten. Deterministischer Weighted-Majority Algorithmus
ist (log4/3 2)-kompetitiv (zzgl. additiven Kosten log4/3 n). Online Lernen mit Kosten, Kosten
cit ∈ [0,1] für Experten i in Runde t=1,...,T. Randomized Weighted-Majority Algorithmus erzeugt erwartete Gesamtkosten K ≤
(1+ε)Kopt + ln(n)/ε.
- Notizen Online Algorithmen 2, Seiten OA8-OA14
- Folien Online Algorithmen 2, Seiten 6-7
- Skript, Abschnitt 8.1.
04.06.2019:
Ski-Rental, deterministische Strategie mit Wettbewerbsfaktor
2-1/K, untere Schranke für deterministische
Strategien. Randomisierte Strategie mit Wettbewerbsfaktor
e/(e-1). k-Server Problem, verallgemeinert das Paging-Problem,
einfache Algorithmen: Greedy, Balance, Randomisierter
Greedy. Work-Function, Definition, Work-Function Algorithmus ist
2k-kompetitiv (ohne Beweis).
- Notizen Online Algorithmen 2, Seiten OA1-OA7, OA15-OA22
- Folien Online Algorithmen 2, Seiten 1-5
- Skript, Abschnitte 5.1 und 7.
28.05.2019:
Paging Problem mit Cachegröße k, FIFO und LRU sind
k-kompetitiv, Beweis über Zerlegung in Teilfolgen
abhängig von Page-Faults von FIFO/LRU. Jeder
deterministische Algorithmus hat Wettbewerbsfaktor mindestens
k. Randomisierter Marking Algorithmus ist 2Hk-kompetitiv, Beweis über Zerlegung in Teilfolgen
unabhängig vom Algorithmus, Analyse der Wahrscheinlichkeit
der Auslagerung von alten Elementen.
- Notizen Online Algorithmen 1, Seiten P10-P25
- Folien Online Algorithmen 1, Seiten 7-15
- Skript, Abschnitte 6.1 und 6.2.
23.05.2019:
Lastbalancierung mit Random Walks, H(G) maximale Hitting-Time in
G, nach erwartet O(H(G) log Φ(ℓ0)) Runden
wird ein balancierter Zustand erreicht. Online Algorithmen, Wettbewerbsfaktor, Makespan Scheduling auf m
identischen Maschinen, LIST Algorithmus ist (2-1/m)-kompetitiv, jeder deterministische
Algorithmus ist mindestens 3/2-kompetitiv, Paging Problem, LFD ist
offline Optimum.
- Notizen Lastbalancierung mit Random Walks
- Notizen Online Algorithmen 1, Seiten P1-P9
- Folien Markoff-Ketten, Seiten 7, 8
- Folien Online Algorithmen 1, Seiten 1-6
- Skript, Abschnitte 5, 5.2 und 6.
21.05.2019:
Random Walks in ungerichteten Graphen G, zugehörige
Markoff-Kette irreduzibel ⇔ G zusammenhängend,
Kette ergodisch ⇔ G zusammenhängend und nicht
bipartit. Grenzverteilung ist πv
= deg(v)/2|E|. Hitting-Time H(u,v) Definition, H(u,u) =
1/πu, H(u,v) < 2|E| wenn {u,v} ∈ E, H(u,v) <
2|E|(n-1) für beliebige Knoten u,v ∈ V. Lastbalancierung
mit Random Walks, H(G) maximale Hitting-Time in G, nach erwartet O(H(G) log Φ(ℓ0)) Runden wird ein balancierter Zustand erreicht.
- Notizen Markoff-Ketten, Seiten MK29-MK35
- Notizen Lastbalancierung mit Random Walks
- Folien Markoff-Ketten, Seiten 7, 8
- Skript, Abschnitt 3.1.
16.05.2019:
Wiederholung Markoff-Ketten, Definitionen: irreduzible und
reduzible Ketten, Periode eines Zustands, periodische und aperiodische Ketten. Stationäre
Verteilungen, Grenzverteilung, Definition ergodische Kette, in
ergodischen Ketten ist die Grenzverteilung die einzige
stationäre Verteilung, ergodisch ⇔ aperiodisch und irreduzibel.
Bei ergodischen Ketten wird vorausgesetzt,
dass limt→∞
Pti,k = limt→∞
Ptj,k > 0 für
alle Zustände i,j,k.
Daher gilt ergodisch ⇔ (aperiodisch ∧ irreduzibel).
- Notizen Markoff-Ketten, Seiten MK15-MK29
- Folien Markoff-Ketten, Seiten 5, 6
- Skript, Abschnitt 3.1.
14.05.2019:
2-SAT Problem, Random-Walk-Algorithmus für 2-SAT, Markoff-Kette zur Laufzeitanalyse, erwartete Laufzeit zum Finden einer
erfüllenden Belegung höchstens n2, nach Laufzeit
k⋅2n2 ist Fehlerwahrscheinlichkeit
höchstens (1/2)k. 3-SAT Problem, gleicher Ansatz
schlechte Schranken in der Ordnung von 2n+2,
Random-Walk-Algorithmus mit Neustart, nach Laufzeit
k⋅(4/3)n⋅poly(n) ist Fehlerwahrscheinlichkeit höchstens (1/e)k.
- Notizen Markoff-Ketten, Seiten MK8-MK14, MK56-MK62
- Folien Markoff-Ketten, Seiten 3, 4
- Skript, Abschnitt 3.1 die Definitionen und Grundbegriffe von Markoff-Ketten.
- Abschnitt 3.3 im Skript behandelt einen anderen Algorithmus für 2-SAT und 3-SAT (und k-SAT mit beliebigem k ≥ 2)
09.05.2019:
Verteilter Algorithmus für nicht-erweiterbares Independent Set, Definition gute Knoten
und Kanten, in jeder Runde wird jeder gute Knoten wird mit
konstanter Wahrscheinlichkeit aus V entfernt, mind. die
Hälfte der Kanten sind gute Kanten, in jeder Runde wird im Erwartungswert
ein konstanter Anteil aller Kanten entfernt, Laufzeit O(log n)
w.h.p. Markoff-Ketten, 2-SAT Problem, randomisierter 2-SAT
Algorithmus, Markoff-Kette zur Laufzeitanalyse.
- Skript, Abschnitt 2.5.2.
- Folien Randomisierte Algorithmen 1, Seite 27
- Notizen Markoff-Ketten, Seiten MK1-MK11
- Folien Markoff-Ketten, Seiten 1-3
- Skript, Abschnitt 3.1 die Definitionen und Grundbegriffe von Markoff-Ketten.
- Abschnitt 3.3 im Skript behandelt einen anderen Algorithmus für 2-SAT und 3-SAT (und k-SAT mit beliebigem k ≥ 2)
07.05.2019:
Hashing mit Verkettung, c-universelles Hashing, erwartete Anzahl
Kollisionen, erwartete Laufzeit für n
Operationen bei Hashtabelle mit m Einträgen ist höchstens n(1 + cn/(2m)). Symmetry
Breaking, Zusammenhangskomponenten, randomisierter paralleler
Algorithmus, Laufzeit O(log n) erwartet und w.h.p.
- Notizen Randomisierte Algorithmen 1, Seiten R47-R55, R86-R94
- Folien Randomisierte Algorithmen 1, Seiten 21-26
- Skript, Abschnitte 2.2.2 und 2.5.1.
02.05.2019:
Skip-Listen, Definition "mit hoher Wahrscheinlichkeit (w.h.p.)", logarithmisch viele Schichten
w.h.p., erwartete Laufzeit von Lookup O(log n) (= erwartete Länge des Suchpfades), erwartete
Laufzeit von Insert und Delete auch O(log n), da dominiert durch entsprechenden
Suchpfad. Fingerprinting, n-Bit Schlüssel x, Fingerprint h(x) mit
Modulo-Abbildung gemäss zufälliger Primzahl aus dem
Intervall [2,nd], für feste Schlüssel x ≠
y gilt h(x) ≠ h(y) w.h.p.
- Notizen Randomisierte Algorithmen 1, Seiten R21-R28, R39-R46.
- Folien Randomisierte Algorithmen 1, Seiten 12-20
- Skript, Abschnitte 2.1.2 und 2.2.1.
30.04.2018:
Monte Carlo Algorithmen, RSA Kryptosystem, Primzahltest, kleiner Satz von Fermat,
Fermat Test, erweiterter Fermat Test, Miller-Rabin Test,
fehlerhafte Klassifikation von zusammengesetzten Zahlen mit
Wahrscheinlichkeit höchstens 1/4. Min-Cut Problem, randomisierter
Min-Cut Algorithmus, Fehlerwahrscheinlichkeit höchstens 1 -
2/n2, Fehlerwahrscheinlichkeit höchstens (1/e)r
nach rn2/2 unabhängigen Wiederholungen
- Notizen Miller-Rabin Test.
- Notizen Randomisierte Algorithmen 1, Seiten R14-R20.
- Folien Randomisierte Algorithmen 1, Seiten 7-11.
- Skript, Abschnitt 2.1.4.
25.04.2019:
Spielbäume, Auswertung mit deterministischen Algorithmen,
untere Schranke an die Laufzeit, Verbesserung durch randomisierte Wahl der
ausgewerteten Kinder. Entscheidungsprobleme, Monte Carlo
Algorithmen mit einseitig beschränktem Fehler.
- Notizen Randomisierte Algorithmen 1, Seiten R1-R13.
- Folien Randomisierte Algorithmen 1, Seiten 1-6.
- Skript, Abschnitte 2.1, 2.1.1.
23.04.2019:
Sekretärproblem, Algorithmus mit Wartezeit n/e, Analyse der
Wahrscheinlichkeit für die Einstellung des optimalen
Bewerbers, Optimalität des Algorithmus
- Notizen Einführung, Seiten E13-E15.
- Notizen Optimalität im Sekretärproblem.
- Skript, Beispiel 1.2.
- M. Beckmann. Dynamic Programming and the Secretary Problem. Computers Math. Applic. 19(11):25-28, 1990.
18.04.2019:
Wahrscheinlichkeitsverteilungen, Ereignisse,
Unabhängigkeit, bedingte Wahrscheinlichkeit, Formel
für die totale Wahrscheinlichkeit,
Zufallsvariablen, Erwartungswert, Linearität des Erwartungswertes, bedingter Erwartungswert,
Markoff-Ungleichung, Varianz, Tschebyscheff-Ungleichung,
Chernoff-Ungleichungen
Die vorgestellten Grundlagen der Stochastik finden sich in einer Vielzahl von Büchern und Skripten.
Material und Literatur:16.04.2019:
Organisatorisches, randomisierte Algorithmen, erwartete
Laufzeit, randomisierter Quicksort, randomisierter
Gehaltsdurchschnitt. Online Algorithmen, Beispiele für
Online-Probleme: Bin-Packing, Ski-Rental, Sekretärproblem.
- Folien Organisation und Einführung.
- Notizen Einführung, E1-E12.
- Skript, Abschnitt 1.2.