A n¨ oveked´es nagys´agrendje, sz´amoss´ag Logika ´es sz´ am´ıt´ aselm´elet, 6. gyakorlat
2009/10 II. f´el´ev
Sz´ am´ıt´ aselm´ elet (6. gyakorlat)
A n¨ oveked´ es nagys´ agrendje, sz´ amoss´ ag
2009/10 II. f´ el´ ev
1 / 1
Nagyord´o, Omega, Theta, Kisord´o Nagyord´ o, Omega, Theta Legyenek f , g : N → R+ f¨ uggv´enyek, ahol N a term´eszetes sz´amok, R+ pedig a nemnegat´ıv val´os sz´amok halmaza. Azt mondjuk, hogy f legfeljebb olyan gyorsan n˝ o mint g (jel¨ol´ese: f (n) = O(g (n)); ejtsd: f (n) = nagyord´ o g (n)) ha l´etezik olyan c > 0 sz´am ´es N ∈ N , hogy oli azt, hogy f (n) ≤ c · g (n) minden n ≥ N sz´amra. Az f (n) = Ω(g (n)) jel¨ g (n) = O(f (n)) teljes¨ ul, ´es f (n) = Θ(g (n)) jel¨ oli azt, hogy f (n) = O(g (n)) ´es f (n) = Ω(g (n)) is teljes¨ ul. Kiord´ o Legyenek f , g : N → R+ f¨ uggv´enyek. f (n) = o(g (n)) (ejtsd: f (n) = kisord´o g (n)), ha f (n)/g (n) → 0.
Sz´ am´ıt´ aselm´ elet (6. gyakorlat)
A n¨ oveked´ es nagys´ agrendje, sz´ amoss´ ag
2009/10 II. f´ el´ ev
2 / 1
´ Eszrev´ etelek: • f (n)/g (n) → 0 ⇔ minden c > 0 eset´ en l´etezik N ∈ N, hogy minden
n ≥ N eset´en f (n) ≤ c · g (n) • f (n) = o(g (n)) ⇒ f (n) = O(g (n)). • f (n) = o(g (n)) ⇒ f (n) 6= Ω(g (n)). • Ha f (n) = O(g (n)) ´ es g (n) = O(h(n)) akkor f (n) = O(h(n)).
Sz´ am´ıt´ aselm´ elet (6. gyakorlat)
A n¨ oveked´ es nagys´ agrendje, sz´ amoss´ ag
2009/10 II. f´ el´ ev
3 / 1
Polinomok ´es exponenci´alis f¨ uggv´enyek 7. Feladat: L´assuk be a k¨ovetkez˝o ´all´ıt´asokat! 1. x > 1-re x ≤ 2x . Teljes indukci´ oval k¨onnyen bizony´ıthat´o, hogy n + 1 ≤ 2n . L´etezik n ∈ N : n ≤ x ≤ n + 1. x ≤ n + 1 ≤ 2n ≤ 2x . 2. Ha c > 1, akkor ∃ n1 , n > n1 : c n ≥ 2. ε := c − 1 > 0. n n 0 n n−1 1 n n c = (1 + ε) = 0 1 ε + 1 1 ε + . . . = 1 + nε + δ, ahol δ ≥ 0. 3. Ha c > 1 ´es k ∈ N akkor nk = O(c n ). Legyen n1 az el˝oz˝o k¨ usz¨ob. n > n1 k eset´en n n ·k ·n n k k k k k k k k n = n1 k ( n1 k ) ≤ n1 k 2 n1 k ≤ n1 k c n1 1 = n1k k k c n . 4. Legyen p(n) egy pozit´ıv f˝oegy¨ utthat´oj´ u k-adfok´ u polinom. Ekkor p(n) = O(nk ). p(n) = ak nk + · · · + a1 n + a0 . ak > 0. p(n) ≤ (ak + 1)nk , ha n ≥ N, valamely N ∈ N-re. Ugyanis (ak + 1)nk − p(n) = nk (1 − ak−1 n1 − · · · − a0 n1k ) → +∞. Sz´ am´ıt´ aselm´ elet (6. gyakorlat)
A n¨ oveked´ es nagys´ agrendje, sz´ amoss´ ag
2009/10 II. f´ el´ ev
4 / 1
5. Minden p(n) polinomra ´es c > 1 konstansra p(n) = O(c n ). p(n) = O(nk ), ahol k p(n) foka. nk = O(c n ), teh´at p(n) = O(c n ). 6. Minden p(n) polinomra ´es c > 1 konstansra p(n) 6= Ω(c n ). Indirekt, tfh. l´etezik d1 > 0 ´es N1 ∈ N, hogy n ≥ N1 -re c n ≤ d1 p(n). Legyen c1 olyan, hogy 1 < c1 < c. Ekkor l´etezik d2 > 0 ´es N2 ∈ N, hogy n ≥ N2 -re p(n) ≤ d2 c1n . Teh´at n ≥ max N1 , N2 -re c n ≤ d1 p(n) ≤ d1 d2 c1n . Azaz ( cc1 )n ≤ d1 d2 , ami ellentmond´as. Teh´at azt kaptuk, hogy: Minden polinomi´alis f¨ uggv´eny lassabban n˝o, mint b´armely exponenci´alis f¨ uggv´eny. ´ Altal´ anosabban: Legyen f : N → R+ egy +∞-hez tart´o f¨ uggv´eny, p egy pozit´ıv f˝ oegy¨ utthat´ oj´ u polinom ´es c > 1, ekkor p(f (n)) lassabban n˝ o, mint c f (n) .
Sz´ am´ıt´ aselm´ elet (6. gyakorlat)
A n¨ oveked´ es nagys´ agrendje, sz´ amoss´ ag
2009/10 II. f´ el´ ev
5 / 1
Feladat
7. Feladat: Melyek igazak az al´abbi ´all´ıt´asok k¨ oz¨ ul? 1
5n7 = O(n7 ), Igen.
2
n log100 n = o(n2 ), Igen.
3
n2 = O(n log100 n), Nem.
4
1 = o(100), Nem.
5
1 = o(n), Igen.
6
4n = O(2n ), Nem.
7
2n = o(4n ), Igen.
8
4n = 2Θ(n) , Igen.
9
(n + 1)3 = n3 + n2 + O(n). Nem.
Sz´ am´ıt´ aselm´ elet (6. gyakorlat)
A n¨ oveked´ es nagys´ agrendje, sz´ amoss´ ag
2009/10 II. f´ el´ ev
6 / 1
Feladat 7. Feladat: Melyik igaz? f (n) = O(g (n)), f (n) = Ω(g (n)), f (n) = Θ(g (n)) minden f¨ uggv´enyp´arra d¨onts¨ uk el. (A logaritmus 2-es alap´ u.) n!, log n!, n3 , 100n , 2100 log n , n log n, nlog n . Megold´ as: Teljes indukci´oval n ≥ 6-ra k¨onnyen l´athat´ o, hogy (felhaszn´alva, hogy (1 + 1/n)n → e): ( n3 )n < n! < ( n2 )n . • log n! = Θ(n log n), • n log n = O(n3 ), n log n 6= Ω(n3 ), • n3 = O(2100 log n ), n3 6= Ω(2100 log n ), • 2100 log n = O(nlog n ), 2100 log n 6= Ω(nlog n ), • nlog n = O(100n ), nlog n 6= Ω(100n ), • 100n = O(n!), 100n 6= Ω(n!).
Sz´ am´ıt´ aselm´ elet (6. gyakorlat)
A n¨ oveked´ es nagys´ agrendje, sz´ amoss´ ag
2009/10 II. f´ el´ ev
7 / 1
Feladat 7. Feladat: Mit mondhatunk arr´ol az f f¨ uggv´enyr˝ ol, melyre f (1) = 1, f (2) = 10, ´es f (3) = 100? 1 f (n) = O(10n ), 2 f (n) = 10O(n) , 3 Egyik fenti ´ all´ıt´as sem igaz minden esetben. Megold´ as: A harmadik a helyes, nem mondhatunk semmit egy f¨ uggv´eny viselked´es´er˝ol nagy n-ekre a kezd˝o´ert´ekek alapj´an. 7. Feladat: L´etezik-e olyan p(n) polinom, melyre az al´abbi f¨ uggv´enyek O(p(n)) nagys´agrend˝ uek? 1 2 3
n!, n 100 , n n/100 .
Megold´ as: 1. Nem, n! ≥ n n 3. Nem, n/100 = n/100 · Sz´ am´ıt´ aselm´ elet (6. gyakorlat)
n n100 n n ( 3 ) . 2. Igen, 100 ≤ 100! . 99n/100+1 n−1 n/100 . · · · ≥ 100 1 n/100−1
A n¨ oveked´ es nagys´ agrendje, sz´ amoss´ ag
2009/10 II. f´ el´ ev
8 / 1
Sz´amoss´ ag
Sz´ am´ıt´ aselm´ elet (6. gyakorlat)
A n¨ oveked´ es nagys´ agrendje, sz´ amoss´ ag
2009/10 II. f´ el´ ev
9 / 1
Sz´amoss´ ag Egy A halmazhoz hozz´arendelj¨ uk az ˝o (|A|-al jel¨ olt) sz´amoss´ag´at. A sz´amoss´ag fogalm´aval az a c´elunk, hogy mondhassuk egy halmazr´ ol, hogy t¨obb, kevesebb vagy ugyananny eleme van mint egy m´asik halmaznek. Ez k¨ ul¨ on¨osen akkor probl´ema, ha a halmazoknak v´egtelen sok elem¨ uk van. Sz´ amoss´ ag • A´ es B halmazoknak megegyezik a sz´amoss´aga, ha l´etezik bijekci´ o k¨ ozt¨ uk. Jel¨ ol´ese: |A| = |B|. • A sz´ amoss´aga legal´abb annyi, mint B sz´amoss´aga, ha van B-b˝ ol
injekci´ o A-ba. Jel¨ol´ese: |A| ≥ |B|. • A sz´ amoss´aga hat´arozottan nagyobb, mint B sz´amoss´aga, ha van
B-b˝ ol injekci´ o A-ba, de bijeci´o nincs. Jel¨ol´ese: |A| > |B|. Cantor-Bernstein t´etel Ha A-b´ ol B-be van injekci´o ´es B-b˝ol A-ba is van, akkor A ´es B k¨ oz¨ ott bijekci´ o is van. Sz´ am´ıt´ aselm´ elet (6. gyakorlat)
A n¨ oveked´ es nagys´ agrendje, sz´ amoss´ ag
2009/10 II. f´ el´ ev
10 / 1
Sz´amoss´ ag Feladatok
7. Feladat: Melyik nagyobb? |N| vagy |Z|? Megold´ as: Megegyezik a sz´amoss´aguk. 0 1 2 3 4 5 6
−3 −2 −1 0
1
2
3
7. Feladat: Melyik nagyobb? |N| vagy |N × N|? 6 5 4 3 2 1 0
21
Megold´ as: Megegyezik a sz´amoss´aguk.
20
22
10
19
23
9
11
18
24
3
8
12
17
2
4
7
13
16
0
1
5
6
14
15
0 1 2 3 4 5 6
Sz´ am´ıt´ aselm´ elet (6. gyakorlat)
A n¨ oveked´ es nagys´ agrendje, sz´ amoss´ ag
2009/10 II. f´ el´ ev
11 / 1
7. Feladat: Melyik nagyobb? |N| vagy |Q|? Megold´ as: Megegyezik a sz´amoss´aguk. N ⊂ Q, ez´ert |N| ≤ Q|. Q+ := { qp | p ∈ N+ , q ∈ N+ , a t¨ort nem egyszer˝ us´ıthet˝ o}. Q− := {− qp | p ∈ N+ , q ∈ N+ , a t¨ort nem egyszer˝ us´ıthet˝ o}. |Q+ | = |Q− |. p + 7→ (p, q) ∈ N × N injekt´ + | ≤ |N × N| = |N|. ∈ Q ıv, teh´ a t |Q q Legyen Q+ = {a1 , a2 , a3 . . . , }, Q− = {b1 , b2 , b3 . . . , }, ekkor Q = {0, a1 , b1 , a2 , b2 , a3 , b3 , . . .} Megsz´ aml´ alhat´ oan v´egtelen sz´ amoss´ ag N sz´amoss´ag´at megsz´aml´alhat´oan v´egtelennek nevezz¨ uk.
Sz´ am´ıt´ aselm´ elet (6. gyakorlat)
A n¨ oveked´ es nagys´ agrendje, sz´ amoss´ ag
2009/10 II. f´ el´ ev
12 / 1
Sz´amoss´ ag Feladatok
7. Feladat: Melyik t¨obb? 1
|R|
2
|[0, 1]|
3
az egys´egsugar´ u k¨orvonal pontjainak sz´ama
4
|[0, 1] × [0, 1]|. 1 2 )) (0,1)
: (0, 1) → R bijekci´ o (0, 1) ´es R k¨ oz¨ ott. Megold´ as: tg(π(x − ϕ (sin ϕ, cos ϕ) 7→ 2π . bijekci´o az egys´egsugar´ u k¨ orvonal pontjai ´es [0, 1) k¨ oz¨ ott. Legyen (an )n∈N+ (egy olyan sorozat, melyre a1 = 0 ´es lim ai ∈ (0, 1), +) a ha x = a (i ∈ N i+1 i egy bijekci´ o [0, 1) ´es pl. ai = 21 − 21i . f (x) = + x ha x 6∈ {ai | i ∈ N } (0, 1) k¨ oz¨ ott. Hasonl´oan megadhat´o egy bijekci´ o [0, 1] ´es [0, 1) k¨ oz¨ ott.
Sz´ am´ıt´ aselm´ elet (6. gyakorlat)
A n¨ oveked´ es nagys´ agrendje, sz´ amoss´ ag
2009/10 II. f´ el´ ev
13 / 1
Sz´amoss´ ag Feladatok
7. Feladat: Mennyi van bel˝ole? 1 v´ eges hossz´ u bin´aris szavak 2 megsz´ aml´alhat´oan v´egtelen hossz´ us´ag´ u bin´aris szavak 3 v´ eges, bin´aris szavakb´ol ´all´o nyelvek Megold´ as: A v´eges hossz´ u bin´aris szavakat felsorol´ o algoritmus adhat´ o: ε,0,1,00,01,10,11,000,001,010,011,100,101,110,111,0000,. . . Teh´at sz´amoss´aga megsz´aml´alhat´oan v´egtelen. Term´eszetes bijekci´ o van 2 ´es 3 k¨oz¨ott: Soroljuk fel a bin´aris szavakat. Egy nyelvhez rendelj¨ uk azt a megsz´aml´alhat´oan v´egtelen hossz´ us´ag´ u bin´aris sz´ ot, melynek 1 az i. bitje, ha benne van az i. sz´ o, 0 ha nem. ´ megegyezik 2 ´es 3 sz´amossz´aga nagyobb, mint megsz´aml´alhat´ o. (Es |R|-el.) Continuum sz´ amoss´ ag R sz´amoss´ag´at continuumnak nevezz¨ uk. Sz´ am´ıt´ aselm´ elet (6. gyakorlat)
A n¨ oveked´ es nagys´ agrendje, sz´ amoss´ ag
2009/10 II. f´ el´ ev
14 / 1
Cantor-f´ele ´ atl´ os m´odszer Jel¨ olje H a megsz´aml´alhat´oan v´egtelen hossz´ us´ag´ u bin´aris szavak halmaz´at. ´ ıt´ All´ as: |H| > |N| |H| ≥ |N|: H0 := {(1, 0, 0, 0, . . .), (0, 1, 0, 0, . . .), (0, 0, 1, 0, . . .), . . .} ⊂ H, ´es |H0 | = |N|. Indirekt tegy¨ uk fel, hogy |H| = |N|. Ez azt jelenti, hogy bijekci´ oba lehet ´all´ıtani H elemeit N elemeivel, azaz H = {ui | i ∈ N} = {u1 , u2 , . . .} a H elemeinek egy felsorol´asa (a term´eszetes sz´amokkal val´ o megindexel´ese). Legyen ui = (ui,1 , ui,2 , . . . , ui,j , . . .), ahol minden i, j ∈ N-re ui,j ∈ {0, 1}. Tekints¨ uk az u = {u1,1 , u2,2 , . . . , ui,i , . . .) megsz´aml´alhat´ oan v´egtelen hossz´ us´ag´ u bin´aris sz´ot, ahol b 0, ha b = 1 ´es 1, ha b = 0. Mivel, minden megsz´aml´alhat´oan v´egtelen hossz´ us´ag´ u bin´aris sz´ o fel van sorolva, ez´ert l´etezik olyan k ∈ N, melyre u = uk . Ekkor u k.bitje uk,k (´ıgy jel¨olt¨ uk uk k. bitj´et), m´asr´eszt uk,k (´ıgy defini´altuk u-t). De ez nem lehets´eges, teh´at az a feltev´es¨ unk, hogy |H| = |N| hamis. Sz´ am´ıt´ aselm´ elet (6. gyakorlat)
A n¨ oveked´ es nagys´ agrendje, sz´ amoss´ ag
2009/10 II. f´ el´ ev
15 / 1
