Rekurence, rekurze a sumy. Základy diskrétní matematiky, BI-ZDM

Rekurence, rekurze a sumy doc. RNDr. Josef Kolář, CSc. Katedra teoretické informatiky FIT České vysoké učení technické v Praze c

Josef Kolar, 2011

Základy diskrétní matematiky, BI-ZDM ZS 2011/12, Lekce 9

Evropský sociální fond. Praha & EU: Investujeme do vaší budoucnosti

doc. Josef Kolář (FIT ČVUT)

Rekurence, rekurze a sumy

ZDM, ZS 2011/12, Lekce 9

1 / 15

Rekurentní problémy

Rekurence Rekurentní problém Problém, jehož řešení je závislé na řešení menších instancí stejného problému. Jak řešíme rekurentní problémy? Řešení lze obvykle vyjádřit rekurzivním algoritmem a jeho vlastnosti odpovídajícími rekurentními vztahy (rekurencemi).

Často nás také zajímá jak formulovat odpovídající iterativní (nerekurzivní) algoritmus jak vyjádřit vlastnosti řešení v uzavřeném tvaru (řešení rekurencí)




2 / 15


Hanojská věž - ToH Příklad 1 Máme tři tyče A, B, C, na tyči A je navlečeno n kruhových disků postupně se zmenšující velikosti. Tyto disky máme přesunout na tyč B tak, že pohybujeme vždy jen jedním diskem a nikdy nepoložíme větší disk na menší. Řešení si vyzkoušíme pro n = 1 nebo n = 2 a uhádneme obecný postup: 1

Pro n = 1 vezmeme disk z tyče A a přemístíme jej na tyč B.

2

Pro n > 1 nejprve přemístíme vrchních n − 1 disků z A na C, potom přesuneme n-tý disk z A na B a konečně přemístíme n − 1 disků z C na B.

Kolik kroků je celkem zapotřebí k přemístění všech disků?




3 / 15


