Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Státnice > DMA > Flashcards

DMA Flashcards

1
Q

A deli B - a|b

A

Pokud b=ka, k je cele cislo, a je faktor, b je delitelne a

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Jestlize a|b a b|c, pak

A

a|c

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

a|b p.t.k

A

abs(a) | abs(b)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Jestlize a|b, b/=0, pak

A

abs(a) <= abs(b), tedy jenom mensi cislo deli vetsi cislo

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Jestlize a|b a zaroven b|a

A

Pak a=b

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Definice prvocisla a slozeneho cisla

A

Prvocislo je takove cislo, ktere deli pouze ono samo a 1
slozene cislo neni prvocislo

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Spolecny delitel d cisel a,b

A

Je pokud d|a, d|b

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Spolecny nasobek d cisel a,b

A

Je pokud a|d, b|d

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Nesoudelna cisla

A

Rekneme, ze cisla jsou nesoudelna, pokud gdc(a,b)=1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

lcm(a,b) * gcd(a,b)

A

abs(a) * abs(b)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Eukliduv algoritmus hledani gcd(a,b)

A

While b/=0
r = a mod b
a = b
b = r
Output a

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Bezoutova veta/rovnost

A

Necht a,b jsou cela cisla. Pak existuji A, B cela tak, ze
gcd(a,b) = Aa + Bb

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Jestlize prvocislo deli nejaky soucin ruznych cisel, tedy

p|(a1a2a3…an)

A

Pak existuje takove ai, ze p|ai

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Pro kazde prirozene cislo x vetsi nebo rovno dvema, existuje prvocislo p tak…

A

Ze p|x

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Ekvivalentni podminky pro kongruenci

A
  1. a == b (mod n)
  2. a mod n = b mod n
  3. b = a + kn, tedy existuje cislo b je jenom nejaky k-nasobek cisla n s posunutim, k je cele cislo
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Jestlize a==u (mod n) a b==v (mod n), pak

A

