2016, Diszkrét matematika

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

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ése legnagyobb k¨ oz¨ os oszt´ o algoritmusa, rekurz´ıv v´ altozat L´ anct¨ ortek racion´ alis sz´ amok l´ anct¨ ort jegyei



Mir˝ol lesz szó?

Sz´ amtartom´ anyok: val´ os sz´ amok, komplex sz´ amok racion´ alis sz´ amok l´ anct¨ ort jegyei val´ os sz´ amok l´ anct¨ ort jegyei ”h´ıresebb” irracion´ alis sz´ amok sz´ amjegyeinek a kigener´ al´ asa k-ik gy¨ ok meghat´ aroz´ asa: Newton m´ odszerrel logaritmus maghat´ aroz´ asa m´ asodfok´ u egyenlet komplex gy¨ okei frakt´ alok: Mandelbrot, Julia



Lánctörtek (Continued fraction) A l´ anct¨ ort egy emeletes t¨ ort, amely kétféle alakban is megadhat´ o, ahol a két alak ´ atalak´ıthat´ o egym´ asba: b1

a0 + a1 +

1

d0 +

b2

1

d1 +

b3 a2 + a3 + . . .

d2 +

1 d3 + . . .

A m´ asodik alak esetében 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éges l´ anct¨ ortek, az irracion´ alis sz´ amok végtelen l´ anct¨ ortek.



Algoritmusok Pythonban 1. 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


Algoritmusok Pythonban 2. feladat: hat´ arozzuk meg az ´ at´ırjuk a maradékos oszt´ ast!!

x y

racion´ alis sz´ amnak megfelel˝ o l´ anct¨ ort jegyeit,

def lanct1(x, y): L = [] while 1: temp = x / y L += [temp] r = x - temp * y if r == 0: break x = y y = r return L >>> lanct(61, 47) [1, 3, 2, 1, 4]



Valós számok

a racion´ alis és irracion´ alis sz´ amok halmaza halmazjel¨ olés: R = Q ∪ Q∗ , egy sz´ am egyszerre nem lehet racion´ alis és irracion´ alis is, a val´ os sz´ amokhoz hozz´ arendelhet˝ o, egy mindkét ir´ anyban végtelen egyenes egy-egy pontja, kommutat´ıvit´ as, asszociat´ıv´ıt´ as, disztribut´ıv´ıt´ as, az egész sz´ amokkal ellentétben a val´ os sz´ amok halmaza nem megsz´ aml´ alhat´ o, a sz´ am´ıt´ astechnik´ aban nem val´ os mennyiségekkel dolgozunk, ezek egy k¨ ozel´ıt˝ o értéke lesz elt´ arolva: lebeg˝ opontos ´ abr´ azol´ as,



Valós számok A val´ os sz´ amok halmaza nem megsz´ aml´ alhat´ o: feltételezz¨ uk, az ellenkez˝ ojét, ha a val´ os sz´ amok halmaza megsz´ aml´ alhat´ o lenne, akkor, a 0 és 1 k¨ oz¨ otti val´ os sz´ amok halmaza is megsz´ aml´ alhat´ o lenne, létezik egy sz´ amsorozat, amelyet a 0 és 1 k¨ oz¨ otti val´ os sz´ amok alkotnak : r1 , r2 , . . . , rn , . . . , alkalmazzuk a k¨ ovetkez˝ o´ abr´ azol´ asi m´ odot: r1 r2 r3 r4 .. . ahol dij ∈ {0, 1, 2, . . . , 9} ekkor az r = 0.d1 d2 d3 d4 . . .

= = = =

0.d11 d12 d13 d14 . . . 0.d21 d22 d23 d24 . . . 0.d31 d32 d33 d34 . . . 0.d41 d42 d43 d44 . . .

egy u ´j val´ os sz´ am lesz,amely nem szerepel a 4 ha dii 6= 4, fenti szab´ aly szerint megadott list´ aban, ahol di = 5 ha dii = 4. ´ MARTON Gy¨ ongyv´ er


Valós számok

Példa: r1 r2 r3 r4 .. .

= = = =

0.3567842 . . . 0.2146577 . . . 0.8945678 . . . 0.3452109 . . .

A list´ aban nem szerepl˝ o val´ os sz´ am: 0.4454 . . . , mert d11 6= 4, d22 6= 4, d33 = 4, d44 6= 4, . . . .



