Diese Webseite ist archiviert, da die Arbeitsgruppe zur RWTH Aachen wechselte.

zurück zur Übersicht


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)).

    Material und Literatur:

  • 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)|.

    Material und Literatur:

  • 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).

    Material und Literatur:

  • 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.

    Material und Literatur:

  • 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

    Material und Literatur:

  • 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.

    Material und Literatur:

  • 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)

    Material und Literatur:

  • 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.

    Material und Literatur:

  • 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.

    Material und Literatur:

  • 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.

    Material und Literatur:

  • 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.

    Material und Literatur:

  • 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)/ε.

    Material und Literatur:

  • 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).

    Material und Literatur:

  • 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.

    Material und Literatur:

  • 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.

    Material und Literatur:

  • 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.

    Material und Literatur:

  • 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).

    Material und Literatur:

  • 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.

    Material und Literatur:
    • 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.

    Material und Literatur:
    • 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, Zusammen­hangskomponenten, randomisierter paralleler Algorithmus, Laufzeit O(log n) erwartet und w.h.p.

    Material und Literatur:

  • 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.

    Material und Literatur:

  • 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 Wahrscheinlich­keit höchstens 1/4. Min-Cut Problem, randomisierter Min-Cut Algorithmus, Fehlerwahrscheinlichkeit höchstens 1 - 2/n2, Fehler­wahrscheinlichkeit höchstens (1/e)r nach rn2/2 unabhängigen Wiederholungen

    Material und Literatur:

  • 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.

    Material und Literatur:

  • 23.04.2019:
    Sekretärproblem, Algorithmus mit Wartezeit n/e, Analyse der Wahrscheinlichkeit für die Einstellung des optimalen Bewerbers, Optimalität des Algorithmus

    Material und Literatur:

  • 18.04.2019:
    Wahrscheinlichkeitsverteilungen, Ereignisse, Unabhängigkeit, bedingte Wahrscheinlichkeit, Formel für die totale Wahrscheinlichkeit, Zufallsvariablen, Erwartungswert, Linearität des Erwartungswertes, bedingter Erwartungs­wert, 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.

    Material und Literatur: