2015, Diszkrét matematika

Diszkrét matematika 4. el˝oadás ´ MARTON Gy¨ ongyvér 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ó az elmúlt el˝oadáson?

Sz´ amtartom´ anyok: val´ os sz´ amok, komplex sz´ amok, Algoritmusok Python-ban. ”h´ıresebb” irracion´ alis sz´ amok sz´ amjegyeinek a kigener´ al´ asa, n-ik gy¨ ok meghat´ aroz´ asa: Newton m´ odszerrel. logaritmus maghat´ aroz´ asa m´ asodfok´ u egyenlet komplex gy¨ okei frakt´ alok: Mandelbrot, Julia



Mir˝ol lesz szó?

sz´ amtani, mértani, harmonikus sz´ amsorozatok saj´ atos sz´ amsorozatok: a faktori´ alis f¨ uggvény Stirling sz´ amok Fibonacci sz´ amok Lucas sz´ amok Catalan sz´ amok algoritmusok Python-ban



Számsorozatok, haladványok Sz´ amtani sorozat: a, a + d, a + 2d, . . . , a + nd, . . . , ahol az a kezd˝ o tag és a d k¨ ul¨ onbség (differencia) val´ os sz´ amok. A sz´ amtani sorozat az f (x) = d · x + a line´ aris f¨ uggvény diszkrét anal´ ogja. Mértani sorozat: a, ar , ar 2 , . . . , ar n , . . . , ahol az a kezd˝ o tag és az r h´ anyados val´ os sz´ amok. A mértani sorozat az f (x) = a · r x exponenci´ alis f¨ uggvény diszkrét anal´ ogja. Harmonikus sorozat: 1 olyan sorozat, ahol a tagok inverzei sz´ amtani sorozatot alkotnak. an 1 1 1 1 Pl. an = , ahol a sorozat els˝ o 4 tagja a k¨ ovetkez˝ o: 1, , , , . . . n 2 3 4 ´ MARTON Gy¨ ongyv´ er


Algoritmusok Pythonban 1.feladat: Az a kezd˝ o tag´ u, d k¨ ul¨ onbség˝ u sz´ amtani sorozat els˝ o n tagj´ anak ki´ır´ asa: def aseq (a, d, n): i = 0 s = a while i < n: print s, s += d i += 1 Kérdések: Milyen bemenetre kell megh´ıvni a fenti f¨ uggvényt, hogy a k¨ ovetkez˝ o sorozatokat kapjuk? −1, 3, 7, 11, 15, . . . 7, 4, 1, −2, −5, . . . 1, 2, 3, 4, 5, . . . 0, 2, 4, 6, 8, . . . 5, 3, 1, −1, 3, . . . ´ MARTON Gy¨ ongyv´ er


Algoritmusok Pythonban

Sz´ amtani sorozat, rekurzi´ os képlet: x0 = a, xn = d + xn−1 def aseq_R2 (s, d, i): if i == 0: return s print s return aseq_R2 (s+d, d, i-1) megh´ıv´ as: aseq_R2(7, -3, 10)



Algoritmusok Pythonban 2.feladat: Az a kezd˝ o tag´ u, r h´ anyados´ u mértani sorozat els˝ o n tagj´ anak ki´ır´ asa: def gseq (a, r, n): i = 0 p = a while i < n: print p, p *= r i += 1 Kérdések: Milyen bemenetre kell megh´ıvni a fenti f¨ uggvényt, hogy a k¨ ovetkez˝ o sorozatokat kapjuk? 1, −1, 1, −1, 1, . . . 1, 2, 4, 8, 16, . . . 1, 3, 9, 27, 81, . . . 1, 0.5, 0.25, 0.125, 0.0625, . . . 2, 10, 50, 250, 1250, . . . ´ MARTON Gy¨ ongyv´ er



Mértani sorozat, rekurzi´ os képlet: x0 = a, xn = r · xn−1 def gseq_R2 (p, r, i): if i == 0 : return p print p return gseq_R2 (r*p, r, i-1) megh´ıv´ as: gseq_R2(1, 1/2.0, 10)



Számtani sorozatok

Rekurzi´ os képlet: x1 = a, xn = d + xn−1 A sorozat n-ik tagj´ anak kisz´ am´ıt´ asa: xn = x1 + d · (n − 1) A sorozat els˝ o n tagj´ anak o ¨sszege: sn =

2 · x1 + d · (n − 1) ·n 2



Mértani sorozatok

Rekurzi´ os képlet: x1 = a, xn = r · xn−1 A sorozat n-ik tagj´ anak kisz´ am´ıt´ asa: xn = x1 · r n−1 A sorozat els˝ o n tagj´ anak o ¨sszege: sn = x1 ·


rn − 1 , r 6= 1 r −1



3.feladat: Egy személy S euro o ¨sszeget tett be egy bankba, k%-os évi kamatra. N év ut´ an mennyi pénzt tud felvenni a bankb´ ol: N k ciklussal és képlettel: S · 1 + 100 def bank (S, k, N): msum = S for i in range(0, N): msum += msum * (k/100.0) return msum, S * ((1 + k/100.0) ** N)



Algoritmusok Pythonban 4.feladat: Egy személy N éven kereszt¨ ul minden év elején S euro o ¨sszeget tett be egy bankba, k%-os évi kamatra. N év ut´ an mennyi pénzt tud felvenni a bankb´ ol: n k 1+ −1 100 k ciklussal és képlettel: sn = S · 1 + · 100 k 1+ −1 100 def bank1 (S, k, N): msumV = 0 for j in range (1, N + 1): msum = S for i in range(0, j): msum += msum * (k/100.0) msumV += msum k1 = 1 + k/100.0 return msumV, S * k1 * (k1 ** N - 1) / (k1 - 1) ´ MARTON Gy¨ ongyv´ er


Algoritmusok Pythonban 5.feladat: Hat´ arozzuk meg az n-ik Harmonikus sz´ amot a képlet: Hn =

n 1 P k=1 k

3 11 25 137 az els˝ o harmonikus sz´ amok: 1, , , , ,... 2 6 12 60 def osszeg (x, y, a, b): sz = x * b + y * a n = y * b g = lnko (sz, n) return sz/g, n/g def harmonikus (n): s1, s2 = 1, 1 for i in range (2, n+1): a, b = 1, i s1, s2 = osszeg(s1, s2, a, b) return s1, s2 ´ MARTON Gy¨ ongyv´ er


Sajátos számsorozatok A faktori´ alis f¨ uggvény: n! = 1 · 2 · · · · · (n − 1) · n A sz´ amsorozat: 1, 1, 2, 6, 24, 120, 720, . . . , F0 = 1, F1 = 1, F2 = 2, . . . A rekurzi´ os képlet: Fn = n · Fn−1 , A Catalan sz´ amok: A sz´ amsorozat: 1, 1, 2, 5, 14, 42, 132, . . . , C0 = 1, C1 = 1, C2 = 2, . . . A sz´ am´ıt´ asi képlet: Cn =

1 2n n+1 n

! =

(2n)! , (n + 1)! · n!

2(2n + 1) Cn , n+2 alkalmaz´ asi ter¨ ulet: kombinatorika A rekurzi´ os képlet: Cn+1 =



Algoritmusok Pythonban 6.feladat: A faktori´ alis f¨ uggvény, iterat´ıv v´ altozat: def faktI (n): p = 1 for i in range (1, n+1): p *= i return p 7.feladat: A faktori´ alis f¨ uggvény, az o ¨sszes érték kiirat´ asa: def faktI1 (n): p = 1 print p, for i in range (1, n+1): p *= i print p,




8.feladat: A faktori´ alis f¨ uggvény, list´ aba: def faktI2 (n): p = 1 L = [] for i in range (1, n+1): p *= i L += [p] return L




9.feladat: A faktori´ alis f¨ uggvény, rekurz´ıv v´ altozat I: def faktR (n): if n == 0: return 1 return n * faktR (n-1) 10.feladat: A faktori´ alis f¨ uggvény, rekurz´ıv v´ altozat II: def faktR1 (n, res): if n == 0: return res return faktR1 (n-1, n * res) Megh´ıv´ as: faktR1 (10, 1)