Algoritmusok Pythonban 3. feladat: hat´ arozzuk meg az a val´ os sz´ amnak megfelel˝ o l´ anct¨ ort jegyeit from math import floor def lanctReal(a, prec): temp = floor(a) L = [int(temp)] i = 0 while i < prec and a != temp: a = 1.0 / (a - temp) temp = floor(a) L += [int (temp)] i += 1 return L >>> lanctReal(61/47.0, 5) [1, 3, 2, 1, 3, 1] ´ MARTON Gy¨ ongyv´ er


Algoritmusok Pythonban 3. feladat: >>> import math >>> lanctReal(math.sqrt(2), 10) [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] >>> lanctReal(math.sqrt(6), 10) [2, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4] >>> lanctReal(math.pi, 15) [3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 3, 3, 23] >>> lanctReal(math.e, 15) [2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1]



Python sintaxis A Decimal t´ıpus: a Decimal t´ıpus a decimal modulban van defini´ alva, a felhaszn´ al´ o´ altal o ´hajtott pontoss´ aggal ´ abr´ azolja a lebeg˝ opontos (val´ os) sz´ amokat, a getcontext.prec() seg´ıtségével a tizedes jegyek sz´ am´ at adhatjuk meg, Az int, a float, a string t´ıpusokb´ ol egyar´ ant létre lehet hozni Decimal t´ıpus´ u értéket. >>> 0.1 + 0.1 - 0.2 0.0 >>> 0.1 + 0.1 + 0.1 - 0.3 5.551115123125783e-17



Python sintaxis

>>> Decimal(0.1) Decimal(’0.1000000000000000055511151231257827021181583404541015625’)

>>> Decimal(’0.1’) Decimal(’0.1’) >>> Decimal(’0.1’) + Decimal(’0.1’) + Decimal(’0.1’) - Decimal(’0.3’) Decimal(’0.0’)



Algoritmusok Pythonban

4. feladat: a

√ n érték meghat´ aroz´ asa l´ anct¨ ortek seg´ıtségével

A kiindul´ o képlet a k¨ ovetkez˝ o, ahol a értéke egy ak´ armilyen sz´ am: √

ha a = 1, akkor:

√

n=a+

2 n−a √ a+ n

n−1

n =1+

n−1

2+

n−1

2+

2+


n−1 2 + ...


Algoritmusok Pythonban 5. feladat: a

√ 2 értékének meghat´ aroz´ asa l´ anct¨ ortek seg´ıtségével: √

1

2=1+

1

2+

1 2 + ... from decimal import Decimal, getcontext 2+

def lanct_sqrt(): p = 500 getcontext().prec = 30 # 30 szamjegy temp = Decimal(0) for x in range (0, p): temp = 1 / (2 + temp) return 1 + temp >>> lanct_sqrt() Decimal(’1.41421356237309504880168872421’) ´ MARTON Gy¨ ongyv´ er


A π szám

a k¨ or ker¨ uletének és ´ atmér˝ ojének h´ anyadosa az eukleidészi geometri´ aban m´ as defin´ıci´ ok is léteznek, melyek kihagyj´ ak a k¨ ort irracion´ alis és transzcendens sz´ am (nincs olyan egész egy¨ utthat´ os polinom amelynek gy¨ oke lenne) 6. feladat: a π értékének meghat´ aroz´ asa l´ anct¨ ortek seg´ıtségével 4

π=

1

1+

2

2

3+ 5+

1

π =3+

2

32 7 + ...


32

6+

52

6+ 6+


72 6 + ...

A π szám

def lanct_pi(): p = 1000 getcontext().prec = 100 # 100 szamjegy temp = Decimal(0) for x in range (p + 1, 0, -1): a = x * x b = 2 * x + 1 temp = a / (b + temp) return 4 / (1 + temp) >>> lanct_pi() Decimal(’3.1415926535897932384626433832795028841971693993751058209 74944592307816406286208998628034825342117067’)



Az e szám

irracion´ alis és transzcendens sz´ am t¨ obbféleképpen lehet értelmezni: e = lim

n→∞

1 1+ n

n .

Az e értékének meghat´ aroz´ asa l´ anct¨ ortek seg´ıtségével: 1

e =2+

1

1+

2

2+ 3+


3 4 + ...


Algoritmusok Pythonban 7. feladat: a loge z értékének meghat´ aroz´ asa l´ anct¨ ortek seg´ıtségével z

log(1 + z) =

12 · z

1+

12 · z

2+

22 · z

3+ 4+

22 · z 5+

32 · z 6 + ...

def lanct_log(z, p, szj): z -= 1 getcontext().prec = szj temp = Decimal(0) for x in range (p, 0, -1): t = (x + 1) / 2 a = x + 1 b = t * t * z temp = b / (a + temp) return z / (1 + temp) ´ MARTON Gy¨ ongyv´ er


Algoritmusok Pythonban 7. feladat: >>> lanct_log(2, 500, 20) Decimal(’0.69314718055994530940’) >>> import math >>> math.log(2) 0.6931471805599453 >>> lanct_log(Decimal(math.e), 1000, 20) Decimal(’0.99999999999999994681’) >>> math.log(math.e) 1.0



Algoritmusok Pythonban 8. feladat: a sin(z) értékének meghat´ aroz´ asa l´ anct¨ ortek seg´ıtségével z

sin(z) =

z2

1+ 2 · 3 − z2 +

2 · 3 · z2 4 · 5 − z2 +

4 · 5 · z2 6 · 7 − z2 + . . .

def lanct_sin(z): p = 300 getcontext().prec = 50 temp = Decimal(0) for x in range (2*p, 0, -2): a = (x+2) * (x+3) - z*z b = x * (x+1) * z * z temp = b / (a + temp) temp = z*z / (2*3-z*z + temp) return z / (1 + temp)



Algoritmusok Pythonban 8. feladat: >>> lanct_sin(60) Decimal(’-0.30481062110221670562576204186131345751440565822218’) >>> import math >>> math.sin(60) -0.3048106211022167 >>> math.sqrt(3)/2 0.8660254037844386 >>> math.sin(60 * math.pi/180) 0.8660254037844386



Algoritmusok Pythonban 8. feladat: def lanct_sinR(z): p = 300 getcontext().prec = 50 z = Decimal(z * math.pi/180) #atalakitjuk a szoget radianna temp = Decimal(0) for x in range (2*p, 0, -2): a = (x+2) * (x+3) - z*z b = x * (x+1) * z * z temp = b / (a + temp) temp = z*z / (2*3-z*z + temp) return z / (1 + temp) >>> lanct_sinR(60) Decimal(’0.86602540378443858934550903079182617193526553351420’)



Aranymetszés, aranyarány (Golden Ratio), a ϕ szám két mennyiség, a, b, a > b az aranymetszés szerint ar´ anylik egym´ ashoz, ha fenn´ all: a a + b def = = ϕ b a

a ϕ meghat´ aroz´ asa érdekében 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 . . . és ϕ ˆ= = −0.61803 . . . 2 2 a ϕ irracion´ alis sz´ am ´ MARTON Gy¨ ongyv´ er


Aranymetszés, aranyarány (Golden Ratio), a ϕ szám

ép´ıtészet: Parthenon homlokzat´ anak ar´ anyértékei: logok: Toyota, Mercedesz, stb. Pentagramma (szab´ alyos o ¨tsz¨ og):

piros zold

=

zold kek

=

kek lila

=ϕ

természet: napraforg´ o spirlajai



Aranymetszés, aranyarány (Golden Ratio), a ϕ szám

Kiindulva az al´ abbi o ¨sszef¨ uggésb˝ ol: ϕ = 1 +

1 , l´ anct¨ ortek seg´ıtségével is ϕ

fel´ırhatjuk a ϕ értékét: 1

ϕ=1+

1

1+ 1+

1 1+


1 ..

.


Algoritmusok Pythonban 9. feladat: gy¨ okvon´ as, a k-ik gy¨ ok meghat´ aroz´ asa, Newton féle m´ odszer alapj´ an √ 1h n i k n meghat´ aroz´ asa: xi+1 = (k − 1) · xi + k−1 , ahol x0 = 1 egy k xi kezdeti érték. ha k = 2, akkor a négyzetgy¨ ok meghat´ aroz´ as´ anak képlete: n 1 xi+1 = · xi + 2 xi a beép´ıtett ∗∗ oper´ atorral: >>> 10 ** 0.5 3.1622776601683795

>>> from decimal import Decimal, getcontext >>> getcontext().prec = 100 >>> 10 ** Decimal(’0.5’) Decimal(’3.16227766016837933199889354443271853371955513932521682685...’) ´ MARTON Gy¨ ongyv´ er


Algoritmusok Pythonban 10. feladat: négyzetgy¨ okvon´ as xi+1 =

n 1 · xi + 2 xi x0 = 1

from decimal import Decimal, getcontext def my_sqrt(n): getcontext().prec = 100 n = Decimal(n) x0 = 1 while True: xi = (x0 + n/x0)/2 if xi == x0: return xi x0 = xi



