Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Matematika IV – 9. týden Vytvořující funkce Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2015 Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Obsah přednášky 1 Vytvořující funkce a Fibonacciho čísla 2 Vytvořující funkce - připomenutí 3 Řešení rekurencí Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí 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. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí 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 a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Plán přednášky 1 Vytvořující funkce a Fibonacciho čísla 2 Vytvořující funkce - připomenutí 3 Řešení rekurencí Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn. 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 n-tého členu posloupnosti. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn. 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 n-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ř. [n = 1], [2|n] apod. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn. 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 n-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ř. [n = 1], [2|n] apod. Pro vyjádření koeficientu u xn ve vytvořující funkci F(x) se pak často používá zápis [xn]F(x). Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Příklad – pokr. Uvažme vytvořující funkci F(x) Fibonacciho posloupnosti. Při podmínkách F0 = 0, F1 = 1 je to F(x) − xF(x) − x2F(x) = x, a tedy F(x) = x 1 − x − x2 . Našim cílem je tedy odvodit vztah pro n-tý člen posloupnosti. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Příklad – pokr. Uvažme vytvořující funkci F(x) Fibonacciho posloupnosti. Při podmínkách F0 = 0, F1 = 1 je to F(x) − xF(x) − x2F(x) = x, a tedy F(x) = x 1 − x − x2 . Našim cílem je tedy odvodit vztah pro n-tý člen posloupnosti. Využijeme k tomu rozklad na parciální zlomky a dostaneme x 1 − x − x2 = A x − x1 + B x − x2 , kde x1, x2 jsou kořeny polynomu 1 − x − x2 a A, B vhodné konstanty odvozené z počátečních podmínek. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Příklad – pokr. Uvažme vytvořující funkci F(x) Fibonacciho posloupnosti. Při podmínkách F0 = 0, F1 = 1 je to F(x) − xF(x) − x2F(x) = x, a tedy F(x) = x 1 − x − x2 . Našim cílem je tedy odvodit vztah pro n-tý člen posloupnosti. Využijeme k tomu rozklad na parciální zlomky a dostaneme x 1 − x − x2 = A x − x1 + B x − x2 , kde x1, x2 jsou kořeny polynomu 1 − x − x2 a A, B vhodné konstanty odvozené z počátečních podmínek. Po substituci λ1 = 1/x1, λ2 = 1/x2 dostáváme vztah x 1 − x − x2 = a 1 − λ1x + b 1 − λ2x , odkud už vcelku snadno vyjde Fn = a · λn 1 + b · λn 2, jak to známe z dřívějška. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Příklad – závěr S využitím počátečních podmínek dostáváme Fn = 1 √ 5 1 + √ 5 2 n − 1 − √ 5 2 n . Jistě je zajímavé, že tento výraz plný iracionálních čísel je vždy celočíselný. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Příklad – závěr S využitím počátečních podmínek dostáváme Fn = 1 √ 5 1 + √ 5 2 n − 1 − √ 5 2 n . 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 Fn snadno spočítat zaokrouhlením čísla 1√ 5 (1+ √ 5 2 )n. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Příklad – závěr S využitím počátečních podmínek dostáváme Fn = 1 √ 5 1 + √ 5 2 n − 1 − √ 5 2 n . 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 Fn snadno spočítat zaokrouhlením čísla 1√ 5 (1+ √ 5 2 )n. Navíc je vidět, že limn→∞ Fn/Fn+1 = 1/λ1 ≈ 0.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ě. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Rozklad na parciální zlomky – připomenutí Analogický postup je možné použít při řešení obecných lineárních diferenčních rovnic k-tého stupně s konstatními koeficienty. Má-li charakteristická rovnice jednoduché kořeny pomůže vždy jednoduchý rozklad na parciální zlomky. Ten 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 st P < st Q (jinak vydělíme se zbytkem) a P(x), Q(x) nemají společné kořeny. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Rozklad na parciální zlomky – připomenutí Analogický postup je možné použít při řešení obecných lineárních diferenčních rovnic k-tého stupně s konstatními koeficienty. Má-li charakteristická rovnice jednoduché kořeny pomůže vždy jednoduchý rozklad na parciální zlomky. Ten 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 st P < st Q (jinak vydělíme se zbytkem) a P(x), Q(x) nemají společné kořeny. Polynom Q(x) rozložíme na kořenové činitele. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Rozklad na parciální zlomky – připomenutí Analogický postup je možné použít při řešení obecných lineárních diferenčních rovnic k-tého stupně s konstatními koeficienty. Má-li charakteristická rovnice jednoduché kořeny pomůže vždy jednoduchý rozklad na parciální zlomky. Ten 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 st P < st Q (jinak vydělíme se zbytkem) a P(x), Q(x) nemají společné kořeny. Polynom Q(x) rozložíme na kořenové činitele. Jsou-li všechny kořeny α1, . . . , α jednoduché, pak P(x) Q(X) = A1 x − α1 + · · · + A x − α . Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Rozklad na parciální zlomky – připomenutí Analogický postup je možné použít při řešení obecných lineárních diferenčních rovnic k-tého stupně s konstatními koeficienty. Má-li charakteristická rovnice jednoduché kořeny pomůže vždy jednoduchý rozklad na parciální zlomky. Ten 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 st P < st Q (jinak vydělíme se zbytkem) a P(x), Q(x) nemají společné kořeny. Polynom Q(x) rozložíme na kořenové činitele. Jsou-li všechny kořeny α1, . . . , α jednoduché, pak P(x) Q(X) = A1 x − α1 + · · · + A x − α . Má-li kořen α násobnost k, pak jsou příslušné parciální zlomky tvaru A1 (x − α) + A2 (x − α)2 + · · · + Ak (x − α)k . Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Rozklad na parciální zlomky – pokr. V případě dvojice komplexně sdružených kořenů nahrazujeme sčitanec A/(x − α) sčítancem (Ax + B)/(x2 + px + q) včetně příslušných mocnin jmenovatele. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Rozklad na parciální zlomky – pokr. V případě dvojice komplexně sdružených kořenů nahrazujeme sčitanec A/(x − α) sčítancem (Ax + B)/(x2 + px + q) včetně příslušných mocnin jmenovatele. Neznámé dopočítáme buď roznásobením a porovnáním koeficientů u jednotlivých mocnin x nebo dosazením jednotlivých kořenů. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Rozklad na parciální zlomky – pokr. V případě dvojice komplexně sdružených kořenů nahrazujeme sčitanec A/(x − α) sčítancem (Ax + B)/(x2 + px + q) včetně příslušných mocnin jmenovatele. Neznámé dopočítáme buď roznásobením a porovnáním koeficientů u jednotlivých mocnin x nebo dosazením jednotlivých kořenů. Výrazy A/(x − α)k převedeme na výrazy tvaru B/(1 − βx)k vydělením čitatele i jmenovatele výrazem (−α)k. Tento výraz již umíme rozvinout do mocninné řady. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Plán přednášky 1 Vytvořující funkce a Fibonacciho čísla 2 Vytvořující funkce - připomenutí 3 Řešení rekurencí Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Definice Buď dána nekonečná posloupnost a = (a0, a1, a2, . . .). Její vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru ∞ i=0 ai xi = a0 + a1x + a2x2 + · · · . Kromě výše zmíněných vytvořujících funkcí se v praxi rovněž často objevují jejich tzv. exponenciální varianty1. g(x) = n≥0 gn xn n! . 1 Používají se i další typy vytvořujících funkcí (např. v teorii čísel se používají Dirichletovy vytvořující funkce, kde roli faktoru xn hraje n−x ), ale těmi se zde zabývat nebudeme. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Definice Buď dána nekonečná posloupnost a = (a0, a1, a2, . . .). Její vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru ∞ i=0 ai xi = a0 + a1x + a2x2 + · · · . Kromě výše zmíněných vytvořujících funkcí se v praxi rovněž často objevují jejich tzv. exponenciální varianty1. g(x) = n≥0 gn xn n! . Jméno vychází z toho, že exponenciální funkce ex je (exponenciální) vytvořující funkcí pro základní posloupnost (1, 1, 1, 1, . . . ). 1 Používají se i další typy vytvořujících funkcí (např. v teorii čísel se používají Dirichletovy vytvořující funkce, kde roli faktoru xn hraje n−x ), ale těmi se zde zabývat nebudeme. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Věta z matematické analýzy: Věta Buď (a0, a1, a2, . . . ) posloupnost reálných čísel. Platí-li pro nějaké K ∈ R, že pro všechna n ≥ 1 je |an| ≤ Kn, pak řada a(x) = n≥0 anxn konverguje pro každé x ∈ (− 1 K , 1 K ). Součet této řady tedy definuje funkci na uvedeném intervalu, tuto funkci označujeme rovněž a(x). Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Věta z matematické analýzy: Věta Buď (a0, a1, a2, . . . ) posloupnost reálných čísel. Platí-li pro nějaké K ∈ R, že pro všechna n ≥ 1 je |an| ≤ Kn, pak řada a(x) = n≥0 anxn konverguje pro každé x ∈ (− 1 K , 1 K ). 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í an = a(n)(0) n! . Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: Sčítání (ai + bi ) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: Sčítání (ai + bi ) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. Vynásobení (α · ai ) všech členů posloupnosti stejným skalárem α odpovídá vynásobení α · a(x) příslušné vytvořující funkce. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: Sčítání (ai + bi ) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. Vynásobení (α · ai ) všech členů posloupnosti stejným skalárem α odpovídá vynásobení α · a(x) příslušné vytvořující funkce. Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: Sčítání (ai + bi ) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. Vynásobení (α · ai ) všech členů posloupnosti stejným skalárem α odpovídá vynásobení α · a(x) příslušné vytvořující funkce. Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami. Pro posunutí posloupnosti doleva o k míst (tj. vynechání prvních k míst posloupnosti) nejprve od a(x) odečteme polynom bk(x) odpovídají posloupnosti (a0, . . . , ak−1, 0, . . . ) a poté podělíme vytvořující funkci xk. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: Sčítání (ai + bi ) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. Vynásobení (α · ai ) všech členů posloupnosti stejným skalárem α odpovídá vynásobení α · a(x) příslušné vytvořující funkce. Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami. Pro posunutí posloupnosti doleva o k míst (tj. vynechání prvních k míst posloupnosti) nejprve od a(x) odečteme polynom bk(x) odpovídají posloupnosti (a0, . . . , ak−1, 0, . . . ) a poté podělíme vytvořující funkci xk. Substitucí polynomu f (x) s nulovým absolutním členem za x vytvoříme specifické kombinace členů původní posloupnosti. Jednoduše je vyjádříme pro f (x) = αx, což odpovídá vynásobení k–tého členu posloupnosti skalárem αk. Dosazení f (x) = xn nám do posloupnosti mezi každé dva členy vloží n − 1 nul. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Dalšími důležitými operacemi, které se při práci s vytvořujícími funkcemi často objevují, jsou: Derivování podle x: funkce a (x) vytvořuje posloupnost (a1, 2a2, 3a3, . . . ), člen s indexem k je (k + 1)ak+1 (tj. mocninnou řadu derivujeme člen po členu). Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Dalšími důležitými operacemi, které se při práci s vytvořujícími funkcemi často objevují, jsou: Derivování podle x: funkce a (x) vytvořuje posloupnost (a1, 2a2, 3a3, . . . ), člen s indexem k je (k + 1)ak+1 (tj. mocninnou řadu derivujeme člen po členu). Integrování: funkce x 0 a(t) dt vytvořuje posloupnost (0, a0, 1 2a1, 1 3 a2, 1 4 a3, . . . ), pro k ≥ 1 je člen s indexem k roven 1 k ak−1 (zřejmě je derivací příslušné mocninné řady člen po členu původní funkce a(x)). Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Dalšími důležitými operacemi, které se při práci s vytvořujícími funkcemi často objevují, jsou: Derivování podle x: funkce a (x) vytvořuje posloupnost (a1, 2a2, 3a3, . . . ), člen s indexem k je (k + 1)ak+1 (tj. mocninnou řadu derivujeme člen po členu). Integrování: funkce x 0 a(t) dt vytvořuje posloupnost (0, a0, 1 2a1, 1 3 a2, 1 4 a3, . . . ), pro k ≥ 1 je člen s indexem k roven 1 k ak−1 (zřejmě je derivací příslušné mocninné řady člen po členu původní funkce a(x)). Násobení řad: součin a(x)b(x) je vytvořující funkcí posloupnosti (c0, c1, c2, . . . ), kde ck = i+j=k ai bj , tj. členy v součinu až po ck jsou stejné jako v součinu (a0 + a1x + a2x2 + · · · + akxk)(b0 + b1x + b2x2 + · · · bkxk). Posloupnost (cn) bývá také nazývána konvolucí posloupností (an), (bn). Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Plán přednášky 1 Vytvořující funkce a Fibonacciho čísla 2 Vytvořující funkce - připomenutí 3 Řešení rekurencí Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Ř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 an jako funkci n. Č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ů: 1 Zapíšeme jedinou rovnicí závislost an na ostatních členech posloupnosti. Tento vztah musí platit pro všechna n ∈ N0 (předpokládajíce a−1 = a−2 = · · · = 0). Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Ř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 an jako funkci n. Č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ů: 1 Zapíšeme jedinou rovnicí závislost an na ostatních členech posloupnosti. Tento vztah musí platit pro všechna n ∈ N0 (předpokládajíce a−1 = a−2 = · · · = 0). 2 Obě strany rovnice vynásobíme xn a sečteme přes všechna n ∈ N0. Na jedné straně tak dostaneme n anxn, což 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 a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Ř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 an jako funkci n. Č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ů: 1 Zapíšeme jedinou rovnicí závislost an na ostatních členech posloupnosti. Tento vztah musí platit pro všechna n ∈ N0 (předpokládajíce a−1 = a−2 = · · · = 0). 2 Obě strany rovnice vynásobíme xn a sečteme přes všechna n ∈ N0. Na jedné straně tak dostaneme n anxn, což je vytvořující funkce A(x). Pravou stranu vztahu je pak třeba upravit na výraz rovněž obsahující A(x). 3 Zjištěná rovnice se vyřeší vzhledem k A(x). Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Ř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 an jako funkci n. Č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ů: 1 Zapíšeme jedinou rovnicí závislost an na ostatních členech posloupnosti. Tento vztah musí platit pro všechna n ∈ N0 (předpokládajíce a−1 = a−2 = · · · = 0). 2 Obě strany rovnice vynásobíme xn a sečteme přes všechna n ∈ N0. Na jedné straně tak dostaneme n anxn, což je vytvořující funkce A(x). Pravou stranu vztahu je pak třeba upravit na výraz rovněž obsahující A(x). 3 Zjištěná rovnice se vyřeší vzhledem k A(x). 4 Výsledné A(x) se rozvine do mocninné řady, přičemž koeficient u xn udává an, tj. an = [xn]A(x) . Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Příklad Řešte rekurenci a0 = 0, a1 = 1 an = 5an−1 − 6an−2 Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Příklad Řešte rekurenci a0 = 0, a1 = 1 an = 5an−1 − 6an−2 Řešení Krok 1: an = 5an−1 − 6an−2 + [n = 1]. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Příklad Řešte rekurenci a0 = 0, a1 = 1 an = 5an−1 − 6an−2 Řešení Krok 1: an = 5an−1 − 6an−2 + [n = 1]. Krok 2: A(x) = 5xA(x) − 6x2A(x) + x. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Příklad Řešte rekurenci a0 = 0, a1 = 1 an = 5an−1 − 6an−2 Řešení Krok 1: an = 5an−1 − 6an−2 + [n = 1]. Krok 2: A(x) = 5xA(x) − 6x2A(x) + x. Krok 3: A(x) = x 1 − 5x + 6x2 = 1 1 − 3x − 1 1 − 2x . Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Příklad Řešte rekurenci a0 = 0, a1 = 1 an = 5an−1 − 6an−2 Řešení Krok 1: an = 5an−1 − 6an−2 + [n = 1]. Krok 2: A(x) = 5xA(x) − 6x2A(x) + x. Krok 3: A(x) = x 1 − 5x + 6x2 = 1 1 − 3x − 1 1 − 2x . Krok 4: an = 3n − 2n. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Quicksort – analýza průměrného případu Ukázka implementace (divide and conquer, rozmyslete, proč není optimální): i f L == [ ] : r e t u r n [ ] r e t u r n qsort ( [ x f o r x in L [ 1 : ] i f x=L [ 0 ] ] ) Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Quicksort – analýza průměrného případu Ukázka implementace (divide and conquer, rozmyslete, proč není optimální): i f L == [ ] : r e t u r n [ ] r e t u r n qsort ( [ x f o r x in L [ 1 : ] i f x=L [ 0 ] ] ) 1 Počet porovnání při rozdělení (divide): n − 1. 2 (Předpoklad náhodnosti): Pravděpodobnost toho, že prvek L[0] je k-tý největší, je 1 n . 3 Velikost tříděných polí ve fázi conquer: k − 1 a n − k. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Quicksort – analýza průměrného případu Ukázka implementace (divide and conquer, rozmyslete, proč není optimální): i f L == [ ] : r e t u r n [ ] r e t u r n qsort ( [ x f o r x in L [ 1 : ] i f x=L [ 0 ] ] ) 1 Počet porovnání při rozdělení (divide): n − 1. 2 (Předpoklad náhodnosti): Pravděpodobnost toho, že prvek L[0] je k-tý největší, je 1 n . 3 Velikost tříděných polí ve fázi conquer: k − 1 a n − k. Pro střední hodnotu počtu porovnání tak dostáváme rekurentní vztah: Cn = n − 1 + n k=1 1 n (Ck−1 + Cn−k) . Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Analýza Quicksortu pomocí vytvořujících funkcí Vyřešme nyní rekurenci nCn = n(n − 1) + 2 n k=1 Ck−1, C0 = C1 = 0 pomocí uvedeného postupu. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Analýza Quicksortu pomocí vytvořujících funkcí Vyřešme nyní rekurenci nCn = n(n − 1) + 2 n k=1 Ck−1, C0 = C1 = 0 pomocí uvedeného postupu. n≥0 nCnxn = n≥0 n(n − 1)xn + 2 n≥0 n k=1 Ck−1xn Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Analýza Quicksortu pomocí vytvořujících funkcí Vyřešme nyní rekurenci nCn = n(n − 1) + 2 n k=1 Ck−1, C0 = C1 = 0 pomocí uvedeného postupu. n≥0 nCnxn = n≥0 n(n − 1)xn + 2 n≥0 n k=1 Ck−1xn xC (x) = 2x2 (1−x)3 + 2xC(x) 1−x Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí Analýza Quicksortu pomocí vytvořujících funkcí Vyřešme nyní rekurenci nCn = n(n − 1) + 2 n k=1 Ck−1, C0 = C1 = 0 pomocí uvedeného postupu. n≥0 nCnxn = n≥0 n(n − 1)xn + 2 n≥0 n k=1 Ck−1xn xC (x) = 2x2 (1−x)3 + 2xC(x) 1−x Vyřešíme tuto lineární diferenciální rovnici prvního řádu (1 − x)2C(x) = 2x 1−x , a tedy C(x) = 2 (1 − x)2 ln 1 1 − x − x , odkud konečně Cn = 2(n + 1)(Hn+1 − 1) − 2n.