Algoritmusok, adatszerkezetek, objektumok 1. el˝ oad´as Sergy´an Szabolcs
[email protected] ´ Obudai Egyetem Neumann J´ anos Informatikai Kar
2011. szeptember 14.
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
1 / 33
Tant´argy c´elja 1
Algoritmikus gondolkod´as kialak´ıt´asa, egyszer˝ u algoritmusok megismer´ese
2
Az objektumorient´alt programoz´asi paradigma alapjainak megismer´ese
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
2 / 33
Tananyag fel´ep´ıt´ese 1
Algoritmus, algoritmus le´ır´asi m´ odjai
2
Struktur´alt programoz´as, vez´erl´esi szerkezetek
3
Programoz´asi t´etelek Objektum orient´alt programoz´as
4
1 2 3 4 5
Oszt´aly, objektum Mez˝ o, met´ odus Konstruktor, destruktor Egys´egbez´ar´as, l´athat´ os´ag Statikus tagok
5
Rendez´esi algoritmusok
6
Logaritmikus keres´es
7
Halmazm˝ uveletek
8
Rekurzi´o
9
Tov´abbi algoritmusok Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
3 / 33
Al´a´ır´as felt´etele Z´arthelyi ´ır´asa az utols´ o el˝ oad´ason >= 40% eset´en al´a´ır´as <= 20% eset´en letilt´as egy´ebk´ent p´ otl´asi lehet˝ os´eg a vizsgaid˝ oszak elej´en
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
4 / 33
Vizsgajegy Al´a´ır´as birtok´aban lehet vizsg´ara jelentkezni
Ponthat´arok Teljes´ıtm´ eny % 88–100 76–87 64–75 51–63 0–50
Sergy´ an (OE NIK)
AAO 01
´ Erdemjegy jeles (5) j´ o (4) k¨ ozepes (3) el´egs´eges (2) el´egtelen (1)
2011. szeptember 14.
5 / 33
Aj´anlott irodalom ´ algoritmusok. Scolar Kiad´o, 2003 Cormen, Leiserson, Rivest, Stein: Uj http://nik.uni-obuda.hu/sergyan/aao
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
6 / 33
Mi az az algoritmus? 1957 el˝ott nem lehetett megtal´alni az algorithm sz´ot a Webster’s sz´ot´arban. Az algorism sz´o volt a sz´ ot´arban, melynek jelent´ese: aritmetikai elj´ar´asok elv´egz´ese arab sz´amokkal. Az els˝o algoritmus, amivel tal´alkozhatunk, az Euklideszi algoritmus volt.
Mai defic´ıci´o J´ ol meghat´arozott sz´am´ıt´asi elj´ar´as, amelynek bemenete egy bizonyos ´ert´ek vagy ´ert´ekhalmaz, ´es amely l´etrehoz valamilyen ´ert´eket vagy ´ert´ekhalmazt kimenetk´ent.
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
7 / 33
P´elda (1) K´av´eautomata 1
V´alaszd ki, amit inni akarsz!
2
Dobj be p´enzt!
3
Ha nem el´eg a bedobott p´enz, akkor menj a 2. l´ep´esre!
4
V´ard am´ıg elk´esz¨ ul a k´av´e!
5
Vedd el a k´av´et!
6
Vedd el a visszaj´ar´o p´enzt!
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
8 / 33
P´elda (2) Nem indul a motor 1
Ellen˝orizd a benzintankot. Ha nincs benne benzin, akkor t¨oltsd tele.
2
Ha m´eg mindig nem indul, akkor ellen˝ orizd az akkumul´atort. Ha nincs megfelel˝oen felt¨oltve, akkor t¨ oltsd fel.
3
Ha m´eg mindig nem indul, ellen˝ orizd a gyerty´at. Ha sz¨ uks´eges, cser´eld ki.
4
Ha m´eg mindig nem indul, vidd el szerel˝ oh¨ oz.
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
9 / 33
P´elda (3)
Euklideszi algoritmus Bemenet: K´et pozit´ıv eg´esz sz´am: m ´es n. Kimenet: A legnagyobb eg´esz sz´am, amely m-nek ´es n-nek is oszt´oja. Algoritmus 1
Osszuk el m-et n-nel ´es legyen r az oszt´asi marad´ek.
2
Ha r = 0, akkor v´eget ´er ´es n a kimenet.
3
Egy´ebk´ent m = n ´es n = r .
4
Ugr´as az 1. l´ep´esre.
Sergy´ an (OE NIK)
AAO 01
m 120 48
n 48 24
r 24 0
2011. szeptember 14.
10 / 33
Az algoritmusokkal szembeni elv´ar´asok V´ egess´ eg: V´eges sz´am´ u l´ep´est k¨ ovet˝ oen v´eget kell ´ernie az algoritmusnak. Meghat´ arozotts´ ag: Az algoritmus minden egyes l´ep´es´et minden lehets´eges esetre prec´ızen defini´alni kell. Bemenet: Egy algoritmusnak nulla vagy ann´al t¨ obb bemenete lehet, amik az algoritmus kezdetekor ismertek. Kimenet: Egy algoritmusnak egy vagy t¨ obb kimenete van, amelyek meghat´arozott viszonyban vannak az algoritmus bemeneteivel. Hat´ ekonys´ ag: Egy sz´am´ıt´ og´ep ´altal v´egrehajtott algoritmust´ol elv´art, hogy gyorsabban m˝ uk¨ odj¨ on mintha sz´am´ıt´ og´ep n´elk¨ ul hajtottuk volna v´egre.
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
11 / 33
Algoritmus le´ır´o eszk¨oz¨ok 1
Mondatok
2
Blokkdiagram
3
Struktogram
4
Jackson ´abra
5
Pszeudok´od
6
Programnyelv
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
12 / 33
Blokkdiagram
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
13 / 33
Struktogram
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
14 / 33
Pszeudok´od Be: m, n r := m mod n Ciklus am´ıg r 6= 0 m := n n := r r := m mod n Ciklus v´ege Ki: n
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
15 / 33
Vez´erl´esi szerkezetek 1
Szekvencia
2
El´agaz´as
3
Ciklus
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
16 / 33
Szekvencia (1) Egy utas´ıt´ast k¨ozvetlen¨ ul egy m´asik ut´an v´egz¨ unk el. Jel¨ ol´ese blokkdiagramban:
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
17 / 33
Szekvencia (2) Jel¨ ol´ese struktogramban:
Jel¨ ol´ese pszeudok´odban: S1 S2
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
18 / 33
El´agaz´as (1) Adott 2 darab felt´etel-program p´aros, az igaz felt´etelekhez tartoz´o programok v´egrehajt´asa Jel¨ ol´ese blokkdiagramban:
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
19 / 33
El´agaz´as (2) Jel¨ ol´ese struktogramban:
Jel¨ ol´ese pszeudok´odban: Ha L akkor S1 k¨ ul¨ onben S2 El´agaz´as v´ege
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
20 / 33
Ciklus (1) Megadott felt´etel teljes¨ ul´ese eset´en egy program (ciklusmag) t¨obbsz¨ori v´egrehajt´asa Jel¨ ol´ese struktogramban:
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
21 / 33
Ciklus (2) A programoz´as nyelvek ´altal´aban t¨ obbf´ele ciklust ismernek, ennek megfelel˝oen a pszeudok´odban is t¨ obbf´el´et haszn´alunk. El¨ oltesztel˝ os ciklus
H´ atultesztel˝ os ciklus
Sz´ aml´ al´ os ciklus
Ciklus am´ıg L S Ciklus v´ege
Ciklus
Ciklus i = i0 -t´ol i1 -ig S(i) Ciklus v´ege
Sergy´ an (OE NIK)
S Ciklus am´ıg L
AAO 01
2011. szeptember 14.
22 / 33
Struktur´alt programoz´as Struktur´alt programnak tekintj¨ uk azokat a programokat, amelyek csak a megengedett elemi programokat tartalmazz´ak a megengedett programkonstrukci´ok (vez´erl´esi szerkezetek) alkalmaz´as´aval. Elemi programok u ¨res program ´ert´ekead´as (´allapot v´altoztat´as)
Megengedett konstrukci´ ok szekvencia el´agaz´as ciklus
Bizony´ıthat´o, hogy a fenti szab´alyok megtart´as´aval minden algoritmussal megoldhat´ o feladatra adhat´ o megold´as.
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
23 / 33
Modul´aris programoz´as Az elk´esz´ıtend˝o programot egyetlen utas´ıt´assal szeretn´enk megoldani. Ha ez nem siker¨ ul, akkor t¨ obb utas´ıt´assal pr´ ob´alkozunk, melyek egyes r´eszfeladatokat val´os´ıtanak meg. Addig folytatjuk ezt a r´eszfeladatokra bont´ast, m´ıg minden r´eszfeladatot siker¨ ul megval´ os´ıtani elemi utas´ıt´asok felhaszn´al´as´aval. ¨ Osszefoglalva: A teljes feladatot r´eszekre bontjuk, majd ezeket a visszavezet´es m´odszer´evel megoldjuk.
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
24 / 33
Modul´aris programoz´as A modul´aris programoz´ast az al´abbi Jackson ´abra szeml´elteti.
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
25 / 33
Modul´aris programoz´as megval´os´ıt´asa A modul´aris programoz´ast pl. f¨ uggv´enyek (illetve elj´ar´asok) h´ıv´as´aval tudjuk megval´os´ıtani. A f¨ uggv´enyek ¨on´all´o r´eszprogramok, melyeknek lehetnek bemenetei ´es visszat´er´esi ´ert´ekei.
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
26 / 33
V´altoz´ok Az algoritmusok megval´ os´ıt´as´ahoz v´altoz´ okra van sz¨ uks´eg¨ unk (ld. Euklideszi algoritmus) Az egyes v´altoz´oknak az algoritmusok sz´am´ıt´ og´epes implement´aci´oj´an´al t´ıpust kell megfeleltetni. Sok esetben az alkalmazott v´altoz´ o t´ıpust´ ol f¨ ugg, hogy milyen algoritmussal oldhat´o meg egy probl´ema.
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
27 / 33
Elemi v´altoz´o t´ıpusok Eg´esz t´ıpusok H´any b´ajton ´abr´azolva? El˝ ojeles/el˝ ojel n´elk¨ uli?
Lebeg˝opontos t´ıpusok H´any b´ajton ´abr´azolva? Vigy´azat! Nem ´abr´azolhat´ o minden val´ os sz´am!
Karakter t´ıpus(ok) Logikai t´ıpus
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
28 / 33
¨ Osszetett t´ıpusok T¨omb¨ok Stringek Strukt´ ur´ak Halmazok Objektumok ...
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
29 / 33
V´altoz´ok jellemz˝oi ´ Elettartam Statikus/dinamikus Konstans/v´altoztathat´ o Hat´ok¨or (lok´alis/glob´alis) F¨ uggv´eny param´eterek´ent ´ert´ek/c´ım szerint ´atadott
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
30 / 33
Algoritmus l´ep´essz´ama Egy algoritmus l´ep´essz´ama alatt azt ´ertj¨ uk, hogy h´any elemi m˝ uveletet (´ert´ekad´as, ¨ osszehasonl´ıt´as, beolvas´as, kiirat´as, stb.) kell v´egrehajtani adott bemenet mellett. Egy algoritmus fut´asi ideje f¨ ugg az algoritmust megval´os´ıt´o programt´ol, a programoz´asi nyelvt˝ ol, a sz´am´ıt´ og´ept˝ol, stb. Algoritmuselm´eletben a fut´asi id˝ ot a l´ep´essz´ammal jellemezz¨ uk. A l´ep´essz´am bemenett˝ ol f¨ ugg˝ o jellemz´es´ere haszn´alatos a ”nagy ord´o” (O) jel¨ol´es.
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
31 / 33
Nagy ord´o Legyenek f (x) ´es g (x) egyv´altoz´ os f¨ uggv´enyek. f (x) = O(g (x)) akkor ´es csak akkor, ha l´eteznek olyan M ´es x0 pozit´ıv val´os sz´amok, hogy minden x > x0 eset´en |f (x)| ≤ M · |g (x)|.
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
32 / 33
Feladatok 1
´Irjuk le a m´asodfok´ u egyenlet megold´asi algoritmus´at folyamat´abr´aval, struktogrammal ´es pszeudok´ oddal.
2
Adott k´et s´ıkbeli pont: P1 (x1 , y1 ) ´es P2 (x2 , y2 ). Keress¨ uk a P1 -en ´es P2 -n ´athalad´o egyenesen az x0 abszissz´aj´ u pont y0 koordin´at´aj´at. Adjon algoritmust a feladat megold´as´ara.
3
K´esz´ıtsen algoritmust, mely eld¨ onti, hogy egy adott ´ev sz˝ok˝o´ev-e vagy sem.
4
K´esz´ıtsen algoritmust, mely megadja, hogy egy adott ´ev adott h´onapja h´any napb´ol ´all.
5
K´esz´ıtsen algoritmust, amely egy pozit´ıv eg´esz sz´amr´ol eld¨onti, hogy pr´ım-e vagy sem.
6
K´esz´ıtsen algoritmust, amely bek´eri egy tank¨ or zh eredm´enyeit, majd kisz´am´ıtja azok ´atlag´at.
Sergy´ an (OE NIK)
AAO 01
2011. szeptember 14.
33 / 33