Algoritmusok Pythonban

11. feladat: természetes alap´ u logaritmus meghat´ aroz´ asa. Haszn´ alhat´ oo ¨sszef¨ uggések: ln (x) = (x − 1) −

∞ (−1)n+1 P (x − 1)2 (x − 1)3 (x − 1)4 + − ··· = (x − 1)n 2 3 4 n n=1

ln (x) = lim n · (x 1/n − 1) n→∞

def ln(x): n = 100000000.0 return n * ((x ** (1/n)) - 1)



Komplex számok A komplex sz´ amok a val´ os sz´ amhalmaz egy olyan b˝ ov´ıtése, melyben negat´ıv sz´ amok esetén is értelmezett a gy¨ okvon´ as. halmazjel¨ olés: C, és h´ arom modell alapj´ an is értelmezhet˝ o: halmazelméleti, geometriai, algebrai modellek halmazelméleti modell: C = {(a, b)|a ∈ R, b ∈ R} , azaz a sz´ amhalmazt rendezett sz´ amp´ arok alkotj´ ak, ahol az elemek val´ os sz´ amok, imagin´ arius rész: az a komplex sz´ am amelynek négyzete -1, jele az i a komplex sz´ amok a + bi alakban ´ırhat´ oak fel, ahol a val´ os rész, b az imarin´ arius rész ha b = 0, akkor val´ os sz´ amot kapunk a val´ os sz´ amok k¨ or´ eben megismert m˝ uveleti tulajdons´ agok megmaradnak addit´ıv semleges elem: z = 0 + 0i multiplikat´ıv semleges elem: z = 1 + 0i addit´ıv inverz elem: −z = −a − bi, multiplikat´ıv inverz elem: 1/z = a/(a2 + b 2 ) − b/(a2 + b 2 )i, z 6= 0



M˝uveletek komplex számokkal M˝ uveleti szab´ alyok: a

=

abs(a)

=

a1 + a2 i p a12 + a22

b

=

b1 + b2 i

a+b

=

(a1 + b1 ) + (a2 + b2 )i

a−b

=

(a1 + b1 ) − (a2 + b2 )i

a·b 1 b a b

=

(a1 · b1 − a2 · b2 ) + (a2 · b1 + a1 · b2 )i b1 b2 − 2 i (b12 + b22 ) (b1 + b22 ) 1 a· b

= =



(1)

Komplex számok Pythonban >>> a = complex(2, 4) >>> a.imag 4.0 >>> a.real 2.0 >>> abs(a) 4.47213595499958 >>> b = complex(1,10) >>> a + b (3 + 14j) >>> a - b (1 - 6j) >>> a * b (-38 + 24j) >>> a / b (0.4158415841584159 - 0.15841584158415842j) ´ MARTON Gy¨ ongyv´ er


Algoritmusok Pythonban 12. feladat: Hat´ arozzuk meg egy m´ asodfok´ u egyenlet gy¨ okeit def megyenlet2 (a, b, c): if a == 0: return egyenlet(b, c) delta = b*b - 4*a*c if delta < 0: valosR = -b / (2*a) imagR = math.sqrt( abs (delta)) / (2 * a) gy1 = complex(valosR, imagR) gy2 = complex(valosR, -imagR) return (gy1, gy2) if delta == 0: gy = -b/(2*a) return (gy, gy) if delta > 0: gy1 = (-b + math.sqrt(delta)) / (2*a) gy2 = (-b - math.sqrt(delta)) / (2*a) return ( gy1, gy2 ) ´ MARTON Gy¨ ongyv´ er


Mandelbrot fraktál

Frakt´ alok: kiindulva egy komplex sz´ amb´ ol, egy iter´ aci´ os folyamat eredményeként a képerny˝ ore kirajzolt pontok frakt´ al alakzatokat hozhatnak létre minél nagyobb az iter´ aci´ o sz´ am, ann´ al jobb a kirajzolt kép min˝ osége a Mandelbrot halmaz iter´ aci´ os képlete: zn+1 = (zn )2 + c, ahol a kezdeti z0 értéket és a c értéket a programoz´ o´ all´ıtja be a Mandelbrot halmaz azokat a c komplex sz´ amokat fogja tartalmazni, amelyekre a zn sorozat nem tart a végtelenbe, és z0 = 0 a zn sorozat a végtelenbe tart, ha az abszol´ utértéke nagyobb lesz mint 2.



