Diskr´etn´ı matematika

(1)

1 / 37

Diskr´ etn´ı matematika

Petr Kov´aˇr petr.kovar@vsb.cz

Vysoká ˇskola báˇnská – Technická univerzita Ostrava

zimn´ı semestr 2021/2022

DiM 470-2301/01, 470-2301/03*, 470-2301/05

(2)

2 / 37

O tomto souboru

Tento soubor je zam´yˇslen pˇredevˇs´ım jako pom˚ucka pro pˇredn´aˇsej´ıc´ıho.

Radu d˚ˇ uleˇzitých informac´ı v souboru nenajdete, protoˇze pˇrednáˇsej´ıc´ı je ˇr´ıká, ukazuje, pˇr´ıpadnˇe maluje na tabuli. Pˇrednáˇsky jsou na webu k dispozici, aby studenti mohli snadno dohledat prob´ıraná témata z pˇrednáˇsek, které zameˇskali.

Pro samostatn´e studium doporuˇcuji skripta:

M. Kubesa: Základy diskrétn´ı matematiky, výukový text P. Kováˇr: Úvod do teorie graf˚u, výukový text

Pro pˇr´ıpravu ke zkouˇsce a p´ısemk´am doporuˇcuji cviˇcebnici:

P. Kov´aˇr: Cviˇcen´ı z diskr´etn´ı matematiky, sb´ırka pˇr´ıklad˚u Vˇse na http://homel.vsb.cz/~kov16/predmety dm.php

(3)

3 / 37

Pˇrehled pˇredn´aˇsky

Kapitola 5. Rekurentnˇe zadan´e posloupnosti motivace

rekurentnˇe zadan´e posloupnosti hlavn´ı ´uloha

metody ˇreˇsen´ı pˇr´ıklady

(4)

4 / 37

5. Rekurentnˇ e zadan´ e posloupnosti

V minulé kapitole jsme pˇripomnˇeli, ˇze ne vˇzdy m˚uˇzeme poˇcty jistých výbˇer˚u vyjádˇrit pomoc´ı jednoduchých vztah˚u probraných v Kapitole 2.

Dnes ukáˇzeme nˇekolik typických situac´ı, které se objev´ı pˇri ˇreˇsen´ı úloh pomoc´ı rekurentn´ıch algoritm˚u.

Ukáˇzeme, jak m˚uˇzeme sloˇzitost nˇekterých vybraných algoritm˚u vyˇc´ıslit.

Typick´e pˇr´ıklady rekurentn´ıch algoritm˚u ˇci postup˚u merge sort

´

ulohy dynamick´eho programov´an´ı

poˇcty uzávorkován´ın+ 1 ˇcinitel˚u pomoc´ın závorek poˇcty

”pˇestovan´ych koˇrenov´ych strom˚u“ v kapitole UTG 4

(5)

5 / 37

5.1. Motivaˇcn´ı pˇr´ıklady

Velmi známý je klasický pˇr´ıpad tzv. Fibonacciho posloupnosti.

Fibonacciho posloupnost

Na ostrovˇe byl vysazen pár malých král´ık˚u. Král´ıci se rozmnoˇzuj´ı aˇz od vˇeku 2 mˇes´ıc˚u, potom vˇsak m˚uˇzeme ˇr´ıci, ˇze kaˇzdý mˇes´ıc vychovaj´ı dalˇs´ı pár král´ık˚u. Jaký je poˇcet f_n pár˚u král´ık˚u po n mˇes´ıc´ıch?

Je evidentn´ı, ˇze f₁=f₂= 1.

Pro n≥3 je poˇcet p´ar˚u urˇcen

poˇctem v pˇredchoz´ım mˇes´ıcifn−1,

je potˇreba pˇripoˇc´ıtat poˇcet pár˚u starých dva mˇes´ıce fn−2, kteˇr´ı nyn´ı dosáhli dospˇelosti a maj´ı mladé.

Celkem máme f_n=fn−1+fn−2 pár˚u, jestliˇze neuvaˇzujeme um´ırán´ı populace.

Reˇsen´ı, tj. vztah proˇ fn odvod´ıme na konci pˇredn´aˇsky.

(6)

6 / 37

Hanojsk´e vˇeˇze

Hanojsk´e vˇeˇze, autorem je ´Edouard Lucas (1842 – 1891) Pˇr´ıklad

M´ame tˇri kol´ıky a sadu disk˚u r˚uzn´ych velikost´ı. Vˇsechny disky jsou

seˇrazeny podle velikosti na prvn´ım k˚ulu. ´Ukolem je pˇrem´ıstit vˇsechny disky na jin´y k˚ul, pˇriˇcemˇz

vˇzdy se pˇresunuje pouze jeden disk, nikdy nesm´ı leˇzet vˇetˇs´ı disk na menˇs´ım.

Jaký je (nejmenˇs´ı) nutný poˇcet krok˚u Hn pro pˇrem´ıstˇen´ı celé vˇeˇze s n disky?

(7)

7 / 37

Hanojsk´e vˇeˇze

Abychom pˇrem´ıstili nejvˇetˇs´ı disk, mus´ı b´yt n−1 disk˚u pˇrem´ıstˇeno na jin´y k˚ul Hn−1 tahy.

Celkov´y poˇcet tah˚u H_n rozdˇel´ıme na tˇri ˇc´asti.

NejprveHn−1 tahy pˇrem´ıst´ımen−1 menˇs´ıch disk˚u na tˇret´ı k˚ul, pak jedn´ım tahem pˇrem´ıst´ıme nejvˇetˇs´ı disk na krajn´ı k˚ul,

nakonec Hn−1 tahy pˇrem´ıst´ıme n−1 menˇs´ıch disk˚u na nejvˇetˇs´ı disk.

Celkový poˇcet tah˚u je dán rekurentn´ım vztahem H_n= 2Hn−1+ 1, pˇriˇcemˇz je jasné, ˇze H₁ = 1.

Reˇsen´ı, tj. vztah proˇ H_n odvod´ıme na konci pˇredn´aˇsky.

(8)

8 / 37

Bitov´e ˇretˇezce bez sousedn´ıch nul

Pˇr´ıklad

Kolik existuje bitových ˇretˇezc˚u délkyn, které neobsahuj´ı sousedn´ı nuly?

(vyuˇzit´ı u ˇcárových kód˚u)

Oznaˇcmea_n poˇcet hledan´ych bitov´ych ˇretˇezc˚u s n bity.

Rozliˇs´ıme, zda ˇretˇezec n bit˚u konˇc´ı 0 nebo 1 (pˇredpokl´adejme, ˇzen ≥3).

pokud ˇretˇezec konˇc´ı 1, tak takov´ych ˇretˇezc˚u je pr´avˇe an−1, kdy jsme na konec pˇridali bit 1,

pokud ˇretˇezec konˇc´ı 0, tak pˇredposledn´ı bit mus´ı být 1 a takových ˇretˇezc˚u je právˇean−2, kdy jsme na konec pˇridali dva bity 10.

Jiná moˇznost nen´ı, proto celkový poˇcet ˇretˇezc˚u délkyn, které neobsahuj´ı sousedn´ı nuly, je

an=an−1+an−2. Zb´yv´a si uvˇedomit, ˇzea₁ = 2,a₂ = 4−1 = 3.

Na konci pˇredn´aˇsky odvod´ıme vztah proa_n.

Pozor:an podobn´e, ale jin´e neˇz Fibonacciho posloupnost.

(9)

9 / 37

Kl´ıˇcov´a slova se sud´ym poˇctem nul

Pˇr´ıklad

Poˇc´ıtaˇcový systém pracuje s kódovými slovy sestavenými z cifer 0, 1, . . . , 9. Platné kódové slovo obsahuje sudý poˇcet cifer 0. Kolik takových kódových slov délkyn existuje?

Oznaˇcmex_n poˇcet hledaných kódových slov s n ciframi.

Rozliˇs´ıme, zda kódové slovo sn ciframi konˇc´ı 0 nebo ne (pˇredpokládáme, ˇ

ze n≥2).

kódových slov, která nekonˇc´ı 0, je právˇe 9xn−1, kdy jsme na konec nˇekterého z xn−1 kódových slov pˇridali cifru 1,2,. . . , 9,

kódové slov, která konˇc´ı 0, je právˇe tolik, kolik je chybných kódových slovxn−1.

Jiná moˇznost nen´ı, proto celkový poˇcet kódových slov délky n, které obsahuj´ı sudý poˇcet nul, je

xn = 9xn−1+ (10ⁿ⁻¹−xn−1) = 8xn−1+ 10ⁿ⁻¹. Zbývá si uvˇedomit, ˇzex1 = 9. Hledáme vztah xn pron-tý ˇclen.

(10)

10 / 37

Poˇcty uzávorkován´ın+ 1ˇcinitel˚u pomoc´ın závorek

Pˇr´ıklad

Máme výraz sloˇzený zn+ 1 ˇcinitel˚u, uzávorkujeme pomoc´ın pár˚u závorek. Kolik existuje r˚uzných zp˚usob˚u uzávorkován´ıC_n?

C₀= 1, nebot’ x₁ je jedin´y zp˚usob.

C₁= 1, nebot’ (x₁⊕x₂) je jedin´y zp˚usob.

C2= 2, nebot’ ((x1⊕x2)⊕x3), (x1⊕(x2⊕x3)) jsou dva zp˚usoby.

C₃= 5, nebot’ 5 zp˚usob˚u (((x₁⊕x₂)⊕x₃)⊕x₄), ((x₁⊕(x₂⊕x₃))⊕x₄), ((x₁⊕x₂)⊕(x₃⊕x₄)), (x₁⊕((x₂⊕x₃)⊕x₄)), (x₁⊕(x₂⊕(x₃⊕x₄))).

Obecnˇe ve vnˇejˇs´ı závorce je vˇzdy právˇe jeden operátor

”⊕“. Vˇsimneme si, ˇ

ze výraz se skládá z operace dvou menˇs´ıch výraz˚u, kterých m˚uˇzeme naj´ıtn r˚uzných podle poˇctu ˇclen˚u nalevo od operátoru ve vnˇejˇs´ı závorce.

C_n=

n−1

X

k=0

C_kC_n−k−1

Rekurentn´ı posloupnostC_n=Pn−1

k=0C_kCn−k−1 se objevuje v ˇradˇe praktick´ych probl´emu, tzv. Catalanova ˇc´ısla.

(11)

11 / 37

5.2. Rekurentnˇe zadan´e posloupnosti Opakov´an´ı:

Posloupnost m˚uˇzeme zadat

v´yˇctem nˇekolika prvn´ıch prvk˚u: 1,3,7,15,31, . . . rekurentnˇe:a_n= 2an−1+ 1, a₀ = 1

vztahem pro n-t´y ˇclen: an= 2ⁿ−1

Nyn´ı se zabýváme rekurentnˇe zadanými posloupnostmi, kdy dalˇs´ı ˇclen se urˇc´ı výpoˇctem na základˇe pˇredcházej´ıc´ıch ˇclen˚u.

Hlavn´ı ´uloha

Naj´ıt vztah pro n-t´y ˇclen.

pokud existuje, pokud to lze a pokud to um´ıme.

(12)

12 / 37

Line´arn´ı homogenn´ı rekurentn´ı rovnice ˇr´adu k s konstantn´ımi koeficienty

Lineárn´ı homogenn´ı rekurentn´ı rovnice ˇrádu k s konstantn´ımi koeficienty je rekurentnˇe zadaná posloupnost tvaru

a_n=c₁an−1+c₂an−2+· · ·+c_ka_n−k, kde c₁,c₂, . . . ,c_k jsou re´aln´a ˇc´ısla,c_k 6= 0.

Rozeberme definici rekurentn´ı rovnice

jelineárn´ı, protoˇze se jedná o lineárn´ı kombinaci pˇredchoz´ıch ˇclen˚u, jehomogenn´ı, protoˇze nemáˇclen, který by nebyl násobkemai, jeˇráduk, protoˇze a_n je vyjádˇren pomoc´ık pˇredchoz´ıch ˇclen˚u, jes konstantn´ımi koeficienty, nebot’ kaˇzdý koeficient u a_i je konstanta, nikoli funkc´ın.

Pro jednoznaˇcné urˇcen´ı posloupnosti dané rekurenc´ı ˇráduk mus´ımezadat k prvn´ıch ˇclen˚u.

(13)

13 / 37

Fibonacciho posloupnost f_n=fn−1+fn−2 je lineárn´ı homogenn´ı rekurentn´ı rovnice druhého ˇrádu s konstantn´ımi koeficienty.

Prvn´ı ˇcleny jsouf1 = 1, f2= 1.

Posloupnost poˇctu bitových ˇretˇezc˚u délky n, které neobsahuj´ı sousedn´ı nuly an=an−1+an−2, je lineárn´ı homogenn´ı rekurentn´ı rovnice druhého ˇrádu s konstantn´ımi koeficienty.

Prvn´ı ˇcleny jsoua₁ = 2,a₂ = 3.

Hanojsk´e vˇeˇze

Posloupnost nutného poˇctu krok˚u Hn pro pˇrem´ıstˇen´ı celé hanojské vˇeˇze s n disky H_n= 2Hn−1+ 1, je lineárn´ı rekurentn´ı rovnice prvn´ıho ˇrádu

s konstantn´ımi koeficienty, kter´anen´ı homogenn´ı. Prvn´ı ˇclen jeH1= 1.

(14)

14 / 37

Kódová slova se sudým poˇctem nul

Poˇcet kódových slov sestavených z cifer 0, 1, . . . , 9, kde nav´ıc kaˇzdé kódové slovo obsahuje sudý poˇcet cifer 0, je lineárn´ı rekurentn´ı rovnice prvn´ıho ˇrádu s konstantn´ımi koeficientyxn= 8xn−1+ 10ⁿ⁻¹. Prvn´ı ˇclen je x₁ = 9.

Tato rovnice nen´ı homogenn´ı, nebot’ ˇclen 10ⁿ⁻¹ nen´ın´asobkema_i. Catalanova ˇc´ısla

Posloupnost Catalanov´ych ˇc´ıselCn=Pn−1

k=0C_kCn−k−1 je urˇcena rekurentn´ı homogenn´ı rovnic´ı. Prvn´ı ˇcleny jsouC₁= 1, C₂ = 2.

Tato rekurentn´ı rovnice nen´ı lineárn´ı, protoˇze ˇcleny C_k,C_n−k násob´ıme a nen´ı pevného ˇrádu, nebot’ poˇcet sˇc´ıtanc˚u roste sn.

Pˇr´ıklad

Rekurentnˇe zadaná posloupnosta_n=an−1·an−2 je rekurentn´ı homogenn´ı rovnice druhého ˇrádu s konstantn´ımi koeficienty. Prvn´ı ˇcleny a1 = 1, a2 = 2.

Tato rekurentn´ı rovnice nen´ı line´arn´ı, protoˇze ˇcleny an−1,an−2 n´asob´ıme.

(15)

15 / 37

5.3. Metody ˇreˇsen´ı rekurentnˇe zadan´ych posloupnost´ı

Hlavn´ı ´uloha ˇreˇsen´ı rekurentn´ıch rovnic

Je-li lineárn´ı rekurentn´ı rovnice (malého) ˇrádu k s konstantn´ımi koeficienty dána rekurentn´ım vztahem a dostatkem prvn´ıch ˇclen˚u, m˚uˇzeme tuto rovnici

”vyˇreˇsit“. To znamená, ˇze budeme hledat vztah pron-tý ˇclen, pomoc´ı kterého lze vyjádˇrita_n bez znalosti pˇredchoz´ıch ˇclen˚u.

