NÁHODNOSTNÉ TECHNIKY
• vlastnosti náhodnostných algoritmov
• typy náhodnostných algoritmov
• náhodnostné algoritmy pre optimalizačné problémy
VLASTNOSTI
NÁHODNOSTNÝCH
ALGORITMOV
VLASTNOSTI
NÁHODNOSTNÝCH
ALGORITMOV
ZÁKLADNÉ POJMY
ZÁKLADNÉ POJMY
Definícia 1
Nech S je (konečný) priestor (elementárnych) udalostí.
Pravděpodobnostně rozdelenie je každá funkcia Pr : V (S) —>» [0,1] s vlastnosťami
(
(i (ii
) P r ({x}) > 0 pre každú elementárnu udalosť x £ S ) Pr{S) = 1
) P r {A U B) = Pr(A) + Pr(B) pre každé udalosti A, B C S také, že A n B = 0.
• hodnota Pr{A) sa nazýva pravdepodobnosť udalosti A
• dvojica (S, Pr) sa nazýva pravdepodobnostný priestor
• ak Pr({x}) =     pre všetky elementárne udalosti x G S, tak Pr sa nazýva uniformné pravděpodobnostně rozdelenie
2
Definícia 2
Nech S je konečný priestor udalostí. Každá funkcia X : S —>> K. sa nazýva (diskrétna) náhodná premenná na S.
Definícia 3
Nech (S, P r) je pravdepodobnostný priestor a X náhodná premenná na S. Očakávaná hodnota náhodnej premennej X je
E[X]d^fY,X(s)-Pr({s})
sGS
ekvivalentné označenie střední hodnota náhodní veličiny
3
• očakávaná hodnota konštantný c je
E [c] = c
• očakávaná hodnota súčinu náhodnej premennej X a konštantný c je
E[cX] = cE[X]
• očakávaná hodnota súčtu náhodných premenných X a V je
E[X + Y] = E[X] + E[Y]
• pre nezávislé náhodné premenné X a V je očakávaná hodnota ich súčinu
E[XY] = E[X]E[Y]
4
VLASTNOSTI
NÁHODNOSTNÝCH
ALGORITMOV
PROBLÉM ROVNOSTI
PROBLÉM ROVNOSTI
• na počítači X je uložená databáza x, na počítači Y je uložená databáza y
• x a y sú binárne retazce dĺžky n
• úlohou je rozhodnúť, či x a y sú zhodné
• zaujíma nás, koľko bitov si musia počítače vymeniť, aby dokázali vyriešiť problém rovnosti
• neexistuje deterministický komunikačný protokol, ktorý by riešil problém rovnosti a pritom si počítače vymenili menej než n bitov
• navrhneme náhodnostný protokol, ktorý je výrazne efektívnejší
5
Náhodnostný protokol pre problém rovnosti
vstup   počítač X má binárny reťazec x = xix2 ... xn
počítač Y má binárny reťazec y = yiy2 .. .yn krok 1 X vyberie náhodne prvočíslo p z intervalu [2, r?2]
(uvažujeme uniformné rozdelenie pravdepodobnosti) krok 2 X vypočíta číslo s = Number(x) (mod p)
X pošle binárnu reprezentáciu čísel s a p počítaču Y krok 3  Y vypočíta číslo q = Number(y) (mod p)
ak q    s, tak y vráti odpoveď x^y
ak q = s, tak y vráti odpoveď x = y
platí s < p < n2
zložitost protokoluje rovná dĺžke binárneho zápisu čísel s, p, nanajvýš
2 • |~log2 n2~\ < 4 • |~log2 n"
red kvalita protokolu
• protokol môže poskytnúť chybnú odpoveď
• nech P(n2) — {p | p je prvočíslo, p < r?2}
• prvočíslo p z P(n2) nazveme špatné pre (x, y), ak jeho výber spôsobí, že náhodnostný protokol vráti nesprávnu odpoveď
• pravdepodobnosť chybnej odpovede pre vstup (x, y) je potom
počet špatných prvočísel pre (x, y)
\pUň\
• pre n > 9 platí
|p(n2)| >
7
pokračovanie
• ukážeme, že špatných prvočísel pre (x,y) je nanajvýš n — 1
• ak x = y, tak Number(x) (mod p) = Number(y) (mod p) pre každé prvočíslo p a odpoveď x = y je vždy správna.
• ak x 7^ y, tak počítač Y vráti nesprávnu odpoveď práve ak X vybral prvočíslo p také, že
Number(x)   (mod p) = Number(y)   (mod p)
tj. ak p delí číslo w = \Number(x) — Number(y)\
• pretože x a y sú binárne retazce dĺžky r?, tak w < 2n
• faktorizáciou čísla w dostávame w = p'^ - p% - ... - p'£, pričom
k< n-1
• w má nanajvýš r? — 1 prvočíselných deliteľov
8
ZÁVER
pravdepodobnosť, že protokol vráti nesprávnu odpoveď je pre n > 9
n — 1        n — 1       In r?2
< —-= <
|P(a72)| " n2/ In n2 " n
9
ZÁVER
pravdepodobnosť, že protokol vráti nesprávnu odpoveď je pre n > 9
n — 1        n — 1       In r?2
< —-= <
P(n2)| " n2/ In n2 " n
deterministický vs. náhodnostný protokol
• n = 1016
• zložitosť deterministického protokolu je 1016
• zložitosť náhodnostného protokolu je 256
• pravdepodobnosť, že náhodnostný protokol vráti nesprávnu odpoveď je nanajvýš 0.36892 • 10~14
9
VLASTNOSTI
NÁHODNOSTNÝCH
ALGORITMOV
MODELY NÁHODNOSTNÝCH ALGORITMOV
MODEL 1
náhodnostný algoritmus A chápeme ako pravděpodobnostně rozdelenie nad kolekciou A\, A^ ..., An deterministických stratégií
pre vstupnú inštanciu w sa náhodne vyberie stratégia A;
kvalitu náhodnostného algoritmu určuje jeho zložitosť očakávaná časová zložitosť
presnosť správnosť výsledku pre rozhodnovacie problémy resp. cena riešenia pre optimalizačné problémy
11
očakávaná časová zložitosť
• výpočet A\ na w označme C/, jeho časovú zložitosť Time(C\)
• definujeme pravdepodobnostný priestor
Sa,w — ({Qb • • • 5 C?}, Pr), kde Pr je pravděpodobnostně rozdelenie nad stratégiami Ai,...,An (typicky sa uvažuje uniformné rozdelenie)
• nad Sa,w definujeme náhodnú premennú Z, Z(C/) d= Time(d)
• očakávaná zložitosť A na w je
r?
ExpTimeA(w) d=lf E[Z] = ^ Pr({C/}) • Z(C/)
/=i
• očakávaná zložitosť náhodnostného algoritmu /4 je
def
ExpTimeA{n) — max{ExpTimeA(w) | |w| = n}
presnosť pre rozhodovací problém
• nad Sa,w definujeme náhodnú premennú X predpisom
x def I 1 ak C/ vypočíta pre w správnu odpoveď X(C/) =
0 inak
pravdepodobnosť že A vypočíta pre w správnu odpoveď je
n
ErrorA{w) = E [X] = ^ Pr({C/}) • X(Q)
i=l
pravdepodobnosť chyby pre algoritmus A je
Error/\ = max{l — Errora(w)}
w
pre optimalizačný problém sa mení definícia náhodnej premennej X tak, aby vypovedala o kvalite vypočítaného riešenia
VLASTNOSTI
NÁHODNOSTNÝCH
ALGORITMOV
MAXIMÁLNA SPLNITEĽNOSŤ
MAX-SAT
daná je booleovská formula v konjunktívnom normálnom tvare, hladáme priradenie, ktoré splna maximálny možný počet klauzulí
náhodnostný algoritmus pre MAX-SAT
vstup formula <t> = f\ A F2 A ... A fm v CNF nad množinou premenných {xi,X2,... , xn}
výpočet pre / = 1,..., n, náhodne uniformné vyber hodnotu ol\ G {0,1} (tj. Pr(ai = 1) = Pr(ai = 0) = \)
výstup  (ai, C*2? • • • , <^n)
očakávaná zložitost algoritmu je rovná dĺžke výstupu (a je optimálna)
presnosť
• o kvalite algoritmu vypovedá pomer počtu splnených klauzulí k počtu všetkých klauzulí
• pravdepodobnostný priestor je ({0,      Pr), kde Pr je uniformné rozdelenie nad {0, l}n
• pre vstup 0 = Fi A F2 A ... A fm definujeme náhodné premenné Zi, Z2,..., zm predpisom
• náhodná premenná Z = YHľ=i    vyjadruje počet splnených klauzulí; kvalita algoritmu je tak vyjadrená hodnotou e [z]
1   ak klauzula F/ je splnená priradením a 0   ak klauzula F/ nieje splnená priradením a
m m
e[z] = e[j2z;]=j2EW
i=l i=l
15
pokračovanie
• predpokladáme, že žiaden literál sa v klauzule neopakuje, že žiadna klauzula neobsahuje súčasne literály x a ->x a že všetky klauzule sú navzájom rôzne
• klauzula F; je nesplnená práve ak všetky jej literály majú hodnotu 0
E [Zi]   =   1 • Pr(F; je splnená) + 0 • Pr(F; nie je splnená)
1 1
=   1--r > -
2k  ~ 2
m m 1
e[z] = E^]>Eíh?
i=l i=l
• očakávaný počet splnených klauzulí pre formulu s m klauzulami je aspoň m/2
16
pokračovanie
• ak každá klauzula obsahuje aspoň k literátov, tak očakávaný počet splnených klauzulí pre formulu s m klauzulami je
(i-(^>
• algoritmus je výhodný pre formule s dlhými klauzulami
• ak každá klauzula má práve 3 literály (MAX-E3-SAT), tak očakávaný počet splnených klauzulí je |m
tj. aproximatívny pomer algoritmu (v očakávanom prípade)
17
VLASTNOSTI
NÁHODNOSTNÝCH
ALGORITMOV
MAXIMÁLNY REZ
MAXIMÁLNY REZ GRAFU (MAX-CUT)
daný je neorientovaný hranovo ohodnotený graf
hľadáme taký rozklad (rez) množiny vrcholov grafu, ktorý maximalizuje súčet cien hrán rezu
náhodnostný algoritmus pre MAX-CUT
vstup graf G — {V^ H), ohodnotenie hrán w : H —> Z
výpočet pre každý vrcholv v & V: s pravdepodobnosťou | pridaj v do množiny U
výstup U,V\U
očakávaná zložitosť algoritmu je rovná počtu vrcholov (a je optimálna)
18
přesnost
definujeme náhodné premenné Z,y pre i, j G {1,..., | V\} predpisom
def ZU =
l ak {/,;} e H, i e U, j e V\U
0 inak
náhodná premenná Z = X^{/y}eH wij^u vyjadruje váhu hrán
rezu
e [z] = ^2 wuE[zij] = ^2 w'jpr\.{'ij}^hrana rezu]
VJ}€H {i,j}€H
= \ E wu
{'J}€H
> -OPT ~ 2
VLASTNOSTI
NÁHODNOSTNÝCH
ALGORITMOV
MODEL II
MODEL 2
• v každom kroku výpočtu existuje niekoľko možností, ako vo výpočte pokračovať
• každá možnosť má určenú pravdepodobnosť
• pravdepodobnostný priestor sa definuje rovnako ako pre model 1
• hodnota Pr(C/) je definovaná ako súčin pravdepodobností výberov uskutočnených vo výpočte C;
• všetky ostatné pojmy sú definované analogicky ako pre model 1
PRÍKLAD - QUICKSORT
Náhodnostný Quicksort
vstup množina čísel A
krok 1 ak A = {b} tak výstup je b
ak \A\ > 2, tak náhodne vyber prvok a G A
krok 2 /\< := {b G /\ I b < a} A> := {b G 4 I b > a}
výstup (Quicksort(/4<), a, Quicksort(/4>))
21
TYPY NÁHODNOSTNÝCH ALGORITMOV
KLASIFIKÁCIA NÁHODNOSTNÝCH ALGORITMOV
Las Vegas
bez chybnej odpovede
s prípustnou odpoveďou neviem
Monte Carlo
• s jednostrannou chybou
• s dvojstrannou chybou
• s neohraničenou chybou
TYPY NAHODNOSTNYCH ALGORITMOV
LAS VEGAS
LAS VEGAS ALGORITMY
Náhodnostný algoritmus A sa nazýva Las Vegas algoritmus pre funkciu F ak pre každý vstup x
Pr{A{x) = F (x)) = 1.
• algoritmus pre každý vstup vypočíta správny výstup
• kľúčovou charakteristikou Las Vegas algoritmu je jeho očakávaná časová zložitosť
• príklad: Quicksort s očakávanou časovou zložitosťou 9{n log n)
23
LAS VEGAS ALGORITMY S ODPOVEĎOU NEVIEM
predpokladáme, že algoritmus ako výstupnú hodnotu môže poskytnúť tzv. neutrálnu odpoveď, označujeme ju neviem
Nech A je náhodnostný algoritmus, ktorý môže ako výstup poskytnúť hodnotu neviem. A sa nazýva  Las Vegas algoritmus pre funkciu F ak pre každý vstup x
(i) Pr(A(x) = F(x)) > 1/2
(ii) Pr(A(x) = neviem) = 1 - Pr(A(x) = F (x))
• algoritmus pre každý vstup buď vypočíta správny výstup, alebo ako výstup poskytne hodnotu neviem
• správny výstup vypočíta s pravdepodobnosťou aspoň 1/2
PRÍKLAD - ROVNOSŤ PODREŤAZCOV
• počítač X má desať reťazcov xi,X2,... ,xio G {0, l}n počítač Y má desať reťazcov yi,y2, • • • ,yio G {0, l}n
• počítač X má rozhodnúť, či existuje j e {1,..., 10} také, že
*/ = X/'
• zaujíma nás, koľko bitov si musia X a Y vymeniť, aby dokázali problém vyriešiť
• deterministický protokol potrebuje v najhoršom prípade lOn bitov
• ukážeme, že existuje randomizovaný protokol, ktorému stačí n + 0(\ogn) bitov
náhodnostný protokol RP pre rovnosť podreťazcov
vstup X má reťazce xi,X2,...,xio £ {0, l}n
Y má reťazce yi,y2,... ,yio e {0,1}"
krok 1 X vyberie náhodne (uniformně) 10 prvočísel pi,... , pio
z intervalu [2, r?2] krok 2 X vypočíta s; = Number(x;) (mod p/) pre / = 1,..., 10 a
pošle čísla pi,..., pio, si,..., sio počítaču y krok 3 V vypočíta q\ — Number{yi) (mod p/) pre / = 1,..., 10 krok 4a ak s; 7^ q\ pre všetky / = 1,..., 10, tak Y pošle X
hodnotu 0 a X vráti odpoveď zamietam krok 4b v opačnom prípade nech j je najmenšie číslo pre ktoré
5j = Q j
Y pošle reťazce j a y,- počítaču X krok 5 X porovná xj a y,-
ak sú zhodné, vráti odpoveď akceptujem ak sú rôzne, vráti odpoveď neviem
zložitosť protokolu RP
• v najhoršom prípade si počítače vymenia čísla pi,..., pio, si,..., sio, Jy j (presnejšie: ich binárne zápisy)
• čísla pi,..., pio, si,..., sio sú menšie než r?2 a každé sa dá reprezentovat binárnym retazcom dĺžky 2[log2r?
• číslo j sa dá reprezentovať 4 bitmi, yj má n bitov
• spolu n + 40 |~log2 n \ + 4 = n + 0(\og n) bitov
27
presnosť protokolu RP
nech r = xi,..., xio,yi,... , yio je vstup taký, že x; 7^ y/ pre / G {1,... ,10}
• ak pre všetky vybrané prvočísla platí
Number(xi) (mod p;) 7^ Number{y\) (mod p/), tak protokol vráti správnu (zamietajúcu) odpoveď
• pre náhodne vybrané p; G P(r?2) je pravdepodobnosť toho, že Number(xj) (mod p/) 7^ Number(yi) (mod p/) aspoň
1 2lnn r?
^ /r^«/ \ XX 2lnr?xio . 20lnr? 1 Pr(RP(r) = zamietam)) > (l--—)    > 1--— > -
• naopak, ak pre nejaké vybrané prvočíslo platí Number(xi) (mod p/) = Number{y\) (mod p/), tak protokol vráti odpoveď neviem
nech r = xi,..., xio, yi,...,yio je vstup a nech j je najmenšie číslo také, že xy = yj
• zrejme Number(xj) (mod py) = Number(yj) (mod py) a protokol akceptuje práve ak Number(x;) (mod p,-) 7^ Number{yi) (mod p/) pre všetky / G {1,... ,7 — 1}
• analogicky ako v predchádzajúcom prípade sa dá ukázať, že pravdepodobnosť takejto udalosti je
z      2 In r?N ;_i 2f / — 1) • In n
(1--y > 1 - ——-—
v        n   J n
• výraz nadobúda minimálnu hodnotu pre j = 10 a preto
^ /r^/ x , x ^ 18 In r? 1 Pr(RP(r) = akceptujem) > 1--> -
• naopak, ak existuje / G {1,... J — 1} také, že Number{x\) mod p/ = Number{y\) mod p/, tak protokol vráti odpoveď neviem.
TRANSFORMÁCIE LAS VEGAS ALGORITMOV I
transformácia algoritmu A s odpoveďou neviem na algoritmus 6, ktorý vypočíta vždy správnu odpoveď
• B simuluje A
• ak A vypočíta odpoveď neviem, tak B začne nový beh algoritmu A
• v opačnom prípade vráti B rovnaký výsledok ako A
vlastnosti algoritmu B
• ak výpočet B skončí, tak vždy vráti správnu odpoveď
• očakávaná časová zložitosť algoritmu B je ExpTimeB(n) G (9(7/rne/\(r?))
30
očakávaná časová zložitosť algoritmu B
• pravdepodobnosť, že B skončí po jednom behu A je aspoň 1/2,
po dvoch behoch 3/4, atď.
• pravdepodobnosť, že B skončiv čase nanajvýš k • 77me/\(i/i/) je aspoň 1 - ^
• búno všetky výpočty A na w s výsledkom neviem majú dĺžku TimeA^w)
• pre / G N nech Ser; označuje množinu tých výpočtov C algoritmu B na w, pre ktoré
(/ — 1)TimeA^w) < Time(C) < i • 77me/\(i/i/)
E P'({C}) <
CeSeti
oo
ExpTimeB(n)   =   ^ E  TimeB(C) ■ Pr({C})
i=l CeSetj
oo ^
< TimeA(w) •
i=i
oo ^
i=i
< 6 • 77me/\(i/i/)
TRANSFORMÁCIE LAS VEGAS ALGORITMOV II
transformácia algoritmu A, ktorý poskytne vždy správnu odpoveď, na algoritmus B s prípustnou odpoveďou neviem
• transformácia má opodstatnenie v prípadoch, keď niektoré výpočty algoritmu A sú neúmerne dlhé
• ako zvoliť hramicu, po ktorej B zastaví beh A a vráti odpoveď neviem tak, aby B bol stále Las Vegas algoritmus?
• postačujúcou hranicou je
2 • ExpTimeA(w)
pretože viac než polovica výpočtov A na w nemôže mať časovú zložitosť väčšiu nezje dvojnásobok priemeru (tj. ExpTimeA(w))
TYPY NAHODNOSTNYCH ALGORITMOV
MONTE CARLO
MONTE CARLO S JEDNOSTRANNOU CHYBOU
pre rozhodovacie problémy
Nech A je randomizovaný algoritmus pre jazyk L. A je Monte Carlo algoritmus s jednostrannou chybou (1MC) pre L ak
(i) pre každé x e L platí Pr{A{x) = 1) > 1/2
(ii) pre každé x 0 L platí Pr{A{x) = 0) = 1
špeciálny prípad 1MC algoritmu: hodnota Pr{A{x) — 1) sa s rastúcou dĺžkou x limitné blíži k 1
34
príkladom Monte Carlo algoritmu s jednostrannou chybou je randomizovaný protokol pre problém rovnosti
protokol akceptuje jazyk
L = {(x,y)\x,y e {0,1}",x ŕ Y,n EN}
protokol akceptuje slovo z jazyka L s pravdepodobnosťou aspoň 1 —
pre slovo nepatriace do L vypočíta protokol vždy správnu (zamietajúcu) odpoveď
pre uvedený protokol platí, že pravdepodobnosť akceptovania sa pre slová z [s rastúcou dĺžkou slov limitné blíži k 1
AMPLIFIKÁCIA
úprava algoritmu s cieľom znížiť pravdepodobnosť chybnej odpovede pri zachovaní jeho (asymptotickej) zložitosti
motivácia
• presnosť vs dôveryhodnosť
• rozdiel medzi hodom mincou a náhodnostným výpočtom
amplifikácia algoritmu A typu Monte Carlo s jednostrannou chybou
konstruujeme algoritmus A^
• algoritmus A^ zopakuje výpočet algoritmu A na vstupe x nezávisle(l) k krát za sebou
• nech cti, ct2, • • •, &k sú výstupy jednotlivých výpočtov
• ak existuje index j taký, že aj = 1, tak algoritmus A^ akceptuje vstup; v tomto prípade x zaručene patrí do L
• naopak, ak ai = (12 = ... = a k = 0, tak algoritmus A^ zamietne; zamietajúca odpoveď algoritmu A^ môže byť nesprávna
• pravdepodobnosť nesprávnej odpovede algoritmu A^ je (Pr(A(x) = 0))^ ; vlastnosť (i) 1MC algoritmu A garantuje, že {Pr{A{x) = 0))* < (1/2)*
vlastnosti amplifikovaného algoritmu Ak
• voľba parametru k je daná požadovanou presnosťou amplifikovaného algoritmu: ak požadujeme presnosť s, tak volíme k tak, aby 1 — (1/2)^ < e
• časová zložitosť algoritmu Ak je k násobkom zložitosti algoritmu A (lineárny nárast)
• pravdebobnosť chybnej odpovede klesá exponenciálne s rastúcim parametrom k
ALGORITMUS MONTE CARLO S OHRANIČENOU CHYBOU
Randomizovaný algoritmus A je Monte Carlo algoritmus s ohraničenou chybou pre funkciu F práve ak existuje s G M, 0 < s < 1/2, také, že pre každý vstup x
Pr(A(x) = F(x)) >±+e.
Las Vegas a Monte Carlo algoritmy s jednostrannou chybou sú špeciálnym prípadom Monte Carlo algoritmov s ohraničenou chybou
39
amplifikácia algoritmu A typu Monte Carlo s ohraničenou chybou
konstruujeme algoritmus At, ktorý pre vstup x
• zopakuje výpočet A na x (nezávisle!) t krát za sebou výstupy jednotlivých výpočtov označí a\,... ,at
• ak existuje hodnota a, ktoré sa v postupnosti ol\, • • • ? &t opakuje aspoň |~|] krát, tak výstupom výpočtu je a
• v opačnom prípade je výstupom neviem
algoritmus At vypočíta správny výsledok s pravdepodobnosťou aspoň
1 - (1 -A-s2ý
dôkaz vlastností amplifikovaného algoritmu At
• pre vstup x označme p a ex čísla také, že
p = Pr(A(x) = F(x)) = \ + ex
• určíme, aká je pravdepodobnosť pr/(x) toho, že algoritmus At vypočíta správny výsledok v práve i výpočtoch (/ < [ŕ/2])
41
pr/(x) =
<
<
t i t i t i
t
i
t
i
t
i
t
i
t
i
p' • (1 - p)
t—l
t > 2i
p.(l-p))'\(l-p)
t—2/
P = 2 +6ľ
x
(^+£x)-(^
i
4 1 4 1 4 1 4 1 4
.2 v
1 1
2 - £x < 2 + £x
£x) • (2 +0)
f-'
A        °X/ V/l
2^2
--e2Y
A J
42
At vypočíta správny výsledok F(x) práve ak aspoň [ŕ/2] behov A vypočíta správny výsledok a preto
Pr(At(x) = F(x))   = l-^pr((x)
;=o
>  1 -
±ch-*>1
i=0 v 7
L4J
1 t z
i-(;-4)!-E
;'=0
t
i
> 1 -
> 1 -
> 1 -
(1-4 .x
(l-4-£2)5
43
horná hranica pre veľkosť chyby (1 — 4 • e2)i sa s rastúcim t blíži k 0
ak chceme, aby pre danú konštantu S platilo
Pr(At(x) = F {x)) >l-5, tak stačí zvoliť t také, že
2 • In č
t >
ln(l -A-s2)
ak ô a e sú dané konštanty, tak ŕ je tiež konštanta a
TimeAt{n) £ 0{TimeA{n))
44
MONTE CARLO S NEOHRANIČENOU CHYBOU
Randomizovaný algoritmus A je Monte Carlo algoritmus
s neohraničenou chybou pre funkciu F práve ak pre každý vstup x
platí
Pr(A(x) = F(x)) > \.
45
amplifikácia algoritmu A typu Monte Carlo s ohraničenou chybou
• pre algoritmus A s neohraničenou chybou sa rozdiel medzi pravdepodobnosťou chyby a hodnotou 1/2 môže s rastúcou dĺžkou vstupu blížit k 0
• ak chceme, aby pre dané fixné S platilo
Pr(At(x) = F (x)) >l-6,
tak počet nezávislých opakovaní algoritmu A musí byť
/, ,x 2 • In ô
ŕ(|x|)* m(i-4.rf)
uvážme situáciu keď Pr(A(x) — F (x)) = \ + ^ > \ aký musí byť počet t nezávislých opakovaní výpočtu A na x, ak požadujeme, aby pre danú konštantu S platilo Pr{At{x) = F(x)) > 1 - ô
/, ,x 2 • In ô
((H> ä ,n(1 _ 4.4)
2 • In 5
- c
X
ln(l-4-2-W)
e, = 2"lxl
2 • In ô * v
-   _2-2-|x| ln(l-y) <-y pre 0<y < 1
=   (-2 -In S) -2
2- x
časová zložitosť je exponenciálna voči dĺžke x,
TimeAt(x) > (-2 • In 5) • 22'W • TimeA(x)
AMPLIFIKÁCIA
AMPLIFIKÁCIA
• úprava algoritmu s cieľom znížiť pravdepodobnosť chybnej odpovede pri zachovaní jeho (asymptotickej) zložitosti
• triviálny postup: opakovanie celého výpočtu
• ako postupovať v situácii, keď opakovanie celého výpočtu vedie k neakceptovateľnému zvýšeniu zložitosti?
MINIMÁLNY REZ
vstup neorientovaný graf
prípustné riešenie rez grafu, tj. rozklad množiny vrcholov grafu na množiny (/4, B)
cena riešenia veľkosť rezu (/4, B), tj. je počet hrán (s, ŕ) grafu takých, že s G A, t G 6
cieľ prípustné riešenie s minimálnou cenou
49
DETERMINISTCKÝ ALGORITMUS
• redukcia na problém nájdenia minimálneho s — t rezu v orientovanom grafe
• v grafe G nahradíme neorientovanú hranu (u, v) G E dvojicou opačne orientovaných hrán (u, v) a (v, u) s kapacitou 1
• zvolíme pevne vrchol s a pre všetky vrcholy t G V \ {s} vypočítame veľkosť minimálneho s — t rezu
• kapacita minimálneho s — t rezu je rovná hodnote maximálneho s — t toku
• celková zložitosť 0(n3)
50
NÁHODNOSTNÝ ALGORITMUS
• algoritmus založený na kontrakcii vrcholov
• multigraf G = (\/, E) - násobné hrany medzi vrcholmi
• kontrakcia: náhodne vyberieme hranu (l/, v) grafu G a vytvoríme graf G'
• u b v sú spojené do jedného nového vrcholu w\ všetky ostatné vrcholy zostávajú nezmenené
• hranu, ktorej jeden z koncových vrcholov tvorí u alebo v, nahradíme hranou s koncovým vrcholom w\ ostatné hrany sú nezmenené
• postup rekurzívně aplikujeme na G'
• G' má supervrcholy w; každý supervrchol w zodpovedá množine S(w) C V
• výpočet končí keď G1 obsahuje len dva supervrcholy v\ a V2
• množiny S(vi) a S(v2) určujú rozklad množiny vrcholov
iniciálne volanie: graf G (V, E) a funkcia S(v) = {v}
Funkce kontrakce(g = (V,E),S: V ->■ 2V)
1 if G má dva vrcholy 1/1 a 1/2 then return (rez (S(vi), S(i/2))
2 náhodne vyber hranu (u, v) G E
3 V <^VU{zuv}\{u,v}
4 E <- E U { {x, zuv} I {x, y} G E, y = u alebo y = v}
5 E <(— E \ { {x,y} I {x,y} G E,y = u alebo y = v}
6 S(zuv) <- S(u) U S(v)
7 Kontrakce(G = (V, E), S: V ^ 2V)
52
Algorimus kontrakcií nájde globálny minimálny rez s pravdepo-
• označme k veľkosť minimálneho rezu
nech F je množina hrán, ktoré tvoria minimálny rez (/4, B)
• ak algoritmus v niektorom z krokov kontrahuje hranu z F, tak jeho výstupom nemôže byť rez (/4, B)
• pre odhad pravdepodobnosti kontrakcie hrany z F potrebujeme odhad počtu hrán: každý vrchol má stupeň aspoň k a preto \E\ > \kn
• pravdepodobnosť, že v prvej iterácii je kontrahovaná hrana
k 2
53
uvažujme situáciu po j iteráciach, keď graf G má n—j supervrcholov a žiadna hrana z F nebola kontrahovaná
každý rez grafu G je rezom grafu G a preto každý vrchol v má stupeň aspoň k
celkový počet hrán v G je aspoň \k(n — j)
pravdepodobnosť, že v iterácii j + 1 je kontrahovaná hrana z F je nanajvýš
k 2 \k(n-j)     n-j
algoritmus nájde rez (/4, B) práve ak v žiadnej iterácii sa nekontrahuje hrana z F
• udalosť ej - v iterácii j nieje kontrahovaná hrana z F
• Pr(ei) >l-2/n
• Pr(£J+1 | £i n £2 n ... n e/) > 1 - 2/(n - j)
Pr(ei) • Pr(^2 | ^1) • • • Pr{en-2 \ e\ n ... n £n_3)
>(!--)(! n
=(—)<"
)...(!
r?
r? —
r? —
-x--4
n(n-l)
n
2
- 2 -i
)
n-j 2 1
<4><3>
55
zložitosť algoritmu kontrakcií
• pravdepodobnosť, že algoritmus nenájde globálny minimál rez je nanajvýš (1 — 1/(2))
• opakovaním výpočtu môžeme znížiť pravdepodobnosť neúspechu (z nájdených rezov vyberáme najmenší)
• ak opakujeme výpočet (£) krát, tak pravdepodobnosť neúspechu je nanajvýš
• celková zložitosť vyššia ako u deterministického algoritmu
optimalizácia algoritmu kontrakcií
1. graf kontrahujeme až kým nemá /(r?) vrcholov, ďalej počítame deterministicky
(optimálna voľba funkcie /(r?) = |_/72/3J)
2. pretože pravdepodobnosť chybnej voľby hrany rastie s počtom iterácií, pri opakovaní výpočtu opakujeme len kontrakcie
v záverečných iteráciach
pri optimálnej voľba parametra h a počtu opakovaní je pravdepodobnosť neúspechu ohraničená konštantou a zložitosť výpočtu je 0(n2{\og n)3)
57
DERANDOMIZÁCIA
DERANDOMIZÁCIA
• algoritmická technika transformácie randomizovaného algoritmu na deterministický algoritmus, ktorý garantuje rovnako dobré výsledky ako randomizovaný algoritmus
• prečo navrhujeme randomizovaný algoritmus?
• (veľmi často) je jednoduchšie analyzovat a dokázat vlastnosti randomizovaného algoritmu než jeho deterministickej varianty
• randomizácia prináša jednoduchost návrhu a analýzy algoritmu, derandomizácia zachováva parametry algoritmu
MAXIMÁLNA SPLNITEĽNOSŤ (MAX-SAT)
Náhodnostný algoritmus pre MAX-SAT
vstup formula <t> = F\ A F2 A ... A Fm v CNF nad množinou premenných {xi,X2,... ,xn}
výpočet náhodne vyber priradenie (ai, a^,..., ctn) G {0, l}n s pravdepodobnosťou Pr(at — 1) = Pr(at — 0) = |,
výstup (ai, C*2j • • • j <2n)
• náhodná premenná Z vyjadruje počet splnených klauzulí
• očakávaný počet splnených klauzulí je
E[Z] > m/2 = ^0P7
59
DERANDOMIZÁCIA ALGORITMU PRE MAX-SAT
• namiesto náhodného rozhodnutia, či premenná x; má hodnotu true alebo false, priradíme hodnotu premennej x; deterministicky
• postupujeme sekvenčne: najprv určíme hodnotu premennej xi, potom X2, atď.
• využíva sa vlastnosť self-redukcie problému
60
• ako určíme hodnotu premennej x\l
• predstavme si, že hodnotu premennej x\ určíme deterministicky, ale hodnoty všetkých ostatných premenných určíme náhodne
• v takom prípade má zmysel zvoliť hodnotu premennej x\ tak, aby sa maximalizovala očakávaná hodnota počtu splnených klauzulí výsledného riešenia
• predpokladajme, že vieme vypočítať očakávaný počet splnených klauzulí E[Z|Xl=i] formule FXi:=i, ktorá vznikne z F dosadením hodnoty true za x\
• premennej x\ priradíme hodnotu true práve ak očakávaný počet je vyšší pre formulu FXl-—\ než pre formulu FXi-q
61
predpis pre určenie hodnoty premennej x\
xi : =
1 ak E[Z\X1=1] > E[Z\ xi =0 J 0 inak
z definície očakávanej hodnoty platí
E[Z]   =   E[Z\Xl=1]Pr[x1 = l] + E[Z\Xl=0]Pr[x1 = 0] =   \{E[Z\X1=1\ + E[Z\X1=0})
ak zvolíme x\ — 1, tak E[Z|Xl=i] > E[Z] ak zvolíme x\ — 0, tak E[Z|xl=o] > E[Z]
62
nech hodnoty, ktoré sme priradili premenným
X\,..., X j
ako určíme hodnotu premennej x,-+i? analogickým postupom:
1 ak f[Z|Xl=ai)...)X/=a/)X/+1=i] > f[Z|Xl=ai)...)X/=a/)X/+1=o] 0 inak
z definície očakávanej hodnoty platí
1
E[Z|Xl=aij. ..?X/.=a/]    =    — E[Z\Xl=ai^ ..)X/=a/,x/+i=l]
1
+ ^ ^    Ui=ai,... ,x/=a/ ,x/+i =o]
63
• pokračujeme až kým neurčíme hodnoty všetkých premenných
• očakávaný počet splnených klauzulí E[Z|Xl=aiv..?Xn=an] vo formule FXl=aij...jXn=an je rovný počtu splnených klauzulí pre zvolené hodnoty premenných
• indukciou overíme, že
1
počet splnených klauzulí = E[Z\Xl=au...,Xn=an] > E [Z] > -OPT
64
ako vypočítame hodnotu £[Z|Xl=ai>...jX/=a/]?
m
F[Z|Xl=ai?...?X/=a/] = ^2 ^[klauzula C; formule FXl=air..?X/=a/ je splnená]
i=i
pre klauzulu C; je
• pravdepodobnosť jej splnenia rovná 1 ak klauzula je po dosadení hodnôt splnená
• pravdepodobnosť je (1 — (\)k) ak po dosadení hodnôt obsahuje klauzula k literálov
65
príklad
F Z
(xi V x2 V -nx3 V x4) A (-ixi V ^x2 V x4) A x2 A (x3 V -1X4)
15|7|1,3_49 16~r8^~2~r4 — 16
8q=i = ŕ^i/e A (^x2 V x4) A x2 A (x3 V -nx4)
^xi = l — -L-^4-h2-h4 — 16
8ci=o = (*2 V -nx3 V x4) A true A x2 A (x3 V -nx4)
7    ^ — Zi1ili3_50 z-xi=0 — g   1  -1-  1   o   1   /i —
16
pre     volíme hodnotu /a/se
66
príklad - pokračovanie
F = (xi V x2 V ^x3 V x4) A (-1x1 V ^x2 V x4) A x2 A (x3 V
FXl=o,x2=o = (-"X3 V x4) A žrue A /ä/se A (x3 V -1x4) Zxl=0,x2=o = | + l + 0 + | = f§
8q=o,x2=i = true A ŕ/r/e A true A (x3 V -1x4) ZXl=0,x2=l = 1 + 1 + 1 + f = fg
pre     volíme hodnotu false
DERANDOMIZÁCIA - ZHRNUTIE
• method of conditional expectations
• „selfredukovateľnosť" problému
• technika sa dá aplikovať na ďalšie prezentované algoritmy
68
NÁHODNOSTNÉ ALGORITMY PRE OPTIMALIZAČNÉ PROBLÉMY
RANDOMIZÁCIA A OPTIMALIZAČNÉ PROBLÉMY
aproximatívny pomer RA algoritmu A chápeme ako náhodnú premennú
cieľom je
• odhadnúť strednú hodnotu náhodnej premennej RA, alebo
• garantovať, že aproximatívny pomer S sa dosiahne s pravdepodobnosťou aspoň 1/2.
69
RANDOMIZOVANÉ APROXIMATÍVNE ALGORITMY
Nech S je konštanta, S > 1. Randomizovaný algoritmus A je randomizovaný E[(5]-aproximatívny algoritmus pre optimalizačný problém U práve ak pre každý vstup x platí, že A{x) je prípustné riešenie x a zároveň   E[(/?/\(x)] < ô
Nech S je konštanta, S > 1. Randomizovaný algoritmus /4 je randomizovaný 5-aproximatívny algoritmus pre optimalizačný problém U práve ak pre každý vstup x platí, že A{x) je prípustné riešenie x a zároveň   Prob(/?/\(x) < 5) > 1/2
/?/\(x) je aproximatívny pomer algoritmu A na vstupe x
NÁHODNOSTNÉ ALGORITMY PRE OPTIMALIZAČNÉ PROBLÉMY
MAXIMÁLNA SPLNITEĽNOSŤ
Náhodnostný algoritmus pre MAX-SAT
vstup formula <t> = C\ A ... A Cm v CNF nad množinou premenných {xi, X2,..., xn} váhová funkcia w\ C — {Ci,... Cm} IR
výpočet náhodne vyber priradenie (ai, qí2, . •., an) g {0, l}n s pravdepodobnosťou Pr(a; = 1) = Pr(a/ = 0) = |,
výstup (ai, Q2? ■ ■ • j c^n)
analýza algoritmu
• náhodná premenná 1/1/ = váha splnených klauzulí
• pre klauzulu c, náhodná premenná l/l/c je rovná váhe, ktorou klauzula c prispieva do l/l/, 1/1/ = J2cgC
označme k počet literálov v klauzule c
klauzula je nesplnená práve ak všetky jej literály sú false, tj. s pravdeposobnosťou 2~k
očakávaná hodnota náhodnej premennej Wc je
F[l/I/C] = wcPr[c je splnená] + 0Pr[c nie je splnená] = wc{l
pre k > 1 platí 1 - 2~k > 1/2 a preto
E[W]=J]E[WC] > ±$>c> ^0P7
kde OPT ]e hodnota optimálneho riešenia
MAX-SAT A ÚLOHA LINEÁRNEHO PROGRAMOVANIA
• pre konštruckiu náhodnostného algoritmu pre MAX-SAT využijeme redukciu na úlohu lineárneho programovania
• pre každú klauzulu c G C označme      (S~) množinu tých literátov, ktoré sa v c vyskytujú v pozitívnom tvare
(s negáciou)
• každej premennej x; booleovskej formule F zodpovedá premenná y úlohy lineárneho programovania
• každej klauzule c zodpovedá premenná zc; hodnota zc = 1 indikuje, že klauzula je splnená
• lineárne ohraničenia garantujú, že zc = 1 len ak aspoň jeden literál klauzuly je splnený
73
redukcia MAX-SAT na úlohu LP
maximalizovať wczc
pri splnení ^ y; + ^ (1 - y/) > zc c G C
/es+ ;esc-
zcG{0,l} CGC y/ G {0,1}      / =
relaxovaná úloha LP
maximalizovať i/i/c^c
pri splnení ^ y/ + ^ (1 - y/) > zc      c G C
0 < zc < 1       c e C
0 < y i < 1       / = 1,..., n
74
vyriešime relaxovánu úlohu LP
nech (yi,... ,y„, zi,..., zm) je optimálne riešenie
booleovskej premennej x; priradíme hodnotu true s pravdepodobnosťou y;
kvalitu nájdeného riešenia vyjadríme pomocou náhod premenných W a Wc
Ak klauzula c má k literátov, tak
E[WC] = (1 - (1 - -k)k)wczc .
• búno c = (xi V ... V x/c)
• c je splnená práve ak nie všetky jej literály majú hodnotu false; pravdepodobnosť takejto udalosti je
i-nf=i(i-y/) >i-(SH^)fc = i-(i-^)fc
>l-(l-f)* zcG[0,l] >l-{l-\)kzc
76
Ak všetky klauzule majú veľkosť nanajvýš k, tak E [l/l/] > (1 - (1 - l)k)OPT
• označme kc veľkosť klauzule c a OPTf hodnotu optimálneho riešenia relaxovanej úlohy LP
• využijeme fakt, že funkcia (1 — (1 — \)k) je klesajúca
E[W] =Ec€Cf[Wc]
> EcgcC1 - í1 " Tc)kc)wcZc >(l-(l-kk)k)EcecWcZc
> (1 - (1 - i)*)OPT7 >(i-(i- i^opt
Algoritmus založený na redukcii na úlohu LP je randomizovaným (1 — l/e) aproximatívnym algoritmom pre MAX-SAT.
KOMBINOVANÝ NÁHODNOSTNÝ ALGORITMUS
• pozorovanie
• algoritmus, ktorý náhodne priraďuje hodnoty premenným, sa chová dobre pre formule s veľkými klauzulami
• naopak, algoritmus založený na redukcii na úlohu lp, sa chová dobre pre formule s malými klauzulami
• otázka
• ako postupovať pre obecnú formulu? kombinovaný algoritmus
náhodne, s pravdepodobnosťou 1/2, vyber jeden z uvažovaných algoritmov
78
Pre kombinovaný algoritmus platí e[W] > |OPT.
• Ai - algoritmus náhodného výberu A2 - algoritmus redukcie na úlohu LP
• dokázali sme, že ak klauzula c má veľkosť k, tak
e[Wc\Ai]   = (l-2"Vc e[WC\A2]   > {l--k)k)wczc
pre kombinovaný algoritmus platí
e[WC]   =   1{e[WC\A!]) + ±e[WC\A2])
(l-2-k + (l-l)k)) 3 >-----wczc > -wczc
e[w] =    Eiwc] >    WcZc = l0PJf ^
oeC oeC
DERANDOMIZÁCIA KOMBINOVANÉHO ALGORITMU
deterministický algoritmus
1. použi derandomizovaný 1/2 aproximatívny algoritmus pre MAX-SAT
2. použi derandomizovaný 1 - 1/e aproximatívny algoritmus pre MAX-SAT
3. výstupom je lepšie z vypočítaných priradení
jedno z vypočítaných riešení musí mať cenu aspoň E[W] > |OPT a preto deterministický algoritmus 3/4-aproximatívnym algoritmom pre MAX-SAT
80
tesné príklady pre 3/4-aproximatívny algoritmus pre MAX-SAT
• f = (Xl V x2) A (-1x1 V x2) A (xi V -1X2) A (-1X1 V -1X2) s jednotkovou váhou klauzulí (OPT=3 a OPTf = 4)
• f = (xVy) A(xV^y) A(^aVz) s váhami klauzulí 1, 1 a 2