Algoritmusok Pythonban 13. feladat: Hat´ arozzuk meg a Mandelbrot halmaz elemeit. Egy halmazbeli elem esetén rajzoljunk #-t a képerny˝ ore, m´ asképp space-t. def fMan(): L1 = [a*0.07 for a in range (-15, 16)] L2 = [a*0.04 for a in range (-50, 26)] for y in L1: L = "" for x in L2: z = 0 c = complex(x, y) for i in range (40): z = z ** 2 + c if abs(z) > 2: L += " " break if abs(z) <= 2: L += "#" print L ´ MARTON Gy¨ ongyv´ er


Julia fraktál 14. feladat: Hat´ arozzuk meg a Julia halmaz elemeit. A Julia halmaz iter´ aci´ os képlete ugyanaz, mint a Mandelbrot halmazé, azzal a k¨ ul¨ onbséggel, hogy a c értéke itt konstans, legyen c = −1 − 0.25i def fJulia(): L1 = [a*0.07 for a in range (-15, 16)] L2 = [a*0.04 for a in range (-40, 36)] c = complex (-1, -0.25) for y in L1: L = "" for x in L2: z = complex(x, y) for i in range (40): z = z ** 2 + c if abs(z) > 2: L += " " break if abs(z) <= 2: L += "#" print L ´ MARTON Gy¨ ongyv´ er


Megjegyzések

az L1, L2 intervallumokat m´ odos´ıthatjuk, a kirajzolt alakzat nagyobb lesz: L1 = [a*0.05 for a in range (-20, 21)] L2 = [a*0.02 for a in range (-80, 31)] a grafikus megjelen´ıtéshez haszn´ aljuk a pygmae csomagot (lehet m´ ast is): http://www.pygame.org/download.shtml a grafikus megjelen´ıtés forr´ asa: http://fractalart.gallery/mandelbrot-set-in-python-pygame



Mandelbrot fraktál, grafikus megjelen´ıtés

from pygame.locals import * import pygame def mainMa(): width, height = 800, 800 screen = pygame.display.set_mode((width,height),DOUBLEBUF) xaxis = width/1.5 yaxis = height/2 scale = 200.0 iterations = 40 for iy in range(height/2+1): for ix in range(width): z = 0 c = complex((ix - xaxis)/scale, (iy - yaxis)/scale)



Mandelbrot fraktál, grafikus megjelen´ıtés for i in range(iterations): z = z**2 + c if abs(z) > 2: v = 765*i/iterations if v > 510: color = (255, 255, v%255) elif v > 255: color = (255, v%255, 0) else: color = (v%255, 0, 0) break if abs(z) <= 2: color = (0, 0, 0) #end for screen.set_at((ix, iy), color) screen.set_at((ix, height-iy), color) #end for, for



Mandelbrot fraktál, grafikus megjelen´ıtés

pygame.display.update() while True: event = pygame.event.poll() if (event.type == QUIT or (event.type == KEYDOWN and event.key == K_ESCAPE)): break #end def mainMa() pygame.quit()



Mandelbrot fraktál



Julia fraktál, grafikus megjelen´ıtés from pygame.locals import * import pygame def mainJu(): width, height = 800,1000 #width, height = 320, 320 screen = pygame.display.set_mode((width,height),DOUBLEBUF) xaxis = width/2.0 yaxis = height/3.7 scale = 170.0 iterations = 40 c = complex (-0.824, -0.17711) for iy in range(height/2 + 1): for ix in range(width): z = complex((ix - xaxis)/scale, (iy-yaxis)/scale) for i in range(iterations): z = z**2 + c if abs(z) > 2.0: color = (i % 8 * 32, i % 16 * 16, i % 32 * 8) break ´ MARTON Gy¨ ongyv´ er


Julia fraktál, grafikus megjelen´ıtés

if abs(z) <= 2: color = (0, 0, 0) screen.set_at((ix, iy), color) screen.set_at((width, height), color) #end for, for pygame.display.update() while True: event = pygame.event.poll() if (event.type == QUIT or (event.type == KEYDOWN and event.key == K_ESCAPE)): break #end def mainJu() pygame.quit()



Julia fraktál c = complex (-0.824, -0.17711)



Julia fraktál

Tov´ abbi c értékek a Julia frakt´ alhoz: c c c c c c

= = = = = =

complex complex complex complex complex complex

(0.285, 0.013) (-0.295, -0.55) (-0.63, -0.407) (-0.624, 0.435) (-1, -0.25) (-1, -0)



2016, Diszkrét matematika

Recommend Documents