Uk´aˇzeme si, jak je moˇzno obecnˇe postupovat:

nejprve sestav´ıme tzv.charakteristickou rovnici, potom najdeme koˇreny charakteristick´e rovnice,

v závislosti na poˇctu koˇren˚u charakteristické rovnice zvol´ıme tvar obecného ˇreˇsen´ı,

v závislosti na hodnotˇe prvn´ıch ˇclen˚u posloupnosti dopoˇc´ıtáme neznámé koeficienty.

Zaˇcneme jednoduch´ymi pˇr´ıpady.

(16)

16 / 37

Charakteristick´a rovnice a jej´ı koˇreny

Je moˇzno uk´azat (napˇr´ıklad postupem s pomoc´ı tzv. vytvoˇruj´ıc´ıch funkc´ı), ˇ

ze ˇreˇsen´ı line´arn´ıch homogenn´ıch rekurentn´ıch rovnic s konstantn´ımi koeficienty bude tvarua_n=rⁿ, kde r je vhodn´a konstanta.

Dosazen´ım do rekurentn´ıho pˇredpisu dostaneme

a_n = c₁an−1+c₂an−2+· · ·+c_kan−k

rⁿ = c₁rⁿ⁻¹+c₂rⁿ⁻²+· · ·+c_kr^n−k r^k = c1r^k−1+c2r^k−2+· · ·+c_kr^k−k 0 = r^k−c1r^k⁻¹−c2r^k⁻²− · · · −ck

Posledn´ı rovnice se nazývá charakteristická rovnicerekurentn´ı rovnice.

Je zˇrejmé, ˇze ˇreˇsen´ı této rovnice v promˇenné r jsou hledaná ˇc´ısla ri. R´ık´ˇ ame jimkoˇreny charakteristické rovnice.

(17)

17 / 37

Postupn´e zobecnˇen´ı ˇreˇsen´ı

Pro n´azornost rozdˇel´ıme ˇreˇsen´ı line´arn´ıch homogenn´ıch rekurentn´ıch rovnic s konstantn´ımi koeficienty do nˇekolika krok˚u.

Kaˇzd´y dalˇs´ı krok zahrne vˇetˇs´ı mnoˇzinu rekurentn´ıch rovnic:

nejprve ukáˇzeme, jak vypadá obecné ˇreˇsen´ı lineárn´ı homogenn´ı rekurentn´ı rovnice ˇrádu 2 s konstantn´ımi koeficienty,

I jestliˇze máme dva r˚uzné reálné koˇreny,

I a jestliˇze máme dva stejné reálné koˇreny,

dále ukáˇzeme, jak vypadá obecné ˇreˇsen´ı lineárn´ı homogenn´ı rekurentn´ı rovnice ˇrádu k s konstantn´ımi koeficienty.

Potom ukáˇzeme, jak vypadá obecné ˇreˇsen´ı lineárn´ı homogenn´ı rekurentn´ı rovnice ˇráduk s konstantn´ımi koeficienty,

a nakonec ukáˇzeme, jak vypadá obecné ˇreˇsen´ı lineárn´ı nehomogenn´ı rekurentn´ı rovnice ˇráduk s konstantn´ımi koeficienty.

Dalˇs´ı zobecnˇen´ı jen zm´ın´ıme.

(18)

18 / 37

Tvar ˇreˇsen´ı

Nejprve ukáˇzeme, jak vypadá tvar obecného ˇreˇsen´ı homogenn´ı rovnice.

Vˇeta

Mˇejme dvˇe reálná ˇc´ısla c₁,c₂. Pokud má charakteristická rovnice r²−c1r−c2= 0 dva r˚uzné (reálné) koˇrenyr1,r2, tak ˇreˇsen´ı rekurentn´ı rovnice an=c1an−1+c2an−2 má tvaran=α1r₁ⁿ+α2r₂ⁿ,

pro n= 0,1,2, . . .. D˚ukaz neuv´ad´ıme.

Plat´ı dokonce silnˇejˇs´ı tvrzen´ı, koˇreny nemus´ı být reálné.

(19)

19 / 37

Pˇr´ıklad

Najdˇete ˇreˇsen´ı rekurentn´ı rovnicean=an−1+ 2an−2, kde a0 = 2, a1 = 7.

Postupujeme podle n´avodu uveden´eho dˇr´ıve:

Pˇredpokl´ad´ame ˇreˇsen´ı tvaru a_n=rⁿ. Dosazen´ım do rekurentn´ı rovnice dostaneme charakteristickou rovnici

r²−r−2 = 0 (r+ 1)(r−2) = 0.

Charakteristick´e koˇreny jsou r1 = 2,r2 =−1. Obecn´e ˇreˇsen´ı je tvaru a_n=α₁2ⁿ+α₂(−1)ⁿ.

Dosazen´ım a0,a1 dostaneme dvˇe rovnice o nezn´am´ych α1,α2. a₀ = 2 = α₁·1 +α₂·1

a₁ = 7 = α₁·2 +α₂·(−1)

Reˇsen´ım soustavy dostanemeˇ α1= 3, α2 =−1, proto obecn´e ˇreˇsen´ı je a_n= 3·2ⁿ−1·(−1)ⁿ.

(20)

20 / 37

Vskutku,

