- Titel: Randomisierte Algorithmen & Probabilistische Analyse
- Organisation: UNI KL
- Seitenzahl: 91
Inhalt
- Randomisierte Algorithmen Probabilistische Analyse
- Sven O Krumke
- Entwurf vom April
- Technische Universität Berlin
- Zielgruppe und Voraussetzungen
- Bücher zum Thema sind
- sofern die obige Reihe absolut konvergiert
- i und daher
- Zusammen mit haben wir dann
- Ek En k On
- b Rekursionsbaum T mit den Pivotelementen
- nHn Dies war zu zeigen
- Bedingte Wahrscheinlichkeiten Unabhängigkeit und einfache Erfolgssteigerung
- den von S und T erzeugten Schnitt
- Das Prinzip der verzögerten Entscheidungen
- für x sonst
- beta beta beta beta
- lim Pr m ee
- Pr z E z
- di k z dz k
- Pr k kk kiz ki
- Pr k kz k
- Pr k kk k Pr k
- pnk z k pnk z k n n
- Lemma Für die Varianz einer Zufallsvariablen gilt
- Var E E
- Var Var G
- Hier benutzen wir die Notation Hn nung
- np für die Harmonische Zahl pter Ord
- Untere Schranken durch das Prinzip von Yao
- der zweite Sohn wird mit Wkeit ausgewertet
- inf Eq CALG Iq f A I
- pALG CALG I pALGCALG I
- qIpALG CALG I
- pALGEq CALG Iq
- Untere Schranken durch das Prinzip von Yao
- Momente und Abweichungen
- ln n ln ln n ln
- t Pr t Dies war zu zeigen
- Zusammen mit zeigt dies die Behauptung
- i k und a A
- für alle a A
- Pr Pij wird gewählt
- und der Linearität des Erwartungswertes folgt dann
- Wir benötigen also ein stärkeres Hilfsmittel
- Dann folgt für alle
- Pr F e
- Außerdem gilt ZILP
- Momente und Abweichungen
- lnm lnm ZILP
- wg ZILP ZLP E
- E et E exp
- expt i E expt i
- pi et pi pi et exppi et
- Pr z z n zn
- Pr n zn z n zn
- Statt des Terms Pr erhalten wir Pr
- Ei müssen wir jetzt nach unten beschränken Mit
- Dies war zu zeigen
- Minimale aufspannende Bäume
- Der Algorithmus von Boruvka
- Zufällige Stichproben für die MSTBerechnung
- n p nq Var p
- wobei q p
- gibt tatsächlich DollarMünzen
- Anhang Der MSTVerikationsalgorithmus mit Linearzeit
- Minimale aufspannende Bäume
- Anhang Der KruskalAlgorithmus zur Bestimmung eines MST
- Man nennt c dann auch die Approximationsgüte von
- Pr u überdeckt
- Randomisiertes Runden für M A S AT
- Pr Cj ist erfüllt
- wobei k k k
- Semidenite Programmierung und M A C UT
- Semidenite Programmierung und M A C UT
- Ein einfacher Algorithmus für M A C UT
- Der Algorithmus von Goemans und Williamson
- Algebra huuhh und Zufall
- Die Technik von Freivalds
- di ri Pr r
- Schnelle Beweise für NP Probabilistische Beweisprüfer
- Codierung des Beweises
- Ga z zn
- Gb z znn
- bij zij zijk
- Gc z znnn
- ai aj ak zijk
- Falsche Beweise und die Verikation
- n Seien r s Z Dann gilt n
- a i a j ri sj
- Der MillerRabin Primzahltest
- nur zwei Lösungen nämlich x und x
- Abkürzungen und Symbole
- O B d A Ohne Beschränkung der Allgemeinheit
- Komplexität von Algorithmen
- B Größenordnung von Funktionen
- Komplexität von Algorithmen
- iii Für alle t n R gilt
- sofern die unendliche Summe existiert
Vorschau
Randomisierte Algorithmen & Probabilistische Analyse
Sven O. Krumke
Entwurf vom 5. April 2004
Technische Universität Berlin
ii
Dieses Skript basiert auf der Vorlesung »Randomisierte Algorithmen & Probabilistische Analyse« (Sommersemester 2003) an der Technischen Universität Berlin. Über Kritik, Verbesserungsvorschläge oder gefundene Tippfehler würden ich mich sehr freuen!
Sven O. Krumke krumke@zib.de
Inhaltsverzeichnis
1 Einleitung 1.1 ielgruppe und Voraussetzungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Danksagung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Einführung 2.1 Das Sekretärinnen-Problem . . . . . 2.1.1 Worst-Case-Analyse . . . . 2.1.2 Probabilistische Analyse . . 2.1.3 Randomisierte Algorithmen 2.2 weimal Quicksort . . . . . . . . . 2.2.1 Probabilistische Analyse . . 2.2.2 Randomisierte Algorithmen 1 1 1 1 3 3 4 4 7 7 7 9 13 13 17 19 22 27 33 33 35 36 43 43 46 46 48 48 54 55
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
3 Grundlegende Techniken 3.1 Bedingte Wahrscheinlichkeiten, Unabhängigkeit und einfache Erfolgssteigerung 3.2 Das Prinzip der verzögerten Entscheidungen . . . . . . . . . . . . . . . . . . . 3.3 Das Coupon-Sammler-Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Erzeugende Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Untere Schranken durch das Prinzip von Yao . . . . . . . . . . . . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
4 Momente und Abweichungen 4.1 Die Markov-Ungleichung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Die Chebyshev-Ungleichung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Chernoff-Schranken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Graphenalgorithmen 5.1 Minimale Schnitte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Minimale aufspannende Bäume . . . . . . . . . . . . . . . . . . . . . 5.2.1 Der Algorithmus von Boruvka . . . . . . . . . . . . . . . . . . 5.2.2 Schwere Kanten . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.3 ufällige Stichproben für die MST-Berechnung . . . . . . . . . 5.2.4 Anhang: Der MST-Verifikationsalgorithmus mit Linearzeit . . . 5.2.5 Anhang: Der Kruskal-Algorithmus zur Bestimmung eines MST