Véletlenített algoritmusok Tegyük fel, hogy van két doboz (A,B), amely egyike 1000 Ft-ot tartalmaz, a másik üres. 500 Ft-ért választhatunk egy dobozt, amelynek a tartalmát megkapjuk. A feladat megoldására két determinisztikus algoritmus használható vagy A-t választjuk vagy B-t. Mindkét algoritmus költsége a legrosszabb esetben 500 (azon input esetén, amelyben nem találtuk meg a pénzt). Másrészt, ha egy olyan véletlenített algoritmust használunk, amely 1/2 valószín˝uséggel választja mindkét ládát, akkor mindkét inputra az algoritmus költségének várható értéke 1/2 · 500 + 1/2 · −500 = 0. Ilyen esetben, ha az algoritmus használ véletlenül generált döntéseket, véletlenített algoritmusról beszélünk. Ezen algoritmusok futása függ a véletlen döntésekt˝ol, így az algoritmus hatékonysága (a kapott eredmény vagy a futási id˝o) egy valószín˝uségi változó, amelynek a várható értékét szokás vizsgálni. Las Vegas és Monte Carlo algoritmusok Az olyan algoritmusokat, amelyek biztosan helyes eredményt adnak Las Vegas típusú algoritmusnak nevezzük (ez esetben az algoritmus futási ideje függ a véletlen döntésekt˝ol és az egy valószín˝uségi változó). Az olyan algoritmusokat, amelyek nem biztos, hogy helyes eredményt adnak (viszont általában kicsi a futási idejük, és gyakran független a véletlen döntésekt˝ol) Monte Carlo típusú algoritmusoknak hívjuk. Eldöntési problémákra az utóbbiak kétfélék lehetnek. • Egyoldali hibás Monte Carlo algoritmus: ekkor az algoritmus az egyik (vagy az igen vagy a nem) válasz esetén nem hibázhat, a másik válasz esetén a hiba valószín˝usége alulról korlátozott. • Kétoldali hibás Monte Carlo algoritmus: mindkét válasz esetén hibázhat az algoritmus, de adott alsó korlát a hibázás valószín˝uségére. Munkatárs felvételének problémája Tegyük fel, hogy egy vállalat alkalmazottat keres és egy állásközvetít˝o minden nap egy új jelöltet küld. A jelölt meghallgatása után dönteni kell felvesszük -e. Ekkor a következ˝o eljárás lényegében az egyetlen, amelynek a végén a legjobb jelöltünk van. A küldött embereket 1-t˝ol n-ig jelöljük. MUNKATARS legjobb:=1 for i=2 to n if i jobb jelölt mint legjobb then elbocsát legjobb felvesz i legjobb:=i Az algoritmus költsége az elbocsátások száma. A legjobb esetben, ha az els˝o jelölt a legjobb egyetlen elbocsátás sem szükséges a legrosszabb esetben pedig (ha a jelöltek jóság szerint növekv˝oen rendezettek) n-1. Átlagos eset Feltesszük, hogy az input egyenletes eloszlás alapján generált az n ember minden lehetséges n! permutációja ugyanakkora valószín˝uséggel lehet a feladat inputja. Legyen Xi az a valószín˝uségi változó, amely 1 ha az i-edik jelöltet felvesszük és 0, ha nem. Ekkor az elbocsátások számát az X = ∑ni=1 Xi − 1 változó adja meg.
1
Másrészt Pr(Xi = 1) = 1/i, mivel az els˝o i jelölt is egyenletes eloszlás alapján érkezik, így ez annak a valószín˝usége, hogy az i-edik a legjobb. Tehát E(Xi ) = 1/i. Következésképpen n
n
E(X) = ∑ E(Xi ) − 1 = ∑ 1/i − 1 = Hn − 1 ≈ ln n − 1. i=1
i=1
Véletlenített algoritmus a munkatárs felvételére Az átlagos eset elemzéssel az a baj, hogy általában nincs igazán okunk az input egyenletes eloszlását feltételezni. Véletlenített algoritmussal gyakran ez a probléma kiküszöbölhet˝o. Tegyük fel, hogy megkapjuk el˝ore a jelöltek listáját (csak a listát semmi egyéb információt) és mi mondhatjuk meg milyen sorrendben jöjjenek. Ekkor a következ˝o véletlenített algoritmus használható. RMUNKATARS legyen a(1),a(2),...,a(n) a jelöltek egy egyenletes eloszlás alapján kapott permutációja legjobb:=a(1) for i=2 to n if a(i) jobb jelölt mint legjobb then elbocsát legjobb felvesz a(i) legjobb:=a(i) Ekkor ugyanúgy, mint a fenti átlagos eset analízisben látható, hogy RMUNKATARS várható költsége Hn − 1. Fontos megjegyeznünk, hogy itt már nem tételeztünk fel semmit az inputról a várható érték a véletlenített algoritmus döntéseire vonatkozik. Gyorsrendezés véletlenül generált felosztó elemmel RandomGyorsrendez 1. Ha csak egy elem van return. 2. Egyébként választunk egyenletes eloszlás alapján egy felosztó elemet. 3. A felosztó elem elé helyezzük a nála kisebb, mögé a nála nagyobb elemeket. 4. RandomGyorsrendez a felosztó elemnél kisebb elemekre 5. RandomGyorsrendez a felosztó elemnél nagyobb elemekre Lemma: A futási id˝o várható értéke legrosszabb esetben is O(n log n) Bizonyítás: • Legyen X a eljárás végrehajtása során a felosztásokban végrehajtott összehasonlítások száma n elem˝u bemenetre. Ekkor a teljes futási id˝o O(n + X). • Legyen zi az i-edik legkisebb eleme a bemenetnek, és Zi j = {zi , zi+1 , . . . , z j }. • Legyen pi j annak a valószín˝usége, hogy zi -t és z j -t valamelyik feloszt eljárás összehasonlítja.
2
• Ekkor pi j = 2/( j − i + 1), mivel akkor lesznek összehasonlítva, ha a Zi j halmazból vagy zi vagy z j az els˝o felosztó elem, és a felosztó elem véletlenszer˝u választása alapján minden elem ugyanakkora valószín˝uséggel lesz a halmazból az els˝o felosztó elem. n • Az összehasonlítások várható száma ∑n−1 i=1 ∑ j=i+1 2/( j − i + 1) = O(n log n)
Minimális vágás algoritmusa A minimális vágás feladat, ahol egy multigráfot kell egy vágással 2 részre osztani úgy, hogy a vágás mérete minimális legyen. (Multigráf: olyan gráf, ahol bármely 2 pont között lehet több él is, azaz az éleknek multiplicitása van). A vágás mérete:= a két csúcshalmaz között átmen˝o élek száma. Egy egyszer˝u véletlenített algoritmussal létre tudjuk hozni a kívánt vágást. Az algoritmus amíg a csúcsok száma legalább 2 véletlenszer˝uen (egyenletes eloszlás alapján) kiválaszt egy élet és ennek két végpontját összevonja egy pontba. Amikor már csak 2 pont van, a két pontban összevont ponthalmazok adják a két halmazt. Legyen OPT egy optimális megoldás (több is lehet) és legyen k ennek a mérete. Lemma Annak a valószín˝usége, hogy az algoritmus az OPT megoldást adja vissza legalább 1/n2 . Bizonyítás Nézzük az els˝o összevonást. Az OPT k mérete miatt bármely pont fokszáma legalább k, mert ha nem így lenne, akkor létezne k-nál kisebb méret˝u vágás. Összesen tehát legalább n · k/2 él van, ebb˝ol az OPT-ban k darab szerepel. Tehát annak valószín˝usége, hogy a véletlenített algoritmusunk az els˝o lépésben végez olyan összevonást, ami OPT-beli élet érint legfeljebb k/(n ∗ ·k/2) = 2/n. Legyen Ei az az esemény, hogy az i. lépésben nem vonunk össze OPT-beli élet. Ekkor: Pr(E1 ) ≥ 1−2/n. Továbbá Pr(E2 |E1 ) ≥ 1 − 2/(n − 1), mivel, ha E1 fennáll, akkor az összevont gráfra is teljesül, hogy a minimális vágás k. És így tovább Pr(Ei |E1 ∩ · · · ∩ Ei−1 ) ≥ 1 − 2/(n + 1 − i), minden i-re. Az összes Ei bekövetkezésének (azaz annak, hogy egyáltalán nem választunk OPT beli élt) a valószín˝usége a fenti feltételes valószín˝uségek szorzata, azaz legalább n
1
2
∏(1 − i ) = (n − 1)n ≥ 1/n2. i=3
A lemma alapján azt kapjuk, hogy Pr(Alg nem optimális megoldást ad vissza)≤ 1 − 1/n2 . Viszont egymástól független véletlen döntésekkel újra végrehajtva az algoritmust, az alsó korlátok szorzódnak, így n2 végrehajtás után a hibás erdemény valószín˝usége kisebb lesz, mint 1/e. 3-MAX-SAT probléma 3-MAX-SAT probléma inputja egy konjuktív normálforma, amely m klóz konjukciója és minden klóz pontosan három különböz˝o literált (változó vagy negáltja) diszjunkciója, és egyik klóz sem tartalmazza ugyanazt a változót és negáltját. A 3-SAT problémában meg kell határozni, hogy kielégíthet˝o -e a formula, azaz van -e olyan értékadás, amely mellett minden klóz igaz. A 3-MAX-SAT probléma azt méri milyen közel van a formula a kielégíthet˝oséghez, azaz mi a maximális száma a kielégíthet˝o klózoknak. A következ˝o tétel mutatja, hogy egy nagyon egyszer˝u véletlenített algoritmus egy jó approximációt ad. Tétel Ha minden változónak egymástól függetlenül 1/2 valószín˝uséggel adunk 0 és 1 értéket, akkor a kielégített klózok várható száma legalább 7/8m. Bizonyítás: Definiáljuk az Yi indikátor változót, amely akkor 1 ha az i-edik klóz ki van elégítve, egyébként 0. Ekkor annak a valószín˝usége, hogy a klóz nincs kielégitve 1/8, hisz annak felel meg, hogy egyik literál sem igaz. Következésképpen E(Yi ) = 7/8. Másrészt, ha Y a kielégített klózok száma, akkor Y = ∑ni=1 Yi , így E(Y ) = ∑ni=1 E(Yi ) = 7/8m. 3
Polinomok egyenl˝oségének ellen˝orzése Legyen P(x) és Q(x) két n-edfokú polinom a feladat ellen˝orízni, hogy azonosak -e. Ha a polinomok az együtthatók által vannak megadva, akkor nyilvánvaló megoldás az együtthatók egyenl˝oségének ellen˝orzése. De el˝ofordulhatnak olyan alkalmazások, ahol a polinomok nem az együtthatókkal vannak megadva, hanem egy jóval bonyolultabb formában, esetleg csak csak egy eljárást használhatunk, amely adott helyen megadja a polinom értékét. A feladat tulajdonképpen az, hogy a P(x) − Q(x) = 0 polinom egyenl˝oséget kell ellen˝orízni. Mivel egy n-edfokú polinomnak legfeljebb n gyöke van, ezért egy megoldás, hogy veszünk n+1 darab értéket x1 , x2 , . . . , xn+1 és minden i-re teszteljük a P(xi ) − Q(xi ) = 0 egyenl˝oséget. Ha minden esetben egyenl˝oség áll fenn, akkor tudjuk, hogy a polinomok megegyeznek egyébként pedig különböz˝oek. Egy gyorsabb Monte Carlo algoritmus a következ˝o: Vegyünk S elemet, amelyeken a polinomok értelmezve vannak, válasszunk véletlenszer˝uen egyenletes eloszlás alapján egy x elemet. Ha P(x) 6= Q(x), akkor a polinomok különböz˝oek, egyébként azt mondjuk megegyeznek. Lemma Annak a valószín˝usége, hogy az algoritmus különböz˝o polinomokat megegyez˝onek mond legfeljebb n/|S|. Megjegyzés: A hiba valószín˝usége csökkenthet˝o a S halmaz méretének növelésével, és független tesztek ismételt végrehajtásával. Mátrixok egyenl˝oségének ellen˝orzése A cél két F test feletti n × n méret˝u mátrix A és B egyenl˝oségének ellen˝orzése. Az algoritmust akkor érdemes használni, ha a mátrixok nem adottak explicit formában csak fekete dobozként számolhatunk velük, vagy mátrixszorzások ellen˝orzésére. A két mátrix, akkor és csak akkor egyenl˝o, ha C = A − B azonosan 0. Tétel Legyen C egy nem azonosan 0 mátrix F felett, továbbá r egyenletes eloszlás alapján generált a {0, 1}n halmazból. Ekkor PR(C · r = 0) ≤ 1/2. Halasztott döntések technikája Adott 1 pakli francia kártya, 52 lap: ebb˝ol 13db 4 kártyát tartalmazó kupacot hozunk létre. A következ˝o játékot játsszuk. • a 13-dik pakliból levesszük a legfels˝o kártyát, • amilyen szám van az aktuálisan felvett kártyán azzal a paklival folytatjuk, • a játéknak vége, ha üres kupachoz érkezünk, • nyertünk: ha minden kártyát felvettünk. Az a kérdés mi a nyerés valószín˝usége, ha egyenletes keverés alapján lettek lerakva a kártyák. A halasztott döntés elve az, hogy amikor a következ˝o kártyát felvesszük, akkor az a kártya a még játékban lév˝o kártyákból egyenletes eloszlás alapján kerül ki. (Úgy vesszük a játékot, mintha a keverést elhalasztanánk eddig az id˝opontig.) Következésképpen a játékban egy egyenletes eloszlás alapján kapott véletlen permutáció sorrendjében vesszük a kártyákat. Vegyük észre, hogy pontosan akkor nyerünk, ha király a permutációban az utolsó lap (pontosan a negyedik királynál áll meg a játék). Ennek a valószín˝usége, így a játék megnyerésének a valószín˝usége is 1/13. A tétel bizonyítása Feltehetjük, hogy C-nek az els˝o sora nem 0, és a nem 0 értékek a sorban megel˝ozik a 0 értékeket. Annak a valószín˝uségét szeretnénk meghatározni, hogy Cr=0. Legyen c a C els˝o sorvektora, melynek els˝o k értéke nem 0, k>0. Vizsgáljuk annak a valószín˝uségét, hogy c és r bels˝o szorzata nem 0, ez alsó korlátot ad arra, valószín˝uségre nézve, hogy Cr=0. A bels˝o szorzat cT r = 0, akkor ha
4
∑ki=2 ci · ri . −r1 = c1 Viszont a halasztott döntések technikája alapján r1 -et választhatjuk a többi érték rögzítése után, így a fenti egyenl˝oség valószín˝usége legfeljebb 1/2. A tétel alapján a véletlenül generált r vektorra ellen˝orízve az Ar = Br egyenl˝oséget, egy 1/2 hibakorlátos Monte Carlo algoritmust kapunk. Szorgalmi Igazoljuk, hogy egy tetsz˝oleges m klózt tartalmazó CNF-ben, ha minden változónak egymástól függetlenül 1/2 valószín˝uséggel adunk 0 és 1 értéket, akkor a kielégített klózok várható száma legalább m/2. Beküldés:
[email protected], Bizonyítás • els˝o négy megoldó 6-6 pont • a második négy megoldó 3-3 pont A szerzett plusszpontok a vizsga minimumkövetelményébe nem számítanak bele.
5