vztahan= 3·2ⁿ−1(−1)ⁿ pron = 0,1,2, . . .

rekurentn´ı rovnicean=an−1+ 2an−2, kdea0= 2, a1= 7 popisuj´ı stejnou posloupnost:

2,7,11,25,47,97,191,385,767,1 537,3 071, . . . Nyn´ı se pod´ıváme na pˇr´ıpad s násobnými koˇreny.

Vˇeta

Mˇejme dvˇe reálná ˇc´ısla c₁,c₂, kdec₂ 6= 0. Pokud má charakteristická rovnice r²−c1r−c2= 0 jeden dvojnásobný (reálný) koˇren r0, tak ˇreˇsen´ı rekurentn´ı rovnicean=c1an−1+c2an−2 má tvaran=α1r₀ⁿ+α2nr₀ⁿ, pro n= 0,1,2, . . ..

Vˇsimnˇete si, ˇze druhý ˇclen obecného ˇreˇsen´ı je vynásoben n.

(21)

21 / 37

Pˇr´ıklad

Najdˇete ˇreˇsen´ı rekurentn´ı rovnicean= 10an−1−25an−2, kdea0 = 3, a₁ = 5.

Opˇet postupujeme stejnˇe:

Pˇredpokl´ad´ame ˇreˇsen´ı tvaru an=rⁿ. Dosazen´ım do rekurentn´ı rovnice dostaneme charakteristickou rovnici

r²−10r+ 25 = 0 (r−5)(r−5) = 0.

Charakteristick´e koˇreny jsou r1 =r2= 5, oznaˇcmer0 = 5. Obecn´e ˇreˇsen´ı je tvaru

a_n =α₁5ⁿ+α₂n5ⁿ.

Dosazen´ım a0,a1 dostaneme dvˇe rovnice o nezn´am´ych α1,α2. a0= 3 = α1·1 + 0

a₁= 5 = α₁·5 +α₂·5

Reˇsen´ım soustavy dostanemeˇ α₁= 3, α₂ =−2, proto ˇreˇsen´ı je a_n= 3·5ⁿ−2n5ⁿ.

(22)

22 / 37

Naˇsli jme vztah pro n-t´y ˇclen

an= 3·5ⁿ−2n5ⁿ, popisuje stejnou posloupnost jako

rekurentn´ı rovnicea_n= 10an−1−25an−2, kdea₀ = 3,a₁ = 5.

Posloupnost je

3,5,−25,−375,−3 125,−21 875,−140 625, . . .

Reˇsen´ı line´ˇ arn´ıch rekurentn´ıch rovnic je moˇzné dále zobecnit pro vyˇsˇs´ı ˇrády.

Vˇeta

Mˇejme reálná ˇc´ısla c1,c2, . . . ,c_k. Pokud má charakteristická rovnice r^k−c₁r^k⁻¹−c₂r^k⁻²− · · · −c_k = 0 r˚uzných k koˇren˚u r₁,r₂, . . . ,r_k, tak ˇreˇsen´ı rekurentn´ı rovnice an =c1an−1+c2an−2+· · ·+ckan−k má tvar an=α1r₁ⁿ+α2r₂ⁿ+· · ·+α_kr_kⁿ, pron= 0,1,2, . . ..

(23)

23 / 37

Pˇr´ıklad

Najdˇete ˇreˇsen´ı rekurentn´ı rovnicea_n= 4an−1−an−2−6an−3, kdea₀ = 6 a1 = 5,a2 = 13.

Dostaneme charakteristickou rovnici

r³−4r²+r+ 6 = 0.

Charakteristick´e koˇreny jsou r₁ =−1,r₂= 2, r₃ = 3. Obecn´e ˇreˇsen´ı je tvaru

an=α1(−1)ⁿ+α22ⁿ+α33ⁿ.

Dosazen´ım a0,a1,a2 dostaneme tˇri rovnice o nezn´am´ychα1,α2,α3. a0 = 6 = α1+α2+α3

a1 = 5 = −α₁+ 2α2+ 3α3

a₂ = 13 = α₁+ 4α₂+ 9α₃

Reˇsen´ım soustavy dostanemeˇ α1= 2, α2 = 5,α3=−1, proto obecn´e ˇreˇsen´ı je

a_n= 2·(−1)ⁿ+ 5·2ⁿ−3ⁿ.

(24)

24 / 37

Obecn´e ˇreˇsen´ı lin. homogenn´ı rekurentn´ı rovnice s konst. koeficienty

Vˇeta

Mˇejme reálná ˇc´ısla c₁,c₂, . . . ,c_k. Pokud má charakteristická rovnice r^k−c1r^k⁻¹−c2r^k⁻²− · · · −ck = 0 r˚uzných t koˇren˚u r1,r2, . . . ,rt

s n´asobnostmim1,m2, . . . ,mt, tak ˇreˇsen´ı rekurentn´ı rovnice a_n=c₁an−1+c₂an−2+· · ·+c_kan−k m´a pron = 0,1,2, . . . tvar

an = (α1,1+α1,2n+· · ·+α1,m1n^m¹⁻¹)r₁ⁿ+ +(α2,1+α2,2n+· · ·+α2,m2n^m²⁻¹)r₂ⁿ+ +· · ·+ (αt,1+αt,2n+· · ·+αt,mtn^m^t⁻¹)r_tⁿ Abychom naˇsli ˇreˇsen´ı, tak