Sajátos számsorozatok A Stirling sz´ amok Els˝ ofaj´ u Stirling sz´ amok: az nx · (x − 1) · (x − 2) . . . (x − n + 1) együtthatója = s(n, k) = s(n − 1, k − 1) − (n − 1) · s(n − 1, k), n ≤ k, k M´ asodfaj´ u Stirling sz´ amok: meghat´ arozza, hogy egy n elem˝ u halmaz h´ any k elem˝ u nem u ¨res r´ e szhalmazra bonthat´ o n = s(n, k) = s(n − 1, k − 1) + k · s(n − 1, k), n ≤ k, k ha k == 0, akkor s(n, 0) = 0 ha n == k, akkor s(n, k) = 1 " # n+1 1 kapcsolat a Harmonikus sz´ amokkal: Hn = · 2 n!



Stirling számok

11.feladat: kapcsolat a harmonikus sz´ amok és Stirling sz´ amok k¨ oz¨ ott: def stirling1 (n, k): if k == 0: return 0 if n == k: return 1 return stirling1(n-1, k-1) - (n-1) * stirling1(n-1, k) def harmonikus(n): return stirling1(n+1, 2), faktI(n)



Sajátos számsorozatok A Fibonacci sz´ amok: A sz´ amsorozat: 0, 1, 1, 2, 3, 5, 8, 13, . . . , A rekurzi´ os képlet: F0 = 0, F1 = 1, Fn = Fn−1 + Fn−2 , léteznek hatékonyabb rekurzi´ os ¨ osszef¨ uggések, alkalmaz´ asuk: kombinatorika, algoritmusok fut´ asi idejének elemzése, minden pozit´ıv egész sz´ am fel´ırhat´ o Fibonacci sz´ amok o ¨sszegeként, aranymetszés, zene, m˝ uvészetek, természet. A Lucas sz´ amok: A sz´ amsorozat: 2, 1, 3, 4, 7, 11, 18, 29, 47, . . . , A rekurzi´ os képlet: L0 = 2, L1 = 1, Ln = Ln−1 + Ln−2 ,



Algoritmusok Pythonban 12.feladat: Fibonacci sz´ amok, klasszikus rekurz´ıv megold´ as, nem hatékony: def fibR (n): if n == 0: return 0 if n == 1: return 1 return fibR (n-1) + fibR (n-2) 13.feladat: Fibonacci sz´ amok list´ aba, iterat´ıv megold´ as, line´ aris fut´ asi id˝ o: def fibL (n): a, b = 0, 1 L = [a, b] for i in range (1, n): L += [a + b] temp = a + b a = b b = temp return L ´ MARTON Gy¨ ongyv´ er



14.feladat: Fibonacci sz´ amok, rekurz´ıv megold´ as hatékony, logaritmikus fut´ asi id˝ o: a feladat visszavezethet˝ o a gyorshatv´ anyoz´ as algoritmus´ ara: " Fn =

1 1

1 0

#n−1

" ,

F5 =

1 1

1 0

#4

" =

5 3

3 2

#

és 2 × 2 m´ atrixszorz´ asokra, ahol a m´ atrix speci´ alis alak´ u: " # " # " # a b a b a2 + b 2 b · (a + c) · = b c b c b · (a + c) b 2 + c 2 a m´ atrixot egy sz´ amh´ armassal tudjuk reprezent´ alni: (a, b, c)



Algoritmusok Pythonban A gyors-hatv´ anyoz´ as m´ asképp: def my_pow (x, n): if n == 0: return 1 temp = my_pow (x, n/2) if n % 2 == 1: return x * temp * temp else: return temp * temp Fibonacci sz´ amok, gyors-hatv´ anyoz´ asra visszavezetve: def fibR1 (n): (a, b, c) = sfib (n) return b def sfib (n): if n == 0: return (1, 0, 1) (a, b, c) = sfib (n / 2) (a, b, c) = (a*a + b*b, b*(a+c), b*b + c*c) if n % 2 == 1: return (a+b, a, b) else: return (a, b, c) ´ MARTON Gy¨ ongyv´ er


2015, Diszkrét matematika

Recommend Documents