Diskrétní matematika - 11. týden Vytvořující funkce a re k u re n ce jrencí Lukáš Vokřínek Masarykova univerzita Fakulta 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í 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. o Donald E. Knuth, The Art Of Computer Programmi • 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 Řešení rekurencí •ooooooo ooo oooo (Formální) mocninné řady 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 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) " k\ 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 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. • Xn -J2akXk = ^ak-nXk. • (EakXk)-(EbkXk) = Eckxk, kde Qk = 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 Ř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. 9 Polynom Q(x) rozložíme na kořenové činitele. • Jsou-li všechny kořeny cti,... ,ct£ jednoduché, pak P(x) Q(X) A! x — ai + ••• + A í X — OLU • Má-li kořen a násobnost k, pak jsou příslušné parciální zlomky tvaru Ai A2 Ak + (x — a) (x — a)2 + ••• + (x — a)k 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 mocninné řady. 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 + 6i = (l-2i)(l-3i) 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. 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, F* = 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). Literatura Vytvořující funkce, rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo omo 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 F(x) = X 1 - x - X2 ' Našim cílem je tedy odvodit vztah pro k-tý člen posloupnosti. Využijeme k tomu rozklad na parciální zlomky a dostaneme x A B + 1 — x — x2 1 — Ax 1 — \ix kde A, /i jsou kořeny ř2 — ř — 1 a A B vhodné konstanty odvozené z počátečních podmínek. Odtud už vcelku snadno vyjde Fk = A ■ Xk + B ■ nk, jak to známe z dřívějška. Literatura Vytvořující funkce, rozvinutí do mocninné řady Vytvořující funkce a Fibonacciho čísla Řešení rekurencí oooooooo oom oooo Příklad - závěr S využitím počátečních podmínek dostáváme i + Vš 1 - a/5 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 Fk snadno spočítat zaokrouhlením čísla -^g(1+2v/^)/c. Navíc je vidět, že lim^^ Fk+i/Fk = 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ě. 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). 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 xk udává a/o tj. ak — [xk\A(x) . 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 • Krok 1: = 5a/c_i — 6a/c_2 + [k = 1]. • Krok 2: /4(x) = 5x/l(x) - 6x2/l(x) + x. • Krok 3: A(x) = x 1 - 5x + 6x2 1 - 3x 1 - 2x • Krok 4: ak = 3k - 2k. 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 p 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). i=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í rekurenci kCk = k(k - 1) + 2 C-i, C0 = Q = 0 i=i pomocí uvedeného postupu. • E/c>o kCkX* = Ek>o ~ l)x* + 2 £fc>0 £?=i C/_ix* • Vyřešíme tuto lineární diferenciální rovnici prvního řádu ((l-x)2C(x))' = ^, a tedy C(x) = (l-x)= n 1 -x — x odkud konečně Ck = 2(k + l){Hk+1 - 1) - 2k.