1 sestav´ıme charakteristickou rovnici,

2 urˇc´ıme charakteristick´e koˇreny (pokud to lze),

3 sestav´ıme ˇreˇsen´ı v pˇredpokl´adan´em tvaru s koeficientyαi,j,

4 dosad´ıme k prvn´ıch (zn´am´ych) ˇclen˚u,

5 vyˇreˇs´ıme soustavu rovnic s k nezn´am´ymi,

6 sestav´ıme obecn´e ˇreˇsen´ı.

(25)

25 / 37

Obecn´e ˇreˇsen´ı line´arn´ı nehomogenn´ı rekurentn´ı rovnice s konstantn´ımi koeficienty

Zat´ım um´ıme ˇreˇsit pouze homogenn´ı rekurentn´ı rovnice . . . Reˇsen´ı nehomogenn´ıch rekurentn´ıch rovnic m´ˇ a dvˇe ˇc´asti

obecn´e ˇreˇsen´ıpˇridruˇzen´e homogenn´ırekurentn´ı rovnice,

jednopartikul´arn´ı ˇreˇsen´ıline´arn´ı nehomogenn´ı rekurentn´ı rovnice.

Vˇeta

Mˇejme reálná ˇc´ısla c₁,c₂, . . . ,c_k, mˇejme funkciF(n) r˚uznou od konstantn´ı nulové funkce.

Jestliˇze a^(p)n jepartikul´arn´ıˇreˇsen´ı line´arn´ı nehomogenn´ı rekurentn´ı rovnice s konstantn´ımi koeficienty

a_n=c₁an−1+c₂an−2+· · ·+c_kan−k +F(n),

tak kaˇzdé ˇreˇsen´ı je tvarua^(p)n +a^(h)n , kdea^(h)n je ˇreˇsen´ıpˇridruˇzené lineárn´ı homogenn´ı rekurentn´ı rovnice s konstantn´ımi koeficienty

an=c1an−1+c2an−2+· · ·+ckan−k.

(26)

26 / 37

Pˇr´ıklad

Ukaˇzte, ˇze a^(p)n =−n−2 je (partikul´arn´ım) ˇreˇsen´ım rekurentn´ı rovnice a_n= 2an−1+n.

Abychom ˇreˇsen´ı ovˇeˇrili, staˇc´ı dosadit a porovnat:

a_n = 2an−1+n

−n−2 = 2 (−(n−1)−2) +n

−n−2 = −n−2.

Vˇsimnˇete si: partikul´arn´ı ˇreˇsen´ı m´a tvara^(p)n =cn+d. Pˇr´ıklad

Ukaˇzte, ˇze a^(p)_n =c·7ⁿ je vhodn´y tvar (partikul´arn´ıho) ˇreˇsen´ı rekurentn´ı rovnice an= 5an−1−6an−2+ 7ⁿ.

Opˇet dosad´ıme a porovn´ame:

an = 5an−1−6an−2+ 7ⁿ c ·7ⁿ = 5c ·7ⁿ⁻¹−6c·7ⁿ⁻²+ 7ⁿ

c = 49 20.

(27)

27 / 37

Vˇeta

Mˇejmek reálných ˇc´ıselc1,c2, . . . ,c_k, mˇejme funkci F(n), která nen´ı konstantn´ı a rovna nule.

Pˇredpokl´adejme, ˇze a^(p)n je ˇreˇsen´ı nehomogenn´ı line´arn´ı rekurentn´ı rovnice s konstantn´ımi koeficienty

an=c1an−1+c2an−2+· · ·+ckan−k +F(n), kde F(n) = (b_tn^t+bt−1n^t−1+· · ·+b₁n+b₀)sⁿ.

1 Jestliˇze s nen´ı koˇrenem charakteristické rovnice pˇridruˇzené lineárn´ı homogenn´ı rekurentn´ı rovnice, taka^(p)n má tvar

(p_tn^t+pt−1n^t−1+· · ·+p₁n+p₀)sⁿ.

2 Jestliˇze s je koˇrenem s násobnost´ım charakteristické rovnice pˇridruˇzené lineárn´ı homogenn´ı rekurentn´ı rovnice, taka^(p)_n má tvar

n^m(p_tn^t+pt−1n^t−1+· · ·+p₁n+p₀)sⁿ.

(28)

28 / 37

Pˇr´ıklad

Reˇste rekurentn´ı rovniciˇ an= 2an−1+n2ⁿ.

Nejprve urˇc´ıme ˇreˇsen´ı pˇridruˇzen´e line´arn´ı homogenn´ı rekurentn´ı rovnice an= 2an−1.

Jej´ı charakteristická rovnicerⁿ= 2rⁿ⁻¹ má nenulový koˇrenr = 2.

Proto tvar obecn´eho ˇreˇsen´ı je a^(h)n =α2ⁿ.

Dále urˇc´ıme partikulárn´ı ˇreˇsen´ı p˚uvodn´ı lineárn´ı nehomogenn´ı rekurentn´ı rovnice. Podle pˇredchoz´ı vˇety pˇredpokládáme tvar ˇreˇsen´ı

an^(p)=n(cn+d)2ⁿ, nebot’z´aklad 2 je koˇrenem charakteristick´e rovnice.

