Diszkr´et matematika 7. 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?
az ord, chr f¨ uggv´enyek az index met´ odus bitm˝ uveletek a base64 k´ odol´ as bin´ aris ´ allom´ any hexa form´ atuma
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Mir˝ol lesz sz´o?
a Fibonacci sz´ amsorozat a Fibonacci sz´ amrendszer beolvas´ asi lehet˝ os´egek: a split ´es join f¨ uggv´enyek pr´ımsz´ amok
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
A Fibonacci sz´amsorozat A sz´ amsorozat: 0, 1, 1, 2, 3, 5, 8, 13, . . . , A rekurzi´ os k´eplet: F0 = 0, F1 = 1, Fn = Fn−1 + Fn−2 , l´eteznek hat´ekonyabb rekurzi´ os ¨ osszef¨ ugg´esek, alkalmaz´ asuk: kombinatorika, algoritmusok fut´ asi idej´enek elemz´ese, minden pozit´ıv eg´esz sz´ am fel´ırhat´ o Fibonacci sz´ amok o ¨sszegek´ent, aranymetsz´es, zene, m˝ uv´eszetek, term´eszet. A Lucas sz´ amok, ugyanaz az o ¨sszef¨ ugg´es a sz´ amok k¨ oz¨ ott, m´ as a k´et kezdeti ´ert´ek: A 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 ,
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
A Fibonacci sz´amsorozat A klasszikus rekurz´ıv megold´ as, nem hat´ekony, exponenci´ alis: def fibR1 (n): if n == 0: return 0 if n == 1: return 1 return fibR1 (n-1) + fibR1 (n-2) A k¨ ovetkez˝ o algoritmus fut´ asi ideje line´ aris: def sfib(a, b, n): if n == 1: return a return sfib(b, a + b, n-1) def fibR2(n): return sfib(1, 1, n) >>> fibR2(100) 354224848179261915075 Mi lesz az algoritmus iterativ v´ altozata? ´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
A Fibonacci sz´amsorozat
L´etezik logaritmikus fut´ asi idej˝ u algoritmus: a feladat visszavezethet˝ oa gyorshatv´ anyoz´ as algoritmus´ ara: " #n−1 " #4 " # 1 1 1 1 5 3 Fn = , F5 = = 1 0 1 0 3 2 ahol meg kell teh´ at hat´ arozni k´et 2 × 2 m´ atrix szorzat´ at: # " # " # " a1 a2 b1 b2 a1 · b1 + a2 · b3 a1 · b2 + a2 · b4 · = a3 a4 b3 b4 a3 · b1 + a4 · b3 a3 · b2 + a4 · b4 A hat´ekonys´ ag v´egett a m´ atrixot egy sz´ amh´ armassal is lehet ´ abr´ azolni, mert az a2 ´es a3 elemek megegyeznek.
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
A Fibonacci sz´amsorozat
A k´et 2x2-es m´ atrix szorzata: def mSzt((a1, a2, a3, a4), (b1, b2, b3, b4)): c1 = a1 * b1 + a2 * b3 c2 = a1 * b2 + a2 * b4 c3 = a3 * b1 + a4 * b3 c4 = a3 * b2 + a4 * b4 return (c1, c2, c3, c4) Feladat: felhaszn´ alva a fenti algoritmust hat´ arozzuk meg a n-ik Fibonacci sz´ amot, a gyorshatv´ anyoz´ as algoritmus´ ara visszavezetve. Hogyan lehet m´eg hat´ekonyabb´ a tenni az algoritmust?
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
A Fibonacci sz´amsorozat, o¨sszef¨ugg´esek Fenn´ all a k¨ ovetkez˝ o: lim
n→∞
Fn+1 =ϕ Fn
Bizony´ıt´ as, v´ azlat: lim
n→∞
Fn+1 Fn + Fn−1 = lim = 1 + lim n→∞ n→∞ Fn Fn
1 Fn Fn−1
1 Fn+1 Fn fenn´ all teh´ at: x = 1 + , ahol a lim = lim =x n→∞ Fn n→∞ Fn−1 x jel¨ ol´est alkalmaztuk. 1 megoldva a x = 1 + egyenletet kapjuk, a k´ert o ¨sszef¨ ugg´est x Binet formula (bizony´ıt´ as matematikai indukci´ oval): √ √ (1 + 5)n − (1 − 5)n ϕn − ϕ ˆn √ Fn = √ = 5 2n · 5 ´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
A Fibonacci sz´amsorozat, o¨sszef¨ugg´esek
√
√
( 1+2 5 )n − ( 1−2 5 )n (1 + √ Fn = = 5
√
5)n − (1 − √ 2n · 5
√
5)n
from math import sqrt def fibN1 (n): temp = pow((1 + sqrt(5))/2, n) - pow ((1 - sqrt(5))/2, n) return int( temp / sqrt(5)) def fibN2 (n): temp = ((1 + sqrt(5))/2) ** n - ((1 - sqrt(5))/2) ** n return int( temp / sqrt(5))
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
A Fibonacci sz´amsorozat Adott n ´ert´ekig, egy sz´ amsorozatba hat´ arozzuk meg k´et egym´ as melletti Fibonacci sz´ am ar´ any´ at: def fibRate(nr): n, L = fibL(nr) fR = [] for i in range(1, n): fR += [ float(L[i]) / L[i-1] ] return fR >>> fibRate(500) [1.0, 2.0, 1.5, 1.6666666666666667, 1.6, 1.625, 1.6153846153846154, 1.619047619047619, 1.6176470588235294, 1.6181818181818182, 1.6179775280898876, 1.6180555555555556, 1.6180257510729614] A fibL f¨ uggv´eny meghat´ arozza nr-n´el kisebb Fibonacci sz´ amok sz´ am´ at, illetve a Fibonacci sz´ amok list´ aj´ at. ´Irjuk meg ezt a f¨ uggv´enyt!! ´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
A Fibonacci sz´amsorozat Hat´ arozzuk meg egy sz´ am Fibonacci sz´ amrendszerbeli alakj´ at. Az eredm´enyt egy string t´ıpus´ u v´ altoz´ oba gener´ aljuk ki: def fibBaseStr(nr): n, L = fibL(nr) #print L[n:0:-1] bL = ’’ i = n - 1 while i > 1: nr -= L[i] bL += str(1) i -= 1 while L[i] > nr and i > 1: bL += str(0) i -= 1 print bL >>> fibBaseStr(100) 1000010100 ´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
A split ´es join f¨uggv´enyek >>> mStr = ’Sapientia EMTE Kolozsvar, 2016/2017’ >>> Lstr = mStr.split() >>> Lstr [’Sapientia’, ’EMTE’, ’Kolozsvar,’, ’2016/2017’] >>> ’’.join(Lstr) ’SapientiaEMTEKolozsvar,2016/2017’ >>> ’ ’.join(Lstr) ’Sapientia EMTE Kolozsvar, 2016/2017’ >>> Lstr = mStr.split(’,’) >>> Lstr [’Sapientia EMTE Kolozsvar’, ’ 2016/2017’] >>> ’’.join(Lstr) ’Sapientia EMTE Kolozsvar 2016/2017’
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
A split ´es join f¨uggv´enyek
>>> mStr = ’http://www.ms.sapientia.ro/~mgyongyi/DiszkretMat/feladatok5.html’ >>> Lstr = mStr.split(’/’) >>> Lstr [’http:’, ’’, ’www.ms.sapientia.ro’, ’~mgyongyi’, ’DiszkretMat’, ’feladatok5.html’] >>> ’’.join(Lstr) ’http:www.ms.sapientia.ro~mgyongyiDiszkretMatfeladatok5.html’ >>> ’/’.join(Lstr) ’http://www.ms.sapientia.ro/~mgyongyi/DiszkretMat/feladatok5.html’ >>> mStr[7:].split(’/’) [’www.ms.sapientia.ro’, ’~mgyongyi’, ’DiszkretMat’, ’feladatok5.html’]
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
A split ´es join f¨uggv´enyek >>> ido = ’12:30:45’ >>> o, p , mp = ido.split(’:’) >>> print o, p, mp 12 30 45 >>> o, p = ido.split(’:’, 1) >>> print o, p 12 30:45 Az enter ment´en osztjuk fel az ´ allom´ any tartalm´ at, meghat´ arozzuk az ´ allom´ any sorainak sz´ am´ at: def fileSplit1(fnev): inf = open(fnev, ’rt’) mStr = inf.read() inf.close() nStr = mStr.split(’\ n’) print len(nStr) >>> fileSplit(’labor6.py’) ´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Beolvas´asi lehet˝os´egek
def beolv1(): x = raw_input() return x >>> beolv1() 12 67 8 90 ’12 67 8 90’ def beolv2(): x = raw_input().split() return x >>> beolv2() 12 3 56 78 901 [’12’, ’3’, ’56’, ’78’, ’901’]
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Beolvas´asi lehet˝os´egek def beolv3(): y = [] x = raw_input().split() for elem in x: y += [int(elem)] return y >>> beolv3() 12 4 5 67 890 [12, 4, 5, 67, 890] def beolv4(): x = map(int, raw_input().split()) return x >>> beolv4() 1 0 1 0 1 1 0 1 [1, 0, 1, 0, 1, 1, 0, 1]
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Beolvas´asi lehet˝os´egek
def beolv5(): x = raw_input() return map(int, list(x)) >>> beolv5() 101011 [1, 0, 1, 0, 1, 1] def beolv6(): x = raw_input() return map(str, list(x)) >>> beolv6() aed454e [’a’, ’e’, ’d’, ’4’, ’5’, ’4’, ’e’]
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Beolvas´asi lehet˝os´egek def beolv7(): y = [] x = raw_input() xStr = map(str, list(x)) for e in xStr: if e in ’0123456789’: y += [int(e)] elif e in ’abcdef’: y += [ord(e) - 97 + 10] elif e in ’ABCDEF’: y += [ord(e) - 65 + 10] else: print ’bad chars’ return return y >>> beolv7() aed55a [10, 14, 13, 5, 5, 10]
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Pr´ımsz´amok Pr´ımsz´ amok: azok az 1-n´el nagyobb eg´esz sz´ amok, amelyek nem oszthat´ oak, csak 1-el ´es o ¨nmagukkal. ¨ Osszetett sz´ amok: azok az 1-n´el nagyobb eg´esz sz´ amok, amelyek nem pr´ımsz´ amok.
1. t´etel Minden 1-n´el nagyobb pozit´ıv eg´esz sz´ amnak van egy pr´ımoszt´ oja. A bizony´ıt´ as indirekt bizony´ıt´ asi m´ odszerrel t¨ ort´enik: tegy¨ uk fel az ellenkez˝ oj´et, azaz l´etezik egy olyan sz´ am amelyiknek nincs pr´ımoszt´ oja; ezek a sz´ amok meghat´ aroznak egy nem u ¨res halmazt. A term´eszetes sz´ amok j´ olrendzetts´eg tulajdons´ aga alapj´ an ebben a halmazban van egy legkisebb ilyen elem, legyen ez n. Mivel n-nek nincs primoszt´ oja, de n osztja n-t, k¨ ovetkezik, hogy n nem pr´ımsz´ am. Azaz n = a · b, 1 < a < n, 1 < b < n. Mivel a < n k¨ ovetkezik, hogy a-nak van primoszt´ oja. De a b´ armely oszt´ oja osztja n-t, ez pedig ellentmond´ as. ´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Pr´ımsz´amok 2. t´etel V´egtelen sok pr´ımsz´ am l´etezik. Egyik bizony´ıt´ asi m´ odszer Eukleid´esz, Elemek c´ım˝ u k¨ onyv´eben tal´ alhat´ o: felt´etelezz¨ uk, hogy a pr´ımsz´ amok halmaza v´eges. Legyenek ezek p1 , p2 , . . . , pn . El˝ o´ all´ıthat´ o Q = p1 · p2 . . . pn + 1. Bebizony´ıthat´ o, hogy Q-nak viszont van egy olyan pr´ımoszt´ oja amelyik nem szerepel a fenti pr´ımsz´ amok list´ aj´ aban. Legyen ez q ´es felt´etelezz¨ uk, hogy megegyezik valamelyik pj -vel. Ez azonban azt jelenti hogy q osztja Q − p1 · p2 . . . pn = 1, azaz 1-t. Ez ellentmond´ as, mert egy pr´ımsz´ am nem oszthatja az 1-et. Pl. Ha o ¨sszeszorozzuk az els˝ o 6 pr´ımsz´ amot, akkor kapunk egy olyan sz´ amot, amelynek biztosan lesz egy u ´j pr´ımsz´ am oszt´ oja: 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031 = 59 · 509 Hendrik Lenstra: V´egtelen sok o ¨sszetett sz´ am l´etezik. Ahhoz, hogy egy u ´j o ¨sszetett sz´ amot kapjunk szorozzuk o ¨ssze az els˝ ono ¨sszetett sz´ amot ´es ne adjunk hozz´ a 1-et. ´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Pr´ımsz´amok 3. t´etel Ha n egy o ¨sszetett sz´ am, √ akkor n-nek van egy olyan pr´ımoszt´ oja, amelyik kisebb vagy egyenl˝ o mint n. Bizony´ıt´ asa a 1. t´etel alapj´ an t¨ ort´enik. Ha n o ¨sszetett, akkor n = √ a · b, ahol 1 < a ≤ b < n. Fenn kell ´ a lljon, hogy a ≤ ask´epp √ √ n, mert m´ √ n < a ≤ b ⇒ n = n · n < a · b. Az 1. t´etel alapj´ an a-nak van √ egy pr´ımoszt´ oja, amelyik n-nek is pr´ımoszt´ oja, amelyik teh´ at ≤ n. A t´etel alapj´ an algoritmusok adhat´ oak meg a pr´ımsz´ amok vizsg´ alat´ ara: oszt´ asi pr´ oba m´ odszere (trial division): ´ allap´ıtsuk meg egy adott sz´ amr´ ol, hogy pr´ımsz´ am-e, Eratoszten´esz szit´ aja: hat´ arozzuk meg egy adott n-ig az o ¨sszes pr´ımsz´ amot, hat´ekonyabb algoritmusok: Miller-Rabin pr´ımteszt, Solovay-Strassen pr´ımteszt, AKS pr´ımteszt, stb. ´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Pr´ımsz´amok
Vizsg´ aljuk meg az oszt´ asi pr´ oba m´ odszer´evel, hogy 101 pr´ımsz´ am-e: a c´el: min´el kevesebb oszt´ ast v´egezz¨ unk az oszthat´ os´ ag eld¨ ont´es´ehez, a 11-el m´ ar nem kell megvizsg´ os´ agot, mert √ alni az oszthat´ 11 · 11 = 121 > 101, vagy b 101c < 11 milyen sz´ amokkal vizsg´ aljuk az oszthat´ os´ agot? csak a p´ aratlan sz´ amokkal vizsg´ aljuk az oszthat´ os´ agot, mert a 2-n´el nagyobb pr´ımsz´ amoknak nem lehet p´ aros oszt´ ojuk, 101 nem oszthat´ o 3, 5, 7, 9 ⇒ 101 pr´ımsz´ am.
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
Algoritmusok Pythonban Vizsg´ aljuk meg az oszt´ asi pr´ oba m´ odszer´evel, hogy n pr´ımsz´ am-e def triald1(n): if n == 2: return True if n % 2 == 0: return False i = 3 while i*i <= n: if n % i == 0: return False i += 2 return True
def triald2(n): i = 3 while i*i <= n: if n % i == 0: return False i += 2 return True
Ha bemenetnek csak p´ aratlan sz´ amot adhatunk, akkor a triald2(n) f¨ uggv´ennyel dolgozunk.
´ MARTON Gy¨ ongyv´ er
2016, Diszkr´ et matematika
