Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo OOOOO oooo Matematika IV - 9. týden Vytvořující funkce podruhé Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2017 □ g Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo ooooo oooo Obsah přednášky Q Vytvořující funkce a Fibonacciho čísla Q Vytvořující funkce - připomenutí Q Řešení rekurencí Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo ooooo 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. □ g = Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo ooooo 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 a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo ooooo oooo Plán prednášky Q Vytvořující funkce a Fibonacciho čísla Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí •oooo ooooo oooo Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fq = 0, Fi = 1, Fn+2 = Fn+i + 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 r?-tého členu posloupnosti. Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí •oooo ooooo oooo Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fq = 0, Fi = 1, Fn+2 = Fn+i + 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 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ř. [n = l],[2|n] apod. Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí •oooo ooooo oooo Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fq = 0, Fi = 1, Fn+2 = Fn+i + 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 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ř. [n = l],[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 Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí o«ooo ooooo oooo Fibonacciho čísla pomocí vytvořující funkce 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 F(x) = T X — x — X Našim cílem je tedy odvodit vztah pro n-tý člen posloupnosti Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí o«ooo ooooo oooo Fibonacciho čísla pomocí vytvořující funkce Uvažme vytvořující funkci F(x) Fibonacciho posloupnosti. Při podmínkách Fo = 0, F\ — 1 je to F(x) — xF(x) — x2F(x) = x, a tedy X ^2 ' — x — X Našim cílem je tedy odvodit vztah pro r?-tý člen posloupnosti Využijeme k tomu rozklad na parciální zlomky a dostaneme x A B -+-, 1 — X — X2 X — Xi X — X2 kde xi,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 Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí o«ooo ooooo oooo Fibonacciho čísla pomocí vytvořující funkce Uvažme vytvořující funkci F(x) Fibonacciho posloupnosti. Při podmínkách Fo = 0, F\ — 1 je to F(x) — xF(x) — x2F(x) = x, a tedy X ^2 ' — x — X Našim cílem je tedy odvodit vztah pro r?-tý člen posloupnosti Využijeme k tomu rozklad na parciální zlomky a dostaneme x A B -+-, 1 — X — X2 X — Xi X — X2 kde xi,X2 jsou kořeny polynomu 1 — x — x2 a A, B vhodné konstanty odvozené z počátečních podmínek. Po substituci Ai = 1/xi, A2 = I/X2 dostáváme vztah x a b + 1 — x — x2 1 — Ajx 1 — A2X odkud už vcelku snadno vyjde Fn = a • \" + b • Aí>, jak to známe z dřívějška. n ^^t^t> Literatura Vytvořující funkce a Fibonacci ho čísla oo»oo Příklad - závěr Vytvořující funkce ooooo připomenutí Řešení rekurencí oooo S využitím počátečních podmínek dostáváme Fn = í + Vš n i - Vš n-i Jistě je zajímavé, že tento výraz plný iracionálních čísel je vždy celočíselný. Literatura Vytvořující funkce a Fibonacci ho čísla oo»oo Příklad - závěr Vytvořující funkce OOOOO připomenutí Řešení rekurencí oooo S využitím počátečních podmínek dostáváme Fn = 1 + VŠ n 1 - 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 Fn snadno spočítat zaokrouhlením čísla Literatura Vytvořující funkce a Fibonacci ho čísla oo»oo Příklad - závěr Vytvořující funkce OOOOO připomenutí Řešení rekurencí oooo S využitím počátečních podmínek dostáváme Fn = 1 + VŠ n 1 - 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 Fn snadno spočítat zaokrouhlením čísla -^(^fi)"- Navíc je vidět, že lim,,-^ Fn/Fn+1 = 1/Ai « 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í oooto ooooo oooo 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 /c-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í, nyní 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í oooto ooooo oooo 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 /c-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í, nyní 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. o Polynom Q(x) rozložíme na kořenové činitele. Literatura Vytvořující funkce a Fibonacci ho čísla oooto Vytvořující funkce - připomenutí ooooo Řešení rekurencí oooo Analogický postup je možné použít při řešení obecných lineárních diferenčních rovnic /c-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í, nyní 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. o Polynom Q(x) rozložíme na kořenové činitele. • Jsou-li všechny kořeny cti, • • •, &i jednoduché, pak P(x) A1 + + Q{X) x - «1 x — a£ Literatura Vytvořující funkce a Fibonacci ho čísla oooto Vytvořující funkce - připomenutí OOOOO Řešení rekurencí oooo Analogický postup je možné použít při řešení obecných lineárních diferenčních rovnic /c-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í, nyní 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. o Polynom Q(x) rozložíme na kořenové činitele. • Jsou-li všechny kořeny cti, • • •, &i jednoduché, pak • Má-li kořen a násobnost k, pak jsou příslušné parciální zlomky tvaru P(x) A1 +----h At Q{X) x - «i x — au Ai A2 + ■■■ + Ak (x — a) (x — a) (x — a) Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí oooo* ooooo oooo Rozklad na parciální zlomky - pokr. V případě dvojice komplexně sdružených kořenů nahrazujeme sčítanec A/[x — a) sčítancem (Ax + 6)/(x2 + px + q) včetně příslušných mocnin jmenovatele. Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí oooo* ooooo oooo Rozklad na parciální zlomky - pokr. V případě dvojice komplexně sdružených kořenů nahrazujeme sčítanec A/[x — a) sčítancem (Ax + 6)/(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 Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí oooo* ooooo oooo Rozklad na parciální zlomky - pokr. <* V případě dvojice komplexně sdružených kořenů nahrazujeme sčítanec A/[x — a) sčítancem (Ax + 6)/(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 — 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 mocninné řady. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo ooooo oooo Plán prednášky Q Vytvořující funkce - připomenutí Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo •oooo oooo Definice Buď dána nekonečná posloupnost a = (ao, ai, a2,.. .)■ JeJí vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru oo a,x' = a0 + aix + a2x2 H----. i=0 Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo o«ooo oooo Kromě výše zmíněných vytvořujících funkcí se v praxi rovněž často objevují jejich tzv. exponenciálníVarianty1. xn n\ n>0 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í ooooo o«ooo oooo Kromě výše zmíněných vytvořujících funkcí se v praxi rovněž často objevují jejich tzv. exponenciálníVarianty1. x n n>0 n\ Poznámka 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,...). 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 Fibonacci ho čísla ooooo Vytvořující funkce - připomenutí oo«oo Řešení rekurencí oooo Věta z elementárního diferenciálního počtu: Věta Buď (ao, ai, a2,...) posloupnost reálných čísel. Platí-li pro nějaké K G K, že pro všechna n > 1 je \an\ < Kn, pak rada a(x)= ^2anX" n>0 konverguje pro každé x G (—^, 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 Fibonacci ho čísla ooooo Vytvořující funkce - připomenutí oo«oo Řešení rekurencí oooo Věta z elementárního diferenciálního počtu: Věta Buď (ao, ai, a2,...) posloupnost reálných čísel. Platí-li pro nějaké K G IR, že pro všechna n > 1 je \an\ < Kn, pak rada a(x)= ^2 a»x" n>0 konverguje pro každé x £ (—^, 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, nebot má a(x) v 0 derivace všech řádů a platí a(")(0) Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo OOO0O oooo 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í ooooo OOO0O oooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (a; + b i) 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 Fibonacci ho čísla ooooo Vytvořující funkce - připomenutí OOO0O Řešení rekurencí oooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (a; + bj) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. • Vynásobení {a • a,) všech členů posloupnosti stejným skalárem a odpovídá vynásobení a • a(x) příslušné vytvořující funkce. Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo OOO0O oooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (a; + bj) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. • Vynásobení {a • a,) všech členů posloupnosti stejným skalárem a odpovídá vynásobení a • a(x) příslušné vytvořující funkce. o 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 Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo OOO0O oooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (a; + bj) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. • Vynásobení {a • a,) všech členů posloupnosti stejným skalárem a odpovídá vynásobení a • a(x) příslušné vytvořující funkce. o Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami. 9 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 (ao,..., 3k-i, 0,...) a poté podělíme vytvořující funkci xk. -írnJ^ < >• e O Q, O Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo OOO0O oooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (a; + bj) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. • Vynásobení {a • a,-) všech členů posloupnosti stejným skalárem a odpovídá vynásobení a • a(x) příslušné vytvořující funkce. o Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami. 9 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 (ao,..., 3k-i, 0,...) a poté podělíme vytvořující funkci xk. 9 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) — ax, což odpovídá vynásobení /c-tého členu posloupnosti skalárem ak. 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í ooooo OOOO* oooo Dalšími důležitými operacemi, které se při práci s vytvořujícími funkcemi často objevují, jsou: o Derivování podle x: funkce a'(x) vytvořuje posloupnost (ai, 2a2, 3a3,...), člen s indexem k je (k + l)ak+i (tj. mocninnou řadu derivujeme člen po členu). Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí OOOO* Řešení rekurencí oooo Dalšími důležitými operacemi, které se při práci s vytvořujícími funkcemi často objevují, jsou: o Derivování podle x: funkce a'(x) vytvořuje posloupnost (ai, 2a2, 3a3,...), člen s indexem k je (k + l)ak+i (tj. mocninnou řadu derivujeme člen po členu). • Integrování: funkce JQX a(ř) dt vytvořuje posloupnost (0, ao, |ai, |a2, ^3,...), pro /c > 1 je člen s indexem k roven \dk-\ (zřejmě je derivací příslušné mocninné řady člen po členu původní funkce a(x)). Literatura Vytvořující funkce a Fibonacci ho čísla ooooo Vytvořující funkce - připomenutí oooo* Řešení rekurencí oooo Dalšími důležitými operacemi, které se při práci s vytvořujícími funkcemi často objevují, jsou: o Derivování podle x: funkce a'(x) vytvořuje posloupnost (ai, 2a2, 3a3,...), člen s indexem k je (k + l)ak+i (tj. mocninnou řadu derivujeme člen po členu). • Integrování: funkce JQX a(t) dt vytvořuje posloupnost (0, ao, |ai, |a2, ^3,...), pro /c > 1 je člen s indexem k roven \dk-\ (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 (cq, ci, c2,...), kde tj. členy v součinu až po jsou stejné jako v součinu (a0 + aix + a2x2 H-----h a/cx/c)(b0 + bix + b2x2 H----b*x*). Posloupnost (cn) bývá také nazývána konvolucíposloupností i+j=k Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí OOOOO Řešení rekurencí oooo Plán prednášky \S m s / Q Řešení rekurencí Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí OOOOO OOOOO «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 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ů: O Zapíšeme jedinou rovnicí závislost an na ostatních členech posloupnosti. Tento vztah musí platit pro všechna n 6 No (předpokládáme a_i = a_2 = • • • = 0). Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí OOOOO OOOOO «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 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ů: O Zapíšeme jedinou rovnicí závislost an na ostatních členech posloupnosti. Tento vztah musí platit pro všechna n £ No (předpokládáme a_i = a_2 = • • • = 0). O Obě strany rovnice vynásobíme xn a sečteme přes všechna n G No- Na jedné straně tak dostaneme J2n anxtl, c°z 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 Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo OOOOO •ooo Ř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ů: O Zapíšeme jedinou rovnicí závislost an na ostatních členech posloupnosti. Tento vztah musí platit pro všechna n £ No (předpokládáme a_i = a_2 = • • • = 0). O Obě strany rovnice vynásobíme xn a sečteme přes všechna n G No- Na jedné straně tak dostaneme J2n anxtl, c°z je vytvořující funkce A(x). Pravou stranu vztahu je pak třeba upravit na výraz rovněž obsahující A(x). Q Zjištěná rovnice se vyřeší vzhledem k A(x). -írnJ^ < ^ > ^ O Q, O Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo OOOOO •ooo Ř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ů: O Zapíšeme jedinou rovnicí závislost an na ostatních členech posloupnosti. Tento vztah musí platit pro všechna n £ No (předpokládáme a_i = a_2 = • • • = 0). O Obě strany rovnice vynásobíme xn a sečteme přes všechna n G No- Na jedné straně tak dostaneme J2n anxtl, c°z je vytvořující funkce A{x). Pravou stranu vztahu je pak třeba upravit na výraz rovněž obsahující A(x). Q Zjištěná rovnice se vyřeší vzhledem k A(x). O Výsledné A{x) se rozvine do mocninné řady, přičemž koeficient u xn udává an, tj. an = [xnl/4(x) . Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo OOOOO o«oo Příklad Reste rekurenci 3o = 0, ai = 1 3n = 5an_i — 6an_2 Literatura Vytvořující funkce a Fibonacci ho čísla ooooo Vytvořující funkce - připomenutí OOOOO Řešení rekurencí o«oo Příklad Řešte rekurenci 3o = 0, ai = 1 3n = 5an_i — 6an_2 Řešení • Krok 1: an = 5an_i — 6an_2 + [n = 1]. Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí OOOOO OOOOO o«oo Příklad ■v Reste rekurencí 3o = 0, ai = 1 3n = 5an_i — 6an_2 ■v Řešení • Krok 1: an = 5an_i — 6a„_2 + [n = 1]. • Krok 2: A(x) = 5xA(x) - 6x2A(x) + x. Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí OOOOO Řešení rekurencí o«oo Příklad Řešte rekurenci 3o = 0, ai = 1 3n = 5an_i — 6an_2 Řešení • Krok 1: an = 5an_i — 6an_2 + [n = 1]. • Krok 2: /4(x) = 5x/l(x) - 6x2A(x) + x. • Krok 3: A(x) = x 1 - 5x + 6x2 1 - 3x 1 - 2x >0 Q,o Literatura Vytvořující funkce a Fibonacci ho čísla ooooo Vytvořující funkce - připomenutí OOOOO Řešení rekurencí o«oo Příklad Řešte rekurenci 3o = 0, ai = 1 3n = 5an_i — 6an_2 Řešení • Krok 1: an = 5an_i — 6an_2 + [n = 1]. • Krok 2: /4(x) = 5x/l(x) - 6x2A(x) + x. • Krok 3: A(x) = x 1 - 5x + 6x2 1 - 3x 1 - 2x • Krok 4: a„ = 3" - 2". >0 0,0 Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo ooooo oo«o Quicksort - analýza průměrného případu Ukázka implementace (divide and conquer, rozmyslete, proč není optimální): ifL []: return [] return qsort([x for x i n L[l:] if x=L[0]]) Literatura Vytvořující funkce a Fibonacci ho čísla ooooo Vytvořující funkce - připomenutí OOOOO Ř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í): if L []: return [] return qsort([x for x i n L[l:] if x=L[0]]) Počet porovnání při rozdělení {dividé): n — 1. O (Předpoklad náhodnosti): Pravděpodobnost toho, že prvek L[0] je /c-tý největší, je ^. Q 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í ooooo ooooo 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 [] return qsort([x for x i n L[l:] if x=L[0]]) Počet porovnání při rozdělení {dividé): n — 1. O (Předpoklad náhodnosti): Pravděpodobnost toho, že prvek L[0] je /c-tý největší, je ^. O 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: n 1 Cn = n-l + y^ - (Cfr_i + Cn-k). n Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo ooooo ooo« Analýza Quicksortu pomocí vytvořujících funkcí Vyřešme nyní rekurenci n nCn = n(n - 1) + 2 ^ Ck-i, C0 = Ci = 0 k=l pomocí uvedeného postupu. Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo ooooo ooo« Analýza Quicksortu pomocí vytvořujících funkcí Vyřešme nyní rekurencí n nCn = n(n - 1) + 2 ^ C0 = Ci = 0 k=l pomocí uvedeného postupu. • E„>0 nC"x" = £„>0 ~ 1)x" + 2 En>0 Efc=l Ck Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí OOOOO OOOOO ooo« Analýza Quicksortu pomocí vytvořujících funkcí Vyřešme nyní rekurencí n nCn = n(n - 1) + 2 ^ Ck-i, C0 = Cľ = 0 k=l pomocí uvedeného postupu En>0 nCnx" = En>0 ~ l)x" + 2 ľn>0 ELl ^ „r'f~\ — 2x2 , oxCW Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo ooooo ooo« Analýza Quicksortu pomocí vytvořujících funkcí Vyřešme nyní rekurenci n nCn = n(n - 1) + 2 ^ C0 = Ci = 0 k=l pomocí uvedeného postupu. • E„>o nC"x" = £„>o ~ 1)x" + 2 En>o ELi ck-ix" • xC(x) =(^ + 2^1 a Vyřešíme tuto lineární diferenciální rovnici prvního řádu ((l-x)2C(x))' = I^, Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo ooooo ooo« Analýza Quicksortu pomocí vytvořujících funkcí Vyřešme nyní rekurenci n nCn = n(n - 1) + 2 ^ C0 = Ci = 0 k=l pomocí uvedeného postupu. • E„>o nC"x" = £„>o ~ 1)x" + 2 En>o ELi ck-ix" • xC(x) =(^ + 2^1 a Vyřešíme tuto lineární diferenciální rovnici prvního řádu ((l-x)2C(x))' = I^, Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo ooooo ooo« Analýza Quicksortu pomocí vytvořujících funkcí Vyřešme nyní rekurenci n nCn = n(n - 1) + 2 ^ C0 = Ci = 0 k=l pomocí uvedeného postupu. • E„>o nC"x" = £„>o ~ 1)x" + 2 En>o ELi ck-ix" • xC(x) =(^ + 2^1 a Vyřešíme tuto lineární diferenciální rovnici prvního řádu ((1-x)2C(x))' = £l a tedy Literatura Vytvořující funkce a Fibonacci ho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo ooooo ooo« Analýza Quicksortu pomocí vytvořujících funkcí Vyřešme nyní rekurencí n nCn = n(n - 1) + 2 ^ C0 = Ci = 0 k=l pomocí uvedeného postupu. • E„>o nC"x" = £„>o ~ 1)x" + 2 En>o ELi ck-ix" • xC(x) =(^ + 2^1 a Vyřešíme tuto lineární diferenciální rovnici prvního řádu ((1-x)2C(x))' = £l a tedy C(x) = (1 - x): In 1 - x — x odkud konečně Cn = 2(n + l)(Hn+i — 1) — 2n.