Pro urˇcen´ı neznámých konstant dosad´ıme partikulárn´ı ˇreˇsen´ı a^(p)_n =n(cn+d)2ⁿ do rekurentn´ı rovnicea_n= 2an−1+n2ⁿ.

(29)

29 / 37

Pˇr´ıklad pokraˇcov´an´ı Dostaneme

n(cn+d)2ⁿ = 2·(n−1)(c(n−1) +d)2ⁿ⁻¹+n2ⁿ (cn²+dn)2ⁿ = 2·(c(n−1)²+d(n−1))2ⁿ⁻¹+n2ⁿ (cn²+dn)2ⁿ = (cn²−2cn+c +dn−d +n)2ⁿ

dn = (−2c+d+ 1)n+ (c −d).

Porovn´an´ım koeficient˚u polynom˚u u n¹ an⁰ dostaneme soustavu rovnic n¹: d = −2c+d + 1

n⁰ : 0 = c−d.

Soustavu vyˇreˇs´ıme a dostaneme c = ¹₂,d = ¹₂ a partikul´arn´ı ˇreˇsen´ı je a^(p)_n =n(¹₂n+¹₂)2ⁿ= (n²+n)2ⁿ⁻¹.

Reˇsen´ı dan´ˇ e rekurentn´ı rovnice je

a_n=a^(h)_n +a^(p)_n =α·2ⁿ+ (n²+n)2ⁿ⁻¹= (n²+n+ 2α)2ⁿ⁻¹. Hodnota konstanta α z´avis´ı na poˇc´ateˇcn´ı hodnotˇe a1.

(30)

30 / 37

5.4. ˇReˇsen´ı motivaˇcn´ıch pˇr´ıklad˚u z ´uvodu kapitoly

Najdˇete ˇreˇsen´ı rekurentn´ı rovnicef_n=fn−1+fn−2, kdef₀= 0, f₁ = 1.

Dostaneme charakteristickou rovnicir²−r−1 = 0.

Charakteristick´e koˇreny jsou r₁ = (1 +√

5)/2,r₂ = (1−√

5)/2. Obecn´e ˇreˇsen´ı je tvaru

fn=α1

1 +√ 5 2

!n

+α2

1−√ 5 2

!n

.

Dosazen´ım f₀= 0, f₁= 1 dostaneme dvˇe rovnice o nezn´am´ychα₁,α₂. 0 = α₁·1 +α₂·1

1 = α₁· 1 +√ 5 2

!

+α₂· 1−√ 5 2

!

Reˇsen´ım soustavy dostanemeˇ α₁=

√ 5

5 ,α₂=−

√ 5

5 , proto obecn´e ˇreˇsen´ı je fn=

√ 5

5 · 1 +√ 5 2

!n

−

√ 5

5 · 1−√ 5 2

!n

.

(31)

31 / 37

Hanojsk´e vˇeˇze

Najdˇete ˇreˇsen´ı rekurentn´ı rovniceH_n= 2Hn−1+ 1, kde H₁ = 1.

Jedn´a se o line´arn´ınehomogenn´ırekurentn´ı rovnici.

Na druhou stranu se jedn´a o rekurentn´ı rovnici prvn´ıho ˇr´adu, ˇreˇsen´ı odvod´ıme jinak.

Vˇsimneme si

H_n = 2Hn−1+ 1

= 2(2Hn−2+ 1) + 1 = 2²Hn−2+ 2 + 1

= 2²(2Hn−3+ 1) + 2 + 1 = 2³Hn−2+ 2²+ 2 + 1 ...

= 2ⁿ⁻¹H1+ 2ⁿ⁻²+ 2ⁿ⁻³+· · ·+ 2 + 1

= 2ⁿ⁻¹+ 2ⁿ⁻²+ 2ⁿ⁻³+· · ·+ 2 + 1

= 2ⁿ−1.

Hledané ˇreˇsen´ı lineárn´ı nehomogenn´ı rovnice hanojských vˇeˇz´ı je H_n= 2ⁿ−1.

(32)

32 / 37

Najdˇete ˇreˇsen´ı rekurentn´ı rovnicean=an−1+an−2, kdea1 = 2,a2 = 3.

Dostaneme charakteristickou rovnicir²−r−1 = 0.

Charakteristick´e koˇreny jsou r1 = (1 +√

5)/2,r2 = (1−√

5)/2. Obecn´e ˇreˇsen´ı je tvaru

a_n =α₁ 1 +√ 5 2

!n

+α₂ 1−√ 5 2

!n

.

Dosazen´ım a1= 2, a2= 3 dostaneme dvˇe rovnice o nezn´am´ych α1,α2. 2 = α1· 1 +√

5 2

!

+α2· 1−√ 5 2

!

3 = α1· 1 +√ 5 2

!2

+α2· 1−√ 5 2

!2

Reˇsen´ım soustavy dostanemeˇ α1= ⁵⁺

√5

10 ,α2= ⁵⁻

√5

10 , obecn´e ˇreˇsen´ı je an= 5 +√

5

10 · 1 +√ 5 2

!n

+5−√ 5

10 · 1−√ 5 2

!n

.

Pˇr´ıklad

(33)

33 / 37

Kl´ıˇcov´a slova se sud´ym poˇctem nul

Najdˇete ˇreˇsen´ı rekurentn´ı rovnicex_n= 8xn−1+ 10ⁿ⁻¹, kdex₁ = 9.