Počet kroků při řešení ToH Označíme minimální počet kroků (přesunů jednotlivých disků) potřebných pro řešení ToH velikosti n jako Tn . Už víme, že T1 = 1, T2 = 3 (můžeme doplnit i T0 = 0), z popsaného postupu řešení plyne ( 0 pro n = 0, Tn = (1) 2.Tn−1 + 1 pro n > 0.

Otázka: Je uvedený postup opravdu optimální?




4 / 15


Počítáme kroky Jak určíme např. T8 ? T2 = 3, T3 = 2 · T2 + 1 = 2 · 3 + 1 = 7, T4 = 2 · T3 + 1 = 2 · 7 + 1 = 15, T5 = 2 · T4 + 1 = 2 · 15 + 1 = 31, T6 = 2 · T5 + 1 = 2 · 31 + 1 = 63, T7 = 2 · T6 + 1 = 2 · 63 + 1 = 127, T8 = 2 · T7 + 1 = 2 · 127 + 1 = 255. UFFF!!! Zkusíme uhádnout vyjádření Tn v uzavřeném tvaru: Tn = 2n − 1,

pro n ≥ 0

(2)

To odpovídá prvním spočteným hodnotám, je to ale opravdu správně?




5 / 15


Ověření uzavřené formule pro Tn Jak dokážeme správnost vztahu (??)? MATEMATICKOU INDUKCÍ! 1

T0 je opravdu nula, neboť T0 = 20 − 1 = 0.

2

Předpokládejme, že vztah (??) platí pro n ≥ 0 a chceme určit hodnotu Tn+1 . Podle vztahu (??) a s využitím indukčního předpokladu dostáváme Tn+1 = 2Tn + 1 = 2(2n − 1) + 1 = 2n+1 − 1.

Je tedy potvrzeno, že řešení rekurentního vztahu (??) má tvar uvedený ve vztahu (??).

Otázka Kolik desítkových číslic je přibližně třeba k vyjádření počtu kroků při přesunu 64 disků? (Nápověda: log10 2 ≈ 0, 3 - doba 584942417355 roků.) doc. Josef Kolář (FIT ČVUT)



6 / 15


Jedno malé kouzlo Místo uhádnutí správného řešení jsme také mohli použít následujícího triku: k oběma stranám rekurence (??) přičteme jedničku: ( 1 pro n = 0, Tn + 1 = 2.Tn−1 + 2 pro n > 0. a zavedeme Un = Tn + 1, pro které platí rekurence ( 1 pro n = 0, Un = 2.Un−1 pro n > 0.

(3)

Není obtížné poznat, že rekurenci (??) řeší geometrická posloupnost Un = 2n , takže Tn = Un − 1 = 2n − 1.




7 / 15


Jak krájet pizzu Příklad 2 Na kolik kousků je možné rozkrájet pizzu pomocí n přímých tahů řezacím kolečkem? Formální znění: Jaký je maximální počet Ln oblastí určených n přímkami v rovině? Pomocí obrázků snadno určíme, že L0 = 1, L1 = 2, L2 = 4 Vypadá to, že by mohlo být Ln = 2n , ale OUHA! - L3 = 4 + 3 - další přímkou dokážeme přidat nejvýše 3 oblasti. Obecně: n-tá přímka (pro n > 0) může zvýšit počet oblastí o k, ⇔ prochází-li k starými oblastmi, ⇔ protne-li stávající přímky v (k − 1) různých bodech, ⇒ takže je k ≤ n a platí Ln ≤ Ln−1 + n, doc. Josef Kolář (FIT ČVUT)

pro n > 0



8 / 15


Umíme krájet pizzu! Všechny předchozí přímky protneme, právě když nová přímka nebude rovnoběžná se žádnou z nich, takže lze docílit rovnost a máme rekurenci: ( 1 pro n = 0, Ln = (4) Ln−1 + n pro n > 0. Prověříme, zda již spočtené hodnoty L1 , L2 a L3 této rekurenci vyhovují. Jak vlastně posloupnost Ln vypadá: 1, 2, 4, 7, 11, 16, 22, . . . Připomíná nám to něco? Ani ne, takže uhádnout řešení asi nepůjde. Zkusíme postupný rozklad rekurence (tzv. telescope).




9 / 15


Postupný rozklad rekurence Dosazujeme do pravé strany hodnoty odvozené z rekurentního pravidla: Ln = Ln−1 + n = Ln−2 + (n − 1) + n = Ln−3 + (n − 2) + (n − 1) + n . = .. = L0 + 1 + 2 + . . . + (n − 2) + (n − 1) + n = 1 + Sn , kde Sn = 1 + 2 + . . . + (n − 2) + (n − 1) + n Umíme určit Sn jako to uměl devítiletý Gauss? Samozřejmě Sn =

n(n + 1) , 2

takže Ln =

n(n + 1) + 1, 2

pro n ≥ 0

(5)

Jsme hotovi? Nikoliv, ještě bychom to měli dokázat indukcí . . . doc. Josef Kolář (FIT ČVUT)



10 / 15


Složitější krájení pizzy Příklad 3 Trochu si zkomplikujeme řezání: namísto přímého řezu povedeme řezy ve tvaru zubu (zlomené přímky) - nakreslíme si obrázek. Jaký bude maximální počet Zn oblastí určených n zuby v rovině? Zřejmě je Z0 = 1, Z1 = 2, Z2 = 7. Jak je to obecně? Přidat nový zub je jako přidat dvě nové přímky, u kterých ale tři oblasti splynou do jedné! Na každý nový zub tedy proti dvěma přímkám ztratíme dvě oblasti: Zn = L2n − 2n = 2n(2n + 1)/2 + 1 − 2n = 2n2 − n + 1, pro n ≥ 0. Jak vidno, Ln ≈ doc. Josef Kolář (FIT ČVUT)

1 2 n , 2

Zn ≈ 2n2



11 / 15


Josefův problém Příklad 4 Skupina židovských povstalců ve válce proti Římanům byla obklíčena v jeskyni. Rozhodli se raději umřít, než aby se vzdali. Stoupli si do kruhu a zabíjeli každého třetího tak dlouho, až zůstal poslední, a ten se zabil sám. Josefovi se ale zemřít nechtělo a protože byl chytrý a navíc měl jednoho komplice, stoupli si na taková místa, že jako poslední zbyli právě oni dva. V naší verzi předpokládáme n lidí rozestavených do kruhu, zabíjí se každý druhý tak dlouho, až zbyde poslední, který zůstane naživu. Máme určit pořadové číslo J(n) přežívající osoby. Pro n=10 budou postupně eliminovány osoby 2, 4, 6, 8, 10, 3, 7, 14 a 9, takže číslo 5 přežije. Platí tedy J(10) = 5. doc. Josef Kolář (FIT ČVUT)



12 / 15


Zkoušíme hádat Platí J(10) = 5. Je z toho možné odhadnout, že J(n) = n/2 pro nějaká malá sudá n? n J(n)

1 1

2 1

3 3

4 1

5 3

6 5

Odhad nefunguje pro n = 4 a n = 6, hodnoty J(n) jsou navíc všechny liché. Při prvním průchodu vypadnou všechna sudá čísla - je-li na počátku 2n lidí (1, 2, 3, 4, . . . , 2n − 2, 2n − 1, 2n), zbyde jich polovina s lichými čísly (1, 3, 5, 7, . . . , 2n − 3, 2n − 1) a další kolo začne eliminací čísla 3. To je obdobná situace jako na začátku, jen čísla přítomných jsou dvojnásobky zmenšené o 1: J(2n) = 2J(n) − 1 pro n ≥ 1 doc. Josef Kolář (FIT ČVUT)



13 / 15


Co dál s Josefem? Jak můžeme využít toho, že J(10) = 5 a J(2n) = 2J(n) − 1 pro n ≥ 1? Zkusíme počítat J(n) pro násobky čísla 10 v argumentu: J(20) J(40)

= 2J(10) − 1 = 2 · 5 − 1 = 9 = 2J(20) − 1 = 2 · 9 − 1 = 17,

takže obecně

J(5 · 2m ) = 2m+1 + 1. A jak to vypadá pro lichý počet osob 2n + 1? Při prvním průchodu vypadnou všechna sudá čísla a po čísle 2n vypadne číslo 1, zbyde tedy menší polovina s čísly (3, 5, . . . , 2n − 1, 2n + 1) a další kolo začne od čísla 3. Máme tedy opět situaci jako na začátku, jen čísla přítomných jsou dvojnásobky zvětšené o 1: J(2n + 1) = 2J(n) + 1 pro n ≥ 1 doc. Josef Kolář (FIT ČVUT)



14 / 15


Dáme věci dohromady Je zřejmé, že naše zjištění pro sudé a liché počty osob spolu se základním případem J(1) = 1 vedou na následující rekurenci pokrývající všechny možné případy: J(1) = 1 J(2n) = 2J(n) − 1, J(2n + 1) = 2J(n) + 1,

pro n ≥ 1 pro n ≥ 1.

Jak vypadá tabulka prvních hodnot J(n)? n J(n)

1 1

2 1

3 3

4 1

5 3

6 5

7 7

8 1

9 3

10 5

11 7

12 9

13 11

14 13

15 15

16 1

Vidíme jasné členění do skupin začínajících mocninami dvou. doc. Josef Kolář (FIT ČVUT)



15 / 15


Rozbor skupin Jak nalézt řešení rekurence pro J(n) v uzavřeném tvaru? n J(n) k

1 1 0

2 1 0

3 3 1

4 1 0

5 3 1

6 5 2

7 7 3

8 1 0

9 3 1

10 5 2

11 7 3

12 9 4

13 11 5

14 13 6

15 15 7

16 1 0

Vyjádříme n ve tvaru n = 2m + k, kde 2m je nejvyšší mocnina dvou nepřesahující n. Pak k (< 2m ) určuje, o kolik n mocninu 2m překračuje. Zdá se, že máme řešení! J(2m + k) = 2k + 1 pro m ≥ 0 a 0 ≤ k < 2m

(6)

Je ale třeba dokázat(indukcí sami!), že (??) opravdu je řešením. doc. Josef Kolář (FIT ČVUT)



16 / 15


Rozbor vlastností J(n) Zkusíme se podívat na vyjádření n a J(n) ve dvojkové soustavě. Nechť n = (bm bm−1 . . . b1 b0 )2 , což znamená, že n = bm 2m + bm−1 2m−1 + . . . + b1 21 + b0 20 , kde každé bi je buď 0 nebo 1, přičemž první dvojková číslice bm je 1. Jelikož je n = 2m + k, můžeme psát n k 2k 2k + 1 J(n) doc. Josef Kolář (FIT ČVUT)

= = = = =

(1 bm−1 . . . (0 bm−1 . . . (bm−1 bm−2 (bm−1 bm−2 (bm−1 bm−2

b1 b0 )2 , b1 b0 )2 , . . . b1 b0 0)2 , . . . b1 b0 1)2 , . . . b1 b0 bm )2 .



17 / 15


Překvapivé odhalení S použitím dvojkového zápisu tak dostáváme vyjádření pro J(n) ve tvaru J (bm bm−1 . . . b1 b0 )2 = (bm−1 bm−2 . . . b1 b0 bm )2

(7)

Hodnotu J(n) tedy dostaneme cyklickým posuvem binárního zápisu argumentu n o jedno místo vlevo. O J(n) by se toho dalo zjistit ještě víc, zkusme se ale zamyslet nad možností řešení zobecněné rekurence platné pro J(n) ve tvaru f (1) = α f (2n) = 2f (n) + β, f (2n + 1) = 2f (n) + γ,

pro n ≥ 1 pro n ≥ 1.

Pro J(n) platila rekurence s hodnotami α = 1, β = −1 a γ = 1.




18 / 15


Průzkum bojem K odhadu řešení nám pomůže tabulka funkce f (n) pro malé hodnoty n. n 1 2 3 4 5 6 7 8 9 10

f (n) α 2α 2α 4α 4α 4α 4α 8α 8α 8α

+

β +

+ + +

3β 2β β

+ + +

7β 6β 5β

γ

+ γ + 2γ + 3γ + γ + 2γ

Koeficienty u α odpovídají nejvyšší mocnině dvou obsažené v n. Mezi dvěma mocninami dvou se hodnoty koeficientů u β snižují s krokem 1 až k 0 a koeficienty u γ zvyšují s krokem 1 počínaje od 0. doc. Josef Kolář (FIT ČVUT)



19 / 15


Odhad řešení zobecněné rekurence Řešení tedy vyjádříme ve tvaru f (n) = A(n) · α + B(n) · β + C(n) · γ. a vzhledem závislostem zachyceným v tabulce hodnot f(n) určíme A(n) = 2m B(n) = 2m − 1 − k C(n) = k, kde jako obvykle n = 2m + k a 0 ≤ k < 2m pro n ≥ 1. Správnost tohoto řešení by ovšem bylo třeba potvrdit indukcí. Ukážeme si ale jiný přístup získání obecného řešení rekurence získané složením několika partikulárních řešení.




20 / 15


Skládání partikulárních řešení Začneme speciálním případem α = 1, β = 0, γ = 0, tedy f (n) = A(n). Rekurence má v tomto případě tvar A(1) = 1 A(2n) = 2A(n) A(2n + 1) = 2A(n)

pro n ≥ 1 pro n ≥ 1

Řešení má tvar A(2m + k) = 2m , jak bychom potvrdili indukcí. Nyní na to půjdeme obráceně: zvolíme nějakou jednoduchou funkci f (n) a zjišťujeme, zda existují konstanty {α, β, γ}, které ji budou prostřednictvím naší rekurence definovat. Zkusíme nejprve f (n) = 1: 1 = α 1 = 2·1+β 1 = 2·1+γ Odtud plyne, že {α, β, γ} = {1, − 1, − 1} vyhovuje rekurenci a platí A(n) − B(n) − C(n) = f (n) = 1. doc. Josef Kolář (FIT ČVUT)



21 / 15


Skládání partikulárních řešení pokračuje Nyní zkusíme funkci f (n) = n: 1 = α 2n = 2 · n + β 2n + 1 = 2 · n + γ Tyto rovnice platí pro všechna n, pokud je α = 1, β = 0 a γ = 1. Shrneme naše výsledky: A(n) = 2m , A(n) − B(n) − C(n) = 1 A(n) + C(n) = n

kde n = 2m + k, 0 ≤ k < 2m

Odtud již snadno získáme zbývající části řešení: C(n) = n − A(n) = k B(n) = A(n) − C(n) − 1 = 2m − k − 1. To odpovídá našemu prvnímu výsledku získanému odhadem. doc. Josef Kolář (FIT ČVUT)



22 / 15

Součty a rekurence

Součty a rekurence Jak souvisí součty a rekurence? Pro posloupnost an je odpovídající P posloupnost částečných součtů Sn = nk=0 ak je definována rekurencí S0 = a0 Sn = Sn−1 + an ,

pro n > 0.

To znamená, že techniky řešení rekurencí budou užitečné i pro získání hodnoty součtů v uzavřeném tvaru. Má-li např. an tvar β + γ · n, pak dostáváme obecný tvar R0 = α Rn = Rn−1 + β + γ · n,

pro n > 0.

Postupem jako Josefova problému můžeme určit R1 = α + β + γ, R2 = α + 2β + 3γ, atd. Obecné řešení bude mít tvar Rn = A(n) · α + B(n) · β + C(n) · γ, kde koeficienty A(n), B(n), C(n) určíme metodou skládání partikulárních řešení. doc. Josef Kolář (FIT ČVUT)



23 / 15

Součty a rekurence

Sčítáme aritmetickou posloupnost R0 = α Rn = Rn−1 + β + γ · n,

pro n > 0.

Zvolíme postupě Rn = 1 ⇒ α = 1, β = 0, γ = 0 ⇒ A(n) = 1 Rn = n ⇒ α = 0, β = 1, γ = 0 ⇒ B(n) = n 2 Rn = n ⇒ α = 0, β = −1, γ = 2 ⇒ 2C(n) − B(n) = n2 Z posledních dvou vztahů určíme C(n) = (n2 + n)/2 P Součet aritmetické posloupnosti nk=0 (a + bk) tedy odpovídá naší obecné rekurenci s parametry α = β = a, γ = b, takže řešení je A(n) · a + B(n) · a + C(n) · b = a(n + 1) + b



n(n + 1) . 2


24 / 15

Součty a rekurence

Další hezký trik Vzpomínáte na Hanoj a její věže? Tam byla rekurence, která se od částečných součtů liší: T0 = 0 Tn = 2Tn−1 + 1,

pro n > 0.

Stačí ale malá úprava a dostaneme T0 /20 = 0 Tn /2n = Tn−1 /2n−1 + 1/2n , Nyní můžeme položit Sn = Tn

/2n

pro n > 0.

a máme

S0 = 0 Sn = Sn−1 + 2−n ,

pro n > 0,

Pn

takže je Sn = k=1 2−k , neboli částečný součet geometrické posloupnosti (2−1 + 2−2 + . . . + 2−n ) s prvním členem 1/2 a kvocientem 1/2, který má hodnotu 1 − ( 21 )n . Platí tedy Tn = 2n · Sn = 2n − 1. doc. Josef Kolář (FIT ČVUT)



25 / 15

Součty a rekurence

Ještě jedna rekurence Připomeneme si ještě Catalanova čísla z přednášky 6: 1 2n Cn = n+1 n Představují počet ”dobrých tras” z levého dolního do pravého horního rohu ve čtvercové mřížce velikosti n × n (trasy nesmí překročit diagonálu). Každou dobrou trasu můžeme rozdělit na dvě části první část od bodu (0, 0) do bodu (k, k), kde se poprvé dostane znovu na diagonálu druhá část od bodu (k, k) do bodu (n, n). První část vždy začíná krokem vpravo z (0, 0) do (1, 0) a končí krokem nahoru z (k, k − 1) do (k, k) (proč?).




26 / 15

Součty a rekurence

Dobré trasy a binární stromy Postup mezi (1, 0) a (k, k − 1) představuje dobrou trasu v mřížce velikosti (k − 1) × (k − 1), která má rohy v bodech (1, 0),(1, k − 1),(k, k − 1) a (k, 0) – takových tras je ovšem Ck−1 . Podobně druhá část mezi body (k, k) a (n, n) představuje dobrou trasu v mřížce velikosti (n − k) × (n − k), která má rohy v bodech (k, k), (k, n), (n, n), (n, k) – takových tras je zase Cn−k Podle sčítacího principu tedy dostaneme Cn =

n X

Ck−1 Cn−k

k=1

Uvažujme nyní různé binární stromy o n uzlech – jejich počet označíme jako an . Každý takový strom má kořen a dále má levý podstrom s k uzly (takových je ak ) a pravý podstrom s n − k − 1 uzly (takových je an−k−1 ) Pn−1 Dostáváme tedy an = k=0 ak an−k−1 a jednoduchou úpravou zjistíme, že an = Cn . doc. Josef Kolář (FIT ČVUT)



27 / 15

Rekurence, rekurze a sumy. Základy diskrétní matematiky, BI-ZDM

Recommend Documents