Einleitung

Randomisierte Algorithmen

  • Zufälliger Wert irgendwie zur Verfügung gestellt
  • Unbekannter nächster Elementarschritt, des Wahrscheinlichkeiten aber bekannt sind
  • Viele deterministische Algorithmen, Auswahl des Algorithmus durch Zufallsstring in Eingabe oder

Zufallsvariablen

Zufällig (mit Erwartungswerten) sind

  • Laufzeit
  • Ergebnis
  • Speicherplatz

Vorteile

  • leichter zu formulieren als deterministische
  • manchmal besser (in Laufzeit oder Ergebnis)
  • kein deterministischer Algorithmus vorhanden

Wichtige Sätze

  • MINIMAX Methode von Yao für untere Schranken von randomisierten Algorithmen
    • .
  • Chebyshev zur ANzahl von Primzahlen
    • .

USTCON

Problem

Graph , . Frage: Sind und in der gleichen Zshkomp.?

Algo USTCON

Random Walk ab mit Länge , wenn gefunden, YES sonst NO.

Analyse USTCON

  • Laufzeit
  • .
  • Fehler
    • Anzahl Schritte bis
    • Markov-Ungl

Random Walks

Widerstandsnetze

  • pro Kante
  • Stromstärke pro Knoten
  • .
  • .
    • .
    • .

STCON

Algo STCON

Random Walk bis , würfle und bei null gebe NO zurück.

Analyse STCON

  • Platz
  • Fehler
  • .

MIN CUT

Algo CONTRACT

Kontrahiere zufällig Knoten, finde Cut zwischen zwei letzten Knoten

Analyse CONTRACT

  • Laufzeit
  • Fehler
    • i-te Phase in der noch keine k-Kante kontrahiert wurde hat (n-i+1) Knoten mit min-degree k, also mindestens Kanten
  • mit Wiederholungen
    • Fehler
    • Laufzeit (det. )

ITERCONTRACT

  • Wahrsch. Cut noch da

Algo ITERCONTRACTDETMINCUT

mal ITERCONTRACT(t) dann deterministisch mit

Analyse ITERCONTRACTDETMINCUT

  • Laufzeit ()
  • Fehler

Algo FASTCUT

Mache zweimal Itercontract bis und rufe auf beiden rekursiv FASTCUT auf

Analyse FASTCUT

  • Laufzeit
  • Erfolg

UOB

Deterministisch UOB

Es gibt immer einen Fall, in dem Knoten angeschaut werden müssen

Algo UOB

Wähle zufällig Kindknoten

Analyse UOB

  • Erwartung mit Induktion
  • MINIMAX von Yao als Vergleich zu unterer Schranke
    • Umschreiben in NOR Gatter
    • wähle Eingabe und erwartete Anzahl besuchter Blätter von bestem Algorithmus A:

Komplexitätsklassen

  • RTM ist DTM mit bis zu zwei Übergangsmöglichkeiten gleicher Wahrscheinlichkeit
    • normalisiert, wenn immer zwei Übergänge und alle Berechnungen gleich lang
  • und einseitig mit Fehler
    • durch Wiederholen bessere Wahrscheinlichkeit
    • sind beide Klassen
  • wenn Fehler
    • durch Wiederholen und wählen des am meisten Vorkommenden bessere Wahrscheinlichkeit
  • Erkennen der Sprache , Erkennen der Nicht-Sprache

MST

Algo BORUVKA

Boruvka Phase: Finde lokal minimale Kanten, kontrahiere diese. Wiederhole bis alle Kanten kontrahiert

Analyse BORUVKA

  • Laufzeit (eine Phase in )

Algo RANDOM SAMPLE

Sortiere Kanten und wähle zu Wahrscheinlichkeit p falls Knoten noch nicht in gleicher Komponente. Alle Kanten sind -leicht

Analysis RANDOM SAMPLE

  • Erwartungswert leichter Kanten

Algo MSF

Mach 3x Boruvka, Sample Kanten, entferne F-schwere Kanten, wiederhole rekursiv

Analyse MSF

  • Laufzeit

Markov-Ketten

Definitionen

  • Zustandsautomat, beschreibbar als Matrix mit stochastischen Zeilen
  • Wahrscheinlichkeit nach Schritten von zu zu gehen; Wahrscheinlichkeit von irgendwann zu zu kommen
  • Erwartungswert Schritte von zum erstenmal zu zu kommen
  • rekurrenter Zustand
    • positiv persistent wenn
    • null-persistent wenn
  • ergodisch, wenn irreduzibel und aperiodisch

Aperiodisieren von Markov-Ketten

  • .
  • .

Ergodische Markov-Ketten

  • existiert
  • besteht aus identischen Zeilen ,
  • .
  • .
  • reversibel wenn

Algo METROPOLIS

Finde Markovkette mit gegebenr stationärer Verteilung. proposal matrix, energy function. Start bei . Berechne mit 2 Schritten:

  • wähle je nach .
  • wenn also , dann
  • wenn also , dann
    • mit Wahrscheinlichkeit

Approximieren

Allgemeines

  • NTM kann zu Problem aus genau Eingaben in poly Zeit akzeptieren
  • .
    • PAS wenn Laufzeit polynomiell in n
    • FPAS wenn Laufzeit polynomiell in n und
  • .
    • PRAS wenn Laufzeit polynomiell in n
    • FPRAS wenn Laufzeit polynomiell in n und

Algo SAMPLEDNF

Rate Lösungen und zähl wie hoch der Anteil richtig geratener Lösungen, rate dementsprechend Anzahl Gesamtlösungen.

Analyse SAMPLEDNF

  • für Fehlerwahrsch. muss Anz. Wiederholungen umgekehrt proportional zu sein, kann exponentielle Laufzeit bedeuten

Algo RANDDNF

??

Analyse RANDDNF

??

Online Algorithmen

Kompetivität Cache Misses

  • MIN ist optimaler Offline Algorithmus
  • Worst Case macht keinen Sinn, weil es immer Anfragen gibt, die Cache Miss erzeugen können
  • , b nicht von Eingabelänge abhängig (aber von C)
  • LRU, FIFO k-kompetitiv

Widersacher

  • oblivious: kennt Code aber nicht Zufallsbits (immer gleiche Eingaben)
  • adaptiv
    • online: kennt Code, kann auf bisherige Anfragen und Zufälle onlie entscheiden
    • offline: kennt auch noch alle zukünftigen Zufallsbits

Algo MARKER

Bei Cachemiss, schmeiße unmarkierten raus, und markieren neuen, wenn alle markiert, entferne Marker

Analyse MARKER

  • -kompetitiv
    • Vergleich mit OPT pro Phase mit sauberen Elementen
    • Unterschiede Cache Elementen in OPT und MARKER mit und

Algo ADAPTW

Kosten von Cachemissen, verdränge daher eher leichte Elemente mit Wahrscheinlichkeit

Analyse ADAPTW

  • k-kompetitiv

k-Server Problem

Kleine Beispiele

Matrizenvergleich

  • Frage in oder aber
  • Abschätzung in O(n^2) mit
  • Fehler
    • letzter bit in muss negative der bisherigen Summe sein

Wörtervergleich

  • Primzahl , Vergleich der modulos
  • Fehler
  • Chebyshev: Zahl hat höchstens n Primteiler

Pattern Matching

  • Wie Wörterbuchvergleich, nächster Fingerabdruck berechnbar
  • in Laufzeit
  • mit Fehler

Quicksort

  • Wähle Pivot zufällig
  • Erwartete Laufzeit in