Nejedn´a se line´arn´ı o homogenn´ırekurentn´ı rovnici s konstantn´ımi koeficienty.

Nejprve najdeme obecn´e ˇreˇsen´ı pˇridruˇzen´e homogenn´ı rekurentn´ı rovnice x_n= 8xn−1.

Jej´ı charakteristická rovnicerⁿ= 8rⁿ⁻¹ má nenulový koˇrenr = 8.

Proto tvar obecn´eho ˇreˇsen´ı je x_n^(h)=α8ⁿ.

Konstantu α m˚uˇzeme urˇcit aˇz budeme zn´at partikul´arn´ı ˇreˇsen´ı.

Dále urˇc´ıme partikulárn´ı ˇreˇsen´ı p˚uvodn´ı lineárn´ı nehomogenn´ı rekurentn´ı rovnice. Podle vˇety pˇredpokládáme tvar partikulárn´ıho ˇreˇsen´ı

xn^(p) =c·10ⁿ,

nebot’ z´aklad 10 nen´ıkoˇrenem charakteristick´e rovnice.

Pro urˇcen´ı konstanty c dosad´ıme partikul´arn´ı ˇreˇsen´ıxn^(p)=c·10ⁿ do rekurentn´ı rovnicex_n= 8xn−1+ 10ⁿ⁻¹.

(34)

34 / 37

Dostaneme

c10ⁿ = 8·c10ⁿ⁻¹+ 10ⁿ⁻¹ 10c = 8c + 1

2c = 1

c = 1

2.

Nyn´ı obecn´e ˇreˇsen´ı rekurentn´ı rovnicexn= 8xn−1+ 10ⁿ⁻¹ je x_n=x_n^(h)+x_n^(p)=α·8ⁿ+1

2·10ⁿ.

Hodnotu konstanty α urˇc´ıme dosazen´ım x1 = 9 an= 1 do obecn´eho ˇreˇsen´ıx_n=α·8ⁿ+¹₂ ·10ⁿ. Dostaneme

9 = α·8 +1 2·10 9−5 = 8α

α = 1

2.

Reˇsen´ı dan´ˇ e rekurentn´ı rovnice vˇcetnˇe poˇc´ateˇcn´ı podm´ınky je x_n= 1

2·8ⁿ+1 2 ·10ⁿ.

(35)

35 / 37

Merge sort

Merge sort je dobˇre známý algoritmus, který slouˇz´ı k seˇrazen´ı posloupnosti n prvk˚u. Jedná se o rekurzivn´ı algoritmus.

Známe-li algoritmus, tak snadno nahlédneme, ˇze poˇcet porovnán´ı a poˇcet operac´ıMn pro seˇrazen´ı posloupnostin prvk˚u m˚uˇzeme shora odhadnout rekurentn´ı rovnic´ıM_n= 2M_dn/2e+n, kde M₁ = 1.

Tuto lineárn´ınehomogenn´ırekurentn´ı rovnici neum´ıme ˇreˇsit, protoˇzenemá pevný ˇrád.

Je moˇzno uk´azat, ˇze ˇreˇsen´ı, tj. poˇcet krok˚u Merge sort algoritmu, je funkce sloˇzitosti

M_n=O(nlogn).

(36)

36 / 37

Hanojsk´e vˇeˇze – jin´e ˇreˇsen´ı

Najdˇete ˇreˇsen´ı rekurentn´ı rovniceHn= 2Hn−1+ 1, kde H1 = 1.

Jedn´a se o line´arn´ınehomogenn´ırekurentn´ı rovnici.

Nejprve najdeme obecné ˇreˇsen´ı pˇridruˇzené homogenn´ı rovniceHn= 2Hn−1. Charakteristická rovnice má tvarr = 2. Má jediný koˇren, proto tvar obecného ˇreˇsen´ı je H_n=α·2ⁿ. Hodnotu konstantyα urˇc´ıme nakonec.

Protoˇze funkceF(n) = 1, tak partikul´arn´ı ˇreˇsen´ıHn^(p) ˇcek´ame tvaru c·1.

Abychom urˇcili hodnotu c, tak partikul´arn´ı ˇreˇsen´ı dosad´ıme do rekurentn´ı

rovnice. Hn = 2Hn−1+ 1

c = 2c+ 1

−1 = c

Partikul´arn´ı ˇreˇsen´ı jeHn^(p)=−1 a obecn´e ˇreˇsen´ı nehomogenn´ı rovnice je tvaru H_n=α·2ⁿ−1.

Nyn´ı vyˇc´ısl´ıme hodnotuα dosazen´ım poˇc´ateˇcn´ı podm´ınkyH1= 1.

Dostaneme 1 =α·2¹−1, tedy α= 1.

Hledané ˇreˇsen´ı lineárn´ı nehomogenn´ı rovnice poˇctu tah˚u ˇreˇsen´ı hanojských vˇeˇz´ı je Hn= 2ⁿ−1.

(37)

37 / 37

Pˇr´ıˇstˇe

Kapitola 6. Kongruence a modul´arn´ı aritmetika motivace

dˇelen´ı a dˇelitelnost

lineárn´ı kongruence o jedné neznámé metody ˇreˇsen´ı

pˇr´ıklady vyuˇzit´ı