a+-b==u+-v (mod n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Definice inverzniho cisla

A

Rekneme, ze b je inverzni cislo k a modulo n p.t.k.
a*b = 1 (mod n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Podminka existence inverzniho cisla

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Postup hledani inverzniho cisla v modulo n

A

TODO

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Kolik muze byt inverznich prvku

A

Vicero, kdyz a ma inverzni prvek x, pak y je inverzyni prvek k a p.t.k
x == y (mod n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Mala Fermatova veta

A

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^(1215+2) = 6^2(6^(1215))
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Pokud pro nesoudelna n,m a cela a,b plati, ze a==b(mod n), a==b(mod m), pak…

A

a==b(mod n*m)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Test na prvocislo

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

Operace v telesu

A

Definuji se stejne jako obycejne operace, akorat se pak musi udelat modulo n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Inverzni cislo v telesu Z

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Jak ze zaporneho cisla udelat cislo telesa Z (neboli mod n)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

Opacny prvek v telesu Z

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

Diofanticka rovnice

A

Je to lib. rovnice tvaru ax + by = c, kde nezname jsou x,y abc jsou koeficienty

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

Kdy ma diofanticka rovnice reseni

A

p.t.k c = k gcd(a,b),
tedy c je nasobkem gcd(a,b)

38
Q

Homogenni rovnice

A

Je to rovnice = 0

39
Q

Existence homogenniho reseni pri partikularnim

A

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
Q

Hledani homogennich koeficientu z rovnice
nebo podle tabulky hledani gcd(x,y)

A

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
Q

Linearni kongruence

A

rovnice typu
ax == b(modn)

b = ax + mn

42
Q

Reseni linearni kongruence (rovnice)

A

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 partikularni 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
Q

Relace definice

A

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
Q

Sjednoceni, prunik, rozdil, skladani vice relaci…

A

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
Q

Inverzni relace

A

R^-1, bere prohozenou dvojici (b,a) a posila je R^-1 relaci na (a,b).
bR^-1a p.t.k. aRb

46
Q

Ctyri vlastnosti relaci

A
  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
Q

Dokazovani vztahu relaci

A

Bud protiprikald uvedu ze neplati,
Nebo zvolim lib. a,b s predpokladem a dojdu k zaveru relace

48
Q

Castecne usporadani

A

Je to vlastni poddruh relace, ktere splnuje tri vlastnosti
RAT - reflexivitu, antisymetrii, tranzitivitu
Treba a|b

Inverze castecneho usporadani je castecne usporadani

49
Q

Hesseuv diagram

A

Diagram relaci, kde zacnu od nejmensiho prvku relace a pripojuju k nemu postupne vzrustajici prvky az nahoru

50
Q

Nejvetsi/nejmensi prvek Hesseuva diagramu

A

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
Q

Maimalni/minimalni prvek Hesseuva diagramu

A

Konec/zacatek kazde vetve/ neexistujou relace vetsi/mensi nez on. Muze jich byt nekolik

52
Q

Linearni usporadani

A

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
Q

Kazde castecne uspoaradni se da…

A

Linearizovat, postupuju po jednom patre a skrtam minima

54
Q

Lexikograficke usporadani

A

Je to usporadain jako slovnik
Porovnavam prvek po prvku dokud nenarazim na vetsi/mensi a prohazuju

55
Q

Dobre usporadana mnozina definice

A

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
Q

Relace ekvivalence

A

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
Q

Trida ekvivalence

A

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
Q

Vlastnosti prvku ze tridy ekvivalence

A
  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
Q

Rozklad mnoziny A

A

Je to rozbiti mnoziny na disjunktni tridy ekvivalence

60
Q

Zobrazeni/funkce

A

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
Q

Funkce ma inverzi p.t.k.

A

Je bijekce

62
Q

Jak velikost mnozin zavisi na existenci bijekce?

A

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
Q

Jestlize |A| <= |B| a zaroven |B| <= |A| pak

A

|A| = |B|

64
Q

Mnozina je konecna

A

Kdyz je prazdna, nebo se da ocislovat jeji pocet prvku KONECNYM CISLEM M

65
Q

Podmnozina konecne mnoziny

A

Je konecna mnozina

66
Q

Nekonecna mnozina

A

Nejde promitnout na konecnou mnozinu,
Treba N je nejmensi nekonecna mnozina

67
Q

Spocetna mnozina

A

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
Q

Sjednoceni nekonecnych mnozin vliv na mohutnost

A

Mohunost se nemeni
|N| = nekonecno
|NxN| = nekonecno + nekonecno = nekonecno…

Ale neplati, ze NxN je vetsi nez N

69
Q

Podmnozina nekonecne mnoziny

A

Existuje i takova, ze ma stejnou mohutnost jako cela nadmnozina, tedy nekonecno

70
Q

Cantorova veta

A

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
Q

Postup indukce

A

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
Q

Slaby princip indukce

A

Predpoklad neco plati pro n, pak ukazu, ze to plati pro n+1, tim dojdu k zaveru, ze to plati pro vsechna n.

73
Q

Silny princip indukce

A

Vyrok plati pro n0, pak plati pro (n+1), ale musim znat vsechny predchozi stavy

74
Q

Pouziti silneho principu indukce

A

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
Q

Induktivni definice mnozin

A

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
Q

Posloupnost T

A

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
Q

Asymptoticky rust posloupnosti

A
  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
Q

Jak rozhodnout a vzajemnem vztahu dvou funckci asymptoticky pdoel definice

A

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
Q

Srovnani asymp. rychlosti prikladu funkci

A

logx
x^n mocninna
n^x exponencialni
x!
x^x

80
Q

Rychlost slozene funkce je dana Thetou funkce…

A

clenem s nejvetsim narustem

81
Q

Rekurentni rovnice

A

Je to nekonecne mnoho rovnice s nekonecne mnoha resenymi, zadani rekurentne pro n-ty clen

82
Q

Linearni rekurentni rovnice radu k

A

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
Q

Postup sestaveni lin. rek. rovnice

A
  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
Q

Pocatecni podminky

A

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
Q

Homogenni rek. rovnice

A

Je takova, kde na jednu stranu prevedeme vsechny posloupnosti a polozime je 0. Tedy v puvodni rovnici vymazu celou konstantni b(n)

86
Q

Reseni rek. lin. rovnice se sklada z…

A

homogenniho reseni + partikularniho

87
Q

Mnozina reseni lin. rek. rovnice radu k je…

A

lin. prostor dimenze k

88
Q

Lin. rek. rovnice s konst. koeficienty

A

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
Q

Postup nalezeni obecneho reseni

A
  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^2} 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
ux^n + vy^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, nlambda^n, nnlambda^n… tak dlouho, dokud nedostanu nutny pocet vektoru…
tedy pri lambda=1 3x sestavim obecne reseni jako
a(n) = v(1^n) + u(n1^n) + w(nn*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
Q

Postup nalezeni partikularniho reseni

A
  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 = 62^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: A2^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
Q

Masters theorem

A

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
Q

Princip inkluze a exkluze pro vypocet poctu prvku sjednoceni mnozin

A

|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

Státnice (4 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions