DMA Flashcards
1
Q
A deli B - a|b
A
Pokud b=ka, k je cele cislo, a je faktor, b je delitelne a
2
Q
Jestlize a|b a b|c, pak
A
a|c
3
Q
a|b p.t.k
A
abs(a) | abs(b)
4
Q
Jestlize a|b, b/=0, pak
A
abs(a) <= abs(b), tedy jenom mensi cislo deli vetsi cislo
5
Q
Jestlize a|b a zaroven b|a
A
Pak a=b
6
Q
Definice prvocisla a slozeneho cisla
A
Prvocislo je takove cislo, ktere deli pouze ono samo a 1
slozene cislo neni prvocislo
7
Q
Spolecny delitel d cisel a,b
A
Je pokud d|a, d|b
8
Q
Spolecny nasobek d cisel a,b
A
Je pokud a|d, b|d
9
Q
Nejvetsi spolecny delitel
Nejmensi spolecny nasobek
A
Nejvetsi prvek mnoziny spolecnych delitelu, je to gcd(a,b)=d pro nenulova a,b, jiank je to 0
analogicky lcm(a,b)=d
Tyto vztahy plati i pro abs hodnoty
10
Q
Nesoudelna cisla
A
Rekneme, ze cisla jsou nesoudelna, pokud gdc(a,b)=1
11
Q
lcm(a,b) * gcd(a,b)
A
abs(a) * abs(b)
12
Q
Zbytek pri deleni cisla a cislem d je r
A
r = a mod d
a = qd + r, kde r je zbytek a q je castecny podil
13
Q
A beze zbytku deli b (a|b) v Z p.t.k.
A
b mod abs(a) = 0, tedy b je beze zbytku delitelne ackem.
14
Q
Eukliduv algoritmus hledani gcd(a,b)
A
While b/=0
r = a mod b
a = b
b = r
Output a
15
Q
Bezoutova veta/rovnost
A
Necht a,b jsou cela cisla. Pak existuji A, B cela tak, ze
gcd(a,b) = Aa + Bb
16
Q
Euklidovo lemma
A
Jestlize d|(ab) a zaroven gcd(a,d)=1, pak d|b
Pokud tedy d deli ab, ale d je nesoudelne s a, pak musi tedy delit b
17
Q
Jestlize prvocislo deli nejaky soucin ruznych cisel, tedy
p|(a1a2a3…an)
A
Pak existuje takove ai, ze p|ai
18
Q
Pro kazde prirozene cislo x vetsi nebo rovno dvema, existuje prvocislo p tak…
A
Ze p|x
19
Q
Fundamentalni veta aritmetikz, prvociselny rozklad
A
Pro libovolne prirozene cislo n, existuje seznam prvocisel (p1,p2…pm) a seznam exponentu (k1,…km) tak, ze
n = p1^k1 * p2^k2… * pn^kn
tedy cislo jde rozlozit na prvocisleny rozklad
20
Q
Cisla a a b jsou kongruentni modulo n p.t.k
A
a == b (mod n) p.t.k n|(b-a)
Tzn cisla a a b ve svete modulo n davaji stejnou hodnotu
1 == 8 (mod 7)
21
Q
Ekvivalentni podminky pro kongruenci
A
- a == b (mod n)
- a mod n = b mod n
- b = a + kn, tedy existuje cislo b je jenom nejaky k-nasobek cisla n s posunutim, k je cele cislo
22
Q
Jak najit vsechna cisla, ktera jsou kongruentni s cislem b pri zadanem n?
A
Hledam vsechny mozne posunu tohoto cisla b o n, protoze po modn daji stejnou hodnotu
{b + kn}, k je cele
23
Q
Jestlize a==u (mod n) a b==v (mod n), pak
A
a+-b==u+-v (mod n)
24
Q
Jestlize a == u (mod n), pak pro a^k…
A
a^k = u^k (mod n)
tedy mocnim to stejne a vzdy se vratim modulem zpatky o stejny kus
25
Definice inverzniho cisla
Rekneme, ze b je inverzni cislo k a modulo n p.t.k.
a*b = 1 (mod n)
26
Podminka existence inverzniho cisla
Necht n je prirozene cislo, Rekneme, ze k cislu a existuje inverzni cislo b ve svete modulo n p.t.k. gcd(a,n)=1
27
Postup hledani inverzniho cisla v modulo n
TODO
28
Kolik muze byt inverznich prvku
Vicero, kdyz a ma inverzni prvek x, pak y je inverzyni prvek k a p.t.k
x == y (mod n)
29
Mala Fermatova veta
Nech n je prvocislo. Je-li a nesoudelne s n, pak plati
a^n-1 == 1 (mod n)
a^n == a (mod n), tedy cislo ve svete modula je furt to stejny, i kdybych ho vzal n-krat
Priklad
Spocitejte 136^182 v n=13.
1. 13 je prvocislo OK
2. nahradim velky cislo je kongruencnim v mod 13 (proste vezmu zbytek po deleni jako 136 mod 13 = 6)
3. 6^182
4. rozlozim 6^182 = 6^(a*(n-1)), tedy 6^182 = 6^12a
5. najdu rozklad 182/12 = 15 + 2 => 6^(12*15+2) = 6^2*(6^(12*15))
6. JENOMZE gcd(6,13)=1 A POUZIJU MFV => 6^12 v n=13 JE 1
7. tedy 6^2 * 6^1 = 36 mod 13 = 10.
30
Pokud pro nesoudelna n,m a cela a,b plati, ze a==b(mod n), a==b(mod m), pak...
a==b(mod n*m)
31
Test na prvocislo
Pro zadane cislo x ho zkousim delit 2,3,4...(x^1/2)
tedy pokud nejde vydelit cisly od 2 do odmocniny z x, pak je to prvocislo
32
Operace v telesu
Definuji se stejne jako obycejne operace, akorat se pak musi udelat modulo n
33
Inverzni cislo v telesu Z
X je inverzni cislo k a p.t.k xa = 1 v telesu Z (neboli 1 mod Z).
Pak x = a^-1 a rekneme ze a je invertibilni cislo
34
Jak ze zaporneho cisla udelat cislo telesa Z (neboli mod n)
Pricitam n tak dlouho, dokud nebudu mit kladnou hodnotu
Tedy -5 v Telesu 7 je
-5 + 7 = 2
Nebo -15 v telesu 4 je
-15 + 4 + 4 + 4 + 4 = 1
35
Opacny prvek v telesu Z
Prvek b je opacny k prvku a p.t.k.
a+b = 0 v Z
b = -a
-a = n - a // tedy pro vypocet opacneho prvku v Z, staci ho odecist od rozmeru modula
36
Diofanticka rovnice
Je to lib. rovnice tvaru ax + by = c, kde nezname jsou x,y abc jsou koeficienty
37
Kdy ma diofanticka rovnice reseni
p.t.k c = k gcd(a,b),
tedy c je nasobkem gcd(a,b)
38
Homogenni rovnice
Je to rovnice = 0
39
Existence homogenniho reseni pri partikularnim
Pokud pro rovnici ax+by=c existuje nejake partikularni reseni xp,yp
pak existuje i jine reseni xh,yh, pokud je muzu posunout
(x0,y0) = (xp + xh) + (yp +yh)
tedy reseni je partikularni (nejake co resi) plus posun homogenniho reseni
40
Hledani homogennich koeficientu z rovnice
nebo podle tabulky hledani gcd(x,y)
treba rovnice
2x + 5y = 0
1. prohodim koeficienty
x = 5k
y = 2k
2. u y zmenim znamenko
vysledek x = 5k, y = -2k, k je cele
koeficienty jsou u radku, kdy jsem skoncil 0
41
Linearni kongruence
rovnice typu
ax == b(modn)
b = ax + mn
42
Reseni linearni kongruence (rovnice)
Treba 45x == 9 (mod 231)
9 = 45x + 231n, tedy je to diafanticka rovnice s promennymi x a n.
Reseni ex p.t.k 9 je nasobkem gdc(231, 45).
Hledam tabulku gcd (ale neresim y sloupec, ten me nezajima)
Kdyz skoncim u radku, ktery zacina 0 => je to homogenni reseni
POTOM vytvorim radek tak, aby zacinal 9 => pak koeficient u toho je partikularni reseni. Neni to ale jedine reseni.
Vysledek je x = part. + homogenni*k. Za k dosazuju 1,2,3... tak dlouho, dokud je vysledek v modulo n, pak se dostanu do cyklu
Reseni existuje nekolik (dokud nenarazime na stenu modulo) a pocet reseni je gcd(n, a) v pripade lin. kongruence ax==b(modn)
43
Relace definice
Necht A,B jsou libovolne mnoziny. Pak podmnozina R(AxB) se nazyva relace. Jestlize (a,b) patri do R, pak a je v relaci R s b
44
Sjednoceni, prunik, rozdil, skladani vice relaci...
Sjednoceni R1, R2 je takva relace, ze a(R1 spolu s R2)b p.t.k. a je v realci R1 s b NEBO v realci v R2. // tedy je to nebo
Prunik je, ze obe relace musi platit zaroven. // spojka i
Rozdil je, ze nesmi platit druha relace. // spojka ale ne
Skaldani je retezeni za sebou. // a pak
Priklad:
R1 - mesta do kterych se dostanu vlakem
R2 = mesta do kterych se dostanu busem
Sjednoceni = mesta do kterych se dostanu vlakem NEBO busem
Prunik = mesta do kterych se dostanu vlakem i busem
Rozdil R1-R2 = mesta do kterych se dostanu vlakem ale NE busem
Skladani = mesta do kterych se dostanu vlakem A PAK busem, tady ale potrebuju tri mesta, sjednoceni relaci VZDY potrebuje zprostredkovatele
45
Inverzni relace
R^-1, bere prohozenou dvojici (b,a) a posila je R^-1 relaci na (a,b).
bR^-1a p.t.k. aRb
46
Ctyri vlastnosti relaci
1. Reflexivita p.t.k. pro vs. prvky a z A plati: aRa (relace sam se sebou)
2. Symetrie p.t.k.: a,b je z A a zaroven aRb, pak bRa (oba prvky patri do A a aRb, pak i bRa)
3. Antisymetrie p.t.k Jestlize aRb a bRa => a=b
4. Tranzitivita: aRb a bRc => aRc
47
Dokazovani vztahu relaci
Bud protiprikald uvedu ze neplati,
Nebo zvolim lib. a,b s predpokladem a dojdu k zaveru relace
48
Castecne usporadani
Je to vlastni poddruh relace, ktere splnuje tri vlastnosti
RAT - reflexivitu, antisymetrii, tranzitivitu
Treba a|b
Inverze castecneho usporadani je castecne usporadani
49
Hesseuv diagram
Diagram relaci, kde zacnu od nejmensiho prvku relace a pripojuju k nemu postupne vzrustajici prvky az nahoru
Je to v podstate topologicke usporadani
50
Nejvetsi/nejmensi prvek Hesseuva diagramu
Spicka nahore/dole je to prvek ktery je vetsi/meni nez vsechny ostatni, je pouze jeden
Je to zaroven i maximalni/minimalni prvek a jsou jedine
51
Maimalni/minimalni prvek Hesseuva diagramu
Konec/zacatek kazde vetve/ neexistujou relace vetsi/mensi nez on. Muze jich byt nekolik
52
Linearni usporadani
Je to takove castecne usporadani, jehoz vsechny prvky jsou porovnatelne mezi sebou a da se vytvorit souvisla cesta (linearizace), tedy graf je pouze retez prvku od nejmensi relace k nejvetsi
53
Kazde castecne uspoaradni se da...
Linearizovat, postupuju po jednom patre a skrtam minima
54
Lexikograficke usporadani
Je to usporadain jako slovnik
Porovnavam prvek po prvku dokud nenarazim na vetsi/mensi a prohazuju
55
Dobre usporadana mnozina definice
Je p.t.k. je linearni a ma nejmensi prvek.
Napriklad N s relaci <= je dobre usporada mnozina
1 je nejmensi prvek a da se linearizovat do ciselne osy
56
Relace ekvivalence
Takova relace ktera splnuje RST
Reflexivitu, symetrii, tranzitivitu
treba =, nebo rovnost abs hodnot..., nebo byt kongruentni modulo n (protoze cisla v telesu se mi rozpadnou na tridy ekvivalence, tedy cislo +k nasobek modulo je jedna trida ekvivalence...)
57
Trida ekvivalence
Trida ekvivalence prvku a vzhledem k relaci R
[a]R = {b z A | aRb}
tedy je to mnozina prvku, ktere jsou v relaci R s a
58
Vlastnosti prvku ze tridy ekvivalence
1. Pokud dva prvky patri do stejne tridy ekvivalce => jsou v relaci mezi sebou
2. Pokud je prvek ze tridy ekvivalence v relaci s nejakym nahodnym prvkem => pak i nahodny prvek patri do tridy ekvivalence.
3. Vychozi bod tridy ekvivalence je zamenitelny, tedy pro vs. b z [a]R plati: [a]r = [b]r, tedy trida ekvivalence b je stejna jako trida ekvivalence a (jsou nahraditelny a stejne)
4. Pro kazde prvky (a,b) plati: aRb p.t.k [a]r = [b], prvky jsou v relaci, pokud maji stejne tridy ekvivalence.
5. Tridy ekv. orvku (a,b) jsou bud totozne, nebo naprosto ruzne bez pruniku
59
Rozklad mnoziny A
Je to rozbiti mnoziny na disjunktni tridy ekvivalence
60
Zobrazeni/funkce
Je druh relace. Rekneme, ze f je zobrazeni p.t.k pro vs. a z prostoru hodnot priradime nejaka b z prostoru obrazu. Tedy (a,b) je v relaci f. Tedy f(a)=b je zobrazeni - druh relace mezi prvky
61
Funkce ma inverzi p.t.k.
Je bijekce
62
Jak velikost mnozin zavisi na existenci bijekce?
Jestli je mnozina A vetsi nez B, pak zobrazeni nemuze byt proste (nema kam pridadit prvky navic aby se neopakovaly)
Jestli je mnizina A menzi nez B, pak zobrazeni nemuze byt na
(dodjou prvky mnoziny A a nepokrzjou vsechny z B)
Tedy jestli existuje bijekce na mnozinach => pak maji STEJNY POCET PRVKU
63
Jestlize |A| <= |B| a zaroven |B| <= |A| pak
|A| = |B|
64
Mnozina je konecna
Kdyz je prazdna, nebo se da ocislovat jeji pocet prvku KONECNYM CISLEM M
65
Podmnozina konecne mnoziny
Je konecna mnozina
66
Nekonecna mnozina
Nejde promitnout na konecnou mnozinu,
Treba N je nejmensi nekonecna mnozina
67
Spocetna mnozina
Existuje mezi ni a N bijekce
Je nekonecna, ale dokazu ocislovat jeji prvky prvky N, je to treba N, Z, NxN, ZxZ, Q
Pokud nedokazu ocislovat, pak je mnozina nespocetna
Treba R, nebo <0,1)
68
Sjednoceni nekonecnych mnozin vliv na mohutnost
Mohunost se nemeni
|N| = nekonecno
|NxN| = nekonecno + nekonecno = nekonecno...
Ale neplati, ze NxN je vetsi nez N
69
Podmnozina nekonecne mnoziny
Existuje i takova, ze ma stejnou mohutnost jako cela nadmnozina, tedy nekonecno
70
Cantorova veta
Pocet prvku mnozin je mensi nez pocet podmnozin jejich prvku
|A| < |P(A)|, kde P(A) je potencni mnozina - mnozina vsech podmnozin prvku A
71
Postup indukce
Mam vyrok: pro nejake n plati neco.
1. nulty krok: n=nejmensi prvek mnoziny plati?
pokud ano
2. Vyrok uz beru jako ze by platil, tedy vim, ze pro nejakej n plati neco.
3. Vytvorim (n+1) rozvoj a zkratim ho tvrzenim z predpokladu pro n-ty prvek.
4. Podivam se, jestli jsem dospel k zaveru, ze pro (n+1) plati neco jako pro n ale pro (n+1).
Tedy pokud neco plati pro n, pak ti plati pro n+1
72
Slaby princip indukce
Predpoklad neco plati pro n, pak ukazu, ze to plati pro n+1, tim dojdu k zaveru, ze to plati pro vsechna n.
73
Silny princip indukce
Vyrok plati pro n0, pak plati pro (n+1), ale musim znat vsechny predchozi stavy
74
Pouziti silneho principu indukce
Napr pri dokazovani ze Fibonacci(n) < 2^n.
Fibonacci ma svoje vlsastni predpoklady
F(0) = F(1) = 1
Fn+1 = Fn + Fn-1
Tedy v indukci potrebuju zavest nekolik indukcnich predpokladu, tedy se divam na prvky predchozi.
Vysledkem indukce bych chtel dokazat, ze plati F(n+1) < 2^(n+1), ale Fn+1 se spocita jako Fn+Fn-1, tedy chci dokazat, ze
F(n) + F(n-1) < 2^(n+1).
Tady vidim, ze budu potrebovat predoklady pro F(n) a F(n-1). Takze zavedu silnou indukci pro oba predoklady, tedy
F(n) < 2^n A ZAROVEN F(n-1) < 2^(n-1).
Pak az zacnu pocitat indukci jako n+1 prvek...
75
Induktivni definice mnozin
Sestavim mnozinu prvku tak, ze rucne nasazim zakladni prvky, a dalsim krokem s jeji pomoci definuju operace, jak se dostat na vsechny dalsi prvky
Priklad:
1. Jednicka lezi v M
2. p lezi v M => pak i p + 1 lezi v M (protoze 1 tam uz lezi a p taky z predpokladu)
Suda cisla
1. 2 lezi v M (jako zakladni sude cislo)
2. p lezi v M => p +- 2 lezi v M
76
Posloupnost T
Je zobrazeni dane jako
1. funkcni predpis T(n) = 2n +1
2. n-ty clen: n = 2n + 1
3. rekurentni predpis : n0 = 2, n1 = 3, n+1 = n - (n-1)...
4. zavorky [2n + 1] pro n od 0 do nekonecna
77
Asymptoticky rust posloupnosti
1. a lezi v o(b) = a je zanedbatelne male oproti b (shora omezene)
2. a lezi v w(b) = naopak
3. a je O(b) = porovnatelne, ale b je o konstantu vetsi
4. ak je theta(b) = jsou srovnatelne
78
Jak rozhodnout a vzajemnem vztahu dvou funckci asymptoticky pdoel definice
Funkce a,b.
1. lim a/b v nekonecnu = 0 => a lezi v o(b)
2. lim a/b v nekonecnu = nekonecno => b lezi v w(b)
3. a <= kb (o konstantu) => a lezi v O(b)
4. lim a/b v nekonecnu = konst => a lezi v theta(b)
79
Srovnani asymp. rychlosti prikladu funkci
logx
x^n mocninna
n^x exponencialni
x!
x^x
80
Rychlost slozene funkce je dana Thetou funkce...
clenem s nejvetsim narustem
81
Rekurentni rovnice
Je to nekonecne mnoho rovnice s nekonecne mnoha resenimi, zadani rekurentne pro n-ty clen
82
Linearni rekurentni rovnice radu k
Je libovolna rovnice ve tvaru
a(n+k) + Suma (i od 0 do k-1) z c(i)*(n)*a(n-1) = bn.
takze treba rovnici a(n+1) = 2an - 1
83
Postup sestaveni lin. rek. rovnice
1. Vsechny poloupnost (vysky a(n)) prevedu na jednu stranu a zbytek necham na prave strane.
2. Pokud mam index n-1 a niz, tak o tolik u vsech posloupnosti posunu index nahoru, aby nejnizsi index zacinal n. A o kolik jsem posunul indexy nahoru, o tolik snizim rozsah
tedy priklad
F(n+1) = F(n) + F(n-1), pro n>=1
1. F(n+1) - F(n) - F(n-1) = 0, pro n>=1 , prevod nalevo
2. F(n+2) - F(n+1) - F(n) = 0, pro n>=0, posun indexu
84
Pocatecni podminky
Je soustava zadanych rovnic na zacatku
Pocet podminek je stejny jako pocet parametru v dane rovnici
napr fibonacci ma dva parametry n a n-1, tedy musi mit dve poc. podminky
85
Homogenni rek. rovnice
Je takova, kde na jednu stranu prevedeme vsechny posloupnosti a polozime je 0. Tedy v puvodni rovnici vymazu celou konstantni b(n)
86
Reseni rek. lin. rovnice se sklada z...
homogenniho reseni + partikularniho
87
Mnozina reseni lin. rek. rovnice radu k je...
lin. prostor dimenze k
88
Lin. rek. rovnice s konst. koeficienty
Je rovnice tvaru, ze zadny koeficient neobsahuje ciste n (bez posloupnosti)
priklad:
a(k+1) = 2a(k) - 1 // tady jsou jen posloupnosti a konstanty, ale zadne ciste n.
89
Postup nalezeni obecneho reseni
1. Prevedu vsechny posloupnosti na jednu stranu
2. Polozim rovnost 0 (homogenni rovnice)
3. Cleny a(k) nehradim lambdami. Pokud je tam (k+1,2,3...) tak je to lambda na ten koeficient - l^2, l^3... Ale clen jenom a(k) je lambda na nultou.
4. Vyresim rovnici l^0 + l^1 + l^2... = 0
5. Dostanu reseni lambda=neco.
6. Toto neco je tzv charakteristicke cislo a tvori bazi posloupnosti., tedy je to {neco^n} pro n od 0 do nekonecna
7. Obecne reseni je tvoreno geometrickou posloupnosti vlastnich cisel
Tedy obecne reseni je tvaru
a(n) = A* lambda^n a jsou to vsechny nasobky vektoru z baze
Kdyby bylo vic ruznych vlastnich cisel, pak obe tvori bazi posloupnosti, ktere resi rovnici. Napr jsem nasel dve ruzne lambdy = x,y
Pak baze je [{x^n}, {y^n} pro n od 0 do nek]
PAK OBECNE RESENI JE LINEARNI KOMBINACE VEKTORU BAZE, COZ DAVA
u*x^n + v*y^n = N-ty clen posloupnosti
JELIKOZ VLASTNI CISLA TVORI BAZI, MUSI JEJIH POCET BYT STEJNY JAKO RAD POSLOUPNOST (K) A BYT LIN NEZAVISLE
Jestli mam vlastni cisla stejne ale velke nasobnosti (naprk lambda = 1 trojnasobne, ale ja potrebuju 3 vektory do baze), tak sestavim posloupnosti jako lambda^n, n*lambda^n, n*n*lambda^n... tak dlouho, dokud nedostanu nutny pocet vektoru...
tedy pri lambda=1 3x sestavim obecne reseni jako
a(n) = v*(1^n) + u(n*1^n) + w(n*n*1^n)
Pokud mam pocatecni podminky, napr ze a(2) = 5 at...
tak do obecneho reseni za ten koeficient (n) dosadim 2 a resim tuto rovnici, nebo soustavu rovnic s pocatecnimi podminkami, z toho mi vypadnou u,v,w.. a sestavim uz plne obecne reseni bez u,v,w a reseni je PAK JEDINE
90
Postup nalezeni partikularniho reseni
1. Zamerim se na pravou stranu a podivam se, co to je
2. Zkusim rozpoznat pravou stranu jako typovy priklad (treba polynom * geometricka posloupnost: -9n * 2^n), polynom stupne k odhadnu stejnym stupnem polynomem atd...
3. Polozim Levou stranu stejnym typovym polynomem, treba (An+B) * 2^n // tedy polynom s geom. posloupnosti
4. Tento typovy polynom dosadim do leve casti zadane rek. rovnice.
5. Dosadim a roznasobim, spocitam co mi odhadujici polynom v puvodni rovnici.
6. Tato rovnice se musi rovnat i prave strance (tedy -9n*2^n).
7. Porovnam koeficienty n a konstanty a zjistim ze napr A=3, B=-2.
8. Partikularni reseni pak ma tvar (An+B)*2^n = (3n-4)*2^n.
9. Spojim to s obecnym resenim a mam hotovy celkovy vysledek.
POKUD ALE GEOMETRICKA POSLOUPNOST MI VYSLA STEJNA JAKO NEJAKY KOREN CHAR. POLYNOMU TAK
Pridam "ochranny" prvek do odhadujiciho polynomu tak, ze to vynasobim n tolikrat, kolik je prekryvu s korenem (asi nasobnosti?)
Tj pokud char. cislo homogenni rovnice mi vyslo 2 A ZAROVEN na prave strane se mi objevuje 2^n, tak partikularni reseni upravim tak, ze odhadujici polynom (An+B)*2^n jeste vynasobim n^k, kde k je nasobnost char. cisla
Pokud prava strana je soucet dvou funkci, tak to resim stejne, akorat i odhadujici polynom poskladam jako soucet dvou (jako kdybych resil dva pripady zvlast)
Priklad
Prava strana = 6*2^n - 12
Odhadujici polynom se bude skladat ze dvou casti jako soucet:
6 - odhadnu konstantnim polynomem A
2^n - odhadnu stejnou geom. radou
-12 - odhadnu konst polynomem B
Tedy muj odhad: A*2^n + B a dal to resim jako normalni priklad
TRIK KDYZ NA PRAVE STRANE NENI GEOM. RADA => udelam ji jako (1^n) MUSIM ALE DAVAT POZOR JESTLI GEOM. RADA NENI STEJNA JAKO CHAR CISLO
91
Masters theorem
Pro funkci zadanou jako
f(x) = a*f(x/b) + cn^d //tedy rozdel a panuj algoritmus
jsou tri druhy asymp. chovani v nekonecnu
1. Jestlize a>b^d => theta(n^(log(b)a)
2. Jestlize a=b^d => theta(n^d * log(n))
3. Jestlize a < b^d => theta(n^d)
Tedy funkce se chova podle nejrychlejsiho clenu a ja se rozhoduju, jestli prvni clen je vetsi, stejny, nebo mensi nez nejaky polynom.
Pokud a > nez pridany polynom -> funkce si toho nevsimne a chova se jako pred tim sama
Nebo jsou cleny stejne a pak se nasobi cleny
Nebo je pridavny zasah je tak velky, ze se funkce chova jen podle nej
92
Princip inkluze a exkluze pro vypocet poctu prvku sjednoceni mnozin
|A sjednoceno s B| = |A| + |B| - |A prunik B|
tedy je to pocet prvku A, pocet prvku B MINUS ALE JEJICH PRUNIK, protoze ten jsem mohl nahodou zapocitat v obou pripadech
