Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Rekurentn´ı rovnice, struktur´aln´ı indukce
Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
1/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Backusova-Naurova forma Napˇr´ıklad syntaxe formul´ı v´yrokov´e logiky ϕ ::= a | tt | (ϕ ∧ ϕ) | (¬ϕ) kde a ∈ At. Pozn´amky 1
Relaxace BNF.
2
P˚ uvod notace: John Warner Backus a Peter Naur pro popis syntaxe jazyka Algol 60. Pravidla stejn´e vyjadˇrovac´ı schopnosti: hindsk´y gramatik P¯an.ini (cca 6. stolet´ı pˇr.n.l.) pro popis sanskrtu. Prvn´ı form´aln´ı popis pˇrirozen´eho jazyka: 3 959 verˇs˚ u d´ıla Ast¯adhy¯ay¯ı. Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
2/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Jin´e z´apisy BNF a
|
tt
ϕ1 ϕ2 ϕ | (ϕ1 ∧ ϕ2 ) (¬ϕ)
|
nebo a
(atom)
|
tt
(true)
|
ϕ1 ϕ2 ϕ (and) | (not) (ϕ1 ∧ ϕ2 ) (¬ϕ)
Axiomy: (atom), (true). Deduktivn´ı pravidla: (and), (not). Syntaktick´y strom (Parsing Tree) a
(atom)
(atom)
b (a ∧ b) (¬(a ∧ b))
Jiˇr´ı Velebil: Y01DMA
(and) (not)
23. u ´nora 2010: Struktur´ aln´ı indukce
3/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Jazyk generovan´y gramatikou Abeceda: Σ = At ∪ {tt, ∧, ¬, (, )}. Mnoˇzina F vˇsech formul´ı je F ⊆ Σ∗ . F je induktivnˇe generovan´a “gramatikou” (atom), (true), (and), (not). Pro kaˇzd´e ϕ ∈ Σ∗ plat´ı ϕ∈F
iff
existuje parsing tree (dan´e “gramatiky”).
Z toho plyne dalˇs´ı indukˇcn´ı princip!
Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
4/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Pˇr´ıklad Pro kaˇzd´e ϕ ∈ F plat´ı: ϕ m´a stejn´y poˇcet prav´ych a lev´ych z´avorek. ˇ sen´ı: Reˇ 1 Tvrzen´ ı plat´ı pro z´avˇer kaˇzd´eho z axiom˚ u (atom), (true). 2
Pro pravidlo (and): Jestliˇze tvrzen´ı plat´ı pro kaˇzd´y pˇredpoklad pravidla (and), pak tvrzen´ı plat´ı i pro z´avˇer pravidla (and).
3
Pro pravidlo (not): Jestliˇze tvrzen´ı plat´ı pro kaˇzd´y pˇredpoklad pravidla (not), pak tvrzen´ı plat´ı i pro z´avˇer pravidla (not).
Podle principu struktur´aln´ı indukce jsme hotovi.
Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
5/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Pˇr´ıklad Pro kaˇzd´e ϕ ∈ F plat´ı: ϕ m´a stejn´y poˇcet prav´ych a lev´ych z´avorek. ˇ sen´ı: Reˇ 1 Tvrzen´ ı plat´ı pro z´avˇer kaˇzd´eho z axiom˚ u (atom), (true). 2
Pro pravidlo (and): Jestliˇze tvrzen´ı plat´ı pro kaˇzd´y pˇredpoklad pravidla (and), pak tvrzen´ı plat´ı i pro z´avˇer pravidla (and).
3
Pro pravidlo (not): Jestliˇze tvrzen´ı plat´ı pro kaˇzd´y pˇredpoklad pravidla (not), pak tvrzen´ı plat´ı i pro z´avˇer pravidla (not).
Podle principu struktur´aln´ı indukce jsme hotovi.
Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
5/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Princip struktur´aln´ı indukce At’ Σ je libovoln´a koneˇcn´a abeceda. At’ G je koneˇcn´a sada odvozovac´ıch pravidel, kter´a induktivnˇe zad´av´a mnoˇzinu slov L ⊆ Σ∗ . At’ A je mnoˇzina vˇsech axiom˚ u z G . At’ D je mnoˇzina vˇsech deduktivn´ıch pravidel z G . At’ V je nˇejak´a vlastnost slov nad abecedou Σ. K tomu, abychom uk´azali, ˇze kaˇzd´e slovo v mnoˇzinˇe L m´a vlastnost V , staˇc´ı uk´azat:a 1
2
Z´akladn´ı krok: Z´avˇer kaˇzd´eho axiomu z mnoˇziny A m´a vlastnost V . Indukˇcn´ı krok: Pro kaˇzdou instanci libovoln´eho deduktivn´ıho pravidla v mnoˇzinˇe D plat´ı: Jestliˇze vˇsechny pˇredpoklady pravidla maj´ı vlastnost V , potom i z´avˇer tohoto pravidla m´a vlastnost V .
a
Tomu se ˇr´ık´ a: Vlastnost V je invariantn´ı na pr˚ uchod gramatikou G . Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
6/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Plat´ı: 1 Jestliˇ ze plat´ı (siln´y nebo slab´y) princip indukce, plat´ı i princip struktur´aln´ı indukce. 2
Pro kaˇzdou nepr´azdnou abecedu Σ plat´ı: existuje mnoˇzina M ⊆ Σ∗ , kterou nelze zadat induktivnˇe.
Dalˇs´ı poznatky: skripta a sb´ırka ˇreˇsen´ych pˇr´ıklad˚ u.
Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
7/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Plat´ı: 1 Jestliˇ ze plat´ı (siln´y nebo slab´y) princip indukce, plat´ı i princip struktur´aln´ı indukce. 2
Pro kaˇzdou nepr´azdnou abecedu Σ plat´ı: existuje mnoˇzina M ⊆ Σ∗ , kterou nelze zadat induktivnˇe.
Dalˇs´ı poznatky: skripta a sb´ırka ˇreˇsen´ych pˇr´ıklad˚ u.
Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
7/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Pˇr´ıklad (Parket´aˇz triminy z minul´e pˇredn´aˇsky) P(n) = poˇcet parket k vyparketov´an´ı m´ıstnosti rozmˇeru n 1
P(1) = 1.
2
P(n + 1) = 1 + 4 · P(n), n ≥ 1.
ˇ Cili: 1
P(n + 1) − 4 · P(n) = 1, n ≥ 1 (rekurentn´ı rovnice).
2
P(1) = 1 (poˇc´ateˇcn´ı podm´ınka).
Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
8/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Pˇr´ıklad (sloˇzitost algoritmu Bubblesort) Oznaˇcte C (n) poˇcet porovn´an´ı v segmentu (pseudo)k´odu for i:=1 to n for j:= i+1 to n if A[i] > A[j] then swap(A[i],A[j]) endif endfor endfor Potom plat´ı: C (n) = (n − 1) + (n − 2) + · · · + 1 + 0 =
n−1 X
k,
n ≥ 1.
k=0
Tedy C (1) = 0, C (n + 1) = C (n) + n, n ≥ 1. Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
9/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Definice Line´arn´ı rekurentn´ı rovnice k-t´eho ˇr´adu s konstantn´ımi koeficienty je z´apis ak X (n + k) + ak−1 X (n + k − 1) + · · · + a0 X (n) = f (n) kde ak 6= 0. Terminologie: Koeficienty: (re´aln´a nebo komplexn´ı) ˇc´ısla ak , ak−1 ,. . . , a0 Prav´a strana: posloupnost f (n) Pˇr´ısluˇsn´a homogenn´ı rovnice: ak X (n + k) + ak−1 X (n + k − 1) + · · · + a0 X (n) = 0 Charakteristick´a rovnice: ak λk + ak−1 λk−1 + · · · + a0 = 0 Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
10/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Kompletn´ı ˇreˇsen´ı homogenn´ı rovnice 1
Vyˇreˇs´ıme charakteristickou rovnici ak λk + ak−1 λk−1 + · · · + a0 = 0. Koˇreny: λ1 (n´asobnost k1 ), . . . , λr (n´asobnost kr ).
2
Koˇren λ1 n´asobnosti k1 ≥ 1 pˇrid´a k1 r˚ uzn´ych posloupnost´ı do fundament´aln´ıho syst´emu: λn1 ,
n · λn1 ,
n2 · λn1 ,
...,
nk1 −1 · λn1
(analogicky pˇrispˇej´ı koˇreny λ2 , . . . , λr ). 3
Fundament´aln´ı syst´em m´a celkovˇe k r˚ uzn´ych posloupnost´ı, protoˇze k1 + k2 + · · · + kr = k.
4
Kompletn´ı ˇreˇsen´ı homogenn´ı rovnice je line´arn´ı kombinace fundament´aln´ıho syst´emu.
Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
11/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Kompletn´ı ˇreˇsen´ı homogenn´ı rovnice 1
Vyˇreˇs´ıme charakteristickou rovnici ak λk + ak−1 λk−1 + · · · + a0 = 0. Koˇreny: λ1 (n´asobnost k1 ), . . . , λr (n´asobnost kr ).
2
Koˇren λ1 n´asobnosti k1 ≥ 1 pˇrid´a k1 r˚ uzn´ych posloupnost´ı do fundament´aln´ıho syst´emu: λn1 ,
n · λn1 ,
n2 · λn1 ,
...,
nk1 −1 · λn1
(analogicky pˇrispˇej´ı koˇreny λ2 , . . . , λr ). 3
Fundament´aln´ı syst´em m´a celkovˇe k r˚ uzn´ych posloupnost´ı, protoˇze k1 + k2 + · · · + kr = k.
4
Kompletn´ı ˇreˇsen´ı homogenn´ı rovnice je line´arn´ı kombinace fundament´aln´ıho syst´emu.
Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
11/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Kompletn´ı ˇreˇsen´ı homogenn´ı rovnice 1
Vyˇreˇs´ıme charakteristickou rovnici ak λk + ak−1 λk−1 + · · · + a0 = 0. Koˇreny: λ1 (n´asobnost k1 ), . . . , λr (n´asobnost kr ).
2
Koˇren λ1 n´asobnosti k1 ≥ 1 pˇrid´a k1 r˚ uzn´ych posloupnost´ı do fundament´aln´ıho syst´emu: λn1 ,
n · λn1 ,
n2 · λn1 ,
...,
nk1 −1 · λn1
(analogicky pˇrispˇej´ı koˇreny λ2 , . . . , λr ). 3
Fundament´aln´ı syst´em m´a celkovˇe k r˚ uzn´ych posloupnost´ı, protoˇze k1 + k2 + · · · + kr = k.
4
Kompletn´ı ˇreˇsen´ı homogenn´ı rovnice je line´arn´ı kombinace fundament´aln´ıho syst´emu.
Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
11/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Kompletn´ı ˇreˇsen´ı homogenn´ı rovnice 1
Vyˇreˇs´ıme charakteristickou rovnici ak λk + ak−1 λk−1 + · · · + a0 = 0. Koˇreny: λ1 (n´asobnost k1 ), . . . , λr (n´asobnost kr ).
2
Koˇren λ1 n´asobnosti k1 ≥ 1 pˇrid´a k1 r˚ uzn´ych posloupnost´ı do fundament´aln´ıho syst´emu: λn1 ,
n · λn1 ,
n2 · λn1 ,
...,
nk1 −1 · λn1
(analogicky pˇrispˇej´ı koˇreny λ2 , . . . , λr ). 3
Fundament´aln´ı syst´em m´a celkovˇe k r˚ uzn´ych posloupnost´ı, protoˇze k1 + k2 + · · · + kr = k.
4
Kompletn´ı ˇreˇsen´ı homogenn´ı rovnice je line´arn´ı kombinace fundament´aln´ıho syst´emu.
Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
11/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Kompletn´ı ˇreˇsen´ı homogenn´ı rovnice 1
Vyˇreˇs´ıme charakteristickou rovnici ak λk + ak−1 λk−1 + · · · + a0 = 0. Koˇreny: λ1 (n´asobnost k1 ), . . . , λr (n´asobnost kr ).
2
Koˇren λ1 n´asobnosti k1 ≥ 1 pˇrid´a k1 r˚ uzn´ych posloupnost´ı do fundament´aln´ıho syst´emu: λn1 ,
n · λn1 ,
n2 · λn1 ,
...,
nk1 −1 · λn1
(analogicky pˇrispˇej´ı koˇreny λ2 , . . . , λr ). 3
Fundament´aln´ı syst´em m´a celkovˇe k r˚ uzn´ych posloupnost´ı, protoˇze k1 + k2 + · · · + kr = k.
4
Kompletn´ı ˇreˇsen´ı homogenn´ı rovnice je line´arn´ı kombinace fundament´aln´ıho syst´emu.
Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
11/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Odhad partikul´arn´ıho ˇreˇsen´ı pro pravou stranu An · P(n), kde A je ˇc´ıslo a P(n) je polynom 1
2
3
d je n´asobnost A jako koˇrene charakteristick´e rovnice. (N´asobnost 0 znamen´a: A nen´ı koˇren). Odhad partikul´arn´ıho ˇreˇsen´ı: nd · An · p(n), kde p(n) je polynom stejn´eho stupnˇe jako P(n). Koeficienty polynomu p(n) z´ısk´ame z poˇzadavku, ˇze nd · An · p(n) m´a ˇreˇsit danou nehomogenn´ı rovnici.
Pro sloˇzitˇejˇs´ı pravou stranu lze pouˇz´ıt princip superposice.
Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
12/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Odhad partikul´arn´ıho ˇreˇsen´ı pro pravou stranu An · P(n), kde A je ˇc´ıslo a P(n) je polynom 1
2
3
d je n´asobnost A jako koˇrene charakteristick´e rovnice. (N´asobnost 0 znamen´a: A nen´ı koˇren). Odhad partikul´arn´ıho ˇreˇsen´ı: nd · An · p(n), kde p(n) je polynom stejn´eho stupnˇe jako P(n). Koeficienty polynomu p(n) z´ısk´ame z poˇzadavku, ˇze nd · An · p(n) m´a ˇreˇsit danou nehomogenn´ı rovnici.
Pro sloˇzitˇejˇs´ı pravou stranu lze pouˇz´ıt princip superposice.
Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
12/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Odhad partikul´arn´ıho ˇreˇsen´ı pro pravou stranu An · P(n), kde A je ˇc´ıslo a P(n) je polynom 1
2
3
d je n´asobnost A jako koˇrene charakteristick´e rovnice. (N´asobnost 0 znamen´a: A nen´ı koˇren). Odhad partikul´arn´ıho ˇreˇsen´ı: nd · An · p(n), kde p(n) je polynom stejn´eho stupnˇe jako P(n). Koeficienty polynomu p(n) z´ısk´ame z poˇzadavku, ˇze nd · An · p(n) m´a ˇreˇsit danou nehomogenn´ı rovnici.
Pro sloˇzitˇejˇs´ı pravou stranu lze pouˇz´ıt princip superposice.
Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
12/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Odhad partikul´arn´ıho ˇreˇsen´ı pro pravou stranu An · P(n), kde A je ˇc´ıslo a P(n) je polynom 1
2
3
d je n´asobnost A jako koˇrene charakteristick´e rovnice. (N´asobnost 0 znamen´a: A nen´ı koˇren). Odhad partikul´arn´ıho ˇreˇsen´ı: nd · An · p(n), kde p(n) je polynom stejn´eho stupnˇe jako P(n). Koeficienty polynomu p(n) z´ısk´ame z poˇzadavku, ˇze nd · An · p(n) m´a ˇreˇsit danou nehomogenn´ı rovnici.
Pro sloˇzitˇejˇs´ı pravou stranu lze pouˇz´ıt princip superposice.
Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
12/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Odhad partikul´arn´ıho ˇreˇsen´ı pro pravou stranu An · P(n), kde A je ˇc´ıslo a P(n) je polynom 1
2
3
d je n´asobnost A jako koˇrene charakteristick´e rovnice. (N´asobnost 0 znamen´a: A nen´ı koˇren). Odhad partikul´arn´ıho ˇreˇsen´ı: nd · An · p(n), kde p(n) je polynom stejn´eho stupnˇe jako P(n). Koeficienty polynomu p(n) z´ısk´ame z poˇzadavku, ˇze nd · An · p(n) m´a ˇreˇsit danou nehomogenn´ı rovnici.
Pro sloˇzitˇejˇs´ı pravou stranu lze pouˇz´ıt princip superposice.
Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
12/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Kompletn´ı ˇreˇsen´ı nehomogenn´ı rovnice 1
Seˇcteme kompletn´ı ˇreˇsen´ı homogenn´ı rovnice a partikul´arn´ı ˇreˇsen´ı.
2
Jsou-li zad´any poˇc´ateˇcn´ı podm´ınky: nakonec urˇc´ıme koeficienty line´arn´ı kombinace fundament´aln´ıho syst´emu.
Shrnuto: 1 Siln´ a analogie s line´arn´ımi diferenci´aln´ımi rovnicemi. 2
Diferenˇcn´ı a sumaˇcn´ı poˇcet, viz napˇr. J. Kauck´y, Kombinatorick´e identity , Veda, Bratislava, 1975 W. G. Kelley a A. C. Peterson, Difference Equations: An Introduction with Applications, Academic Press Inc., New York, 1991 Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
13/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Kompletn´ı ˇreˇsen´ı nehomogenn´ı rovnice 1
Seˇcteme kompletn´ı ˇreˇsen´ı homogenn´ı rovnice a partikul´arn´ı ˇreˇsen´ı.
2
Jsou-li zad´any poˇc´ateˇcn´ı podm´ınky: nakonec urˇc´ıme koeficienty line´arn´ı kombinace fundament´aln´ıho syst´emu.
Shrnuto: 1 Siln´ a analogie s line´arn´ımi diferenci´aln´ımi rovnicemi. 2
Diferenˇcn´ı a sumaˇcn´ı poˇcet, viz napˇr. J. Kauck´y, Kombinatorick´e identity , Veda, Bratislava, 1975 W. G. Kelley a A. C. Peterson, Difference Equations: An Introduction with Applications, Academic Press Inc., New York, 1991 Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
13/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Kompletn´ı ˇreˇsen´ı nehomogenn´ı rovnice 1
Seˇcteme kompletn´ı ˇreˇsen´ı homogenn´ı rovnice a partikul´arn´ı ˇreˇsen´ı.
2
Jsou-li zad´any poˇc´ateˇcn´ı podm´ınky: nakonec urˇc´ıme koeficienty line´arn´ı kombinace fundament´aln´ıho syst´emu.
Shrnuto: 1 Siln´ a analogie s line´arn´ımi diferenci´aln´ımi rovnicemi. 2
Diferenˇcn´ı a sumaˇcn´ı poˇcet, viz napˇr. J. Kauck´y, Kombinatorick´e identity , Veda, Bratislava, 1975 W. G. Kelley a A. C. Peterson, Difference Equations: An Introduction with Applications, Academic Press Inc., New York, 1991 Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
13/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Kompletn´ı ˇreˇsen´ı nehomogenn´ı rovnice 1
Seˇcteme kompletn´ı ˇreˇsen´ı homogenn´ı rovnice a partikul´arn´ı ˇreˇsen´ı.
2
Jsou-li zad´any poˇc´ateˇcn´ı podm´ınky: nakonec urˇc´ıme koeficienty line´arn´ı kombinace fundament´aln´ıho syst´emu.
Shrnuto: 1 Siln´ a analogie s line´arn´ımi diferenci´aln´ımi rovnicemi. 2
Diferenˇcn´ı a sumaˇcn´ı poˇcet, viz napˇr. J. Kauck´y, Kombinatorick´e identity , Veda, Bratislava, 1975 W. G. Kelley a A. C. Peterson, Difference Equations: An Introduction with Applications, Academic Press Inc., New York, 1991 Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
13/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Definice (O-notace) ˇ At’ f , g : N → R jsou funkce. Rekneme, ˇze f ∈ O(g ) (nˇekdy i f (n) ∈ O(g (n))) (ˇcteme: f je tˇr´ıdy velk´e O g ),a kdyˇz existuj´ı C a n0 tak, ˇze plat´ı |f (n)| ≤ C · |g (n)|, a
pro vˇsechna n ≥ n0
Zavedl Paul Bachmann v roce 1892.
Pˇr´ıklady 1
f ∈ O(f ) plat´ı vˇzdy.
2
6n3 − 127n2 + πn ∈ O(n3 ).
3
3n ∈ / O(np ), pro kaˇzd´e p ∈ N.
4
n! ∈ O(nn ). Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
14/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Vˇeta At’ f , g : N → R jsou funkce a at’ limita |f (n)| n→+∞ |g (n)| lim
existuje a je koneˇcn´a. Pak f ∈ O(g ). Pozor! Obr´acen´ı t´eto vˇety neplat´ı. Pro f (n) = sin n, g (n) = 1 plat´ı f ∈ O(g ), ale limn→+∞
|f (n)| |g (n)|
neexistuje.
Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
15/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Hierarchie (asymptotick´e) sloˇzitosti 1
2
3
Polynomi´aln´ı: napˇr´ıklad O(n4 ). Slogan: polynomi´alnˇe sloˇzit´e algoritmy jsou “rychl´e”. Pˇr´ıklad: Bubblesort je O(n2 ). Exponenci´aln´ı: napˇr´ıklad O(2n ). Slogan: exponenci´alnˇe sloˇzit´e algoritmy jsou “pomal´e”. Pˇr´ıklad: test prvoˇc´ıselnosti postupn´ym dˇelen´ım (Eratosthenovo s´ıto). A ˇrada dalˇs´ıch tˇr´ıd sloˇzitosti. . .
Viz napˇr´ıklad T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, 2001
Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
16/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Strategie Divide and Conquer Probl´em velikosti n je rozdˇelen na a podprobl´em˚ u velikosti bn a pˇri dˇelen´ı je “spotˇrebov´an ˇcas” f (n). Celkov´y ˇcas T (n) je pak d´an vztahem n T (n) = a · T ( ) + f (n), n ≥ 1. b Pˇr´ıklad (Merge-Sort) Vstup: pole ˇc´ısel ~x = x[1], . . . , x[n]. V´ystup: setˇr´ıdˇen´e pole ˇc´ısel ~x . ( c pro n = 1 Sloˇzitost: T (n) = 2T (n/2) + cn pro n > 1.
Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
17/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Rovnice Divide and Conquer n T (n) = a · T ( ) + f (n), b kde a ≥ 0, b > 0 jsou pˇrirozen´a ˇc´ısla. Pokud n = b k , pak plat´ı
n ≥ 1,
n T (n) = a · T ( ) + f (n) b n n 2 = a · T ( 2 ) + a · f ( ) + f (n) b b n n n 3 2 = a · T ( 3 ) + a · f ( 2 ) + a · f ( ) + f (n) b b b .. . k−1
X n n = a · T( k ) + aj · f ( j ) b b k
j=0
Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
18/19
Struktur´ aln´ı indukce Rekurentn´ı rovnice Rekurentn´ı rovnice Divide and Conquer
Divide and Conquer, pokraˇc. Pokud n = b k , plat´ı k
T (n) = a · T (1) +
k−1 X
aj · f (
j=0
n ) bj
Vˇeta At’ T : N → R je rostouc´ı funkce, kter´a pro vˇsechna n dˇeliteln´a pˇrirozen´ym ˇc´ıslem b ≥ 2 splˇ nuje rekurentn´ı rovnici ( c pro n = 1 T (n) = , a · T (n/b) + cn pro n > 1. kde a ≥ 1, c > 0 jsou re´aln´a ˇc´ısla. Pak plat´ı: T (n) ∈ O(nlogb a ), kdyˇz a > b, T (n) ∈ O(n log n), kdyˇz a = b. Jiˇr´ı Velebil: Y01DMA
23. u ´nora 2010: Struktur´ aln´ı indukce
19/19
