Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo ooo oooo Diskrétní matematika - 11. týden Vytvořující funkce a re k u re n ce Lukáš Vokřínek Masarykova univerzita Faku ta informatiky podzim 2020 Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo ooo oooo Obsah přednášky Q Vytvořující funkce, rozvinutí do mocninné řady Q Vytvořující funkce a Fibonacciho čísla Q Řešení rekurencí Literatura Vytvořující funke oooooooo nutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí ooo oooo Doporučené zd roje • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. □ fp1 = Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo ooo oooo Doporučené zdroje • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. • Donald E. Knuth, The Art Of Computer Programming. • Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1994. Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla oooooooo ooo Plán přednáš Q Vytvořující funkce, rozvinutí do mocninné řady Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí •ooooooo ooo oooo (Formální) mocninné řady r Definice Buď dána nekonečná posloupnost a = (ao, ai, a2,.. .). Její vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru oo 3kxk = a0 + a\x + a2x2 H----. k=Q >0 Q,o Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí O0OOOOOO ooo oooo (Formální) mocninné řady Věta Buď (ao, ai, a2,...) posloupnost reálných čísel. Platí-li pro nějaké R £ IR, že pro všechna k ^> 0 je \a^\ < Rk, pak řada a(x)= ^2akxk k>0 konverguje pro každé xg(-^). Součet této řady tedy definuje funkci na uvedeném intervalu, tuto funkci označujeme rovněž a(x). Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí O0OOOOOO ooo oooo (Formální) mocninné řady Věta Buď (ao, ai, a2,...) posloupnost reálných čísel. Platí-li pro nějaké R £ IR, že pro všechna k ^> 0 je \a^\ < Rk, pak řada a(x)= ^2akxk k>0 konverguje pro každé xg(-^). Součet této řady tedy definuje funkci na uvedeném intervalu, tuto funkci označujeme rovněž a(x). Hodnotami funkce a(x) na libovolném okolí 0 je jednoznačně určena původní posloupnost, neboť má a(x) v 0 derivace všech řádů a platí aW(0) 3k = ^T' Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oo«ooooo ooo oooo Přehled mocninných řad V. A (Ai1'V" 1*1—-) In fc>0 1 £čí íMííi--) 1 -x ^ /c ' fc>l ex /c>0 k>0 i _v^A + "-i (1 -x)" ~ ^ V n-1 v ' /c>0 v 1 _v^A + n-i (1 - ax)n ~ 2-" V n-1 , /c>0 >0^O Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí ooo«oooo ooo oooo V dalším bude výhodné položit a_i = 0, a_2 = 0, atd. (pak můžeme sčítat přes všechna k)\ • E akxk + E bkxk = E(a/c + bk)xk □ s Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí ooo«oooo ooo OOOO V dalším bude výhodné položit a_i = 0, a_2 = 0, atd. (pak můžeme sčítat přes všechna k)\ • E 3kxk + £ bkxk = £(afc + bk)xk. Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí ooo«oooo ooo oooo V dalším bude výhodné položit a_i = 0, a můžeme sčítat přes všechna k)\ • E akxk + E bkxk = E(a/c + bk)xk. • Xn -J2akXk = J2ak-nXk. Ť — Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí ooo«oooo ooo oooo V dalším bude výhodné položit a_i = 0, a_2 = 0, atd. (pak můžeme sčítat přes všechna k)\ • E 3kxk + £ bkxk = E(a/c + bk)xk. 9 a-J2 akXk = J2{aak)xk. • Xn -J2akxl< = Y.ak-nXk. • (EakXk)-(Y,bkxk) = Eckxk, kde Ck = Yl a'bJ- i+j=k Posloupnost (ck) bývá také nazývána konvolucí posloupností {ak),(bk)- Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla v i Řešení rekurencí OOOO0OOO ooo oooo Ukažme si důležitý příklad využívající konvoluci posloupností: Příklad ^a(x) je v.f.p. (a0, a0 + ai, 3q + a\ + a2,.. .)■ l4r- (i,",- J = Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí OOOO0OOO ooo oooo Ukažme si důležitý příklad využívající konvoluci posloupností Příklad Y^a(x) je v.f.p. (a0, a0 + ai, a0 + a\ + a2,.. .)■ Příklad Zkusme pomocí vytvořujících funkcí najít explicitní vzoreček pro 1 + 2 + • • • + 2k. Protože je vytvořující funkce posloupnosti (2^), je vytvořující funkcí pro posloupnost (1 + 2 H----+ 2k) funkce i i r_ o _j___l_ /I 1-x ' l-2x ^ ' l-2x 1-x* H Proto je zpětně tato posloupnost rovna (2 • 2k — 1) >0 Q,o Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí OOOO0OOO ooo oooo Ukažme si důležitý příklad využívající konvoluci posloupností Příklad Y^a(x) je v.f.p. (a0, a0 + ai, a0 + a\ + a2,.. .)■ Příklad Zkusme pomocí vytvořujících funkcí najít explicitní vzoreček pro 1 + 2 + • • • + 2k. Protože je vytvořující funkce posloupnosti (2^), je vytvořující funkcí pro posloupnost (1 + 2 H----+ 2k) funkce l-x l-2x = 2 • l-2x Proto je zpětně tato posloupnost rovna (2 • 2k — 1) Rozklad na parciální zlomky! Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí OOOOO0OO ooo oooo Rozklad na parciální zlomky - připomenutí Rozklad na parciální zlomky jsme již viděli dříve při integraci racionálních lomených funkcí, přesto připomeneme: • Předpokládáme, že P(x)/Q(x) je podíl polynomů, kde deg P < deg Q (jinak vydělíme se zbytkem) a P(x), Q(x) nemají společné kořeny. X4A ^ *3i <- u i Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí OOOOO0OO ooo oooo Rozklad na parciální zlomky - připomenutí Rozklad na parciální zlomky jsme již viděli dříve při integraci racionálních lomených funkcí, přesto připomeneme: • Předpokládáme, že P(x)/Q(x) je podíl polynomů, kde deg P < deg Q (jinak vydělíme se zbytkem) a P(x), Q(x) nemají společné kořeny. 9 Polynom Q(x) rozložíme na kořenové činitele. Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí OOOOO0OO ooo oooo Rozklad na parciální zlomky - připomenutí Rozklad na parciální zlomky jsme již viděli dříve při integraci racionálních lomených funkcí, přesto připomeneme: • Předpokládáme, že P(x)/Q(x) je podíl polynomů, kde deg P < deg Q (jinak vydělíme se zbytkem) a P(x), Q(x) nemají společné kořeny. Ji-jC 9 Polynom Q(x) rozložíme na kořenové činitele. • Jsou-li všechny kořeny cti,... ,ct£ jednoduché, pak P(x) _ *i | | At Q(X) x — a\ x — olu Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí OOOOO0OO ooo oooo Rozklad na parciální zlomky - připomenutí Rozklad na parciální zlomky jsme již viděli dříve při integraci racionálních lomených funkcí, přesto připomeneme: • Předpokládáme, že P(x)/Q(x) je podíl polynomů, kde deg P < deg Q (jinak vydělíme se zbytkem) a P(x), Q(x) nemají společné kořeny. 9 Polynom Q(x) rozložíme na kořenové činitele. • Jsou-li všechny kořeny cti,... ,ct£ jednoduché, pak P(x) ^ Ax ~ ~~At _)_... _l_ Q(X) x-ai x-ať (3&£\ • Má-li kořen a násobnost k, pak jsou příslušné parciální z tvaru lomkvj^^ (x - a) (x - a)2 (x - a)k /JL. Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí OOOOOO0O ooo oooo Rozklad na parciální zlomky - pokračování • V případě dvojice komplexně sdružených kořenů nahrazujeme sčítanec A/[x — a) sčítancem (Ax + B)/(x2 + px + q) včetně příslušných mocnin jmenovatele. Literatura Vytvořující funkce rozvinutí do mocninné řady OOOOOO0O Vytvořující funkce a Fibonacciho čísla ooo i Řešení rekurencí OOOO Rozklad na parciální zlomky - pokračování • V případě dvojice komplexně sdružených kořenů nahrazujeme sčítanec A/[x — a) sčítancem (Ax + B)/(x2 + px + q) včetně příslušných mocnin jmenovatele. • Neznámé dopočítáme roznásobením a buď porovnáním koeficientů u jednotlivých mocnin x nebo dosazením jednotlivých kořenů. Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí OOOOOO0O ooo oooo Rozklad na parciální zlomky - pokračování • V případě dvojice komplexně sdružených kořenů nahrazujeme sčítanec A/[x — a) sčítancem (Ax + B)/(x2 + px + q) včetně příslušných mocnin jmenovatele. • Neznámé dopočítáme roznásobením a buď porovnáním koeficientů u jednotlivých mocnin x nebo dosazením jednotlivých kořenů. • Výrazy A/(x — a)k převedeme na výrazy tvaru 6/(1 — j3x)k vydělením čitatele i jmenovatele výrazem {—a)k. Tento výraz již umíme rozvinout do mocntTTTTSYady. Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí OOOOOOO* ooo oooo Rozklad na parciální zlomky - vychytávka Protože preferujeme 1 —/3x, bude lepší jmenovatel rozložit rovnou na součin takovýchto činitelů, např. 1 - 5x + 6x2 = (1 - 2x)(l - 3x), □ ► 4 S> Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí ooooooo* ooo oooo Rozklad na parciální zlomky - vychytávka Protože preferujeme 1 — fix, bude lepší jmenovatel rozložit rovnou na součin takovýchto činitelů, např. 1 - 5x + 6x2 = (1 - 2x)(l - 3x), který obecně získáme "otočením" polynomu provedeme substituci x = i a vynásobme ŕ2: l-5i + 6£ = (l-2i)(l-3i) ŕ2-5ŕ + 6 = (ŕ-2)(ŕ-3) Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí ooooooo* ooo oooo Rozklad na parciální zlomky - vychytávka Protože preferujeme 1 — f3x, bude lepší jmenovatel rozložit rovnou na součin takovýchto činitelů, např. 1 - 5x + 6x2 = (l-2x)(l-3x), který obecně získame "otočením" polynomu provedem^ubstituci x = |a vynásobme t2\ l_5± + 6Í = (l-2±)(l-3±) t2 -5ŕ + 6 = (ŕ-2)(ŕ-3)_ Přitom poslední tvar je již klasický rozklad na kořenové činitele, ve kterém můžeme použít např. známé vzorečky pro kořeny kvadratického polynomu. □ e Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo ooo oooo Plán přednášky Vytvořující funkce a Fibonacciho čísla Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí OOOOOOOO «00 oooo Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem F0 = O, Fi = 1, Fk = Ffr_i + F/,.2 pro /c > 2. Již dříve jste si uváděli všemožné výskyty této posloupnosti v přírodě, v matematice nebo v teoretické informatice (podrobně viz http://is.muni.cz/th/41281/prif_d/disertace.pdf). Našim cílem bude (opět) najít formuli pro výpočet r?-tého členu posloupnosti. Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí OOOOOOOO «00 oooo Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem F0 = O, Fi = 1, Fk = Ffr_i + F/,.2 pro /c > 2. Již dříve jste si uváděli všemožné výskyty této posloupnosti v přírodě, v matematice nebo v teoretické informatice (podrobně viz http://is.muni.cz/th/41281/prif_d/disertace.pdf). Našim cílem bude (opět) najít formuli pro výpočet ^-tého členu posloupnosti. Poznámka (Nejen) pro manipulace se sumami používají autoři Concrete mathematics velmi vhodné označení [logický predikát] výraz je roven 1 v případě splnění predikátu, jinak 0. Např. [k = l],[2|/c] apod. V) o Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí OOOOOOOO «00 oooo Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem F0 = O, Fi = 1, Fk = Ffr_i + F/,.2 pro /c > 2. Již dříve jste si uváděli všemožné výskyty této posloupnosti v přírodě, v matematice nebo v teoretické informatice (podrobně viz http://is.muni.cz/th/41281/prif_d/disertace.pdf). Našim cílem bude (opět) najít formuli pro výpočet r?-tého členu posloupnosti. Poznámka (Nejen) pro manipulace se sumami používají autoři Concrete mathematics velmi vhodné označení [logický predikát] výraz je roven 1 v případě splnění predikátu, jinak 0. Např. [k = l],[2|/c] apod. Pro vyjádření koeficientu u xk ve vytvořující funkci F(x) se pak často používá zápis [x/c]F(x). V) o Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo o«o oooo Příklad - pokr. Uvažme vytvořující funkci F(x) Fibonacciho posloupnosti. Při podmínkách F0 = 0, F\ = 1 je to F(x) - xF(x) - x2F(x) =x, a tedy X — x — X 2 ' Našim cílem je tedy odvodit vztah pro /c-tý člen posloupnosti. 1 -X.-V. v* Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo o«o oooo Příklad - pokr. Uvažme vytvořující funkci F(x) Fibonacciho posloupnosti. Při podmínkách Fq = 0, F\ — 1 je to F(x) — xF(x) — x2F(x) = x, a tedy x — x — x 2 ' Našim cílem je tedy odvodit vztah pro /c-tý člen posloupnosti. Využijeme k tomu rozklad na parciální zlomky a dostaneme x A B ^Hy^-i^M^ l-x-x2~l-Ax + l- /ix\« :r Ar^°> ^ kde A, jsou kořeny t — t — 1 a A 6 vhodné konstanty odvozené z počátečních podmínek. Odtud už vcelku snadno vyjde Fk = A'\k + B'íLk, jak to známe z dřívějška 1 * <\->* < □ ► < [3p ► < -e ► < -e Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo oo« oooo Příklad - závěr S využitím počátečních podmínek dostáváme Jistě je zajímavé, že tento výraz plný iracionálních čísel je vždy celočíselný. Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo oo« oooo Příklad - závěr S využitím počátečních podmínek dostáváme i + Vš i - Vš Jistě je zajímavé, že tento výraz plný iracionálních čísel je vždy celočíselný. Uvážíme-li navíc, že (1 — \/5)/2 ~ —0.618, vidíme, že pro všechna přirozená čísla lze F^ snadno spočítat zaokrouhlením čísla i (i+Vš\k Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo oo« oooo Příklad - závěr S využitím počátečních podmínek dostáváme F u = VŠ i + Vš i - Vš Jistě je zajímavé, že tento výraz plný iracionálních čísel je vždy celočíselný. Uvážíme-li navíc, že (1 — VŠ)/2 « —0.618, vidíme, že pro všechna přirozená čísla lze F^ snadno spočítat zaokrouhlením čísla -^g(1+2v/^)/c. Navíc je vidět, že tim^-xx F^i/F^ = A « 1.618, což je poměr známý jako zlatý řez objevuje se již od antiky v architektuře, výtvarném umění i hudbě. At ýrínjJU/ Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo ooo oooo Plán přednášky Q Řešení rekurencí Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí OOOOOOOO OOO «000 Řešení rekurencí Mocninné řady jsou velmi silným nástrojem pro řešení rekurencí (a to nejen lineárních!). Tím je míněno vyjádření členu a^ jako funkci k. Často se s pomocí řad podaří vyřešit na první pohled velmi složité rekurence. &k^ 1^(^U-* ( ty Obvyklý (takřka mechanický) postup pro řešení rekurencí se skládá ze 4 kroků: O Zapíšeme jedinou rovnicí závislost a^ na ostatních členech posloupnosti. Tento vztah musí platit pro všechna k 6 No (předpokládajíce a_i = a_2 = • • • = 0). Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí OOOOOOOO OOO «000 Řešení rekurencí Mocninné řady jsou velmi silným nástrojem pro řešení rekurencí (a to nejen lineárních!). Tím je míněno vyjádření členu ak jako funkci k. Často se s pomocí řad podaří vyřešit na první pohled velmi složité rekurence. Obvyklý (takřka mechanický) postup pro řešení rekurencí se skládá ze 4 kroků: O Zapíšeme jedinou rovnicí závislost ak na ostatních členech posloupnosti. Tento vztah musí platit pro všechna k £ No (předpokládajíce a_i = a_2 = • • • = 0). O Obě strany rovnice vynásobíme xk a sečteme přes všechna k g No- Na jedné straně tak dostaneme J2k>o akxk> c°ž je vytvořující funkce A(x). Pravou stranu vztahu je pak třeba upravit na výraz rovněž obsahující A(x). Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí OOOOOOOO OOO «000 Řešení rekurencí Mocninné řady jsou velmi silným nástrojem pro řešení rekurencí (a to nejen lineárních!). Tím je míněno vyjádření členu a^ jako funkci k. Často se s pomocí řad podaří vyřešit na první pohled velmi složité rekurence. Obvyklý (takřka mechanický) postup pro řešení rekurencí se skládá ze 4 kroků: O Zapíšeme jedinou rovnicí závislost a^ na ostatních členech posloupnosti. Tento vztah musí platit pro všechna k £ No (předpokládajíce a_i = a_2 = • • • = 0). O Obě strany rovnice vynásobíme xk a sečteme přes všechna k g No- Na jedné straně tak dostaneme J2k>o akxk> c°ž je vytvořující funkce A{x). Pravou stranu vztahu je pak třeba upravit na výraz rovněž obsahující A(x). O Zjištěná rovnice se vyřeší vzhledem k A(x). Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí OOOOOOOO OOO «000 Řešení rekurencí Mocninné řady jsou velmi silným nástrojem pro řešení rekurencí (a to nejen lineárních!). Tím je míněno vyjádření členu ak jako funkci k. Často se s pomocí řad podaří vyřešit na první pohled velmi složité rekurence. Obvyklý (takřka mechanický) postup pro řešení rekurencí se skládá ze 4 kroků: O Zapíšeme jedinou rovnicí závislost ak na ostatních členech posloupnosti. Tento vztah musí platit pro všechna k £ No (předpokládajíce a_i = a_2 = • • • = 0). O Obě strany rovnice vynásobíme xk a sečteme přes všechna k g No- Na jedné straně tak dostaneme J2k>o akxk> c°ž je vytvořující funkce A{x). Pravou stranu vztahu je pak třeba upravit na výraz rovněž obsahující A(x). O Zjištěná rovnice se vyřeší vzhledem k A(x). O Výsledné A(x) se rozvine do mocninné řac[y, přičemž koeficient u xk udává ak, tj. ak = \xk]A(x) . n>*^^- f*-*t Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla v Řešení rekurencí oooooooo ooo o«oo Příklad Reste rekurencí 3o = 0, 3i = 1 3k = 5a/c_i - 6ak_2 Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo ooo o«oo r Příklad 1 v Reste rekurenci arj = 0, ai = 1 3k = $ak_i — 6a/c_2 r k'1 * 1 Řešení • Krok 1: = 5a/c_i — 6a/c_2 + [/c = 1]. Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo ooo o«oo Příklad Reste rekurencí 3o = 0, ai = 1 3k = 5a/<_i — 6a/<_2 Řešení • Krok 1: ak = $3k-\ — §ak-2 + [k = 1]. - • Krok 2: >4(x) = 5xA(x) - 6x2-4(x) + x. □ e Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo ooo o«oo Příklad v Reste rekurenci 3q = 0, ai = 1 3k = 5a/c_i — 6a/c_2 Řešení • Krok 1: a/< = 5a/c_i — 6a/<_2 + [/c = 1]. • Krok 2: 4(x) = 5x4(x) - 6x2A(x) + x. • Krok 3: . i v x 1 1 -4(x) = = w 1 - 5x + 6x2 1 - 3x 1 - 2x 1= ^) Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo ooo o«oo Příklad 1 Reste rekurenci 3o = 0, ai = 1 3k = 5a/<_i — 6a/c_2 r- ^ Řešení • Krok 1: = Ďa^-i — §ak-2 + [k = 1]. - • Krok 2: /\(x) = 5x/4(x) - 6x2A(x) + x. • Krok 3: x 1 1 {X)~ l-5x + 6x2 ~ l-3x l-2x" • Krok 4: a* = 3* - 2k. □ e Literatura Vytvořující oooooooo funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla ooo Řešení rekurencí oo«o Quicksort - analýza průměrného případu Ukázka implementace (divide and conquer, rozmyslete, proč není optimální): ifl_ []: return [] retu rn qsort([x for X in L[l:] if x=L[0]]) Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo ooo oo«o Quicksort - analýza průměrného případu Ukázka implementace (divide and conquer, rozmyslete, proč není optimální): ifl_ []: return [] retu rn qsort([x for X in L[l:] if x=L[0]]) O Počet porovnání při rozdělení (divide): k — 1. O (Předpoklad náhodnosti): Pravděpodobnost toho, že prvek L[0] je /-tý největší, je ^. O Velikost tříděných polí ve fázi conquer: i — 1 a k — i. ^iS^ <■€.*■ < -e Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo ooo oo«o Quicksort - analýza průměrného případu Ukázka implementace (divide and conquer, rozmyslete, proč není optimální): if L []: return [] retu rn qsort([x for x in L[l:] if x=L[0]]) O Počet porovnání při rozdělení (divide): k — 1. O (Předpoklad náhodnosti): Pravděpodobnost toho, že prvek L[0] je /-tý největší, je ^. O Velikost tříděných polí ve fázi conquer: i — 1 a k — i. Pro střední hodnotu počtu porovnání tak dostáváme rekurentní vzta h: k 1 Ck = k-l + ^2~ (C/_i + Ck_i). Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo ooo ooo« Analýza Quicksortu pomocí vytvořujících funkcí Vyřešme nyní rekurencí kCk = k{k - 1) + 2 Q-i, Q> = Q = 0 pomocí uvedeného postupu Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo ooo ooo« Analýza Quicksortu pomocí vytvořujících funkcí Vyřešme nyní rekurenci kCk = k(k - 1) + 2 C-i, C0 = Ci = 0 i=i li pomocí uvedeného postupu. £líX) «■ k^Ct" ^^X^^ * • £*>0|*Cfc** = Efc>offi - !)*{ + 2 E/c>o E?=i C/_ixfc Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo ooo ooo« Analýza Quicksortu pomocí vytvořujících funkcí Vyřešme nyní rekurenci k kCk = k(k - 1) + 2 C-i, Q = Ci = 0 i=i pomocí uvedeného postupu. • E/c>o kQxk = £fc>0 k(k - l)xk + 2 Efc>0 Eti d-ixk < □ ► < [3p ► < -e ► < e Literatura Vytvořující funkce rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo ooo ooo« Analýza Quicksortu pomocí vytvořujících funkcí Vyřešme nyní rekurencí k kCk = k(k - 1) + 2 C-i, Q = Q = 0 i=i pomocí uvedeného postupu. • Efc>o kCkxk = E^o k(k - l)xk + 2 E,>0 Eli 0_ixfc .xC'(x) = Ií^ + 2$M • Vyřešíme tuto lineární diferenciální rovnici prvního řádu ((l-x)2C(x))' = ^,atedy (ÍJ C(x) = 7-ttt n--x K ] (1-x)2 V 1-x . odkud konečně Ck = 2(k + l)(Hk+1 - 1) - 2k.