Diszkr´et matematika 2. el˝oad´as ´ MARTON Gy¨ ongyv´er Sapientia Egyetem, M˝ uszaki ´ es Hum´ antudom´ anyok Tansz´ ek Marosv´ as´ arhely, Rom´ ania
[email protected]
2016, ˝ oszi f´ el´ ev
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Mir˝ol volt sz´o az elm´ult el˝oad´ason?
K¨ ovetelm´enyek, k¨ onyv´eszet ´ Attekint˝ o Sz´ amtartom´ anyok: term´eszetes sz´ amok, eg´esz sz´ amok, Alapm˝ uveletek, t´ıpusok, algoritmusok Python-ban
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Mir˝ol lesz sz´o?
A gyorshatv´ anyoz´ as algoritmusa - iterat´ıv, rekurz´ıv v´ altozatok. Sz´ amtartom´ anyok: racion´ alis sz´ amok, irracion´ alis sz´ amok Racion´ alis sz´ amok sorozatba rendez´ese legnagyobb k¨ oz¨ os oszt´ o algoritmusa, rekurz´ıv v´ altozat L´ anct¨ ortek racion´ alis sz´ amok l´ anct¨ ort jegyei
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Algoritmusok Pythonban
1. feladat: hat´ arozzuk meg 2100 ´ert´ek´et. ** oper´ atorral, az eredm´eny long t´ıpus´ u ´ert´ek lesz, ami a Pythonban v´egtelen precizit´ as´ u eg´esz ´ert´eket jelent, ezt az eredm´eny v´eg´en megjelen˝ o L szimb´ olum jelzi. >>> 2**100 1267650600228229401496703205376L H´ any szorz´ ast v´egez az algoritmus az eredm´eny meghat´ aroz´ as´ ahoz?
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Algoritmusok Pythonban L´etezik olyan algoritmus, amely 2100 meghat´ aroz´ asakor 9 darab szorz´ ast v´egez. Hogyan?? A gyorshatv´ anyoz´ as algoritmus´ aval, amely logaritmikus fut´ asi idej˝ u. Mit jelent ez? 2. feladat: hat´ arozzuk meg x n ´ert´ek´et. def my_pow (x, n): res = 1 while n <> 0: if n % 2 == 1: res = res * x x = x * x n = n / 2 return res >>> my_pow(2, 100) 1267650600228229401496703205376L ´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Algoritmusok Pythonban 3. feladat: a gyorshatv´ anyoz´ as, rekurz´ıv (1)v´ altozat def my_pow1 (x, n): if n == 0: return 1 if n % 2 == 0: return my_pow1 (x * x, n / 2) return x * my_pow1 (x * x, n / 2) >>> my_pow1(2, 100) 1267650600228229401496703205376L A gyorshatv´ anyoz´ as, rekurz´ıv (2)v´ altozat: def my_pow2 (x, n): if n == 0: return 1 temp = my_pow2 (x, n/2) if n % 2 == 1: return x * temp * temp else: return temp * temp ´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Racion´alis sz´amok
halmazjel¨ ol´es: Q = { ba : a, b ∈ Z, b 6= 0}, eg´esz sz´ amok rendezett p´ arjak´ent is felfoghat´ oak, tulajdons´ agok: kommutat´ıvit´ as, asszociat´ıv´ıt´ as, disztribut´ıv´ıt´ as, a racion´ alis sz´ amok halmaza z´ art az o ¨sszead´ asra, kivon´ asra, szorz´ asra, oszt´ asra n´ezve, o ¨sszead´ asra, szorz´ asra n´ezve minden elemnek lesz inverz eleme, s˝ ur˝ un rendezett halmazt alkotnak: b´ armely k´et racion´ alis sz´ am k¨ oz¨ ott van egy harmadik, v´egtelen sok alakban fel´ırhat´ oak → irreducibilis t¨ ort, sorozatba rendezhet˝ oek, tizedes t¨ ort alak: v´eges vagy v´egtelen szakaszos t¨ ortek.
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Algoritmusok Pythonban 4. feladat: hat´ arozzuk meg egy adott racion´ alis sz´ am irreducibilis alakj´ at. a
x y
racion´ alis sz´ amot az (x, y ) sz´ amp´ arral fogjuk jel¨ olni,
egy t¨ ort irreducibilis, ha a sz´ aml´ al´ o ´es nevez˝ o legnagyobb k¨ oz¨ os oszt´ oja 1 meg kell hat´ arozni k´et sz´ am legnagyobb k¨ oz¨ os oszt´ oj´ at: eukleid´eszi algoritmus (rekurz´ıv v´ altozat) def iAlak (a, b): l = lnko(a, b) return (a/l, b/l) # k´ et sz´ am legnagyobb k¨ oz¨ os oszt´ oja, eukleideszi algoritmus def lnko(a, b): temp = a % b if temp == 0: return b return lnko(b, temp)
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Racion´alis sz´amok A racion´ alis sz´ amok halmaza megsz´ aml´ alhat´ o: a racion´ alis sz´ amok halmaza felsorolhat´ o, azaz l´etezik egy sz´ amsorozat, amelyet a racion´ alis sz´ amok alkotnak : r1 , r2 , . . . , rn , . . . , b´ armelyik racion´ alis sz´ am fel´ırhat´ o p/q alakba:
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Algoritmusok Pythonban 5. feladat: Az el˝ oz˝ o oldalon megadott sorrend szerint ´ırassuk ki az els˝ o 55 racion´ alis sz´ amot, I. m´ odszer. def aRacionalis (k): for j in range(1, k+1): print (j, k+1-j), print >>> (1, (1, (1, ... ...
def racionalis (n): for k in range(1, n+1): aRacionalis (k)
racionalis (10) 1) 2) (2, 1) 3) (2, 2) (3, 1) (3, 8) (4, 7) (5, 6) (6, 5) (7, 4) (8, 3) (9, 2) (10, 1)
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Algoritmusok Pythonban Az 5. feladat seg´edf¨ uggv´eny n´elk¨ ul, egym´ asba ´ agyazott for ciklus-sal: def racionalis1 (n): for k in range(1, n+1): for j in range(1, k+1): print (j, k+1-j), print Lesznek olyan racion´ alis sz´ amok, amelyek t¨ obbsz¨ or is megjelennek a gener´ alt sz´ amok k¨ oz¨ ott?! Ha egy sz´ amp´ arb´ ol k´epezhet˝ o racion´ alis sz´ am nem irreducubilis, akkor azt jelenti, hogy m´ ar egyszer ki volt gener´ alva az 5. feladat befejez´ese h´ azi feladat.
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Algoritmusok Pythonban Az 5. feladat lista adatszerkezettel, a list´ aba sz´ amp´ arok ker¨ ulnek: def aRacionalisL (k): #az L list´ at ¨ ures listak´ ent inicializ´ aljuk: L = [] for j in range(1, k+1): #az L lista v´ eg´ ehez hozz´ afuzunk egy sz´ amp´ art: L = L + [(j, k+1-j)] return L Megjegyz´esek, ”kommentek” haszn´ alata: egysoros megjegyz´es: #ez egy egysoros megjegyz´ es t¨ obbsoros megjegyz´es: """ez egy t¨ obbsoros megjegyz´ es"""
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Algoritmusok Pythonban 6. feladat: ´Irassuk ki az els˝ o n racion´ alis sz´ amot, alkalmazva a k¨ ovetkez˝ o j k an k¨ ovetkez˝ o racion´ alis sz´ am: 2 · yx + 1 − yx reciproka, algoritmust: az yx ut´ ahol als´ o eg´esz r´eszt jelent, II. m´ odszer. pl:
5 2
→2·
pl:
5 3
→2·
j k 5
j2k 5 3
+1−
5 2
=2·2+1−
5 2
=5−
+1−
5 3
=2·1+1−
5 3
=
5 2
(9−5) 3
= =
(10−5) 2 4 3
→
=
5 2
→
3 4
Ezzel a m´ odszerrel a k¨ ovetkez˝ o list´ at kapjuk: (1, 1) (1, 2), (2, 1) (1, 3), (3, 2), (2, 3), (3, 1) (1, 4), (4, 3), (3, 5), (5, 2), (2, 5), (5, 3), (3, 4), (4, 1) ...
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
2 5
Algoritmusok Pythonban
6. feladat: a feladat megold´ as´ ahoz t¨ obb f¨ uggv´enyt is meg kell ´ırni Az
x y
racion´ alis sz´ am ut´ ani racion´ alis sz´ am meghat´ aroz´ asa:
def nextRac (x, y): nrx = (2 * (x/y) + 1) * y - x nry = y g = lnko (nrx, nry) return (nry / g, nrx / g)
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Algoritmusok Pythonban
6. feladat: A sz´ amp´ arok ki´ırat´ asa: def lista1 (x, y, n): print(x, y) for i in range (0, n): (x, y) = nextRac(x, y) print (x, y), megh´ ıv´ as: lista1 (1, 1, 7)
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Algoritmusok Pythonban
6. feladat: A sz´ amp´ arok list´ aban val´ o elt´ arol´ asa: def lista2 (x, y, n): L = [(x, y)] for i in range (0, n): (x, y) = nextRac(x, y) L = L + [(x, y)] return L megh´ ıv´ as: lista2 (1, 1, 7)
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Irracion´alis sz´amok halmazjel¨ ol´es: Q∗ , azok a sz´ amok, melyek nem ´ırhat´ oak fel k´et eg´esz sz´ am h´ anyadosak´ent, azaz a v´egtelen, nem szakaszos tizedes t¨ ortek, ”h´ıresebb” irracion´ alis sz´ amok: √ 2 = 1.4142 . . . , π = 3.1415 . . . , e = 2.7182 ..., √ φ = 1+2 5 = 1.6118 . . . , az aranyar´ any. a sz´ am´ıt´ astechnika az irracion´ alis sz´ amok k¨ ozel´ıtett ´ert´ek´et tudja meghat´ arozni l´ anct¨ ortek seg´ıts´eg´evel k¨ onnyed´en meglehet hat´ arozni a k¨ ozel´ıtett ´ert´ek t´ızedesjegyeit
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
L´anct¨ortek (Continued fraction) A l´ anct¨ ort egy emeletes t¨ ort, amely k´etf´ele alakban is megadhat´ o, ahol a k´et alak ´ atalak´ıthat´ o egym´ asba: b1
a0 +
b2
a1 + a2 +
1
d0 +
a3 +
1
d1 +
b3 b4 ..
1
d2 +
d3 +
.
1 ..
.
A m´ asodik alak eset´eben a [d0 , d1 , d2 , d3 , . . . ] sz´ amsorozatot a l´ anct¨ ort jegyeinek h´ıvj´ ak. Meg´ allap´ıthajuk, hogy: a racion´ alis sz´ amok v´eges l´ anct¨ ortek, az irracion´ alis sz´ amok v´egtelen l´ anct¨ ortek. ´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
L´anct¨ortek, p´elda Alak´ıtsuk ´ at
37 13
37 -t 13
l´ anct¨ ortt´e:
1
=2+ 1+
5+ Alak´ıtsuk ´ at
41 11
= [2, 1, 5, 2] = 2.(846153)
1
41 -t 11
1 2
l´ anct¨ ortt´e:
1
=3+
= [3, 1, 2, 1, 2] = 3.(72)
1
1+ 2+
1 1+
1 2
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Algoritmusok Pythonban 7. feladat: hat´ arozzuk meg az
x y
racion´ alis sz´ amnak megfelel˝ o l´ anct¨ ort jegyeit
def lanct(x, y): L = [] while 1: L += [x / y] r = x % y if r == 0: break x = y y = r return L >>> lanct(89, 63) [1, 2, 2, 2, 1, 3] >>> lanct(89, 55) [1, 1, 1, 1, 1, 1, 1, 1, 2] ´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
