KMI/ALM3
´ matematika 3 Algoritmicka Mgr. Petr Osiˇcka, Ph.D.
ZS 2014
Pˇ redn´ aˇ ska 1 ´ proble ´m Algoritmicky Definice 1. Abeceda Σ je koneˇcn´ a nepr´ azdn´ a mnoˇzina. Prvk˚ um Σ ˇr´ık´ame symboly. Slovo (ˇretˇezec) nad abecedou Σ je uspoˇr´ adan´ a sekvence znak˚ u z Σ. D´elka slova x ∈ Σ je d´elka t´eto sekvence. Mnoˇzinu vˇsech slov nad abecedou Σ oznaˇcujeme jako Σ∗ . Jazyk L nad Σ je libovoln´a podmnoˇzina Σ∗ . Pˇ r´ıklad 1. Mˇejme ΣBool = {0, 1}. Sekvence 0001, 1110, 00 jsou slovy nad touto abecedou, sekvence 12, #43k nejsou. Σ∗ je pak mnoˇzina {0, 1, 00, 01, 10, 11, 000, . . . }. Definice 2. Necht’ Σ je abeceda. Pak algoritmick´y probl´em definujeme jako dvojici hL, Ri, kde L ⊆ Σ∗ je mnoˇzina vstup˚ u (instanc´ı) a R je relace zachycuj´ıc´ı vztah mezi instancemi a spr´avn´ ymi v´ ysledky. Tedy pokud hx, yi ∈ R, pak y je spr´ avn´ ym ˇreˇsen´ım x. Form´ alnˇe je L ⊆ Σ∗ mnoˇzina zak´odov´an´ı instanc´ı pomoc´ı ˇretˇezc˚ u nad abecedou Σ, a R ⊆ Σ∗ × Σ∗ , v´ ysledky tak´e k´ odujeme pomoc´ı Σ. Pro uk´ azku si probl´em testov´ an´ı prvoˇc´ıselnosti uvedeme ve verz´ıch bez k´odov´an´ı pomoc´ı ˇretˇezc˚ u i s jeho k´ odov´ an´ım. (a) Bez pouˇzit´ı ˇretˇezc˚ u m˚ uˇzeme probl´em zav´est n´asledovnˇe. Mnoˇzina instanc´ı je d´ana {n | n ∈ N, n > 1}, spr´ avn´e ˇreˇsen´ı je ANO, pokud je n prvoˇc´ıslo, jinak NE. (b) Zavedeme-li k´ odov´ an´ı nad ΣBool takov´e, ˇze zak´odov´an´ım n je jeho z´apis ve dvojkov´e soustavˇe, k´odov´ an´ım ANO je slovo 1 a k´ odov´ an´ım NE je slovo 0, pak je probl´em pops´an pomoc´ı dvojice hL, Ri takov´e, ˇze: L = {x ∈ {0, 1}∗ | x je z´ apis ˇc´ısla n ve dvojkov´e soustavˇe, n ∈ N, n > 1} a hx, yi ∈ R pr´avˇe kdyˇz x je zak´ odov´ an´ım prvoˇc´ısla. Proˇc k´ odovat vstupy a v´ystupy? Velikost instance m˚ uˇzeme zav´est jako d´elku zak´odovan´ı dan´e instance. M˚ uˇzeme tak zachytit sloˇzitost algoritmu, kter´ a by jinak z´ ustala skryt´ a. Naivn´ı algoritmus pro test prvoˇc´ıselnosti (ten, kter´ y zkouˇs´ı dˇelitelnosti vˇsemi menˇs´ımi ˇc´ısly) m´a pro pˇr´ıpad (a) z pˇredchoz´ıho pˇr´ıkladu sloˇzitost O(n), protoˇze vstup n m´a velikost n. V pˇr´ıpadˇe zak´odov´an´ı pomoc´ı dvojkov´e soustavy m´ a algoritmus sloˇzitost exponenci´ aln´ı, protoˇze d´elka z´ak´odov´an´ı n je lg n. Pokud se v instanci probl´emu vyskytuje mnoˇzina ˇc´ısel, bereme ˇcasto jako velikost instance jejich poˇcet. Zanedb´ av´ ame tak ovˇsem velikost tˇechto ˇc´ısel. Nˇekter´e operace, o kter´ ych pˇri anal´ yze algoritmu pˇredpokl´ad´ame, ˇze maj´ı konstantn´ı sloˇzitost, maj´ı ve skuteˇcnosti pro velk´a ˇc´ısla sloˇzitost horˇs´ı (napˇr´ıklad sˇc´ıt´an´ı, porovn´av´an´ı na souˇcastn´em harwaru). Pokud zavedeme velikost instance jako d´elku zak´odov´an´ı, tomuto probl´emu se vyhneneme. ˇ ım vˇetˇs´ı ˇc´ıslo, ˇc´ım vˇetˇs´ı je d´elka jeho z´ C´ ak´ odov´an´ı a tedy i d´elka zak´odov´an´ı instance.
´m˚ Typy proble u Definice 3. Probl´em hL, Ri je rozhodovac´ım probl´emem, pokud je mnoˇzina vˇsech moˇzn´ ych v´ ysledk˚ u dvouprvkov´ a, tj |{y | (x, y) ∈ R pro x ∈ L}| = 2. Jeden z prvk˚ u t´eto mnoˇziny pak oznaˇcujeme jako rozhodnut´ı ANO, druh´ y z prvk˚ u jako rozhodnut´ı NE. Rozhodovac´ı probl´em je probl´emem zjiˇstˇen´ı, jestli dan´a instance m´a poˇzadovanou vlastnost. Pokud ji m´ a, oˇcek´ av´ ame odpovˇed’ ANO, pokud ji nem´ a, oˇcek´av´ame odpovˇed’ NE. Protoˇze R je v tomto pˇr´ıpadˇe jednoduch´e, m˚ uˇzeme probl´em reprezentovat pomoc´ı jazyka. Slova, kter´a k´oduj´ı instance, pro kter´e je odpovˇed’ ANO, do jazyka patˇr´ı, slova, kter´ a k´ oduj´ı instance, pro kter´e je odpovˇed’ NE, do jazyka nepatˇr´ı.
Pˇ r´ıklad 2. (a) Probl´em testov´ an´ı prvoˇc´ıselnosti je rozhodovac´ı probl´em. (b) Typick´ ym rozhodovac´ım probl´emem je probl´em splnitelnosti formul´ı v´ yrokov´e logiky v konjunktivn´ı norm´ aln´ı formˇe (CNF). Formule je v CNF, pokud je konjunkc´ı klausul´ı. Klausule je disjunkc´ı liter´ al˚ u, z nichˇz kaˇzd´ y je bud’ v´ yrokovou promˇennou nebo jej´ı negac´ı. Formule (x ∨ y) ∧ (y ∨ z) je v CNF, kdeˇzto formule (x ∧ y) ∨ (x → ˇ y) nen´ı v CNF. Kaˇzdou formuli v´ yrokov´e logiky lze pˇrev´est do CNF. Rekneme, ˇze formule ϕ je splniteln´ a, pokud existuje ohodnocen´ı v´ yrokov´ ych promˇenn´ ych takov´e, ˇze ϕ je pravdiv´a. Napˇr´ıklad formule (x ∨ y) je splniteln´ a, protoˇze pro ohodnocen´ı x = 1, y = 1 je pravdiv´a. Oproti tomu formule (x ∧ ¬x) splniteln´a nen´ı, protoˇze nen´ı pravdiv´ a pro ˇz´ adn´e ohodnocen´ı promˇenn´ ych. Probl´em splnitelnosti formul´ı v´ yrokov´e logiky, kter´ y oznaˇcujeme jako SAT, je probl´emem urˇcen´ı toho, zda je formule splniteln´a. Probl´em je tedy urˇcen jazykem {zak´ odov´ an´ı ϕ | ϕ je splniteln´ a formule v CNF}. Definice 4. Necht’ Σ je abeceda. Optimalizaˇcn´ı probl´em je ˇctveˇrice hL, sol, cost, goali, kde L ∈ Σ∗ je mnoˇzina instanc´ı dan´eho probl´emu, sol : L → P(Σ∗ ) je zobrazen´ı pˇriˇrazuj´ıc´ı instanci probl´emu mnoˇzinu jej´ıch pˇr´ıpustn´ ych ˇreˇsen´ı; cost : L × P(Σ∗ ) → Q je zobrazen´ı pˇriˇrazuj´ıc´ı kaˇzd´e instanci a pˇr´ıpustn´emu ˇreˇsen´ı t´eto instance jeho cenu; goal je bud’ minimum (pak mluv´ıme o minimalizaˇcn´ım probl´emu) nebo maximum (pak mluv´ıme o ˇ maximalizaˇcn´ım probl´emu). Rekneme, ˇze y ∈ sol(x) je optim´ aln´ım ˇreˇsen´ım instance x, pokud cost(x, y) = goal{cost(y, x) | x ∈ sol(x)}. Optimalizaˇcn´ı probl´em je probl´emem v´ ybˇeru ˇreˇsen´ı s nejlepˇs´ı cenou z mnoˇziny vhodn´ ych ˇreˇsen´ı dan´e instance. Vhodn´ a ˇreˇsen´ı obdrˇz´ıme pomoc´ı zobrazen´ı sol, cenu kaˇzd´eho z nich urˇcuje cost. Nakonec goal n´am ˇr´ık´a, jestli chceme naj´ıt to s nejvˇetˇs´ı nebo s nejmenˇs´ı cenou. ´ Pˇ r´ıklad 3. (a) Uloha batohu: je d´ ana mnoˇzina poloˇzek s r˚ uzn´ ymi v´ahami a kapacita batohu. Chceme nal´ezt takovou podmnoˇzinu poloˇzek, kter´ a se do batohu vejde (souˇcet vah tˇechto poloˇzek je nejv´ yˇse kapacita batohu). Souˇcasnˇe chceme batoh zaplnit co nejv´ yce, tedy hled´ame takovou mnoˇzinu poloˇzek, kter´a vede k nejvˇetˇs´ımu moˇzn´emu (menˇs´ımu neˇz kapacita) souˇctu. ´ Uloha batohu Instance:
{(b, w1 , . . . , wn ) | b, w1 , . . . , wn ∈ N}
Pˇr´ıpustn´ a ˇreˇsen´ı: Cena ˇreˇsen´ı:
sol(b, w1 , . . . , wn ) = {C ⊆ {1, . . . , n} | P cost(C, (b, w1 , . . . , wn )) = i∈C wi
C´ıl:
maximum
P i∈C
wi 6 b}
ˇ ısla wi odpov´ıdaj´ı objem˚ C´ um jednotliv´ ych pytl˚ u s p´ıskem, b je kapacita batohu. Pro instanci I = (b, w1 , . . . , w5 ), kde b = 29, w1 = 3, w2 = 6, w3 = 8, w4 = 7, w5 = 12, existuje jedin´e optim´aln´ı ˇreˇsen´ı C = {1, 2, 3, 5} s cenou cost(C, I) = 29. Lze snadno ovˇeˇrit, ˇze vˇsechna ostatn´ı pˇr´ıpustn´a ˇreˇsen´ı maj´ı menˇs´ı cenu. (b) Probl´em tˇr´ıdˇen´ı lze tak´e formulovat jako optimalizaˇcn´ı probl´em. Pro sekvenci prvk˚ u a = a1 , . . . , an a jejich uspoˇr´ ad´ an´ı 6 je poˇcet inverz´ı definov´ an jako Inv(a) = |{(ai , aj ) | i < j, ai aj }|, tedy jako poˇcet dvojic prvk˚ u, kter´e jsou nejsou uspoˇr´ ad´ any ve spr´ avn´em poˇrad´ı. Pak je probl´em tˇr´ıdˇen´ı definov´an n´asledovnˇe: Probl´ em tˇ r´ıdˇ en´ı Instance:
a = a1 , . . . , an , uspoˇr´ad´an´ı 6
Pˇr´ıpustn´ a ˇreˇsen´ı:
sol(a) = mnoˇzina vˇsech permutac´ı prvk˚ u a1 , . . . , an
Cena ˇreˇsen´ı:
pro x ∈ sol(a) je cost(a, x) = Inv(x)
C´ıl:
minimum
Algoritmus dan´emu vstupu (instanci nˇejak´eho probl´emu) pˇriˇrazuje v´ ystup. Z vnˇejˇsku jej lze tedy ch´apat jako ˇ zobrazen´ı. Form´ alnˇe zap´ıˇseme fakt, ˇze algoritmus A pro vstup x vr´at´ı y jako A(x) = y. Rekneme, ˇze A ˇreˇs´ı probl´em hL, Ri pokud (x, A(x)) ∈ R pro kaˇzd´e x ∈ L, tedy pokud pro kaˇzdou instanci probl´emu vrac´ı A spr´ avn´e ˇreˇsen´ı. 2
U optimalizaˇcn´ıch probl´em˚ u, pro kter´e nezn´ ame efektivn´ı algoritmus pro nalezen´ı optim´aln´ıho ˇreˇsen´ı, se ˇcasto spokoj´ıme s algoritmem, kter´ y vrac´ı ˇreˇsen´ı pˇr´ıpustn´e–ne nutnˇe optim´aln´ı, ale souˇcasnˇe pracuje efektivnˇe. Takov´ y algoritmus naz´ yv´ ame aproximaˇcn´ım algoritmem.
ˇ ´ sloˇ Casov a zitost ˇ Casov´ a sloˇzitost (d´ ale jen sloˇzitost) algoritmu A je funkce T imeA : N → N pˇriˇrazuj´ıc´ı velikosti vstupn´ı instance poˇcet instrukc´ı, kter´e mus´ı algoritmus A bˇehem v´ ypoˇctu prov´est. Protoˇze obecnˇe nemus´ı algoritmus pro dvˇe r˚ uzn´e stejnˇe velk´e instance prov´est stejn´e mnoˇzstv´ı instrukc´ı, potˇrebujeme poˇcty instrukc´ı pro instance stejn´e velikosti nˇejak´ ym zp˚ usobem agregovat. ˇ Definice 5. Oznaˇcme si tA (x) poˇcet instrukc´ı, kter´e algoritmus A provede pro instanci x ∈ L. Casov´ a sloˇzitost v nejhorˇs´ım pˇr´ıpadˇe je definovan´ a T imeA (n) = max{tA (x) | x ∈ L, |x| = n}. Sloˇzitost v pr˚ umˇern´em pˇr´ıpadˇe je pak P T imeA (n) =
x∈L,|x|=n tA (x)
|{x | |x| = n}|
.
Jedn´ım z vyuˇzit´ı sloˇzitosti (mimo zˇrejm´e vyuˇzit´ı k porovn´an´ı algoritm˚ u) je rozdˇelen´ı probl´em˚ u na prakticky ˇreˇsiteln´e a na praktick´ y neˇreˇsiteln´e. Jak ovˇsem pˇriˇradit sloˇzitost k probl´emu? Definice 6. Necht’ U je algoritmick´ y probl´em. • O(g(n)) je horn´ım omezen´ım sloˇzitosti probl´emu U, pokud existuje algoritmus A ˇreˇs´ıc´ı U takov´ y, ˇze T imeA (n) ∈ O(g(n)). • ω(f(n)) je doln´ım omezen´ım sloˇzitosti probl´emu U, pokud pro kaˇzd´ y algoritmus B ˇreˇs´ıc´ı U plat´ı, ˇze T imeB (n) ∈ ω(f(n)) Za horn´ı omezen´ı sloˇzitosti probl´emu bereme sloˇzitost nejlepˇs´ıho zn´am´eho algoritmu. Nal´ezt doln´ı omezen´ı sloˇzitosti je oproti tomu mnohem komplikovanˇejˇs´ı. Mus´ıme totiˇz vylouˇcit existenci algoritmu se sloˇzitost´ı danou doln´ı hranic´ı nebo lepˇs´ı. To je netrivi´ aln´ı a pro naprostou vˇetˇsinu probl´em˚ u je takov´a hranice nezn´am´a (vylouˇc´ıme-li napˇr´ıklad hranici danou t´ım, ˇze algoritmus mus´ı pˇreˇc´ıst cel´ y vstup). Pˇr´ıkladem probl´emu, pro kter´ y je tato hranice zn´ am´ a je napˇr´ıklad tˇr´ıdˇen´ı porovn´av´an´ım, pro kter´e neexistuje algoritmus se sloˇzitost´ı lepˇs´ı neˇz O(n log n). Probl´emy rozdˇelujeme na prakticky ˇreˇsiteln´e a prakticky neˇreˇsiteln´e pomoc´ı jejich horn´ıho omezen´ı sloˇzitosti. Rozdˇelen´ı je n´ asleduj´ıc´ı – probl´em povaˇzujeme za praktick´ y ˇreˇsiteln´ y, pokud pro je jeho horn´ı omezen´ı sloˇzitost O(p(n)), kde p(n) je polynom. Tedy, probl´em je praktick´ y ˇreˇsiteln´ y, pokud pro nˇej existuje algoritmus s nejh˚ uˇre polynomickou sloˇzitost´ı. – ostatn´ı probl´emy povaˇzujeme za prakticky neˇreˇsiteln´e. Proˇc polynomick´ a sloˇzitost? Polynom je nejvˇetˇs´ı funkce, kter´ a neroste rychle.“ U tohoto d˚ uvodu pˇredpokl´ad´ame, ˇze stupeˇ n polynomu ” nebude extr´emnˇe velk´ y (napˇr. 100). U vˇetˇsiny zn´am´ ych algoritm˚ u s polynomickou sloˇzitost´ı, nen´ı stupeˇ n polynomu vyˇsˇs´ı neˇz 10. Druh´ ym d˚ uvodem je to, ˇze polynomy jsou uzavˇren´e vzhledem k n´asoben´ı (vyn´asoben´ım dvou polynom˚ u dostaneme zase polynom). Pokud uvnitˇr algoritmu A spouˇst´ıme nejv´ıˇse polynomick´ y poˇcet kr´ at algoritmus B s nejh˚ uˇre polynomickou sloˇzitost´ı, m´a tento algoritmus tak´e nejh˚ uˇre polynomickou sloˇzitost (pˇritom samozˇrejmˇe pˇredpokl´ ad´ ame, ˇze pokud bychom povaˇzovali sloˇzitost algoritmu B pˇri anal´ yze A za konstantu, bude sloˇzitost A m´ıt nejh˚ uˇre polynomickou sloˇzitost). V podstatˇe tedy m˚ uˇzeme efektivn´ı algoritmy skl´adat do sebe (analogicky vol´ an´ı funkc´ı pˇri programov´ an´ı) a z´ıskan´ y algoritmus bude tak´e efektivn´ı. 3
´ notace Asymptoticka Definice 7. O(f(n)) je mnoˇzina vˇsech funkc´ı g(n) takov´ ych, ˇze existuj´ı kladn´e konstanty c a n0 takov´e, ˇze 0 6 g(n) 6 cf(n) pro vˇsechna n > n0 . Ω(f(n)) je mnoˇzina vˇsech funkc´ı g(n) takov´ ych, ˇze existuj´ı kladn´e konstanty c a n0 takov´e, ˇze g(n) > cf(n) > 0 pro vˇsechna n > n0 . Θ(f(n)) je mnoˇzina vˇsech funkc´ı g(n) takov´ ych, ˇze existuj´ı kladn´ı konstanty c1 , c2 a n0 takov´e, ˇze 0 6 c1 f(n) 6 g(n) 6 c2 f(n) vˇsechna n > n0 . Z´ apis g(n) = O(f(n)) je pˇr´ıkladem tzv. jednostrann´e rovnosti (v n´asleduj´ıc´ıch u ´vah´ach lze zamˇenit Ω a Θ za O). Rovn´ıtko v n´ı interpretujeme jinak, neˇz je obvykl´e (coˇz je zˇrejm´e, na obou stran´ach rovnosti nejsou objekty stejn´eho typu). Korektnˇe by mˇel b´ yt vztah zaps´an jako g(n) ∈ O(f(n)), nicm´enˇe pouˇzit´ı rovn´ıtka se jiˇz zaˇzilo a stalo se de facto standardem. Pro pochopen´ı v´ yznamu rovnost´ı, ve kter´ ych se asymptotick´a notace nach´az´ı na lev´e i na prav´e stranˇe, si staˇc´ı uvˇedomit, ˇze v´ yraz, ve kter´em se tato notace nach´az´ı pˇredstavuje mnoˇzinu funkc´ı. Tedy napˇr´ıklad v´ yraz n3 + O(n) je mnoˇzina {n3 + f(n) | f(n) ∈ O(n)}. Protoˇze na obou stran´ ach = jsou mnoˇziny a jedn´a se o jednosmˇernou rovnost, interpretujeme = jako ⊆. Pro aritmetiku s mnoˇzinami funkc´ı plat´ı intuitivn´ı pravidla. Uv´aˇz´ıme-li mnoˇziny funkc´ı S a T , pak plat´ı S + T = {g + h | g ∈ S, h ∈ T }, S − T = {g − h | g ∈ S, h ∈ T }, S · T = {g · h | g ∈ S, h ∈ T }, S ÷ T = {g ÷ h | g ∈ S, h ∈ T }. Skl´ ad´ an´ı funkce s mnoˇzinou funkc´ı provedeme obdobnˇe, f(O(g(n))) = {f(h(n)) | h ∈ O(g(n))}. Napˇr´ıklad log O(n2 ) je mnoˇzina logaritm˚ u z funkc´ı omezen´ ych shora kvadrikou. Pokud jsou asymptotick´e v´ yrazy vnoˇreny, pak mnoˇziny sjednot´ıme, tedy napˇr´ıklad [ O(g(n) + O(f(n))) = {O(h) | h ∈ g(n) + O(f(n))}.
4
Rozdˇ el a panuj Z´ akladn´ı kostra algoritmu RaP pro vstup I je n´asleduj´ıc´ı: 1. Pokud je |I| < b pro pevnˇe danou konstantu b, je v´ ysledek trivi´aln´ı nebo jej poˇc´ıt´ame jin´ ym algoritmem. Algoritmus A tento v´ ysledek jenom vr´ at´ı. 2. Z instance I vygenerujeme instance I1 , I2 , . . . , Ik , takov´e, ˇze I > |Ii | pro vˇsechna 1 6 i 6 k. 3. Rekurzivnˇe zavol´ ame algoritmus A pro I1 , I2 , . . . , Ik . 4. V´ ysledky rekurzivn´ıch zavol´ an´ı zkombinujeme do v´ ysledku aktu´aln´ıho zavol´an´ı a tento v´ ysledek vr´at´ıme. V algoritmech realizuj´ıc´ıch techniku Rozdˇel a panuj m˚ uˇzeme rozpoznat dvˇe oddˇelen´e f´aze, kter´e ji dali n´ azev. Bˇehem prvn´ı f´ aze, kter´e ˇr´ık´ ame Rozdˇel, algoritmus vygeneruje mnoˇzinu menˇs´ıch instanc´ı. Bˇehem druh´e f´ aze, pojmenovan´e jako Panuj, sestav´ıme ze ˇreˇsen´ı vypoˇcten´ ych pro menˇs´ı instance ˇreˇsen´ı instance p˚ uvodn´ı. Pˇr´ıkladem algoritmu pouˇz´ıvaj´ıc´ı strategii rozdˇel a panuj je MergeSort (kter´ y jiˇz vˇsichni zn´ate). Algoritmus 1 Mergesort 1: procedure MergeSort(A, l, p) 2: if p < l then 3: q ← b(l + p)/2c 4: MergeSort(A, l, q) 5: MergeSort(A, q + 1, p) 6: end if 7: Merge(A, l, q, p) 8: end procedure
. rozdˇel
. panuj
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21:
procedure Merge(A, l, q, p) n1 ← q − l + 1 n2 ← r − q for i ← 0 to n1 − 1 do L[i] ← A[l + 1] end for for i ← 0 to n1 − 1 do R[i] ← A[q + i + 1] end for L[n1 ] ← R[n2 ] ← ∞ i←j←0 for k ← l to p do if L[i] 6 R[j] then A[k] ← L[i] i←i+1 else A[k] ← R[j] j←j+1 end if end for end procedure
´ za c ˇasove ´ sloˇ Analy zitosti D´ıky rekurzivn´ım zavol´ an´ım se sloˇzitost ned´ a vyj´adˇrit pˇr´ımo, ale mus´ıme ji vyj´adˇrit pomoc´ı rekurence. Oznaˇc´ımeli tuto sloˇzitost T(n), pak T (b) = Θ(1), T (|I|) =
k X
T (|Ik |) + f(|I|).
i=1
Pro instanci o velikosti menˇs´ı nebo rovno b je sloˇzitost´ı algoritmu konstanta (prvn´ı ˇr´adek kostry algoritmu). Pro zbyl´e instance algoritmus spoˇc´ıt´ a instance menˇs´ı (ˇr´adek 2) a kombinuje v´ ysledky rekurzivn´ıch zavol´an´ı (ˇr´ adek 4), sloˇzitost tˇechto ˇr´ adk˚ u je vyj´ adˇrena funkc´ı f(n). Abychom spoˇcetli sloˇzitost cel´eho algoritmu, mus´ıme jeˇstˇe P pˇriˇc´ıst sumu sloˇzitost´ı rekurzivn´ıch zavol´ an´ı, tedy sumu ki=1 T (|Ik |).
5
Sloˇzitost chceme vyj´ adˇrit v uzavˇren´e formˇe, to je ve formˇe, kter´a neobsahuje rekurentn´ı vol´an´ı sebe sama“ ” na prav´e stranˇe rovnosti (hled´ an´ı uzavˇren´e formy se ˇr´ık´a ˇreˇsen´ı rekurence). Rekurence m˚ uˇzeme vyˇreˇsit pˇresnˇe, nebo–pokud je pˇresn´e ˇreˇsen´ı obt´ıˇzn´e– se spokoj´ıme s odhadem uzavˇren´e formy. V takov´em pˇr´ıpadˇe se spokoj´ıme s v´ ysledkem v asymptotick´e notaci. ´ rekurence 1: Hanojske ´ ve ˇˇ Snadna ze T (n) = 2T (n − 1) + 1 T (1) = 1
Hodnoty pro prvn´ıch p´ ar ˇc´ısel n
T(n)
1 2 3 4
1 3 7 15
Tipneme, ˇze T (n) = 2n − 1, pokus´ıme se v´ ysledek dok´azat indukc´ı. Pro n = 1 rovnost trivi´alnˇe plat´ı. Pˇredpokl´ adejme, ˇze plat´ı pro n − 1. Pak T (n) = 2T (n − 1) − 1 = 2(2n−1 − 1) = 2n − 1. ´ rekurence 2: Kra ´ jen´ı Pizzy Snadna T (0) = 1 T (n) = T (n − 1) + n Rekurenci rozvineme: T (n) = T (n − 1) + n = = T (n − 2) + (n − 1) + n = .. . = 1 + 1 + 2 + ··· + n = =1+
n(n + 1) 2
V´ ysledek jeˇstˇe dok´ aˇzeme indukc´ı. Pro n = 0 rovnost trivi´alnˇe plat´ı. Pˇredpokl´adejme, ˇze plat´ı pro n − 1, pak T (n) = T (n − 1) + n =
n(n − 1) n(n + 1) +1+n= +1 2 2
ˇn´ı metoda substituc Postup pro odhad pomoc´ı O notace (pro Ω notaci je postup analogick´ y): 1. Odhadneme uzavˇrenou formu pomoc´ı asymptotick´e notace, tj ˇze uzavˇren´a forma patˇr´ı do O(g(n)) pro nˇejakou funkci g(n). 2. Vybereme jednu funkci f(n) z asymptotick´eho odhadu, pˇri specifikaci funkce m˚ uˇzeme vyuˇz´ıt konstant. Pro tuto funkci indukc´ı dok´ aˇzeme, ˇze T (n) 6 f(n), ˇc´ımˇz dok´aˇzeme, ˇze T (n) = O(g(n)). Bˇehem d˚ ukazu lze zvolit vhodn´e hodnoty konstant. 6
Pˇ r´ıklad 1:
T (n) = T (bn/2c) + T (dn/2e) + 1 T (1) = 1 Odhadneme jako O(n). Vybereme funkci cn−b = O(n), c > 0, b jsou konstanty. Chceme dok´azat T (n) 6 cn−b pro nˇejak´e hodnoty konstant b, c. To udˇel´ ame indukc´ı. Indukˇcn´ı pˇredpoklady jsou: T (bn/2c) 6 c(bn/2c) − b T (dn/2e) 6 c(dn/2e) − b Dok´ aˇzeme nerovnost pro T (n). T (n) = T (bn/2c) + T (dn/2e) + 1 6 c(bn/2c) − b + c(dn/2e) − b + 1 6 cn − 2b + 1 = = cn − b + (−b + 1) Zvol´ıme b = 1 a t´ım dostaneme T (n) 6 cn − 1, coˇz jsme chtˇeli dok´azat. Zb´ yv´a ovˇeˇrit pˇr´ıpad, kdy n = 1. Nerovnost T (1) = 1 6 cn − 1 plat´ı pro jak´ehokoliv c > 2. Dohromady jsme dok´azali, ˇze T (n) 6 2n − 1 a tedy T (n) = O(n). Pˇ r´ıklad 2:
T (n) = 2T (bn/2c) + n T (1) = 1 Odhadneme je O(n lg n). Pokud vybereme funkci cn lg n m˚ uˇzeme dok´azat spr´avnost obecn´eho indukˇcn´ıho kroku pro c > 1 T (n) 6 2(cbn/2c lg(bn/2c) + n 6 cn lg(n/2) + n = cn lg n − cn lg 2 + n 6 cn lg n U okrajov´e podm´ınky ovˇsem naraz´ıme na probl´em. T (1) = 1 6= 1 lg 1 = 0 M˚ uˇzeme vyuˇz´ıt toho, ˇze dokazujeme asymptotick´ y odhad a nerovnost proto m˚ uˇze platit aˇz od urˇcit´eho n0 . Pro n > 3 uˇz T (n) nez´ avis´ı na T (1), ale staˇc´ı zn´at T (2) a T (3). Volbou n0 = 2 m˚ uˇzeme posunout“okrajovou ” podm´ınku smˇerem nahoru (ˇc´ımˇz pˇr´ıpad n = 1, kter´ y zp˚ usobuje probl´emy, z d˚ ukazu vypust´ıme) a nahradit okrajovou podm´ınku pomoc´ı T (2) = 4, T (3) = 5, s t´ım, ˇze nyn´ı mus´ı b´ yt c > 2.
7
f(n)
f(n)
f(n1 ) f(n2 )
1
f(nk )
+
1
1
Pk i=1
f(nk )
+ poˇcet list˚ u =
v´ ysledek
Obr´ azek 1: Idea metody odhadu pomoc´ı stromu rekurze
Odhad pomoc´ı stromu rekurze Metoda odhadu pomoc´ı stromu rekurze je zaloˇzen´a na jednoduch´e myˇslence. Rekurentn´ı vztah T (n) =
k X
T (ni ) + f(n).
i=1
si pˇredstav´ıme jako strom. Uzly stromu odpov´ıdaj´ı jednotliv´ ym rekurzivn´ım vol´an´ım.“ Kaˇzd´emu uzlu pˇriˇrad´ıme ” mnoˇzstv´ı pr´ ace, kterou pomysln´ y algoritmus pˇri dan´em vol´an´ı provede. Listov´e uzly tak budou m´ıt pˇriˇrazenu konstantu, kter´ a odpov´ıd´ a okrajov´ ym podm´ınk´am rekurentn´ıho vztahu. Mnoˇzstv´ı pr´ace vnitˇrn´ıch uzl˚ u pak odpov´ıd´ a aplikaci funkce f na argument dan´eho rekurzivn´ıho vol´an´ı. V koˇrenu tedy provedeme f(n) pr´ ace, v jeho i-t´em potomku pak f(ni ). Pˇrirozenˇe, pokud seˇcteme pr´aci pˇriˇrazenou vˇsem uzl˚ um, dostaneme ˇreˇsen´ı rekurence. Souˇcet provedeme ve dvou kroc´ıch. Nejdˇr´ıve pro kaˇzdou u ´roveˇ n stromu seˇcteme pr´aci provedenou v uzlech na on´e u ´rovni, pot´e seˇcteme sumy z jednotliv´ ych vrstev. Pˇ r´ıklad:
T (n) = 2T (n/4) + n2 T (1) = 1 Zaˇcnˇeme konstruovat strom rekurze. Koˇrenu pˇriˇrad´ıme n2 . Potomk˚ um koˇrene, kteˇr´ı odpov´ıdaj´ı T (n/4) pˇriˇrad´ıme (n/4)2 . Uzl˚ um v dalˇs´ı vrstvˇe, odpov´ıdaj´ıc´ım T (n/16) (rekurzivn´ı vol´an´ı s argumentem n/4) pˇriˇrad´ıme (n/16)2 . V prvn´ı vrstvˇe se nach´ az´ı 2 uzly, suma pr´ ace je tedy 2(n/4)2 , v druh´e vrstvˇe se nach´az´ı 4 uzly, suma je tedy 2 4(n/16) . Nyn´ı si m˚ uˇzeme vˇsimnout urˇcit´e pravidelnosti. Pr´ace, kterou provedeme v jednom uzlu v i-t´e vrstvˇe (koˇren je v nult´e vrstvˇe) odpov´ıd´ a (n/4i )2 , poˇcet uzl˚ u v i-t´e vrstvˇe je 2i , suma pˇres vˇsechny uzly v t´eto vrstvˇe i i 2 2 i je tedy 2 (n/4 ) = n /8 . Listy se nach´ azej´ı ve vrstvˇe log4 n, jejich poˇcet je tedy 2log4 n = n1/2 . Odvozen´ı tohoto: v´ıme, ˇze log2 n = a tedy log4 n = log2 nlog4 2 . Dosad´ıme do 2log4 n a dostaneme 2log2 n
log4 2
Pokud nyn´ı seˇcteme vˇsechny vrstvy, dostaneme X
log4 n−1
T (n) =
(n2 /8i ) + n1/2
i=0
X
log4 n−1
= n2
i=0
8
(1/8i ) + n1/2
= nlog4 2 .
log4 n log4 2
n2
n2
n2 16
n2 256
n2 16
n2 256
n2 256
1 1 1
n2 8
n2 256
n2 64
1 1 1
nlog4 2
Obr´ azek 2: Strom rekurze pro rekurenci T (n) = 2T (n/4) + n2 Abychom se zbavili z´ avislosti na n v sumˇe, nahrad´ıme ji sumou cel´e geometrick´e posloupnosti. Dostaneme tedy X
log4 n−1 2
T (n) = n
(1/8i ) + n1/2
i=0 ∞ X 6 n2 (1/8i ) + n1/2 i=0 2
=n
1 + n1/2 1 − 1/8
Odhad ˇreˇsen´ı rekurence je O(n2 ).
Master theorem Peˇcliv´e vyˇreˇsen´ı metody stromu pro specifick´ y druh rekurenc´ı d´a n´asleduj´ıc´ı vˇetu. Porovn´av´ame rychlost r˚ ustu strom (nlogb a je poˇcet list˚ u) s rychlost´ı r˚ ustu funkce f(n) (ze znˇen´ı vˇety). Vˇ eta 1. Necht’ a > 1 a b > 1 jsou konstanty a f(n) je funkce a T (n) je definovan´ a na nez´ aporn´ych cel´ych ˇc´ıslech pomoc´ı rekurence T (n) = aT (n/b) + f(n), pˇriˇcemˇz n/b interpretujeme jako bn/bc nebo dn/be. Pak m˚ uˇzeme T (n) n´ asledovnˇe asymptoticky omezit. 1. Pokud f(n) = O(nlogb a− ) pro > 0, pak T (n) = Θ(nlogb a ). 2. Pokud f(n) = Θ(nlogb a ), pak T (n) = Θ(nlogb a lg n). 3. Pokud f(n) = Ω(nlogb a+ ) pro > 0 a pokud af(n/b) 6 cf(n) pro konstantu 0 < c < 1 a vˇsechna dostateˇcnˇe velk´ a n, pak T (n) = Θ(f(n)).
´ na ´ soben´ı velky ´ ch c ˇ´ısel Rychle Jsou d´ ana dvˇe ˇc´ısla A a B (v bin´ arn´ım z´ apisu, cel´ y postup lze upravit pro z´apis ˇc´ısel v jak´ekoliv soustavˇe), a chceme spoˇc´ıtat A · B. Algoritmus n´ asoben´ı pod sebe ze z´akladn´ı ˇskoly m´a sloˇzitost O(n2 ). ˇ ıslo A je reprezentov´ano sekvenc´ı Pˇredpokl´ ad´ ame poziˇcn´ı reprezentaci kladn´ ych ˇc´ısel ve dvojkov´e soustavˇe. C´ Pn i bit˚ u an−1 an−2 . . . a0 (pro n, kter´e je mocninou 2) pokud plat´ı, ˇze A = zme ˇc´ısla A1 dan´e i=0 ai 2 . Uvaˇ
9
sekvenc´ı bit˚ u an−1 . . . an/2 a A2 dan´e sekvenc´ı bit˚ u an/2−1 . . . a0 . Pak plat´ı, ˇze A = A1 2n/2 + A2 . M˚ uˇzeme ps´ at AB = (A1 2n/2 + A2 )(B1 2n/2 + B2 ) = A1 B1 2n + (A1 B2 + B1 A2 )2n/2 + A2 B2 Mohli bychom navrhnout rekurzivn´ı algoritmus, kter´ y pro n-bitov´a ˇc´ısla A, B urˇc´ı A1 ,A2 , B1 , B2 (to jsou vˇsechno (n/2)-bitov´ a ˇc´ısla), rekurzivnˇe spoˇc´ıt´ a souˇciny A1 B1, A1 B2 , A2 B1 , A2 B2 a s jejich pomoc´ı pak spoˇcte v´ ysledek podle pˇredchoz´ıho vztahu. Rekurzi ukonˇc´ıme v momentˇe, kdy n´asob´ıme jednobitov´a ˇc´ısla. Protoˇze n´ asoben´ı mocninou dvou m˚ uˇzeme realizovat pomoc´ı bitov´eho posuvu, kter´ y m´a line´arn´ı sloˇzitost, a sˇc´ıt´an´ı ˇc´ısel m´ a tak´e line´ arn´ı sloˇzitost, je sloˇzitost navrhovan´eho algoritmu d´ana rekurenc´ı T (n) = 4T (n/2) + O(n) T (1) = O(1), jej´ımˇz ˇreˇsen´ım je Θ(n2 ). Abychom dos´ ahli algoritmu s menˇs´ı sloˇzitost´ı, mus´ım ubrat rekurzivn´ı zavol´an´ı. To m˚ uˇzeme prov´est d´ıky n´ asleduj´ıc´ı u ´vaze: A1 B2 + A2 B1 = A1 B2 + A2 B1 + A1 B1 − A1 B1 + A2 B2 − A2B2 = A1 B1 + A2 B2 + A1 (B2 − B1 ) + A2 (B2 − B1 ) = A1 B1 + A2 B2 + (A1 − A2 )(B2 − B1 ), a proto AB = A1 B1 2n + [A1 B1 + A2 B2 + (A1 − A2 )(B2 − B1 )]2n/2 + A2 B2 Nyn´ı staˇc´ı jenom tˇri rekurzivn´ı zavol´ an´ı, mus´ıme spoˇc´ıtat A1 B1 , A2 B2 a (A1 −A2 )(B2 −B1 ). Vzniklo nebezpeˇc´ı, ˇze budeme muset n´ asobit z´ aporn´ a ˇc´ısla. To lze ale snadno obej´ıt t´ım, ˇze si nejdˇr´ıve spoˇc´ıt´ame znam´enko v´ ysledku, a pak vyn´ asob´ıme absolutn´ı hodnoty ˇc´ısel. Algoritmus 2 N´ asoben´ı velk´ ych ˇc´ısel 1: procedure Multiply(X,Y,n) 2: s ← sign(X) · sign(Y) 3: X ← abs(X) 4: Y ← abs(Y) 5: if n = 1 then 6: return X · Y · s 7: end if 8: A ← ˇc´ıslo tvoˇren´e n/2 lev´ ymi bity X 9: B ← ˇc´ıslo tvoˇren´e n/2 prav´ ymi bity X 10: C ← ˇc´ıslo tvoˇren´e n/2 lev´ ymi bity Y 11: D ← ˇc´ıslo tvoˇren´e n/2 prav´ ymi bity Y 12: m1 ←Multiply(A, C, n/2) 13: m2 ←Multiply(A − B, D − C, n/2) 14: m3 ←Multiply(B, D, n/2) 15: return s · (shift(m1 , n) + shift(m1 + m2 + m3 , n/2) + m3 ) 16: end procedure
´ na ´ soben´ı polynom˚ Rychle u
10
