Diszkr´et matematika 5. el˝oad´as ´ MARTON Gy¨ ongyv´er Sapientia Egyetem, M˝ uszaki ´ es Hum´ antudom´ anyok Tansz´ ek Marosv´ as´ arhely, Rom´ ania
[email protected]
2015, ˝ oszi f´ el´ ev
´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
Mir˝ol volt sz´o az elm´ult el˝oad´ason?
sz´ amtani, m´ertani, harmonikus sz´ amsorozatok saj´ atos sz´ amsorozatok: a faktori´ alis f¨ uggv´eny Stirling sz´ amok Fibonacci sz´ amok Lucas sz´ amok Catalan sz´ amok algoritmusok Python-ban
´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
Mir˝ol lesz sz´o?
aranymetsz´es, aranyar´ any a Fibonacci, Lucas sz´ amokkal val´ o kapcsolat sz´ amrendszerek sz´ amrendszerek k¨ oz¨ otti ´ atalak´ıt´ asok sz´ amok o ¨sszead´ asa, szorz´ asa bin´ aris sz´ amrendszerben
´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
Aranymetsz´es, aranyar´any (Golden Ratio) k´et mennyis´eg, a, b, a > b az aranymetsz´es szerint ar´ anylik egym´ ashoz, ha fenn´ all: a a + b def = = ϕ b a
a ϕ meghat´ aroz´ asa ´erdek´eben fel´ırhatjuk:
ϕ=1+
1 a+b = 1 + a , azaz fenn´ all: a b
1 ⇔ ϕ2 = ϕ + 1 ϕ
megoldva a fenti egyenletet kapjuk, hogy √ √ 1+ 5 1− 5 ϕ= = 1.61803 . . . ´es ϕ ˆ= = −0.61803 . . . 2 2 a ϕ irracion´ alis sz´ am ´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
Aranyar´any, alkalmaz´asok
´ep´ıt´eszet: Parthenon homlokzat´ anak ar´ any´ert´ekei: logok: Toyota, Mercedesz, stb. Pentagramma (szab´ alyos o ¨tsz¨ og):
piros zold
=
zold kek
=
kek lila
=ϕ
term´eszet: napraforg´ o spirlajai
´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
Aranyar´any, l´anct¨ortek
Kiindulva az al´ abbi o ¨sszef¨ ugg´esb˝ ol: ϕ = 1 +
1 , l´ anct¨ ortek seg´ıts´eg´evel is ϕ
fel´ırhatjuk a ϕ ´ert´ek´et: 1
ϕ=1+
1
1+ 1+
1 1+
´ MARTON Gy¨ ongyv´ er
1 ..
.
2015, Diszkr´ et matematika
A Fibonacci sz´amok, Lucas sz´amok
a Fibonacci sz´ amsorozat: 0, 1, 1, 2, 3, 5, 8, 13, . . . , a rekurzi´ os k´eplet: F0 = 0, F1 = 1, Fn = Fn−1 + Fn−2 , a Lucas sz´ amsorozat: 2, 1, 3, 4, 7, 11, 18, 29, 47, . . . , a rekurzi´ os k´eplet: L0 = 2, L1 = 1, Ln = Ln−1 + Ln−2 , kapcsolat, k´epletek: Ln = Fn−1 + Fn+1 = Fn + 2 · Fn−1 = Fn+1 − Fn−2 Fn =
Ln−1 + Ln+1 Ln−3 + Ln+3 = 5 10
´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
Kapcsolat a Fibonacci sorozattal meg´ allap´ıthat´ o: lim
n→∞
Fn+1 Fn + Fn−1 = lim = 1 + lim n→∞ n→∞ Fn Fn
fenn´ all teh´ at: x = 1 +
1 Fn Fn−1
1 Fn+1 Fn , ahol a lim = lim = x jel¨ ol´est n→∞ Fn n→∞ Fn−1 x
alkalmaztuk. megoldva a x = 1 +
1 egyenletet kapjuk, hogy x Fn+1 =ϕ lim n→∞ Fn
Ln+1 =ϕ Ln Binet formula (bizony´ıt´ as matematikai indukci´ oval): √ n √ n n (1 + 5) − (1 − 5)n ϕ −ϕ ˆ √ Fn = √ = 5 2n · 5 hasonl´ oan: lim
n→∞
´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
Algoritmusok Pythonban
1. feladat: Fibonacci sz´ amok, az aranymetsz´esi k´eplettel: √ √ √ √ ( 1+2 5 )n − (1 − 1+2 5 )n (1 + 5)n − (1 − 5)n √ √ Fn = = 5 2n · 5· def fibN (n): return int(( pow(1+math.sqrt(5), n) - pow (1-math.sqrt(5), n))/ (math.sqrt(5) * pow (2, n))) def fibN1 (n): return int(( (1+math.sqrt(5)) ** n - (1-math.sqrt(5)) ** n )/ (math.sqrt(5) * 2 ** n))
´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
Sz´amrendszerek eg´esz sz´ amok: b´ armely 1-n´el nagyobb sz´ amrendszerben ´ abr´ azolhat´ oak, a sz´ am´ıt´ astechnik´ aban gyakran haszn´ alt sz´ amrendszerek: 10, 2, 8, 16, 256, 2-es sz´ amrendszer: bin´ aris sz´ amrendszer, 8-as sz´ amrendszer: okt´ alis sz´ amrendszer, 16-os sz´ amrendszer: hexadecim´ alis sz´ amrendszer, legyen n az a sz´ am, amit ´ atszeretn´enk ´ırni b sz´ amrendszerbe, ekkor, Z∗ -vel jel¨ olve a nem negat´ıv eg´esz sz´ amok halmaz´ at: n = ak b k + ak−1 b k−1 + · · · + a1 b 1 + a0 b 0 , ahol k ∈ Z∗ , ai ∈ Z∗ , ´es ai < b, minden i ∈ {0, . . . , k} ´ert´ekre ´es ak 6= 0. 10-es sz´ amrendszerben 10 szimb´ olum van: 0, 1, 2, . . . , 9. 2-es sz´ amrendszerben 2 szimb´ olum van: 0, 1. 256-os sz´ amrendszerben 256 szimb´ olum van
´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
Sz´amrendszerek, p´eld´ak
Pl. Mi (215)10 , 2-es sz´ amrendszerbeli alakja? fenn´ all: 215 = 128 + 64 + 16 + 4 + 2 + 1 = 1 · 27 + 1 · 26 + 0 · 25 + 1 · 24 + 0 · 23 + 1 · 22 + 1 · 21 + 1 · 20 . teh´ at: (215)10 = (1101 0111)2 . Pl. (1 0111 0010)2 , melyik 10-es sz´ amrendszerbeli sz´ amnak felel meg? fenn´ all: (1 0111 0010)2 = 1 · 28 + 0 · 27 + 1 · 26 + 1 · 25 + 1 · 24 + 0 · 23 + 0 · 22 + 1 · 21 + 0 · 20 = 256 + 64 + 32 + 16 + 2 = 370. teh´ at: (1 0111 0010)2 = (370)10 .
´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
Sz´amrendszerek, p´eld´ak
8-as sz´ amrendszerben 8 szimb´ olum van: 0, 1, 2, 3, 4, 5, 6, 7. Pl. Mi (215)10 , 8-as sz´ amrendszerbeli alakja? fenn´ all: 215 = 3 · 82 + 2 · 81 + 7 · 80 teh´ at: (215)10 = (327)8 . Pl. (6702)8 , melyik 10-es sz´ amrendszerbeli sz´ amnak felel meg? fenn´ all: 6702 = 6 · 83 + 7 · 82 + 0 · 81 + 2 · 80 = 3072 + 448 + 2 = 3522. teh´ at: (6702)8 = (3522)10 .
´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
Sz´amrendszerek, p´eld´ak
16-as sz´ amrendszerben 16 szimb´ olum van: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C , D, E , F . Pl. Mi (7432)10 , 16-os sz´ amrendszerbeli alakja? fenn´ all: 7432 = 1 · 163 + 13 · 162 + 0 · 161 + 8 · 160 teh´ at: (7432)10 = (1D08)16 . Pl. (E 2D07)16 , melyik 10-es sz´ amrendszerbeli sz´ amnak felel meg? fenn´ all: E 2D07 = 14 · 164 + 2 · 163 + 13 · 162 + 0 · 161 + 7 · 160 = 917504 + 8192 + 3328 + 7. teh´ at: (E 2D07)16 = (929031)10 .
´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
Algoritmus: 10-es sz´amrendszerb˝ol b sz´amrendszerbe
n-et elosztjuk marad´ekos oszt´ assal b-vel: n = b · q0 + a0 , ahol 0 ≤ a0 < b. q0 -ot elosztjuk marad´ekos oszt´ assal b-vel: q0 = b · q1 + a1 , ahol 0 ≤ a1 < b. addig folytatjuk a marad´ekos oszt´ ast, am´ıg 0 oszt´ asi eg´eszr´eszt kapunk. Pl. Alak´ıtsuk ´ at 7432-t 16-os sz´ amrendszerbe: 7432 464 29 1
´ MARTON Gy¨ ongyv´ er
= = = =
464 · 16 + 8 29 · 16 + 0 1 · 16 + 13 0 · 16 + 1
2015, Diszkr´ et matematika
Algoritmus: b sz´amrendszerb˝ol 10-es sz´amrendszerbe
hatv´ any¨ osszeget sz´ amolunk a b sz´ amrendszerbeli sz´ amjegyekb˝ ol Pl. Alak´ıtsuk ´ at 1D08-t 10-es sz´ amrendszerbe: 1D08 = [1, 13, 0, 8] → [8, 0, 13, 1] 8 8 3336 7432
= = = =
´ MARTON Gy¨ ongyv´ er
8 · 160 0 · 161 + 8 13 · 162 + 8 1 · 163 + 3336
2015, Diszkr´ et matematika
Algoritmusok Pythonban 2. feladat: Alak´ıtsunk ´ at egy sz´ amot 10-es sz´ amrendszerb˝ ol b sz´ amrendszerbe def alakit10_b(nr, b): L = [] while nr > 0: L = [nr % b] + L nr = nr / b return L megh´ıv´ as: alakit10_b(14, 2) az eredm´eny: [1, 1, 1, 0] ha oda-vissza ´ atalak´ıt´ ast kell v´egezni, akkor aj´ anlatos a ford´ıtott sorrendet el˝ o´ all´ıtani, ekkor az L = [nr % b] + L sor helyett az L = L + [nr % b] sor sz¨ uks´eges.
´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
Algoritmusok Pythonban 3. feladat: Alak´ıtsunk ´ at egy b sz´ amrendszerbeli sz´ amot 10-es sz´ amrendszerbe def alakitb_10 (L, b): nr = 0 p = 1 for elem in reversed(L): nr += elem * p p *= b return nr
def alakitb_10_1 (L, b): nr = 0 p = 1 l = len(L)-1 for i in range (l, -1, -1): nr += L[i] * p p *= b return nr
megh´ıv´ as: alakitb_10([1, 1, 1, 0], 2) az eredm´eny: 14 a reversed(L) megford´ıtja a bemeneti list´ at ha a ford´ıtott sorrend lesz a bemenet, akkor nem sz¨ uks´eges reversed f¨ uggv´eny haszn´ alata, illetve az alakitb_10_1 f¨ uggv´enyben range(0, l+1) lesz. ´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
Kapcsolat a 2, 8, 16 sz´amrendszerek k¨oz¨ott
bin´ aris → okt´ alis: h´ armas csoportokat form´ alunk: Pl. [1, 1, 1, 1, 0, 1, 1] → [1, 1, 1, 1, 0, 1, 1] → [1, 7, 3] bin´ aris → hexadecim´ alis: n´egyes csoportokat form´ alunk Pl. [1, 1, 1, 1, 0, 1, 1] → [1, 1, 1, 1, 0, 1, 1] → [7, B] k
bin´ aris → 2 : k-as csoportokat form´ alunk Pl. 2 → 256 = 28 , 8-as csoportokat form´ alunk: [1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1] → [1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1] → [57, 107]
´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
Algoritmusok Pythonban 4. feladat: Alak´ıtsunk ´ at egy sz´ amot 2-es sz´ amrendszerb˝ ol 2k sz´ amrendszerbe def alakit2_2k(L, k): L1 = [] l = len(L) i = l - 1 while i >= 0: nr = 0 p = 1 for j in range (0, k): nr += L[i] * p i -= 1 p *= 2 if i == -1: break L1 = [nr] + L1 return L1
´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
Algoritmusok Pythonban
4. feladat: Alak´ıtsunk ´ at egy sz´ amot 2-es sz´ amrendszerb˝ ol 8-as sz´ amrendszerbe megh´ıv´ as: alakit2_2k([1, 1, 0, 1, 0, 1], 3) az eredm´eny: [6, 5] Alak´ıtsunk ´ at egy sz´ amot 2-es sz´ amrendszerb˝ ol 256-os sz´ amrendszerbe megh´ıv´ as: alakit2_2k([1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1], 8) az eredm´eny: [57, 107]
´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
Algoritmusok Pythonban
5. feladat: Alak´ıtsunk ´ at egy sz´ amot 2k sz´ amrendszerb˝ ol 2-es sz´ amrendszerbe def alakit2k_2(L, k): L1 = [] l = len(L) - 1 for i in range(l, -1, -1): nr = L[i] for j in range (0, k): L1 = [nr % 2] + L1 nr = nr / 2 return L1
´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
Algoritmusok Pythonban 5. feladat: Alak´ıtsunk ´ at egy sz´ amot 8-as sz´ amrendszerb˝ ol 2-es sz´ amrendszerbe megh´ıv´ as: alakit2k_2([6, 5], 3) az eredm´eny: [1, 1, 0, 1, 0, 1] Alak´ıtsunk ´ at egy sz´ amot 256-os sz´ amrendszerb˝ ol 2-es sz´ amrendszerbe megh´ıv´ as: alakit2k_2([57, 107], 8) az eredm´eny: [1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1] A k´et f¨ uggv´enyt egy¨ utt alkalmazva: megh´ıv´ as: alakit2_2k(alakit2k_2([217, 107, 28, 142, 55], 8), 8) az eredm´eny: [217, 107, 28, 142, 55]
´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
K´et bin´aris sz´am ¨osszead´asa Legyen a k´et sz´ am ´es bin´ aris alakjuk: A B
= =
al−1 al−2 . . . a1 a0 bl−1 bl−2 . . . b1 b0 ,
jel¨ olj¨ uk c-vel a tov´ abbviteli ´ert´eket az o ¨sszead´ as szab´ aly´ at alkalmazva a k´et legh´ ats´ o bitre: a0 + b0 + c, ahol c = 0 az els˝ o tov´ abbviteli ´ert´ek az o ¨sszead´ as szab´ aly´ at alkalmazva ´ altal´ anosan: ai + bi + ci−1 , ahol a tov´ abbvitel ´ert´eke: ci = b(ai + bi + ci−1 )/2c, az aktu´ alis bit ´ert´eke: ri = (ai + bi + ci−1 ) mod 2, ami ugyanaz mint: ri = (ai + bi + ci−1 − 2 · ci ). ´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
Algoritmusok Pythonban 6. feladat: K´et bin´ aris sz´ am o ¨sszead´ asa: def osszeg (A, B): l1, l2 = len (A), len (B) i, j = l1 - 1, l2 - 1 c, R = 0, [] while i >=0 and j >= 0: temp = A[i] + B[j] + c R = [temp % 2] + R c = temp / 2 i, j = i - 1, j - 1 while i >= 0 : temp = A[i] + c R = [(temp) % 2] + R c = temp / 2 i -= 1 while j >= 0: temp = B[j] + c R = [(temp) % 2] + R c = temp / 2 j -= 1 return [c] + R ´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
K´et bin´aris sz´am szorzata Legyen a k´et sz´ am, ´es bin´ aris alakjuk: A B
= =
al−1 al−2 . . . a1 a0 bl−1 bl−2 . . . b1 b0 ,
A szorz´ as szab´ aly´ at alkalmazva: A·B
= =
A · (b0 · 20 + b1 · 21 + · · · + bl−1 · 2l−1 ) (A · b0 ) · 20 + (A · b1 ) · 21 + · · · + (A · bl−1 ) · 2l−1
Ha bi = 1, akkor A · bi = A Ha bi = 0, akkor A · bi = 0 Minden iter´ aci´ on´ al meg kell hat´ arozni 2k -val val´ o szorz´ as ´ert´ek´et: jobbr´ ol kieg´esz´ıtj¨ uk k darab 0-val a bin´ aris alakot. Python, k darab null´ asokb´ ol ´ all´ o lista l´etrehoz´ asa: L = k * [0]
´ MARTON Gy¨ ongyv´ er
2015, Diszkr´ et matematika
