Pentel|nvi Pal
Szpivrl,nr-,nrvr6nrralaxirASa f Srn.rr-,ESZTESE AZ Ar-GoRTTMIKUS a rn NirAsr-uxul,Asr FoLYAMATBAN
13udapest 1999
B6nki Don6tMtiszakiFSiskola Tan6rkepzoTansz6k
Lektor6lta Tdth Bdldnd Varga Lajos
PAL1999. @Penteldnyi
I S B N9 6 38 5 1 3 8B 8
kisziilt A kiadv ftnyTEMFIJS Pharet6mogatdssal
[,IGA'|L]I{A I,'i'i}
/
-
,
A Tl]l fl'7
.i-E.f
.[:t-.il-
EI6sz6 Az algoritmikus.szemldlet fejleszt6semdltatlanulmell6zottteriilet ahazai olitat6sban.Szeiepelehet ebbenannal..,h.rgy ugy trinik, mintha az'algoritrnikus gondolkod6s'elnevezdsvalamif6le mechanikustevdkenys6getsugallna,amit eleveellentdtesnek 6rzrinka kreativit6ssal. Jelenfr6somegyik fontoscdlja,hogy az emlitetthi6nyt p6tolja 6s a felt6telezettellentmondSstfeloldja. Az algoritmikus szeml6let oktatdsi folyamatra gyakorolt hat6sait 6s m6dszertanivonzataitvizsgiilva azttapasztaljuk,hogy ezek a rendszerszeml6let sztiks6gszeri 6s automatil,.us 6rv6nyesril6 s6bencisszegezhetok. Az algoritmikus szeml6letm6dterm6szet6bSlfakad6an nyujt hathatos segitsdgeta tananyag (kiilonbozo szintij egys6geinek6s eg6sz6nek)vilAgosrendszerezdsdhez 6ppitgy, mint az oktatdsi gyakorlat legktilonboz6bb teriiletein felmeriil6 feladatok 6ttekilrthetS, logikus megold6smenet6nektervez6s6hez.Ugyanakkor, az algoritmikus gondolkoddsra nevelds, dz algoritmikus szernl6letm6d kialakititsitraval6 torekvds amellett,hogy noveli az adott tantirgy oktat6s6nak hat6konysilgfn,a szSmit6stechnik5ban tanitott programozitstis segiti. Rem6lhet6leg e tanulm6ny segits6get nyirjthat ahhoz is, hogy a szal
Tartalomjegyz6k
1 . Ember6s technika 6s gdpesftdse 1.1. A fizikai 6s a szelleinirnunk6kmechar'izhl6sa 1.2. Analog 6s digit6lis technika 1.3. P6rhuzamaz ember6s a szhmit6g6pkozott I.4. Infonnatika I.4.I. Az informatikaeredete | .4.2. Az informatika rdsztertiletei 1.5. A digitfiis szdmit6g6phaszniiata 1.5.1.Kozvetit6sa g6pi k6d 6s a magasszintrinyelvekkozott L.5.2.A nyelvekszintaxisads szemantik6ja
5 5 7 9 13 13 I4 15 l5 2A
2 . A technikai fejlSd6shat6saa programozilsoktat6s6ra
ZJ
2.I. A programozSstanit6s6naktort6neti 6ttekint6se 2.2. Algoritmus, folyarnatitbra6s program Terminol6gi a-tortdnetimegfontoI5sok
23 25
3 . Az algoritmikusfeladatmegold6stanit6sa Az algoritmikusgondolkod6sjelent6sdgeaz aktatdsban feladatmegold6s 3.1. A hagyom6nyos6s a szfimit6g6pes fiiggetlen algoritmusok 3.2. Programnyelvt6l,ill. szftmitogdptfpust6l 3.2.1.A mondatszenilefr6svizualiztllsa (Pszeudokod Folyamatitbra - Struktograrn) 3.2.2. A magasszinttiprogramnyelvekalaputasit6sai Alapvet6 folyamat6braszimb6lumok 3.2.3.Ciklusok ezdslogikai dontdssel 3.2.3.1. Ciklusszerv ciklusutasitdssal 3.2.3.2.Ciklusszervezds 3.2.4. Indexesv6ltozok(Tonrbdk) tordeldse 3.2.5. A folyamatSbra 3.2.6. A strukturdltpi:ogramoz6srdl
27 27 28 28 29 34 35 a 1
) t
39 41 4)
4. Algoritrnusok 6,saz algoritmus-szerkeszt6s tanithsa 4.1. Az algoritmus-szerkes ztdstanit6sa6s a megold6sialgoritmusokg6p ndlktili ellen6rzdse 4.2. A megold6sialgoritmusokfinomit6s6nakfolyamata A "l6p6sr6ll6p6sre"modszer 4.3. Az induktiv 6s deduktivmegkozelit6sosszehasonlit6 elemzdse a'programoz6sitdtelek' tanitits6ban 4.4 l(ornplex rnegold6sialgoritniusokkidolgo zhsa
44
5. Algoritmikus szemldletrioktatds
111
44 47 B4 91
5.1. Algoritmikus szeml6letritanft6si-tanul6si folyamat 112 5.2. P6rhuzama tandri 6s a programozoi tevdkenys6gkozott 113 5.3. A mintap6ld6kszerepeaz algoritmizirl6stanit6si-tanul6sifolyarnatdbanll4 5.4. Az algoritmikusfeladatmegold6stanftSs6nakn6h5ny kognitiv pszichologiaivonatkozdsa 116 116 5.4.1. Produktiv 6s reproduktivgondolkodds 1t7 ds kreativit6s 5.4.2.Analogikusprobl6mamegold6s
Irodalom
t2a
1. Ember 6s technika
1.1. A fizikai 6s a szellennimunkf k mechanizilSsa6s g6pesit6se
Legutobbievtizedeinketgyakranaz automatiziiirskor6naknevezrk. Ez az az elterjed6sdre utal, amelyek egyre elnevezdsazoknaka gdpi berendez6seknek tobb m.r"rnk6t kdpesekegyv6gtdben,emberibeavatkozilsndlkul elv6gezni. A fejl6d6s rugoja kdts6gkiviil az a tdrry, hogy az ember igyekszik a farasfi.omunk6kt6lmenektilni: mind afizikai munk6kt6l, mind pedig a szellemi rutirununk6ktol. Tort6netilegkdt alapvetSkorszakot kiilonboztetiink meg: mechanizfiist 6s gepesitest. A fizikai munk6k tertiletdn kdts6gkivtil a szerszSmokhaszn|lata az, amely a mechanizfiitstjellemzi. A szersz6marra szolg6lt - 6s szolg6l mind a mai napig , hogy az ember saj6t testi erejdvel vegzett munk6j6t megkonnyitse, annakhat6sfok6tjavftsa. Ett6l m6g azonbanaz energiaforr5stov6bbra is az elo test marad; ak6r a saj5t emberi, akdr a segitsdgtilhfvott 6llatok teste. Tehat rnindenkdppenbiologiailag is 6talakitott energi6kat hasznal fel. A dont5nek vagy forradalminak nevezhet6 v|ltozitst a g6pesit6sjelenti, amikor is az tortenik, hogy az 616test az energia6ramb6lkil6phet 6s a tenndszet energi6i gepekenkeresrtnI hasznosulnak. A szellemi rutinmr-rnk6k automatiziiilsa is rdgi torekvdse az A kozismert rdgi sz6molo1ep,az abacuspdldfnl az emldkezest emberisegnek. segiti: ainikor h6rom golyohozhozzhadunkkettSt,nem kell mind a ket szatnot tartanunk. egyszerreeml6kezeti.inkben Rutinmunkaa gyakran ismdtl6d6,egyszeri szftmol6simriveletek v6gz6se is - p6ld6ul az osszead6s6.A pen*furgdptetsz6legesensok szamot k6pes "gytijt6s6t"(osszegzds6t) is elv6gzi - teh6t egy osszeadni,sot a rdszosszegek koriStozott eml6kezettel. mem6ri6val rendelkezo, mechanikus, szamtani mtiveietetvegz6gdp. kori.ilminyektol Szellemirutinmunkaaz a tev6kenys6gis, amit " a v'Sratlan vezdrldsnek" tobbnyire ciklikusan ismdtl6do linyegdben flrggetlen, nevezlrettink.Ilyen feladat volt pdld6ul az elso gozgepekszelepeineknyit6sazarasa. A rnunkateh6t"*gy adottjelensdg6szlel6se"- "beavatltoz6s"unalornig isrirdtlodoegym6sut6nja,ciklusa volt. A fiatal Watt kital6lt egy szerl<ezetet, anrely'az iszleidst6s a sziiksdgesbeavatkozast- vezdrldst- automatikusan ott az ipari forradalom. eivdgzr:iinl'eiriben ezzell,:ezci6d
Ismeretes,hogy mfr a mult szfnadban meglepoen bonyolult mint6ju szoveteket sz6ttek automatikus vezdrl6su szov6gepeken, vagy p6ld6ul szSzadunkelej6n azautomatikus - lyukszalaggalvezdrelt - gepzongordknyolctizpercesmuveket is j6tszottak. A lyukszalagon ldv6 lyukak helyzete dontotte mikor melyik billentyiit mozditsa ffieg, el, hogy a pneumatikusj6tsz6berendez6s vagyis a lyukak "vez6reltdk" a zongor6t,6s a lyukak cisszess6ge- az utasit6sok egym6sut6nja- jelentette az elv6gzend6muveleteket 6s azok sorrendjet: a programot. A vezdrl6s fogatromkordbe 1.artaz6szellemi rutinmuntrra az egyszeru vizsg6lat 6s dont6s is. A dontds akkor egyszerii,ha csup6nndh6ny lehetSsdgre kell felkdsztilntink, 6s b6rmi lesz is a lehet6sdgek vizsgilIat6nakeredmdoye, "dontdshozo" eszkoz mindig egydrtelmr,i,hogy mit kell tenntink. Mechanikus p6ldaul .gy almaosrtillyozci:a r6csoknagys6gszerint szefialasztjftk az alm6t, 6s a ktilonbozo mdretiieketm5s-m6sl6d6batov6bbitjdk. a kifejez6seket hasznftltunk, amelyek Pdld6inkban olyan szitmitftstechnik6nak is alapfogalmai: mem6ria, sz6mtani (aritmetikai) dontds,program. A peldAkban mtiveletek, vezdrlls, vizsg iiat (osszehasonlit6s), olyan tevdkenysdgeketvdzoltunk, melyek minden ffnisihan egydrtelmuen eldonthet6,hogy a kovetkezo ffnisban mit kell tenni. Ha a gozgepdugattyuia az egyik holtponton van (A esemdny),nyisd ki az g szelepet. Ha a masik holtpontonvarl (B esem6ny),nyisd ki a b szelepet.Ha nincs egyik holtponton sem (e esemdny),ne csin6lj semmit: 0 tev6kenys6g.Vil6gos, hogy a h6rom esenr6nykoziil valamelyik mindig bekovetkezik ("igaz"), ds mindig csak az egyik kovetkezik be. A Watt-fdle automatika mindig egyerteimuen el tudja donteni,mit tegyen(1.6bra):
bemenet( input )
Watt automatika
A. B vagyC
kimenet( output) E,b vagy 0
kclruirnenyekkozott nem lehet!) (ds rnassemmitr)'en i .lrbra
"input" Az automatikatehtfi6szlel bizonyostdnyeket (bejov6, "ha adatokat), majd elvegzra A, akkor a' ezeketmint A, B 'ragyC esemdnyeketazonosftja, 6s vagy onmagaelvdgzi az ha B, akkor b, ha C, akkor 0" logikai hozzhrendel6st, vagy utasit6stad annak elvegzes6re. d,b,0 tev6kenysdget, A mai szamitogeptobb l6nyeges szempontbirlktilonbozik az emlitett automat6ktol. Kdpes arra, hogy az input adatokkal logikai 6s aritmetikai nriiveleteket vegezzen,vagyis az adatokat emberi beavatkozasn6lku1, igen bonyolult utasit6sok al.apjfn- m6s adatokk6 alakitsa. Mukdd6se igen gyors' mivel elektromos impulzusokkal dolg ozik. Mindig van kisebb-nagyobb mem6riffia,ahol az adatoliat6s a programokatt6ro1ja.A progiam tdrolt volt6b6l adodik, hogy a program megv6l,.rlrtaftisaeset6n ugyanaza g6p egdszenrn6s Az elekironikus sz|mitogdpsok ktilonbozo jellegu feladatrikeJv6gzeserek"dpes. cdlra felhaszn6lhato, univerzdlis, flexibilis (hajl6kony, rugalmas) eszkoz. Muk6dtetds6hez azonbansziiksdgvan arra,hogy a megoldand6feladatot 6s a megoid6smenet6ta matematika,a logika nyelv6n fogalmazzukmeg.
1,2. Anal6g 6s digitflis technika I\4int koztudott, 6pit6elemek szempontj6b6l, valamint az informdciokezeldstechnikaja szerintk6tfele gdpetkiilonboztettinkmeg: anal6g 6s digit6lis E megktilonboztetdsazonban sokkal 6ltal6nosabb,minthogy szftmitog6peket. lennealkahna:zhato. csak a szdmitogdpekre Az anal,5g6s digit6lis technika, s5t ugyanazon eszkozvagy jelens6g anal6g 6s ciigit6iis szemldletem6s tertileteken is megkulonboztethetS:a karor6nli is lehet anal6g vagy digitSlis, vagy egy voltmdr6 mtiszer is lehet ugyanaz,s6t egy matematikaifuggvdny megad6sais lehets6gesdiagrammal vagy lrtdkthbld;zattal. Az analog szamitogdpek olyan gdpelemekbSl 6piilnek, amelyek valamilyen folytonosanvaltoz,ofiztkai mennyisdggeljelkdpezik,jelenitik rneg a "szamit6s"eredmdnydt,6s - elvileg - a bemenoadatoklegkisebbv|ltozfis6rais kdpesekreag6lni. A ctigitatis szfimitogdpekkapcsol6 jellegu tizemben mukodnek. A sz6mokat itt a sz6mjeg;'ei
fesztilts6gpl. 0V vagy 6V. Atvitt 6rtelembenk6t6ll6srikapcsolonaktekintheto az is, hogy egy m6gnesgyuruaz egyik vagy a m6sik irirnybanvan m6gnesezve; vagy akdr az, hogy egy darabpapfnrakndh6nyn6gyzetmiilim6ternyifeliilete ki van lyukasztvavagy nincs kilyukasztva.Teh6t k6t6ll6srikapcsolirelkdpzelheto mechanikusan is, elektronikusan is, m6gnesesenis. lv digit6lis eszkoz lcinyeg6benolyan jelekkel dolg ozik, amelyek egyni6stol dlesen es j oi elki.ilonfthet6k;mivel a gdpelemekszdmavdges,ezert a lehetsegeskiilonbozo 6llapotokszdmais vdges,kovetkez6sk6ppen a szdmol6sipontoss6gv6ges.(Egy digit6lis eszkoz az egym6shoznagyon kozeli drtdkeket 6ltal5ban nern tudja rnegkiilonboztetni.) Els6 pillanatban szinte drthetetlena digit6lis eszkozoktdrhodit6sa.Az anaiog eszkozok elvileg pontosak,a digit6lis eszkozoknem: a Ji -t anal6g eszkozzel (korz6vel) elvileg "v6gtelen pontosan" meg tudjuk szerkeszteni, ugyanakkor egy digit6lis eszkozbencsak v6ges pontoss6ggal itbr|zolhatjuk (hiszen az itbrttzolt szdmlegyekszttmasztiksdgkdppenvdges).A mennyisdgek, amelyekkeldolgozunk (pdldSul.gy szabiiyozSsifolyamatbana h6m6rs6klet,az elektromos6ram),rendszerintanal6gmennyisdgek:az anal6gmennyisdgeket megint csak sztiksdgszeri pontoss6gveszt6sSran - digitaiis jeleld<"ekell alakitanunk,fn. analog-digit6liskonverterekkel.Tipikus AD-konverterpdld6ul az aut6 kilomdterszdml6loja. A megtett ut analog (folltonos v6ltoz6su) mennyis6g,azonbana digitdlis mdr6eszkoztinkonpdld6ul az 1-es szam nem jelzi, hogy vajon 1000 ffi-t, 1638vagy dppen 1999m-t tettiink-emeg. Vdgul az anal6g eszkozok "talcan kin6lnak" bizonyos bon.,volult maternatikai mriveleteket.Ilyen pdld6ul az integr6l6s,a differenci6i6s.Tudjuk, hogy a kondenz|tor feszultsege ardnyosa rajta 6rtftramlo toltdssel.arni nern mds, rnint az 6ramido szerinti integr6lja: 1 I
u(t)
at
C [i1t1
Az egyszertikondenzdtortehdt elvileg "pontosan"tud integriilni,ugyaneztegy digit6iiseszkozbonyolult,kozelit6modszeren alapuloprogrammalv6,gzi,vegso "pontatlanul". soron Tekintve,hogy az analoggdpekndlfolytoncismukoclestimirszerekrolvan sz6, a pontossdgotcsak itgy fbl";ozhatjuk,ha egyre finornabb kiciolgoz.6s6^ kovetkezdskdppenegyre dr6gdbb gdpelemekethaszndiuirk.Ahol viszont kapcsol6li vannak, ott a kapcsold:ill6soliegymdstol - viszonylag olcscr peclig gepelernekesetdnis - j6l eiktilcnfthetokes a poiriossagf-rtj::ozasara tobbct eg)/szer[ienaz az eszkoz irii reiirlelkezdsiinlire, ]rog1' l.':apcsi,rl6l
mint ahogy a szdnftanbantobb szamiegy kapcsolohelyzetekkel, teh6t leii6saval -, ugy a digit6lis gdpben:tobb kapcsol6 haszniiatfxal leiret el6rni a nagyobb pontoss6got. Ha teh6t egy diagramot kdszitunk, ahol a pontoss6g fuggv6rry6b.n a gdp6pit6si kolts6geket szeretn6nkilbrazolnt,akkor a digit6lis gep-i<pontosshgfnaka fi:ggvdny6bena r6juk forditott koltsdg novekeddsekozel line6risnaktekinthet6, mert hiszen k6tszerespontoss6gel6resehezk6tszeraruryi kapcsol6tke}l haszn6lni.A pontoss6gfok ozdsaaz analoggepekeset6benpedig meredek kolts6gnoveked6ssel jit , mihelyt egy bizonyos hat6ron triljutunk (Z.ihra). Tdbbek kozott ennek az egyszenifelismerdsnekkoszonheto,hogy az utobbi n6gy 6vtizedbena digitflis g6pek sokkal nagyobbm6rt6kbenelterjedtek, mint az analogg6pek.
bo .() U)
..b%'
&t)'
disltary
2.abra
1.3. Pdrhuza,maz ember 6s a szamit6g6pktiziitt
A ma ismert leg6ltalSnosabbszamitoeszkaz,,&z un. Turing-gep elvi leir6s6t Turing angol maternatikusadta meg 1936-ban.Munkassaganvornan dlenti kutat6s indr-rltmeg a szdmft6sokautomattz|ll,saterin. Megsziilettek az rniikodogdpek,amelyekaz emberszaiitai'aszinte elso, reidkkel6s jelfogol.J
r6diotizeneteit. Ezek a gdpek azonban meg mindig inkebb a bevezet6ben "program" lenyegeben emlitett automat6krokonai. Fix programmalmrikodtek,a maga a gdp szerkezetevolt. Ahhoz, hogy m6s algoritmus szerint rnukddjenek, valamik6ppm6dositani kellett a gdp szerkezet6t. Neumann J6nos 1948-ban zseniSlis felismer6srejutott: egy igazin "adat", mint maguk az"rgazi 6ltal6nosc6hi szhmitoeszkozn6la program 6ppugy adatok" teh6t a programot is a mem6riihan lehet - sot, kell! - t6rolni, akdrcsakaz adatokat. Az adatok 6s a program fizikai rnegjelenitdseis legyen egyformd, d gdpet pedig ugy kell megdpiteni,hogy a mem6ri6tolvasvamindig tudja, vajon egy "adat" programl6p6st,mriveletet jelent, vagy operandust, amivel a muveletetvdgre kell hajtani. ,\z alftbbiakban a szftmitogdp legteljesebb ki6pitdsri v6ltozatat v6zoljuk, bizonyos tekintetben - m6r arnikor is feltdtel ezzik, hogy a szitmit6gdp ugyanrigy dolgozik, mint az ember. Erzekeli a kornyezeteben lej6tszod6 folyamatokat, azokb6l mdrdsi adatokat vesz fel, ezeket feldolgozza, a dont6sei feldolg oz6s eredm6nyek6ppendontdseket hoz, itdleteket alkot 6s nyom6n- be is avatkozika folyamatba(3.6bra).
KoaHtae Konyvtar ( hdttdrtarak)
Emldkezet ( memoria)
VEZERLES i I
Erzekel6s ( input )
Gondolkodas (LAE )
JELATALAKITOK
Eredmenykozles ( outnut )
HAfASERctsiror
I Kornyezet ( Folyarnat)
II
3 .abra
10
Autom atizfifusi drtelemben ez egy zdrt hat6sl6nc.Az ihra aljitn a folyamatot thriuoltuk 6s felt6telezzik, hogy a folyamatb6l valamilyen megfigyel6s vagy m6r6s utjSn - vagy a kozvetlen lrzdkszerveinkkel, vagy mtiszerek utj6n (6rzekel6s).Az fiel6talakitok) - eljirtnak bizonyos adatak az erzdkszerveinkhez 6rz6ke16s nyom6n az adatok az ember agyhba jutnak es az etnber . Az emberi agynak lesznek akivetve (gondolkod6s) gon,Colkodok6pessdgdnek azonbannem a gondolkod6s az egyetlen szerepkore,hanem rendelkezik m6g k6tir6nyir is (eml6kezds).A gondolkodhsaz eml6kez6ssel eml6kezotehets6ggel kapcsolatban van: tehdt a gondolatainkban megfordul6 adatokat k6pesek vagl'unk az emldkezettinkbenelt6rolni, illetve - sziiks6g szerint - onnan eloszedni.A gondolkod6seredm6nyek6ppensztilet6 dont6seink,itdleteink a kozloszerveken keresztiil mehetnek vissza a kornyezetiinkbe; a bizonyos hatdserosit6kon kozlSszerveinhbdlkimend informdciok pedig visszajuthatnak a folyamathoz 6s afi. valamifdlek6ppen keresztiil Ez val
11
Sziiks6g van a mriveleteket tdnylegesenv6grehajt6 un. logikai-aritmetikai egys6gre(LAE), amely - mint neve is mutatja - egyszerulogikai 6s szamtanr mriveletekelv6gzdslrek6pes. Amir6l eddig sz6 vblt: a vezdrl6s,a gondolkod6s6s az emldkezesszerep6t elji*szog6pegysdgekegyuttesenalkotj6k a sz6mit6gdpun. kozponti egysdgdt.A kozponti egys6genbeliil a vezlrloegysdget 6s a logikai-aritmetikai egys6get processzomakis szokt6khfvni. Tehfrt.a processora t6nylegeselj6rastlefolyato g6pegysdg(processus- elj6r6s). Szriks6g van a szitmitogdp kornye zetdvel kapcsolatot tarto perif6ri6lis input ds output egysdg (bemeno6s kimen6 egysdg). egysdgekre: A periferiSk feladata kett6s. A kozponti egys6g elektromos vagy m6gneses jelekkel "dolgozik"; ezeket az ember az of lrzdkszerv6velnyilv6n nem tudja 6rz6kelni. Teh6t a perif6ri5k szerepe egyfel6l az, hogy az ember 6ltal erzekelhetSvagy leadhat5jelekbSl olyat csin6ljon, amelyet a kozponti egys6g erzekelnitud 6s forditva fiel6taiakit6s). az 6thidal6sa, A periferi6k szerepem6sfel6l annak a sebess6gktilonbsdgnek amely a gyors kozponti egyseg6s a lassir emberi mukoddskozott fenn6ll. A kozponti egys6g, minthogy elektronikus alegysdgekb6i 6lI, nyilvanval6an sokkal gyorsabbanfog mukodni, mint az emberkeze, amellyel adatokat g6pel be esetleg,de gyorsabbanmtikodik az elektromechanikuseszkozoknelis. (A a tnechanikus mindig az elektronikusegys6gek,a leglassabban leggyorsabban egysdgekmtikodnek.) A periferi6k koze szok6s sorolni mdg az rin. hf*tertftrakat is, amelyek a szdmitogdpmem6ri5j6nak a kapacit6sb6vitdsdreszolg6lnak. A h6tt6rt6rak termdszetesenszintdn a kozponti vezdrloegysdgfeli.igyeletealatt 6llnak (az ihr in szaggatottv onaIIal j eIk6pezett v ezerloirnpuIzusok) . Megktilonboztet6sula h6ttdrtdrakt6l, a kozponti egys6gheztartozo thr neve: folytonosanbeavatkozo). operativt6r (operativ - mirkod6, a rnr-ikoddsbe alapelvek,e n6gy kovetelm6nylenyegdben e szamitogdpdpit6si A Neuinann-fdl mag6ban foglalja a mai szanitogdpek szerkesztesr alapelveit is. Az mint beiktatdsfthoz mennyis6ginoveked6seujabb gdpegysdgek a'Catfeldolgoz6s min6sdgiv6ltozdshozvezetett,a korszerti 6pit6elemekpedig sokkal gyorsabb ez a fejiodes rnirkodestl6s nagyobbkapacit6srigdpek 6pit6sdteredmdnyeztdk; azonbana neumannialapelvekldnyeg6tnem drintette. Megi egyezzik mdg, hogy az ihrhn a szabiilyozottfblvatnattal iillando, vazcltunk. emberikozvetit6snelliiil liapcsolatban6llo, irn. on-line sz6rnitogepet neln kerul sor, az embercsak szerrrl6lcije Itt az ernbei'kozvetlenbeavatkoz6shra egy ilyen koinplex moclon automa.tizfit folyanratnak.fu{a a szdmitogepel< tobbsdgemdg nenl ebben az automatiziilts6giilirriiliben iizetiicl, hanent az
12
ibrtn 1Sthatodupla vizszintes vonal feletti kidpitetts6gben, a folyamatt6l elv6lasdv a (off-line). A szttmitogdpteh6t on-line iizemel, ha a programjftnak mukod6s6hez sztiks6gesadatokatkozvetlentil, emberi beavatkozdsn6lkiil kupja meg (pd1d6ul elektromos a szabfilyozand6folyamat ldnyegesparam6tereita m6rSkdsz{i16kek jelei formdj iban), es ha a program eredm6nyekdntkapott adatokatkozvetlentil adja 6t a szabtiyozand6 folyamatnak, vagyis emberi beavatkozds ndlktil, kcrzvetlentil szabiiyozza. Ellenkez6esetbena szSmit6g6poff-line iizemel: az adatbevitelaz ember dolga, a sz6mit6g6pmeghatarozza a teend6ket, majd az,okatism6t az ember vegzi (vdgezteti)el. Tdnylegesgyakorlati probldna6kmegold6s6n6lis rendszerinta feldolg ozand6adatokatnem a mdr6mriszerekr6lkozvetleniil vesszrik,hanem a m6rt aclatokatelSbb kezi er6vel valahol rendszerezzik ds artan figy adjuk a a a mdsik oldalr6l, a szamitogepoutput oldal6r6l, Nem is sz61r, szitmitogdpnek. esetdnsokszor amikor is a gep eredmdnyeketkozol; p61d6ultermel6sir6nyit6s nem hagyjuk a szdmitogdp dontdseit kozvetlenul a termeldsi folyamatba beavatkozni, hanem osszei.il a termeldsi 6fte1<ezletds a szamitogep 6ltal szolg6ltatottfeldolg ozottadatokat vagy elfogadja, vagy elveti.
1.4. Inforrnatika
L"4.1.Az infonneatikaenedete
Az 'informatika'viszonylaguj elnevezds.Francia(infonnatiqtre)6s ndtnet (Informatik) nyelvteruleten haszn6lt6k eloszor az 1970-es evekben. csak az ut6bbi dvtizedbenkezdetttdrt hoditani. NlagS'errorsz6gon 1985-bena BudapestiMuszalii Hgyetem G6pdszmdrnokiKarirn inform:itika laborirtoriumothoztak letre. sr:aliona7' 19E7-bena Viilarliosritd:rniirilierori rregkezrlddottez.iufcrrtirai.ilta clt.tai6s.
1' 1 i-)
Ugyanebbenaz 6vbena Kande,K6lm6n VillamosipariMtiszaki Foiskol6n is informatikusk6pz6sindult. tetmdszetesenm6r 6vekkel Hasonl6 kepzes - tartalmi* illet6en ' kor6bban is volt a tudcm6nyegyetemel<en,mtiszaki egyetemeken 6s fdiskol6kon. Az informatika az elektronika 6s a matematikahat|teruletdn jott l6tre. Erre utalnak az angol nyelvteriiletenkor6bban hasznaltkifejez6sek: Computer Science(szimitog6p-tudom6ny)6s Computing Science(sz6rnitdstudomtny).Az ut6bbi evtizedekben azonban el6bb az Informatics, majd az Infonnation TeclrnoIogy ki fej ez6sek hasznftlatav iit 6ltal 6noss6. Kordbban az informatik6t csak tapasztalatitudom6nynak tekinthetttik, hiszen alapvet6en a kiilonb ozo tudom6nytertiletekrcjl6s a gyakorlatbol vett elj6r6sok6s fog6sokkever6kevolt. A 70-es6vekt6lkezdvem6giscsakegyreonAllobbtudom6nny6v61t.
L.4.2.Az informatik a r6,szteriiletei Az informatik6nakn6gy rdsztertiletealakult ki: a muszaki informatrka,az alkalmazottinfonnatika, az alapinformatika6s az elm6letiinformatika. A mriszaki informatika tenilete egy el6re meghatlrozott tulajdons6gu szitmitog6pmeg6pit6se. Az alkalmazott informatika tertilete a szamitog6pek haszn|lata, mazott informati ku s ny i l r'6n alkalmaz6saa l egktil onboz6bb tertileteken.Az al\
l"i
Az informatika tudom6nyos alapjainak megteremtds6velaz elmdleti informatika foglalkozik. Ennek a tertiletnek koszonheto,hogy az informatika mint tudom6ny elfogadott6 v6lt. A fejl6d6s bhr 6ri6si, a gyakorlatban az infarrmatikam6g mai is el6tt jSrnak alkalrnazottm6dszerckaz ehndtretek ink6bb kisdrletij ellegii tudomfny .
1.5. A digitilis szfmft6g6p hasunflata
1.5.1. Kiizvetft6s a g6pi k6d t4sa magasszintii nyelvek kiiziitt
A ma i.izemel6,korszerti, elektronikus elemekb6l dptilt szamitogdpek dontStobbsdgedigit6lis. Digit6lis elemekb6l 6piil: kdt6ll5sri kapcsol6k vannak benne; teh(* ha a g6ppel valamit csin6ltatni akarunk, akkor ezel
t
!
01101010,11001101 ... stb. (256 vari6ct6).A 0 6s az I a kettessz6mrendszer "bit" elnevezds(binary digil sz6mjegyei:bin6ris sz6mjegyek.Ebb6l szftrmazika : kettes szSmrendszerbeli szdmjegy).A bit az informdcio legkisebb egys6ge. "kozlend6nket" ilyen, kettes szhmrendszerbeli(bin6ris) jelsorozatold
i. utasft6s: "vidd be a 113-ikrekesztartalm6taz akkumul6torba" 2. utasft6s: "add hozzaa 114. rekesz tartalmi* az a\
mfiveleti bin6ris kodja:
az Legyen | ilililil 3. utasitas
1 / '
l()
10i01101 0 i1 0 1 1 0 1 1 0 0 0110 1
Ezek az un. "mirveleti kodok", ezel
r
mem6riarekesz
2
3
4
1 0 1 0110 1 0 111 0 0 0 1 0 11 0 11 0 1 0 111 0 0 1 0 cim mtiveletik6d cfm muveletik6d
ll4 113 6 5 1 0 0 0110 1 0 111 0 0 1 . . .0 0 0 1 0 0 0 1 0 0 0 1 0110 bin6ris 17 bin6ris 22 cfm muveletilcod
115 0 0 1 0 0111 bin6ris39
(a programvdgrehaitinautdn)
Vaiamivel egyszeriibb leir6st kapunk, ha a bit-vari6ci6kat negyes csoportokba fbglalva egy-egy i 6-os szSmrendszerbeli(hexadecim6lis) szilmjeggyel fejezzuk ki :
T AD
2 71
3 6D
4 72
5 8D
113 rl4 115 11 16 27
6 73
"ijeszt6", holott p6ld6nkbanaz osszeadandok Gepi programunkei6g (leg{'eiiebb0 ds ?"55kozotti eg6sz szdmokatadhatunk 1'.ci:l6tozott nagysAgat ossze.osszegiiksernleliet255-ndltobb). es a nehezprobleinh"1aval, az ad-atokki- es be',riteldnek l"{enr1'cglalkoztunk ;izliijekilds*) rn*gi*iretos':tineltiz ltroblemiritis cigrzis (az-adcttrnenrori3i'elie
1t ' l l
Azt azonbanmdr ennekalapj6nis elk6pzelhetjiik, alaposanleegyszerusitetttik. h6ny ilyen jellegirutasit6stkellenelefrnunkp6ld6ulaz + firggvenyegyetlen nl.
helyettesitdsi 6rtdk6nekki szirmitdstthoz. Programozhatunk teh6t gdpi k6dban, de ez roppant farads6gos 6s tern6rdekhibalehetbsdgetrejt. Ha a szamitog6pekfeltal6l6sa ota m6g rnindig csak igy lehetne programozni, akkor n6h6ny elszhntv6llalkozon kiviil alig akaclnaember, ak\ szlmitrig6pethasznal. "nyelvek" A szftmitog6pekelterjed6s6nekel6felt6tele az volt, hogy olyan sztilessenek,amelyeken a felhaszn6l5k viszonylag konnyen meg tudj6k fogalmazni probl6mSik megold6sdnakalgoritmus6t, a gdp pedig az ilyen nyelven megirc programokat i* tudja alakitani megfelel6 g6pi utasit6sok sorozatftvdazun. forditoprogrammal.A forditoprogramteh6tegy speci6lis,gepi de az emberi nyelvenmegirt program:bemenoadatai(inpuda)egy mesters6ges, gondolkod6sh oz kozel 6116nyelven megiri szoveg, dz irn. forr6sprogramsorai, kimenete (outputja) pedig maga is egy g6pi nyelvti program, dz fin. targyprogram, amely pontosan azokat a mriveleteket vegzi el, mint amit a a leforditott,gdpi nyelvu program 6ltal6ban fon6sprograme16ir.Term6szetesen sokkalhosszabb,mint a forr6sprogram. A forditoprogram kdtf6lekdppendolgozhat: vagy irgy, hogy eloszor a teljes forr6sprogramotleforditja g6pi k6dra, 6s csak ezutln indfthat,6(futtathat6) a program (az ilyen forciitoprograitlotcompiler-neknevezzi.ik),vagy fgy, hogy a fon'dsprogramotsoronl'dnt forclftja ("6rtelmezi"), ds az igy kapott gdpi utasit6sokat azonnal vdgrehatjtja (interpreter), vagyis a fordit6s es a programfutfisidSben nem v6lik szet.A cornpiler munk6ja az fr6sban fordito az tnterpreter6a tolm6csdhozhasonlit. ernberdhez, "feladatorientSlt", vagyis elsosorban A programozasinyelvek nagy rdsze alkalmas. megoldds6ra egy bizonyosfeladatcsoport A IIORTRAN pdldirul a rnuszaki szitmitttsoknyelve (FORmula TRANslator), k6sziilt (CoinrnonBttsiness mig a COBOL az tizleti eletbenva16felhaszndl6sra OrientedLanguage).Ennek megfeleloenegy szdmszinusz6irakmeghatarozasa FORTRAN-banegyetlenutasit6s,COBOL-banalig lehetleirni, ugyanakkoregy formanyorntatv6nyrakiirt kimutat6s k6szfttlse a nairi tizleti forgalotnr6l a oni'oli-rIt feladat. COBOL-ban egyszcrfi, IrOR-l'RAhl-banL', ket nagy csoportra alap.iarr A prograrnozasiny'elveketteliesftokdpessdg{ik assr:rllllynvelr'ekreds lnagasszinttinyeivellre. oszthatjulr.I
18
Az assemblynyelvekndl a forr6sprogramegyutasit6sa ftltalftbanegy gdpi a fordit6s ut6n), vagyis a fon6sprogram utasit6snakfelel meg (ennyi \eszbe161e hosszaosszem6rhetSa gdpi k6dir program hosszfval. A programozasrndgis konnyebb,rrrintg6pi k6dban,mivel -
amuveletik6dok hel,vcttrneghatStozattrovid szavakat,roviditdseket frhatunk
-
at6r egyesteriileteit"szimbolikuscfmekkel"jelolhetjiik,pl. Xl ,X2,23. A mriveletek megad6s/rrr6|teh6t nem kell konkrdt tArtertiletrehivatkoznunk, meg szabadr;lunka cimki sz6mitftst6l,ami a programozdstal6n legnagyobbhibaforr6sa
-
a bonyolult, de rutinszerii miiveleteket (p1. input-output muveletek) el6remegfrt gdpi rdszprograinok(subroutine-ok,makro-k) befuz6sdvel tik egyszertisithetj
-
aprogrambamegfegyzeseketirhatunk (magyardzoszovegeket),amelyek a gep a programmiikod6sdtvil6gosabb6teszik; ezeketa megiegyz6seket fordit6skozben figyelmen kfvtil hagyja.
A fenti g6pi k6df program ASSEMBLER nyelven nagyj6b6l a ndzneki (feltdve,hogy azXl,X2, Z3 szirnbolikuscftnek m6r kovetkez'Skdppen konkrett6rtertiletetielentenek,6s az adatokbennvannakXl, X2-ben):
LDA Xi
&oaD to Accumulator,azaztoitsdbe az akkumul6torba Xl tartalmdt)
ADD X2
(ADD, &zaz add hozza az akkumulator tartalmahoz X2 tartalndt: az eredmdny az akkumul6torban lesz)
STA Z3
(STore Accumulator, azaz tarold az akkumul6tor tartalm6tZ3-banl
"grlpi L6thatoan az assembly szintri nyetr.,'rndgnrinclig inkabb a sfrtz" i]1trkczelebb, de azr:ii- riokkal ditheto..\tr,atteltintlrctoitb" gonclolkoilA rnint a ge1;i1'''5d.
i {i
X.5.2.A nyelvek szintaxisa6sszemantikdja
A magas szintu (51ta15nosc6lir vagy feladatorient6lt) ptogramoz6si nyelvek olyan utasftdsokb6l6llnak, amelyek tdbb6-kev6sb6hasonlftanaka rnatematik6ban,mtiszaki 6letben stb. megszokott jelrendszerhez. A fenti p6ld6nak megfelelS utasit6s szinte rninden magas szintu programnyelven a kovetkezo: 23:Xl +X2 Itt csak egyetlenszokatlandolog van: ez az utasft6snem azt jelenti,hogy Z3 egyenl6 Xl 6s X2 osszegdvel(vagyis nem egyenlet,mint ahogyana matematik6banmegszoktuk),hanem irn. 6rt6kad6utasit6s:aztjelenti, hogy Z3 vegye fel Xl 6s X2 osszegdnekaz 6rt6k6t.A gdp kisz6molja,mi van az egyenlosegjeljobb oldal6n (fiiggetlentl att6l, mi van 6ppen Z3-ban), 6s az eredm6nytbeirja Z3-ba (b6rmi volt is ott). A matematik6banaz
X_X+1 kifej ez6sdrtelmetlen:nincs olyan vdges X, amely onmag6n6leggyel nagyobb viszont ez gyakori utasit6s,hiszen azt jelenti: lenne. A szftmitfistechnik6ban "vedd az X jehi rekesztartalmfit,adj hozzit egyet,6s az eredmdnytt6rold ujra X-ben",vagyisnoveldmeg eggyel X-et. Ha most forditott sorendben ndzzik a fenti h6rom pdld6t,l6tszik, milyen hosszu g6pi program lesz egyetlen tomor, magas szintu nyelven kiadott trtasit6sb6l.Bel6that6, milyen nehdz dolga van a forditoprogramnak.Az Y:SIN(X) , azaz "sz6moldLii X szinuszat,6s az eredmenytt6rold Y-ban" magas szintu nyelven kiadott utasit6s tabbsztn gepi mtiveletet igenyel. De nehezdclga \ran a forditoprogramnakazdrt is, rnert pontosanmeg kell drtenie, mit kivdnunk. problernajahoz. El,irkeztunka nyelvek sziirtaxis6nakes szemantik6jdnak r'agyis az, hogl' rnit szabacl (Szintaxis:a helyesirdsiszab6lyck osszessdg*, jeleriiestan,)A helyesfr6sra a hdrli,iiz-rtapi tlletbeir lt,:frni,es mit nern;szemantika:
.)i1
is tigyeltink, holott egy apr6 t6ved6stdbbnyire nem okoz zavart.Ha afi, irjak: "sz6moldki X szimusz6t" nagyval6sziniis6ggel"tudni lehet",hogy a szinuszra , goncloltak: segit az asszociAci6s k6pess6g. A szttmitogep azonban nem "betu asszoci6l: mrikoddse szigoriran determinisztikus 6s mindart,. amire szerirrt"nem tanitott6k meg, nem 6rti (nem is lenne cllszeru,ha drten6!). A programnyelvek teh6t szigorir helyesir6si szabftlyokat irnak elo. milyen jelek (bettik, sz6mok,speci6lisjelek) fordulhatnakelo a Meghatdrozzhk, programban,az utasitfsokatmilyen kulcsszavakkalkell jelolnrink, v6ltozornkat (pl. X I, X2, Z3 stb.) milyen m6don nevezhetjtikel, hogyanvdlasrthatjukel az egyesutasit6sokatstb. A szigorris6g6rthet6: azt, amit leirunk, egy gdpnekkell 6ftelmeznie. Mindaddig, mfg a fon6sprogramban szintaktikai hiba van, a forditirprogram6,lta\6bannem hajland6 leforditani. A szitmit6g6pegyik haszna, hogy pontossagranevel. Tegytik fel, hogy hib6tlan algoritmus alapiin szintaktikailag hibatlan programot sikerult irnunk. Lefordittatjuk ds elinditjuk. Az elso futtat6sokn6l tobbnyire afi. tapasrtaljuk,hogy a program valamilyen hibajelzdssel1e6ll,vagy ha v6gigfut, az eredm6nyakkor sem az, amitvarnank.A hiba abb6l gyokereztk, B6rmilyen nyelven hogy nem tigyelti.inka nyelv szemantik6j6ra,jelent6stan6ra. programozunk,pontosanismernunk kell annak szemantik6jat, vagyis azt, hogy a a gep pontosanmit csin6l.Ez els6sorbana nyelv egy-egyutasit6sunkhat6s6r strukturitjhnmulik, de fugg a gep fet6pft6s6t5lis. Ez a teny magyarazza,hogy mi6rt nem lehet egyetlenmagasszintti prograrrulyelvismertetdsdrekorl6tozni a szfimitftstechnika oktat6s6t: a bonyolultabb feladatolcnfl menthetetlenril zs6kutctbajutn6nk. A forditoprogramszemantiki$anmtilik, vajon az
X - YlZl* 22
a a gep hat6s6r ntasitirs
+
- gyel VAgV QJ t
A kc-vetkezoutasit6sokviszont
Y 2,.
vel tolti fel az X valtozot.
Z,
- melyek az
l t 71 t l binornialisegytitthato l r l \K./
ditdkdtszfmoijdrkki - szemantikailashibftlanok,a legt O D De6p rnegiselobbutdblihrbfs erediri'in.itarl:
'21
A1: A2: 43 : T :_
1 . * 2 x 3 * 4. *. . I*2*l*... I*Zxlx ... All(AZxA3)
(n-ig leirjuk az eg6szszdmokat) (k-ie leirjuk az egdszszbmokat) (n-k-ig leirjuk az eg6szszamokat)
Azt vhrnank,hogy T eg6sz szhmlesz 6s igy dolgozn6nkvele tov6bb, pl. tornbok elemeit indexelhetn6nkT-vel. A val6s6gban T nem mindig egesz. M6r viszonylag kis n-ek esetdn is tort sz6mokat kapunk eredm6nyiil, ami a tov6bbiakban komoly logikai hib6t okozhat. Az ok egyszeru: a v6ges 6s mtlveletvdgzds.Elkeriilnr azanbancsak ugy lehet, pontossfrgfi szitmttbrdzol|,s ha szdmitunk16,ehh ezvlszont valamennyire ismerntink kell magata gepet is. A programorilsinyelv teh6t.a megengedettutasit6sok(rendszerintangol - egyiittesen.A nyeivti) kulcsszavainakosszessdge6s a nyelv szintaxisa szintaxisfogalornkordbetartozik az, hogy milyen karakterekfordulhatnake16a programban -
milyen szab6lyokszerintkdpezheti.inkviitozoneveket,
cimkdket,saj6tfrrggv6nyneveketstb. milyen sorrendbenes milyen form6tumbanfrhatjuk le az utasit6sokat, hogyan v|Iaszthatjukel 6ket egym6stol milyen hosszirlehetegy-egyutasit6sstb. A nyelv szemantik6ja,jeient6stana:a nyelvben rogzitett inform6ci6k, mindenekel6tt az utasitasok 6rtelme zesi szabtilyainakosszessdge. A programozasinyelveket iiltalf'bangdpekt6l firggetleniil alakitj6k ki, es meg igyekeznekugy megalkotni,hogy egy adott teruletenminel tobb feladatot "abstract lehessenoldani veli.ik. Ezeket a - konkrdt gdpt6l elvonatkoztatott, gdpre" elk6pzelt - nyelveket hivatkozdsi nyelvelaiek nevezziik. Kozismerl nyelvekp6ld6ul: FORTRANI (FOli.mula TRANslator) (CornmcnBusinessOrielted Language) COBOL (Alcorithmic Language) ALGOL LanguageTrlr.1.) (Ilrogt'atnming PLll (FOrmulaCAlculator) FOCAI(ileginnersAll purpcseSymboiicInstrttctionCode) BASIC e1tfranciamatematikusrol) IIASCAL (a X\llL szaz,adban
22
Amikor egy szdmitogepgyir valamelyik gdptipus6t alkahnass5 akarja tenni egy magasszintii programnyelvfogadSsdra - vagyis elk6sziti a nyelvnek az adott g6pre szol6 fordit6programj6t , gyakran dont irgy, hogy a 'bizonyos utasit6sait elhagyja, mert saii* gepdn az annak hivatkozhsi nyelv megfelel6 mriveleteket nehdz, vagy 6ppen lehetetlen lenne megvalositani. A hivatko zitsi nyelvnek az adott g6pre va16alkalmazdsifi, adapt|lilsftt(ami tehftt a lehet6sdgek valamelyes m6dosftilsdt jelenti), implement6l6snak nevezzik. Ebben az 6rtelembenbesz6liink olykor IBM-COBOL-ro1, TPA-FOCAL-r61, COMMODORE-BASIC-r6I stb. Adott programozasi nyelv valamely e6pi megval6sul6s6tg6pi reprezent5nsnakis nevezik. "g6pspecifikus", A fentiekb6l nyilv6nval6, hogy a fordit6programmindig 6s e lefo;clitott t6rgyprogramcl.,is azak (vag3'is egy gdpi k6df program rendszerint nem flrttathat6 m6s tipusir g6pen, mint amilyenen forditott6k). A magas szintti nyelveken irt programok azonban elvileg g6pfuggetlenek: ugyanart a FORTRAN nyelvti forr6sprogramotelvileg b6rmely g6p FORTRAN forditoprogramja le tudja forditani, 6s futtatni tudja, vagyis a programokat fon6s-6llapotbancserdlnilehet a gdpekkozott. Ez azonbanrendszerintcsak elv: a ktilonbozo gdpi reprezent6nsokmiatt a forr6sprogramokcsereje rendszerint m6dosit6sokatkiv6n.
2. A technikai fejl6d6shatfsa a programozfs oktat6s6ra 2,1. A programozis tanftSsinak tiirt6neti 6ttekint6se
Tapasztalatokmutatjiik, hogy ha tortdneti elemzdst adunk egy adott szaktertletr6l, ez egyfajtamotivdcilt adhat a hallgat6nak,s6t a sz6ban forgo k6rddskorjobb megdrtdsdtis szolgSlja.A programozilstanitilsftnaktortdnetdt tanulmSnyoma az alilbbiakban l6thatjuk majd, hogy a probl6mamegold6s menetdbenfokr6l-fokra egyre erbteljesebbenkertilt eloterbe az algoritmusfies szerepe szerkes , a konlcdt programnyelvtSl, ill. szdmitogeptipustol fiig gertlen algoritrniz6l6s. el rnagunkat,legeloszoris annak FIa valarnelyterulet miivel6sdresz6njr"rk probldmamegold6s tanitrirldnetidtiekint6sdvelk"ellliezdenunk.Azalgoritmikr-rs a programazasoktatdsanaktortdneti 6ttekint6se, szhm6"ra t5.s6r'aiftrglalkrsz6t;6s hibfinah, iiirtdneti ta:nris;rgainakvizsgS.lata fejlocidsdrick,erectindn5,s;r.,t
.1.:
elosegiti a jelen jobb meg6rt6sdt6s a jovS ig6nyeineka lehet6 legpontosabb meghatirozas1t A tortdnetisdg elv6nek kovetelmdnye a szakoktatasra vitathatatlanulfenn611,de indokolt lehet ezt arvrakegy speci6lisr6sztertilet6re' az informatika, a progr amazasoktat6s6rais adaptalni pl. a szttmithstechnika, m6g al',kor is, ha a sz6ban forgo tudom6ny6gviszonylag fiatal volta csak "A fejletts6gigen gyakran nem a ,r.i6,ryebb mdretti id6ivet engedvizsg6lnunk. az fejl6d6s termdszetesegyrn6sut6nj6nak, hanem egdszen m5s okoknak eredmenye, aminek figyelmen kivtil hagydsa, vagy helytelen egyoldalu ndlktil a magyar6zatat6veskovetkeztet6sekneklehet forr6sa.A mrilt meg6r16se fejlodds tanuls6gai a jelenre ndzve drthetetlenek."l A programozas oktat6stortdneti 6ttekintese mag6t61 6rtet6d6 termlszetessdggelteszi majd hely6re az algoritmus kitiintetett szerepdt:a hangsulyt az algoritmus ds nem a programfogalm6rakell helyezntink. Az 1950-es 6vekig a programozok ndh6ny konkrdt szhmitogdp hasznalatf*tanult6k meg. A gepek konstruktSreitanitott6k meg oket egy-egy adott szamitog6p haszi6lat6ra. Gyakorlatilag minden progralnoz6nak saj6t egydni m6dszere volt arra, hogyan szerkesszen algoritmust az adott si6rnitog6pre.Kezdetbena programozhsmagukkal a szamitog6pekkelfolytatott kis6rletezestjelentette. Ebben az id6ben nem volt m6g sztiks6g 6ltal6nosan haszn6lhatoprogramozdsim6dszerekre,mhr csak a korl6tozottlehet6s6gek6s a szamit6g6pek szerlnyebb megbizhat6s6ga mi att sem. A 60-as 6veket a progr amozdsinyelvek korak6nt szoktuk emlegetni. A vonatkoz6 torekv6sek magas szintu programozftsirn6dszerekegysdgesitdsdre programozdsi nyelvek kidolgo zhstthaz vezettek. Tdbb szaz (tdbb6-kev6sb6 gOpntggetlen) programozdsi nyelv sztiletett. igy azutdn a programoz6s taiitftsfnak a kdrd6seis el6tdrbekertilt. Kezdetbenez a programoz6sinyelvek folyamat6val az oktatfsban tanit6sdbanmertilt ki, az algoritmus-szerkeszt6s nemigenfoglalkoztak. Azoktatdsic6lla1kdsziiitkidolgozaff-feladatol:is ink'abb csakaz adottprogramozhsinyelv elemeinektanitfst* cdlozt6k. Az algtritmikus programozds kora akkor kezd6dott, amikor a 70-es 6vekben fe;lOaesnek ir-rdult a programozas tanit6s6nak rn6dszertana. A struktur6lt progrutooz6ssalkapcsolatosm6dszertanieredmdnyekelsosot'ban E.W.Dijkstra,O.J.Dahles C.A.R.FIoarenevdhezfuzadnek' Az el6bbiek alapjdrnelmondhato teh6t, hogy a programozastanit6sa kisdrieti jellegu tuclom6nykdntindult, hiszen az kezdetbentudom6nyokraes egyar6nttdinaszkodoeljdr6sokis fog6sok egi'tittesc gyakorlaii tapasztalatokra volt. Dolalci E. Knuth amerikai prof'csszor1968-banrnegjelentkon-r'r'iinel< cirne: " fhe Art of ComputerProgramming" is arrill Sr"ulkodili,hogy lnaga a
' Viglt, /1.: ", -':i;t';.i"olrtcttas toi'tdrteitt, Lludilpest-1'9:'2 ' .).,i.
"beavatottak" miiv6szi fokra szerzo is ink6bb mestersdgbelitigyessegr6l, a A fejlesztett gyakorlati tud6s6rol kiv6n sz61ni,semmint elmdleti tudom6nyr6l."A fe3tOaestj6l mutatja E.W.Dijkstra 1976-ban megielent miivdnek cime: D.Gries 1981-bennapvil6got Discipline of Programming". F{asonlokdppen "The Science of Programming", amely a l6tott mgnkfijfnak cirne: s tortdnetutj6nak uj abb mdrfoIdkov6t i elzi. programozdstanit6
2.2. Algoritmus, folyarnathbra 6s program Term ino16gia-tdrt6netimegf*ntoifii;ok
A programozfistanit6s6naktortdnetdt ffitekintveegy6rteimuigazolttstnyer koncep.i6nk, miszerint a hangsrilyt a program helyett az algoritrnusra kell helyezntink. Nem lenne szerencsds,ha valamely, probl6mamegold6algoritrnust mindj6rt egy konkr6t programnyelven kezdendnk irni, hiszen ez esetben a probidmahelyett azadott programozitsinyelv irnd el6, hogy rnilyen r6szletekkel foglalkozzunk. Valamennyireis osszetettebbprobl6ma eset6npedig, mdg az algoritmus, ismeret6benis, utasit6srendszer vagyis a megold5sravezetokdpletes-szoveges - kiildnosen kezdok szamdra kozvetleniil szftmitogdpesprogramot irni, egyebkdntis vesz6lyesv6ilaikoz6s.A programhib6kkeres6se6sjavitdsa sokkal tobb idonkbe 6s fflrads6gunkbakerulhet,mintha munk6nkbanv6gig 6ttekintheto rendettartunk. A rendtartd,segyik l*gjobb eszkozeaz algoritmusrajzos vazlata, a folyan:at6bra. Folyamat6br6t rajzolni ldnyeg6ben annyit jelent, rnint megfogadni a "el6re megtervezni",ogorogtil "ptoklasszikustan6csot:a feladat megold6s6t "el6 -rajzo\ni".Ez6rt m6dszertaniszempontbolalapvetoen gramazili",magyarul idlszerti valamely feladat szamitogdpimegold6sasor6n a modell-algoritmusutat vdgigidrni. J6llehet valamely adott magas szintti folyamat6bra-program programnyelvet szem el6tt tartva rajzolhatunk un. program-orient6lt iolyu* atthrdt is, m6gis a technikai fejl6d6s sziilte sztntelen valtozasok kozepette mdg nagyobb jelentSs6get kell tulajdonitauunk az 6ltaianos iil. amely egyszersrnindkonkrit progral]"In)'elvtol, foiyzunat6brakeszftesdnek, szdrnit6geptipust6I fu ggetlen algor ttrntz|lfrsti s j eIent. LLz i:iiunik Erdeliesrnegfigyelni,hogy - amin[ ez az elobbiei;Lrirl "a1g.c',ritrnus" ds a "program" sravak kozul, erecleti.ieienliisettekitrtYeLr
25
"program" sz6 takarja art. a fogalmat, amit ma raizos algoritmusnak, folyam ati$rinak mondunk. A program sz6t azonbanma az algoritmus kodolt v6ltozat6rahaszn6ljuk:amikor programozunk,val6j fhan egy algoritmust irunk le valamilyenprogramozdstnyelven. Korunkban az 'algoritmus' sz6 a szdmttitstechnika egyik alapvet5 szakkifejezdsekdntkertilt be sz6tSrunkba;ilyen 6rtelemben csak a szazad derek6n jelent meg el6szor. A sz6 kialakulilsfra vonatkoz6an ktilonf6le "logaritmus" szo drdekes elkdpzeldsekkeltal6lkozunk. E. Donald Knuth a bettijf$ekf* velte felfedezni benne; n6h6ny tort6ndsz az I. szfnadban 61t arab matematikus,Abu Dzsafar Vluhammad Ibn fuIusza al Hvarizmi nev6vel hozza az atdny, hogy angol lexikonok .Ezutobbit l6tszik alfuthmasztani osszefirgg{sbe "algorithm" helyett az "algorism" szot tal6ljuk ffieg, kor6bbi kiad6saibana mai amely eredetileg arab sz6mokkal v6gzett aritrnetikai mriveleteketjelentett. A sz6nak ebben az lrtelemben vett jelent6se az id6k folyam6n feled6sbemerult. M6dosult alakj ttbanm6r azuj tudom6ny 6ltal haszn6ltfogalom nyert kifejez6st: Az algoritmus olyan utasit6:soksorozata,amely azon muveletek sorrendj6t hathrozzameg,amelyek adott feladat(csoport)b6rmely lehets6geskimenetel6re n6zveannakmegoldist* adjdk. A definfci6t 6tgondolva erezzik, hogy az algoritmus univerz6lis "emeljiik le a kagyl6t - v6rjuk meg a fogalom. A telefonftlkdben elhelyezett telefon6l6si stb. tdrcstnzunk bugo hangot - dobjuk be az 6rm6t ritmutat6t6l kezdve, a k6t termdszetesszhm legnagyobb kozos osztoj6nak meghat6raz6sira szolg6lo (EuklidestSl szSrmazo) mechanikus elj6r6son ker:eszttil egeszenegy g6palkatr6,szgyirttsi folyamatdnakleirasiig valojaban algoritmusokr6lvan sz6.A paprik6skrumpli vagy a m6kos beigli receptjeis algoritmus,csakitgy,mint pdld6ula fecsk6kkoltoz6siosztone - meg akkor is, lra ez utobbi algoritmus l6p6seit pontosan nem ismerjtik. (Vajon maga a rdszlet6ben szigoriran tervezett minden Vil6gmindens6g, amely 6s fejl6d6stmutat,nem - egy esetleg szerintifeldpitetts6get torvdpyszenisdgek "vdgrehaititsa"?) onnrag6tis befoly6solo- Algoritmus megma is folytatod6 Amikoi' a tan trkepzesben a tanbrjelolteknekp6ldaul a tanul6s tanit(tsf* tanitjuk, voltakdppena tanul6salgoritmusirtkell 6tgondolnunk,kidolgoznunk. a szantitogdpes A kezdo programozal< tanft6sakor pedig mag6nak "arlgoritmusfnak" (probl6ma- niodeil - algoritmus menetdnek, ftlaclatmegold6s - prograin) vdzol6s6t hasznaljr-rk az algoritmusfcgalmSnnll - tal6n legelso-
",4 ^/- l)
szembeszoko anal6g megvil ttgithsira. Kor6.ntsem v6letlen ez utobbinak aj6nlott (itt csak v6zlatosan hasonl6s6gapolya Gyorgy2probl6mamegold6sra kozolt) algoritmus6val: 1) 2) 3) 4)
a probllma megdn6se, terv k6szit6se, a terv kivitelezdse, visszatekintds.
3. Az algoritrnikusfeladatmegold6stanftfsa Az algoritmikus gondolkodfs jelent6s6geaz aktatisban
3.1. A hagyom6nyos6s a szfmit6g6pesfeladatrnegold6s
Vizsg6ljukmeg az algoritmusszerep6t6s helyet aprobl6mamegold6sban. m6r a szhmitog6pek A feladatmegoldfsnakbizonyosmenetrendjetermdszetesen es a *.gielen6se elStt is kialakult. A kovetkez6kben a hagyom6nyos mu nkaflzisainakosszehasonlit66ttekint6s6vel sz6init6gdpesprobldmamegold6s hasznalata szeretndnk megvil iryitani itt, hogy a t6rolt programri szamitog6p mennyibenmodositja e menetrendet. munkafhzisa\: A hagyomAnyosfeladatmegold6s ( 1) a probl6mafelvetdse6s elemz6se, (2) a megold6s(legtobbszormatematikai)rnodelljdnek vagy kivSlasztlasa, megszerkesztese terv keszitese (3) megold6.si (a rnegolddsaigoritmus6nakkidolgozasa), (4) a telaclattdnylegesmegoldfsa fitrnutatdsaszerint, az algonitmrus elemz6se.felhaszn6l6sa' (5) a kapott ereclmdnyeii
..r "'l
A sz|mito gep es feIadatmegoId6s mu nkafilzisai : ( 1) a probl6mafelvet6se6s elemz6se, (2) a megold6s(legtobbszorrnatematikai)modelljdnek lnegszerkeszt6se vagy kiv6laszthsa, (3) megold6siterv kdszitdse (a megolddsalgoritmus6nakkidolgo zisa), (4) Az algoritmus szfm{t6g6pi prograrnba foglalSsa, majd a program szhmit6g6pifuttatdsa, (5) a kapott eredm6nyekelemzdse,felhasznzl|,sa. Feltiletesen szeml6lve azt gondolhatn6nk, hogy a hagyorn6nyos 6s a szilmitogdpesfeladatmegold6salgoritmusakozotti egyetlenktilonbsdg, hogy a megold6sitervetaz egyik esetbenaz ember,a m5sik esetbena szdmitogdphajtja vdgre. A k6t munkafolyamat kozotti donto kiiionbsdg val6j6ban persze az algoritmus el6re kidolgozottsS,ginakm6rt6k6ben6s pontossitgihan rejlik. A hagyom6nyos rnegolddsn6l az algoritmus szervezdse ds vegrehajt6sa ak6rh6nyszoregybefolyhat,meit argondolkod6-sz6mo16 ember fej6ben a soron kovetkez6 miiveletek kivfiasrtfts6val legtobbszor a v6grehajtSsis egyutt itr; imbitr terjedelmesebbfeladat megoldfxilhoz mindig cdlszeru un. megoldasi tervet k6sziteni, amely m6s szavakkal 6ppen az algoritmus tdbb6-kevdsbe j elenti. pontosmegszerkeszt6sdt
3.2. Programnyelvt6l,ill" szfmit6gdptfpust6lfiiggetlenalgonitmusok 3.2.1"A rnondatszeriilefr6svizualiz{lilsa (PszeudokdC F onyamat6bra Stnuktogram) Ktilonbazo algoritmusleir6 eszkozok koziil v6laszthatunk: pl. foll'amatabra, struktogram, mondatszerii leir6s. Mindegyiknek kozos cdlja rnegoiddsiten,etkdsziteniegy adott felarlattfpusra, aniely val6j6bana megold6s menetdnekg6ptol ds konkrdt progranuryelvt6l friggetlen, szemldletes, a logikai gondolatmenetetegydrlehnrienkoveto 6s a szerkezeti egysdgeket vildgosan ttikrozo leir6sa. Ezeket az algoritrnuslefr6 eszkozokethaszn6lhatjuk akkor is, ha nern okvetlen sz6rnit6gdppelkell rnegoldanunkegy adott feladatot. A tanit.lsi-tanr"rJiisi folyamathana probldmainegolddsnak erre a kreativitast igenylo szakaszara, az algoritmus konstruiilasdra kell koncentrilrrutili,ltiszcna \/dgrehajt6s csuphnniechanikustevdkenysdg,akaraz, eniber,aliara gep vigzi azi.
'r {r
3.2.2.A magasszintiiprogramnyelvekalaputasitisai Alapvetdfoly'annatibraszimb6lruneok
Aza1goritmustajobb6ttekinthet6segkedv66rt form6ban adjuk meg: un. tblyamatfhrSt, vagy mds szoval blokkdiagramot kdszftiink. A tovabbiakban a (valamely) magasszintri nyelven programozo ember algoritmus-szerkeszt6, folyam atibra-keszita tev6kenysegehez szuks6ges legfontosabb ismereteket, a szok6sosanhaszn6lt szimb6lumokat 6s ezek jelentds6tfoglaljukosszeroviden. A folyamat6braszimb6lumokkal kapcsolatbanmegiegyez,nrk,hogy az altalunk hasznaltjeloldsek nem kizdrolagosak, &z irodalomban sz6mosm6s v6ltozattal is tai6lkozhatunk. A folyamat6brakezdeteta .ihrdn lSthat6szimb6lummaljeloljtik.
4.abra Az adatbeviteli utasft6s rdvdn a beviteli periferian keresztul adunk ertdketvalamelyvSltozo(k)nak(5.6bra).
A.B,C
\J
b)
a)
5.abra
Az-,5.a) 6bran az X nevtl viritozo) it.. 5.b) abran az A. R e{sC nevii 'tz"X, valtoziili liapnakefrdlietaclatl,-*r'ifellel: a szimitogei.:a beadottrirtei
:- ,/
Az 6rtdkadoutasitasa bal oldalon eil6 @gyetierr)v6itozciiak ad ertdicei: a jobb oldalon 6116aritmetikai kifejezdskisz6mitott 6rtdkdt. 6.o) 6bra. Az ertekadoutasft6sv6grehajtdsakdt - idSben egym6sutdni - l6pdsbol6ll : a sz.fmitogdp
el6szor megdllapftjaa jobb oldalon 6116kifej ezds6r-t6ket, majd ert az erteketelrakja abal oldalonen6viltozo nevdvel azonosftottt6rtertiletre. (A balra mutato nyil szimbolumj6l kifej ezi az emlitettid6beli sorendiseget.)
D --- 82- 4Ac
6.a) 6bra Tekintsrik pdld6ul a 6.a) fhra drtdkad6utasftds6nakvdgrehajt6s6t: D ,,legyenegyenl6" B2 - 4AC . A sz6mitogdp,,el6veszi" a B, az A 6s a C valtozonevekkel azonositott tfrteniletekr6l az ott t6rolt szfumert6keket, ezekkel az adatokkai kisz6mitja a 82 4AC aritrnetikai kifej ezds 6rt6k6t, majd elteszi ezt a D v iiltozondvvel azonositott t6rteruletre.
6.b) abra A 6.b) 6brdn ldthatodrt6kadoutasitds ,,X legyeneg1'enl5Y" hatasara a szarnftogep ,,elovesziaz Y nevri fi6k tafialm6t es ezt L-,eteszi az.X ne.,'ii fiokba". Mint minden hasonlat,a ,,fiokoshasonlat" is sdntit: e szarnitogep ktilonbizo vlltozonevekkel ezonositott tarteruletei eg)' kisse rn6str; int ."rniilicldneli",inint t\z ernlitr:t1-,,ilyen vagy olvannerriifi6l':nk". Valaiabrn,
:U
aurikor a szamitogepeliiveszi azY vSltozisxtdvvelazanositotitfrieruletrol az ott t6rolt sz6m6rt6ket,majd elrakja art az X villtozon6wel azonositott t6rteriiletre, akkor ezen tev6kenys6g eredm6nyekdntmindk6t t6rteriileten otzt ugyanazt a szdmdrt6ket.,,Kivette azY fi6kbol, majd elhelyerte azX fi6kban." (D. eztital azy fiok nem tirijlt ki - mik6nt a hasonlatsugallni -, hanem megmaradtaz eredetitartalma!)
6.c) ttbra "X legyen egyenlo 3,5". A V6gul a6.c) ilbrSnis6rtdkad6utasit6stl6tunk: sz6mitog6pez esetben is az utasit6sjobb oldal6val foglalkozik el6szor: itt konstans szamdrtdket taliil, efi. t6rolja el a bal oldalon 6116 va\tozondvvel azonositott t6rtertiletre. A jobb oldalon taliit konstans szitmdrt6ket,a 3,5-et "betesziaz X nevti fiokba". Az erterad6 utasitfs jobb oldal6n 6116aritmetikai kifejezdsben v6ltoz6k, konstansok 6s fi:ggvdnyek lehetnek matematikai alapmriveleti jeleldcel ugyanakkora zfrojelezdsis megengedett. osszekapcsolva, A frggvdnlrek 6rt6kdt a szhmitog6pilltalthan valamely el6re megirt gdpi rutin vdgrehultarauaI szhmitjaki. Folyamatszervezdskorazokata frggvdnyeket hasznalhatjukaz aritmetikai kifejezdsekben,amelyeknek feldolgozo rutinj6t a v6lasztottprog ramazhsinyelv forditoprogramja kezelni tudj a. A dontds rdvdn a folyarnatibra elilgazik. A sz6rnit6gepes program tdnyleges fut6sa majd bizonyos feltetel(ek) teljesuldsetol firggoen vdgrehajt6s6valfolytat6dik. A - vag),lagosan- valamelyik utasft6s(csoport) valosit meg. dontdsteh6t feltdteltSlfuggo vezedesatad6st
J.ibra
3l
A logikai clontds ketfel6 tcrtdrrS ell,gazhsttesz lehetciv6 (7 .6bta)- A rombuszba felt6telkdnt logikai kifej ezdstirhatunk, amelyet ki6rtekelve logikai 6rt6ket: IGAZ-at vagy F{AMIS-aI (IGEN-| vagy NEM-et) kapunk eredrndnyul. A logikai kifej ezdslegegyszerubbfonnaja egyetlen rel6cio. A matematik6bol ismereteseka lehetsdgesrel6ciojeiek::, <, {, >, >, #. Egyszerubblogikai kifejez6seket logikai oper6torokkal osszekapcsolvatetsz6legesenbonyolult logikai kifej ez6st k6szithetiink. Az alapvet6 Boole-oper6torokat a 8.6br6n l6thato tfhl|zatban foelaltuk ossze.
Logikai mriveiet ( Booie- operdtor)
Altal6nosBoole-algebrai jelcil6s6s elnevezds
Halmaza,igebrar anal6gia
VAGY
\ /
halmazok egyesitese
OR
diszjurkcio
V
( logikaiosszeadzrs )
ES
A
AND
t
/\ /
.
r
J
( logikaiszorzas ) Tagadas
NOT
_1
neg6cio
I
vagy unloja
"
KonrunKcto
\
I\-/I
f I hatmazokkozosrdsze vagy metszete
ki egeszi tovagy komplementerhalmaz
8.abra
Az aritmetikai dontds folyamatthra szimboluma a 9.6brftn l6thato. A rornbuszbairt aritrnetikai kifej ezdskisz6mitott (aktu6lis) ert6kdnek elojeldtol fugg6en itt h6rom iranyba ilgazhatunkel.
kifejezes
9.abrzt
,1 .
)L
Terrn6szeicsena kdtftle dontds bfnnelyike megvalosithat6 a masik is. segitsdgdvel H6romn6l tobbfel6 tortdnS elilgazitsfolyamatilbra szimbolum6t adtuk meg p61d6ula rombuszbabeirt aritmetikaikifej ez6skisz6mitott a 10.6br6n.I1yenkor fuitdteleleiret. ertdke a i.ruionbczoii'dnyoiibavai6 el6ga';,Latds
10.dbra
A I 1.5br6n az eredm6nyek kiirat6sara szolg6l6 adatkiviteli utasit6s folyam atabra szimb,5lum6t adtuk meg. Kezenfekv6, hogy ez hasonlo az adatbeviteljelkdpdhez, az inform 6ci6-iraml6sellentdtesir6nyit a nyil jelzi.
-.'/
1l . a b r a A folyamathbra egyes blokkjait folyamatvonallal kapcsoljuk ossze, jelezvdn a mtiveletek vdgreliajt6s6naksorrendjet(IL.ihra). A programir6skor ndha a folyarnatvonalnakis utasitfst feleltetunk meg. Ez a feltetel ndlkiili vezdrl6s6tad6stnregvalosito ugrir utasiids majdnem minden magas szintti nyelvbenmegtal6lhat6.
I
t, I I
I
ll.abra
))
A folyamatitbravegetjelzoszimb6lumota 13.6br6nl6thatjuk.
13.6bra
3.2.3.Ciklusok
A feladatok szilmitog6pes megold6s6ban gyakran el6fordul, hogy bizonyos utasit6sokattobbszoris v6gre kell hajtani. E*, az utasit6sokisrnetelt lefr6san6lkiil is megval6sithatjuk. sot adoff esetben ldnyegesen A programoz6 munkaja kevesebb kell a programba kevesebblehet -, ha egyesutasit6sokatcsak egyszer-kdtszer irnia akkor is, ha azokata gdp b6rmilyen sokszor is hajtja majd v6gre. Ilyenkor a vezerl6st a m6r vdgrehajtott utasit6sokra adjuk ttt feit6teles (vagy feltetel ndlktili) ugro utasit6ssal.Az utasit6sokatosszekot6folyamatvonalakhurkot, irn. ciklust alkotnak(14.itbra).
I zf.2trr-a
.'r ,4 _1ri.
A ciklusban a tobbszorv6grehajtand6utasit6sokata ciklus magi6nak utasit6snak(dontesnek)is kell nevezzik.A ciklusbanfeltdteles vez6rl6s6tado lennie, hogy a ciklusmagmegfelel6 szhmuvdgrehajthsaut6n a programfutds el6bb-utobb felt6tel6nek A ki16p6s a ciklusbolkil6phessen. tor,6bbhaiadhasson, teljestilniekell, 6s ert, ugy lehet e16rni,hogy a felt6telbenszereplovaltoz6k megv6ltoztatjuk. ismdteltv6grehajt6s6vai 6rtdkdta ciklusbanl6v6 utasitasok
logikaiddnt6ssel 3.2.3.LCihlusszervez6s
A ciklus f6 rdszei:
15.abr-a
?q
A I 5.itbrarovidit6seinekj elent6se:
CE: A ciklusel6kdszitdse tobbnyirekezdeti6rtdk(ek)megadilsdtjeienti. A ciklus eldkdszitdse CM: Ciklusmag , Allhat sz6ntutasit6s(csoporl). A ciklusmaga tobbszorivdgrehajt6sra is. de lehetb6rmilyenbonyolultprogramr6szlet egyetlenutasit6sb6l, vagy akdrciklusokatis tartalmazhat. Felt6telesutasit6sokat MR: M6dositoresz hogy a kil6p6sifelt6telegyszer A modosit6r6szr6v6nv6lik 1ehet6v6, majdteljestil. KF:
Kil6p6si feltdtel A logikai dont6seredm6nyekdntvagy a ciklusmagotkell ism6telten vdgrehajtani,vagy ki kell tdpni a ciklusbol.
"h6tul tesztel6 ciklus"-t l5tunk: a ciklusmag ut6n a A l'.fhrdn fn. modosito r6sz koverkezik 6s a ciklus v6g6n ("h6tul") vizsgaljuk a kilepesi feitetelt. J6l l6thato, hogy ebben a ciklusszewezdsi sem6ban a ciklusmag legaldbbegyszerv6grehajtdsrakeriil. A hurokban szerepl6 btokkok sorrendjetetszdsszerint valaszthatomeg.
pdld6ulrin. "el6l tesztel6ciklus"-rolis (16.abra):itt mindjarta fgy besz6lhetiink niepeti felt6tel vizsgdlatftval kezd6dik a ciklus. Az ilyen fajta ciklusszewezdsnelelofordulhat,hogy a ciklusmagutasft6saita szamitogep egyszersemhajtja v6gre. CE
I 6.abra T
r,yi z
3i-'
Vannak olyan termdszetri feladatok, amelyekndl mdr a ciklusba valo bel6pds eli,ii elcltjl, hogy a ciklusrnagot hfunyszorkell majd v6grehajtani. Ilyenkor a vdgrehajt6sokat sz6moljuk. A szftmlitlokdnt haszn6lt vhltozot ciklusv altozonak nevezzik. A?ft, hogy a ciklus rnagja h6nyadszor kenil vdgrehajt6sra,a ciklusv6ltoz6 mindenkori ert6kemutatja, ez6rt e valtozo ertel<et - a ciklus minden egyes v6grehajtSsakor egy 6rtdkad6utasit6snakp61d6ul eggyel novelnie kell (modosito rdsz). Az ilyen irn. szitmlillassal vezdrelt elore rogzitjiik. ciklrrsoknalteh6t a ciklusmag v6grehajtdsinak darabszdmtrt
3 .2.3.2.Ciklusszexrez6sciklusutasftissal megolddsasor6n olyan A ciklusok haszn6lata a feladatok szfumitog6pes gyakori, hogy a magas szintri programoz6si nyelvek irn. ciklusutasit6sokatis tartalm aznak.Ezek titalf}lan a szdml6l6ssalmtikdd6 ciklusokat vagy a 15. vagy a l6.ihra szerintval6sitj6kmeg andlkiil, hogy a ciklust szervezo
CIKLUSELOKESZITES-t, ds KILEPESIFELTETE,L-I RESZ.I MODOSjTO onallo utasft6sok fonn6jaban le kellene frnunk. Egy ilyen ciklusutasft6s hasznalataesetdnm6r a folyamat6bra keszitdsekoris lehetSsegtinkvan a ciklus roviditett rajzalfts6ra.A ciklusutasitSs folyam atftbra szimboluma a 17 -ftbtdn l6thato.
CV : KE -t6l VE-ig LK l6peskozzel
Ciklusmas
.1 r7
) l
Az ihr an hasz;r61trov i ditdsek :
CV: KE,: VE,: LK:
ciklusvhltoz6, kezdoert6k, v6g6rtdk, l6p6skoz. 17.fibra
Ezek egyutt ,azt jelentik, hogy a CV ciklusv iitozo 6rt6ke a KE kezdoerrdkt6l a VE v6,qdrt6kig az LK l6p6skorrlyi 6rt6kkel v6ltozik 6s a ciklusmag utasit6sait a g6p minden irj drtdk felvdtele ut6n vdgrehajtia. Az ".gy szemilybeir ujonnanhaszn6lthatszogalaku blokk neve: ciklusfej.Ez tehat elldtja" a CE ciklus-el6k6szit6s,az MR m6dosito resz6s a KF kil6pesi felt6tel blokkjainak feladat6t.A ciklusmag v6gdt az 6br6n \i*hata otszog alakir blokk jelzt, amelybea ciklusv6ltoz6 nev6t irjuk. A lT.ihrin 16that6jelkep, a ciklusutasit6sszimb6luma csup6n annyit jelez, hogy (valamely) szttmlttl5ssalvezdrelt ciklusrol van szo. Mag6rol a tehat - a programnyelvismeretendlkul - nem tudhatjuk,hogy ciklusutasit6srol "h6tul tesztei6", vagy a mukodo ciklusoknak a 18.5braszerinti a szaml6l6ssal "eI6I tesztel6" v|ltozati*takarj a'e. 19.abraszerinti
CV>VE
CV+LK CV *- CV + 1ii CV>VE
18.irbra ,)(] JO
'
3.2.4. Indexes vfl tazbk(Tdnabiik)
a A magas szintti programoz6si nyelvek kiv6tel n61kti1lehet5v6 teszik 6s az tombvdltozol (indexes v6ltoz6k) haszn6la#rt.A tombv6ltozot a neve indexe egytittesenazonositja. Az operativ tixategt sokfiokos szekrenyhezhasonlitva"beszdlttinkm6r A, A, B, C stb' nevu B, C stb. nevti (ind.* n6ltuli) vSltozoktartalm6r6l mint az "mag6nyos fi6kok" (egyes)fiokok" tartalm6rol. Ezek az index n6lkiili v6lto zok voltak az operativt6rban. elemti Tekintstink egy valamilyen szempontbol osszetartoz6, N ne adathalmart! Jogosan mertil fbl az igdny, hogy ezeket az adatokat rendszerteleniil taroljuk ("ne szorjuk sz6t a szekr6ny legkulonbozobb tar egy ellrelyezkedestifiokju1bu";,hanem erre a cekajeloljtik ki az operativ tombj6t. A Z1.ihrin p6ld6ul az A(I) nevri egymdrettitombot szemldltetjiik, egyes amely N db adat t6rol6s6raalkalmas,ha az index: r=1,2,...,N-A tornb t6rteriileteitenXtalcsup6nazindex azonositja:A(1), A(2), ... , A(N)'
A$) A(0) A(1) A(2)
A(N)
i9
Az egym6retfitomb helyett nem v6letleniil hasznfiatos a matematik6bol kolcsonvett vektor elnevezds is, amelynek elemeit egyindexes valtozoiarak nevezik. Ugyanugy a'k6tm6retri tombot, amelynek elemei ketindexes valtozok.,a matematik6b5I ko I csonvett kifej ezdssel m6trixnak nevezik. Pdld6ul egy NxM-es A m6trix elemeit cdlszenien az A(I,J) nevu kdtmdretri tombben t6rolhatjuk (2l.6bra). Az A(I,J) kdtindexes valtozo a k6tm6retri tomb "I-edik sor6ban ds J-edik oszlop6ban tal6lhato fiokj6t" azonositja.
0 1 2
I
A(I,J)
21.abra
Term6szetesenlehetnek kett6ndl nagyobb mdretti tombok is (kett6nei tobb indexesvSltozok).Az indexek 6rtdke mindig eg6szszam.A tornbvaltozo indexebekonstanst,valtazat vagy aritmetikai kifej ezdstfrliatunk. M.gi egyezzil<, hogy az indexben szereplo kifeJezds formajirra is tartalm6ra n6,zve a prograinoz6si nyelvek ktilonbozo megszorit6sokat tartaiinazna\<.
40
.
3.2.5. A folyamatdbra tiirdel6se
zeti feladatok terjedelmesebbfolyam atabrfn Bonyolultabb, nagyobb 161eg Ilyen esetbenc61szeruel6szor vazlatos, irn' fo gyakrar, ,r.h.zen 6ttekinitretOt<. ds jol fotyu* at1brffikdsziteni, amely rovidsdge miatt konnyen 6ttekintheto koveth eto(ZL.itbra).
1.alprograrnneve
2. alprogramneve
3. alprogramneve
22.fibra (rnas A vazlatos fo folyamat6bra programr6szletekb6l,alprogramokboi szoval: eljar6sokbol) 6llhat, amelyeket azutan ktilon folyarnatabrakon rdszletezhetunk(.23.itbra)1. alprogramneve
,,f,
1. alprogram neve
23.abra
r'l
leir6 Ennek a megold6snakel6nye az is, hogy a rdsrtev6kenysdgeket folyamatthritk ktilon, akhr m6s szem6ly iital is elk6szithetok6s ktilon kiprob6lhat6k,lejatszhat6k. Az itt isrnertetettm6clszer,a folyamathbri,/r-tordeldsenem csak az algoritmus(a folyamatdbra)k6szit6sekornyqithatjelent6s segitseget.Ha egy biionyos rdszfeladatota f6 folyamatbantobb helyen is v6grekeil hajtani,ugY efr.az elj6rdstcsakegyszerkell kidolgoznunk(legfeljebba nev6tkell tobbszor (6saz hanema programoktordel6s6re leimunk).Hogy ne csaka folyamatSbr6k, a magasszintu ismetl6sekeftertl6s6re) is lehet6s6gnyiljon, term6szetesen programoz6sinyelvekbenis haszn6lhat6kilyen alprogramok(el.larasok).Az Lgaiasot teh6t nem on6ll6 programok, hanem a fdprogramb6l hivhato piogru*rdszek,alprogramok.A sz6mitogepoperativt6rj ihan |lta\fLbancsakegy de petaa"ybanvannakjelen. V6grehajt6suka f6programb6lkezdemdnyezhet6, folyat6 dik az ott soronkovetkezo ut6n a fdprogramv6grehajt6sa v6grehajt6suk utasit6ssal.Az eljar6sok egymdsba6gyarhat6k,vagyis az alprogramnakis lehet(nek) alprogramja(i). Az alprogramok szerkeszt6sekora kulonbozo eltdr6 szabiiyaitkell figyelembevenni. programnyelvek
3.2.6. A strukturilt programozisr6l
A v1zlatos fo folyam atitbra keszitesdnekgondol ata mag6banhordozza a lehet6s6g6t. modulrendszerdrvdnyesit6sdnek Az egyes programrdszletekb6l, alprogramokbol mint epitokocl<6kbol bonyolult 6pitmdnyekemelhet6k.Maguk a bonyolult programok tetszolegesen 6pft6kovei lehetnek egy esetieg meg magasabb is - mint modulok stnrl
,,1')
I
,1;
n,1, f
I
V
elilgazfisok
sorozat
ciklusok lzi.ribra
.1 -
+J
A hibakeresdsmegkonnyitds6neliig6nye is azt szorgalmazz4 hogy algoritmusaink megfogalmaz,lsakorcsakis ilyen folyamatilbra-szerl<ezetekbSl epitkezztink, a strukturitlt programozas el5bb ttrgyalt elveit 6s szabalyart szisorilanbetartsuk.'
tanitsunh? 4. Algoritmusokat vagy algoritmtrs-szerkeszt6st .4'.L. tanitSsa6s Az a[gol'itrnus-szel"keszt6s a megoldisi algoritrnusokg6p n6lktili ellen6rz6se
ugy kez;d6dik,hogy a probl6in6t eiemezztik, A tcljes probl6marnegold6s ut6na ebb6l matematikai modellt alkotunk, a matematikai modellhez kidolgozunk egy algoritmust 6s vdg{il az algoritmusalapj6n programot irunk: program. probldma - modell algoritmus Teh6t adva van valamilyen probldma 6s ehhez nektink kell tnatematikai modellt fel6llitanunk. Olyan helyzetbenvagyunk, mint a koz6piskol6s di6k, amikor szovegesegyenletetkell megoldania:a szovegbenfelvetettprobl6m6bol valamilyen kdpletet, valamilyen modellt kell felirnia. Ilyenkor a szoveg linyegtelen rdszeit elhagyjuk 6s csak a ldnyegesekrekoncentr6lunk.Ez egy kozepiskolai p6lda szintjdn folottdbb egyszeri; az 6letben felvet6do probl6m6kb6l azonbansokszor csak nehezentudunk helyes modellt alkotni, mefi scrkanvitatjakazt, hogy a probl6m6banmi a l6nyeges6s mi a ldnyegtelen. A kdrd6s teh6t annak eidontdse, hogy a probl6ma val6di rnegoldisfthoz t6nylegesenmilyen feladatot keil kitrizni. A matematikaimodellben teh6t a kitrizendofeladatkorvonalai foglaltatnak. A modell birtok6ban hozz|foghatunk az algoritmus megszerkesztesdhez. Az algoritmus a megold6s egydrtelmti szabilyrendszere,amely v6ges sok utasit6s meghatarozott rendben tort6nS eloir6sa r6vdn tetszolegesensok egymdstolcsak adataikbanktilonboza - feladat megold6saruvezet. Amikor "haszn6latiutasit6s" szerint nyilv6iroshelyr6l telefonflunk 6s a kiftggesztett i6runk €1, akkor is algoritmust hasznalunk: ahhoz, hogy kapcsolatot sotrendbenvdgre kell valamelyrn6sik6llom6ssal,rneghatarozott terernthessilnk nrajdhajtanunkaz algoritmusutasit6sait - le kell vemi.inka kagylot, tneg kell v6rnunka birgo hangot,bc kel1dobnunk az ertndtstb. A ktilonb6zo aclatokitt a kiilonbo:i:6hiv6szdmok. Az algoritrnrls megfogalmazhat6szovegesellis, de koml'ebben igazodtink el, ha rajzosan adjuk meg. Az algcrritrnusrajzos is saokdsncve,lni. vag_yfbli'atnat6branak bloi.,li-eliagrarrrnalt rrregfogalmazasat
'/t 'tT1
A szitmitogdp eredm6nyes hasznillattnakkul cskdrd6se, hogy megfeIeI6-e kidolgozoff, az algoritmus,amely alapj6ndolgozunk.Egy pontos,r6szletesen megir6saszinte szovegesvagy rajzos algoritmusbirtok6bana forr6sprogram ezdrt r6szletesenkell foglalkozunkaz algoritmus mechanikustev6kenys6g, alapelveivel. k6szit6s6nek Az el6zSekbenr6szben m6r hangsrilyoztuk,hogy a h6tkoznapi valamelyest gondolkod6s, a matematikaigondolkod6s6s a g6p "gondolkod6sa" eltdr egym6st6l. Mivel algoritmusunkat adott esetben szftmitog6p fogja vdgrehajtani, mindig tigyelntink kell ana, hogy az egyes ldpdsek mogott ",6reznik az absztrakt gdpet": tudnunk kell, mire kdpes 6s mire nem. (ILendszerintafr. rrcmvessziik iudoin6sul,hogy a gep elernibbldpdseketv6gez, mint mi.) Erdemes tekintettel lenni affa is, hogy milyen megold6s mennyi mem6ri6t kot le, 6s h6ny g6pi utasitd.svdgrehajt6sfnigdnyli (vagyis mennyi tut6si id6tjelent). Tegytik fel, hogy van valamilyen X 6s Y v5ltoz6nk,6s ezek tartalm6t fel akarjuk cser6lni.Egy matematikailevezet6sbenkonnyti dolgunk vani az
X-+Y vagy m6g inkitbb az
X < + Y
Y+X jelol6sek bdrmelyike felredrthetetlentil kifejezi sz6nd6kunkat.Am ha nem vagyunk el6g koriiltekint6ek, 6s a fenti hazzirendel6stmechanikusanfrjuk le egy algoritmusba,hib6s eredmdnytkapunk: X+-Y Y+-X Az elso utasft6ssalminden rendbenvan, hiszen art jelenti: "vedd az Y valtozo jelenlegi (aktu6lis) tartalmirt, 6s tedd az X-be" . Ha ez az utasit6s egy sz'Smitogdp programjihan szerepel, akkor X 6s Y egy-egy pontosan rneglratilrozott(rnegcimzett) mem6riarekesztjelent. A szdrnitogdp ldpdsrol l6pdsrehalad, tehirt az X <- Y utas{tdshat6s6raaz Y jelu rekesz tartalm6t 6tmdsoljaX-be. Most rdtdra kovetkezoutasit6sra:Y +- X MiveI az X rekesz tartalma most mdr ugyanaz,mint az Y rekeszd,ezdtLa rndsoclikutasitds vegrehajt6sautdn - a felcser6ldshelyett - rnindk6t rekeszbenaz eddigi Y drtdkdtta161juk, 6s az X eredetitarlalmaelveszett.
"r,)
segiti: kovet6sit6bl6zat\<6szitese Az elobbiek(a helyelenalgoritmus)belfuthsdt
1.BE,X, Y z.zu X, Y ("eredeti") 3.X<-Y 4.Y<-X 5. KI X, Y ("6trendezett") Legyenpl. a k6t 6rtdk 3 6s 5 :
Az eredmenyteh6t:
eredeti: X : 3
6trendezett:X:
5
Y:5
Y:5
(helytelen!)
A feirti valtozacser6thelyesencsak egy harmadikrekesz kozbeiktatdsaval vegezhetjtikel, pl. fgy:
Z +.X X<-Y Y <_Z KezdSk szamara segitheti a probldma onallo megoldfsat, ha megkdrdezzik hogyan cserdlndk ki pdldaul ket (egy vorosbotral es eLI)' feherborraltoltott) hordo tartahn6t.Az alapveto analogia aklcor is sep;it,ha a Sot. ha ritviiirgitr-inka hasonlat egyes rdszleteibeneltdresekniutatlcoznai<. is segithetika jobb tticgrirt.i,it. ma,g,iilc az elt6rdsel< lo l,rilionbsegekre, rrr,:rfi:le
:; i_r
Kovetesit6bl6zata helyesalgoritmushoz:
1.BEX,Y 2 . K I X , Y (" eredeti") 3.2 +-X 3.X<-Y 4.Y +-Z 5 . K I X , Y ("6trendezett") Az eredeti6rt6keklegyenekismdt 3 6s 5 :
Az eredm6nymost:
eredeti: X : 3
6trendezett:X: 5
Y:3
Y:5
(helyes)
4.2.A megoldfsi algoritmusokfinomft6sinak folyamata A "l6p6sr6ll6p6sre" m6dszer
A kovetkezo feiadat rneeolddsavalaz algoritrnusszerkeszteslblvamatat szeretnenkeruekeltetni. L,egyenX1,x2, X3,..., Xn mindegyikehat|rozottanpozitiv, vaul,is xi > 0 nagysAgszerintcsokkenosoroz.atba. Vi-re. Renclezzfikezelicta szarnokat
l F ,
+l
1. megoldSs Tegyiik fel eldszor,hogy n kicsi, legyenpl. n - 3 . " Hogvan rendezndnk mi h6rom sz6mot? Az igazat megvallva ran6z6'sre l6tjuk",melyik a legnagyobb,melyik a legkisebb:ha a h6rom szampl. 5, 18, 13, azonnalle tudjuk irni a helyes sorrendbe:18, 13, 5. Nem is olyan konnyu "a megfogalmazni,mit csin6ltunk,hiszen megold6solyan termdszetes". Mindenesetrev al6szintileg i gy gondolkodtunk: 1) 2) 3) 4) 5) 6) 7) 8)
egy darabpapina leirjuk a h6rom szfimot kikeressiika legnagyobbat leirjuk a papir egy m6sik r6sz6re valamilyen m6don jelezzik, hogy ezzel a szSmmalmar nem kell foglalkoznunk (pl " Sthuzzuk) a marad6kb6lkikeresstika legnagyobbszSmot lefrjuk a papk m6s rdsz6reirt szfimut6n ithuzzuk a megmaradtegyetlensz6motleirjuk a papir m6sik rdszdre,az elozo kett6 ut6n.
Milyen szhmitoe6pesalgoritmustsugall ez az eljitrds?Mindenekel6tt kell - pl. Xl, X2,X3 -, amelyekbebeolvassuk lennielegal6bb3 mem6riarekesznek a rendeznikiv6nt szdmokat.Ki kell jelolntink mdsik h6rom rekeszt ("a papir m6sik r6sz6t"),ahov6 imm6r helyes - nagys5.g szerintcsokken6- sorrendben dtirjuk a sz6mokat.Elvileg irhatn6nk az Xl, X2, X3 rekeszbe,ez azonban bonyodalmatokozna.Legyenteh6ta rendezettsz6moknakkijelolt h6rom rekesz Yl, Y2,Y3. I{ogyan keressiik ki a h6rom sz6m koziil a legnagyobbat? A legkezenfekv6bbmodszera kovetkezo(a legnagyobbsz6motYl-ben t6roljuk rnajd!): a) Yl-be beirjukXl-et Yl-et X2-vel.Ha Yl<X2, akkorYl-be beirjukX2 b) osszehasonlitjuk tartalm6t. (Ha Yl>X2, akkor Yl-et nem valtaztatjuk) Y1-e1. X3-mal.Ha Yl<X3, akkorY1-bebeirjuk X3 c) osszehasonlftjuk tartairn{t. (F{aY1>X3, aiikor nern vl,ItoztatjukYi-et).
.,ftoo
Hogyan v6lasszukki a m6sodik legnagyobbszamot?Kozolnunk kellene a gdppel,hogy "a legnagyobbsz6mmalmfir ne foglalkozzon;az igy megmaradtak koziil keresseki a legnagyobbat!"Melyik is a legnagyobbszdm? Ebben a pillanatban nem tudjuk, csak azt, hogy mennyi! Ha azonbantudn6nk, tnelyik, "athuzhatn6nk". Azert kellene itthuznt,hogy tdbb6 ne jelenhessenIneg, mint "legnagyobb". Mivel sz6mainka feladat megfogalmazdsaszerint hatarozottan pozitivak, ezdrt a legnagyobb sz6m hely6re nu116tiwa 6s ezut6n a sz6mok kozott a legnagyobbatmegkeresvea m6sodik legnagyobbatkapjuk. Ez az6rt lennej6, mert igy ism6t az a), b), c) l6p6seketv6gezhetn6nkel, csak 6ppenY1 hely6beYz-t iwa. Melyik a legnagyobbszitm?"Az, amelyiknekaz 6rt6keY1. Ezt kell teh6t kinull6zni", feleljtik, 6s m6ris irjuk a l6p6seket: d.) e.) * f)
haYl : Xl, akkor Xl <- 0 ha Yl :X2, akkor X2 +- 0 ha Yl : X3, akkor X3 <- 0
(vagyisX 1-et toroljtik)
Ezzel algoritmusunkbanelkovetttik a letezo legkellemetlenebblogikai hib6t. Ha egy programsohanem mtikodikj6l, (vagyis az input adatokb6lnem a kiv6nt outputot 6llitja el6), az\<ellemetlen,de legal6bb azonnaldszrevessztika tesztelds(pr6bafuttat6s,logikai vizsg6lat)sor6n,6s tobb-kevesebbkinlod6ssal megtal6lhatjuk, kijavithatjuk a hibdt. A programoz6 rgazi "rdm6hna" az a program, arnelyik tobbnyire j6l mrikodik, ndha azonbannem; pl. a tesztelds majd az "6les" sor6nhfszszorjol lefut, ennekalap.jirnhib6tlannaknyilv6nftjr-rk, fut6sbanhib6seredmdnytad. Sajnosa fenti algoritmussalmegirt programunkis ilyen lenne,ugyanis
ha az input
akkor az output
5 , 1 8 ,1 3 1 4 2 ,I 1 ,5 3
1 8 ,1 3 , 5 ( i 6 ) , t 4 2 , 5 31, 1 ( i 6 ) ,
stb.
viszontha az input I4,2, Iil
akkol az output 1 4 , 2 ,0
tl9
(rossz!)
Teh6t ha tobb, egyenlo nagysfgu szdmvan az input adatokkozott, akkor ezeket egy kiv6televel "elnyeli". Mi6rt? Azert, mert amikor megtaltita a legnagyobbszdmot,a d*), .-), t') utasit6sokbanminden olyan t6rol6t kinull6zott, amelyekbenez a sz6m szerepel,holott a feladatmegfogalmazasanem zitria ki hogy ak6r az osszessz6megyformalegyen! annaka 1ehet6s6g6t, Gondoskodnunkkell teh6t arr6l, hogy a gepa d), e), 0 l6p6sekbenmindig "legnagyobb szhm" csak egy t6ro16t nullinzon ki (tulajdonk6ppen a " meghatarozasffi kell modositanunk: a legnagyobb szam az elso olyan, amelynek6rt6keYl"). Az algoritmusfolyathsateh6t:
d) haYl :Xl, e) ha Yl:X2,
akkor Xl <-0, 6sne hajtsdv6greselne)-t,semf)-et! akkor XZ +0, 6s ne hajtsdv6gref)-et!
0 ha Yl : X3, akkor X3 <-0 Most V6gre eljutottunk a mdsodik legnagyobb szdmmeghatfuozdsithoz. m6r szintemechanikusanirhatjuk:
s ) Y 2+ X l h) i) j) k) l)
ha ha ha ha ha
Y2 <X2, akkor Y2 < X3, akkor Y2: Xl, akkor Y2 : X2, akkor Y2: X3, akkor
Y2 Y2 Xl X2 X3
<-X2 +-X3 <- 0, + 0, e 0.
(ha nem,nincsteendonk) (ha nem,nincsteendonk) 6s ne hajtsdv6gresemk)-t, sem 1)-t 6s ne hajtsdv6gre l)-t
A rendezdsgyakorlatilagbefejezSdott,hiszena kdt szam mar a van Yl, Y2-ben,ds csakegyetlenX nem z6rus. Nyugodtanfrhatjuk teh6t vdgelj6r6skdnt:
"heiyen"
m) ha Xl <> 0, aldcor Y3 +--Xl n) ha X2 <> 0, akkor Y3 +- X2 o) ha X3 <> 0, akkor Y3 +- X3. l'l6zziilimeg pontosan,hogyanis alakulnaka rnegfelelSkovetesitirblaze'tokt
_r \/
megfelel6 j*) k*) 1*) El6szora helytelen d'*) e*) f") ... dsperszeaz enrrek esetdn. 16p6sek LegyenXl, X2,X3 rendre5, 18,13 .
1*)
X1
5
x2
.*{
X3
-v' ;-r ---5\
Y1 Y2 Y3
.d 18 l3
\
5
Az eredmdnyYl, Y2, Y3 - ra 18,13,5 (helyes).
2*)
LegyenXl, X2,X3 rendre142,I 1,53.
M
xf i-142 X ) i rr ^r .-
X3 Yi
I
I
L
I
I
i ft-l ,-/'"
,)7
j
i I
I I
@;
I
><
Y2
-{
I J
a)
I
I
b)
c)
d).I e)*
0 * l e ) h)
(\,.f. ) i ) 1r :-./l
|
||
I
|,
I
l l i i i r u
i ) | . i l - | t ) - I t ) * | n - r Ii n ) , o )
r\z eredmdnyYl, Y2, Y3 - ra 142,53,11 (helyes).
.l L
I
I
3 * ) LegyenXl, X2,X3 rendre14,2,14'
x 3I ' o l Y lI l v l h)luli)-
luilull.l " lenyelte " !
Yl, Y2,Y3 - ra 14,2,0 (rossz!)' Azeredmdny ds perszeaz ennekmegfelel6...j) k) l) l6pesekesetdna A helyes d) .) 0 kovetdsr tthllzat az al6bbiak szerint alakul. 1)
L e g y e nX l , X 2 , X 3 r e n d r e5 , 1 8 , 1 3.
Y1, Y2, Y3 - ra 18,13,5 (heiyes)' Az eredrndni,
52
2)
LegyenXl, X2,X3 rendre142,11,53.
x2lc)l
@;4 i '/ t - - l
l (u )i
AzeredmdnyY1, Y2, Y3 - ra 142,53,11 (helyes).
3)
LegyenXl, X2,X3 rendre14,2,L4. (KRTTIKUSESET)
X1
){1
x2
)
X3
X
Y1
-Y
>0-
(
I
@)
\ ( ()
Y2 Y3 a)
b)
c)
d)
e)
-(E \
-.--\
(Dl
tl 0le)
h)
i) l:l
l
l
II
lt \(: -i' '
k )I t l l - l l " i i o )
Az eredrndnyY1, Y2, Y3 - ra 14, 14,2 (l
53
l
lfti val6ban 6rti, hogyan mukod tl<ez az algoritmus,btzonylra eszreveszi, volna hogy az D 6s azl) sorban a felt6telvizsgfiat felesleges,nyugodtanirhattuk
igy is: X3 <- 0 . Vlidrt? Szovegesalgoritmusunknakaz emlitett felesleges dontdsek ndlkuli iik : v 6ltozat6tfoiyamatabr6ni s szemldltetj
xr,x2,x3 y1*-
Xl
Y1 < x 2 Yl---_
Yl <X3
Y1*- X3
Xl*-
'\ al. 4
l
Y2#
xl
Y l , Y 2, Y 3
(A rendezisif*iatlat 1.megoidasa) Iroll,ainatabra
-)_)
Fogalmazzuk meg els6 megold6sk6nt kapott algoritmusunkat pszeudokodbanis! Mielott azonbanert megtenn6nk,gondoljuk 6t, hogy a vonatkoz6 rrreg6llapod6sunk6rtelm6bennem hasznalhatjuka pszer-rdokodokra "ugr6" utasit6st.A strulitur6lts6gellen hat6 (a BASIC-b6I talin ismerSs)GOTO d), e), 0 6s az ezzelanal6g j), k), l) ldp6sekndlmertilhetnefol ez a kdrd6s;a probl6ma azonbanmegoldhat6 ugr6 utasit6shaszn|lata n6lkiil is, ha az egyes "nem" 6,ghtis kihaszn6lva,egymdsbailgyazottel6gazS'sokkal logikai dont6sek doleozunk.
igo bI6ma_eIs6_megoId6sa a1gori tmus_ar endezds 1 . B EX T , X 2 , X 3 2. Yl +- Xl AKKOR 3, HA YI <X2 3 . 1 .Y l < - X 2 HAVEGE AKKOR 4. HA Yl < X3 4 . 1Y . l e X3 HAVEGE AKKOR 5. HA Yl :Xl
s'1'Xl <- oruroNBEN YI:X2 AKKOR 5 . 2 . 1 .X 2 e 0 KI.ILONBEN 5.2.2. X3 +- 0 HAVEGE
5.2.HA
6. 7,
8.
FL{VEGE Y2 <- Xl AKKOR HA Y2<X2 7. 1 . Y 2 + - X 2 HAVEGE AKKOR HA Y2 < X3 8.1. Y2 +- X3 HAVEGE
9. FIA
Y2:XT
AKKOR
9'r' Xl <- orut-oNBEN 9.2.FIA
AKKOR Y2:X2 9.2.1. X2 +- 0.. KULONBEN 9.2.2. X3 <- 0 HAVEGE
FIAVE,GE AKKOR 10. I.IA Xi <> O 1 0 . 1Y . 3 +- Xl HAVEGE 11. I-iA X2 <> 0 AK1{Oir 1 1 . 1Y. 3 + X 2 HAVEGE 12. HA X3 + O AKKOR r2.t. Y3 <- X3 HAVEGE 13. KI Yl, Y2,Y3 (a rendez6si probl6rna1.megold6sa) algoritmus_vdge
2. megold6s Els6 megold6sunk - btr hib6tlan - egyiital6n nem "szrip". I{6rom szam kedveertviszonylaghosszriprogramot kellett fmunk: a tenylegesen rendezdse leirt (lerajzolt)dont6siutasit6sokszSma
1 )3 : 1 1 , ( 3 - 1+ 3 - 1 ) x ( 3 - +
3 szarnesetdn
(miert 6ppenennyi?) 4 szamesetdn
( 4 - I + 4 ^1 ) x ( 4 1 - )+ t l : 2 2 ,
5 sz6inesetdn
+ )5 : 3 7 ( 5 - 1+ 5 - 1 ) * ( 5 - 1 stb.
57
n szdrm esetdn
2*(n-1)*(n-1) + n
dontdsiutasit6stkelleneleirnunk.
A program hem " fitalilnosithat6" n szSm rendezds6nek eset6re (n . Az is bosszant6, hogy tulajdonkdppen maldnern pontosan tetszSleges) ugyanazokataz utasit6sokatism6telgetjtik,csak egyszerY1-gyel, egyszer Y2vel stb. Az igazi elvi probl6maaz, hogy annyi utasft6stkellett leirnttnk, ahSny sztiksdges. ldp6sa feladatmegolddsithoz Szinte kivdtel ndlktil mindig drvdnyes a kovetkez6 szabtiy: az olyan algoritmus, amelybenminden utasft6stlegfeljebb egyszerhajtunk vdgre, nem ! Azdrt nent, mert a programozhs tobb id6t igdnyel, mint val6 szarnitogdpre amennyialatt egy kozonsdgeskalkul6torral megoldjuk a feladatot. Minden magas szintii programnyelv kin6l olyan lehet6s6get,hogy a hasonl6jellegt'r vdltozokatirn. tornbokbe foglaljuk cissze,kozos n6vvel 6s egy indexszel hivatkozzunk r6juk, 6s ez az index maga is lehet vfitozo. A jeloldsmodis hasonlitamatematikAb6l ismertyt,yz,yt, ...,Ynjeloldshez. Amikor a matematikabanazyr*yr* y, * yq * yr * yu +y,
osszeget
7
\i X:L
yi - vel jeloljuk, mindegyik yi kiilon szdm,egym6shozsemmi koztik;
i= I
(rgaz,kozostulajdons6ggalrendelkeznek,t.i., hogy mindegyikiikosszeadando).
7
A
r
2- yi
ciklikus miiveletvcgzdstjelol ki, a kovetkezo osszegkepzes
i=I
algoritmussal:
1) 2) 3) 4) 5) 6)
legyenaz i index 6rt6keI legyenx 6rtdke0 legyenxdrtdkex*yi noveldmeg i erl6kdt1-gyel ha t(7 , tdrj visszaa 3. ldpdshez veige.
5B
P6ld6nkban az i index viitozo. A tombolc hasznillatinak 6s az indexek (is) az az elonye, hogy a v6ltozok6nt valo megad6s6naka szfumit6stechnik6ban program ciklikuss6 tehet6: a g6p tobbszor is v6grehaitja ugyanazol
1) 2) 3) 4) 5) 6)
legyenaz I index 6rt6ke 1 legS'enr drt6!;e0 legyenxert6kex*Yi noveldmeg i 6rt6k6tl-gyel ismdteldmeg a 3) 6s 4) utasit6sokatmindaddig, amig i nem nagyobb7-nel v6qe.
Egyrn6sik - az elozavelegyen6rt6kti- lehets6gesv5ltozat: 1)
legyenx ertdke0
2)
7-ig (egyes6vel)6s az i rninden6rtdkdn6l vedd az r ertekeit1-161 hajtsdvdgre a kovetkezoutasit6st: legyenxdrt6kex*Yi
3)
vege.
A szovegesen megadott algoritmusok kulonboz,o v|ltozatarhoz nyilvan kulonbozo pszeudokodosprogramokat,ill. folyamatfbrfkat adhatunk meg. A l6thato,hogy az els6 ketto ldnl,ss6benazonos osszehasonlitva harom va\toz.titot hogy nem szerepel torlorsdg,i (a m6sodik csup6n annyibol szerencsdsebb, ugro utasit6s),a harmadik valtozatazonbanlenl/egesen b*nne a neJrikivein;rtos tonior*bb.
5t)
Az elso 6s masodik vdltozatot kozos folyamatfhriival szenrieltethetjuk;a megfelelopszeudokodokatmindj 5rt az egyesfolyamatdbraszimbolumok melle irjuk: eliaras12 dsszeszo
fr6s_l_2 osszegz6_.1j 1. i <- 1 2.xe0 3. CIKLUS 3 . 1 .x < - x + Y ( i ) 3 . 2 .i < - i + 1 AMEDDIG i> 7 NEM TELJESUL elj6r6svdge.
i *-- i+l
6sszegz6eijaras12
(a sor6na gep ciklikusanismdtlia 3.1.6s 3.2. utasit6sokat A v6grehajt6s ciklusmagot),mindaddig, amig az indexvSltozo(ciklusv6ltozo) meg neln halad egy el6re meghatixozatt drt6ket (esetunkben a hetet). P6ld6nkban magunk kezeljik az indexv fitozot (mi noveljuk 6s - ebbena megold6sbana ciklus vegdn - mi vizsg6ljuk, el6rte-e a felsS hat6rt), erre azanban itt nincs felt6tlenul szriksdg. Minden magas szintti progranmyelv biztositja az un. szilmlftl6ssal ez felel meg a harmadikvaltozatnak: rnr.ikod6cikluskdpzdslehet6sdgdt,
osszegzoeijiras j
6rds_3 osszegz6_*1j 1 .x + - 0 2. CIKLUSi - l-tol 7-ig (eg1'esivel) 2 . 1 . x < x- + y ( i ) II CIKLUSVE,G I eljaras_vdge.
1 - t o l7 - i e ( e g y e s e v e i )
x<-x+y(i)
I I
rll
i\_
I osszcszoeiiaras :_. '
I ) _.:./
60
Amikor a g6p el6szor erkezika2. utasit6shoz("vfltortasd i 6rt6k6t 1-t6l 7-rg"), "ciklusv6g"-igtalitlhat6utasit6s(oka)t. be6llitja i 6rtdkdt1-re,majd v6grehajtjaa Most eggyel megnbveli i 6rt6k6t,mqid megvizsg6lja,nem haladtuk-e meg a "ciklusfej"-benmegadottfels6 hatftrt ("7-ig"). Ha nem, akkor visszat6ra 2.1. i - 2 - vel). Ha a utasitdsra6s ismdt vdgrehaitsaa ciklus magj6t (termdszetesen cikltrsvdgel6r6sekorazt 1rzdkeli,hogy i, a ciklusv6ltoz6 tovfibbinovel6seset6n meghaladndaz eloirt hatdrt akkor nem t6r vissza, hanem attera ciklusv6g ut6ni utasit6sra. T6rjiink vissza a rendez6si feladathoz! Tekintstik az Yl, Y2, Y3 egyrittes6t egyetlen tombnek, melynek elemeit a magas szintu nyelvek helyesir6siszabiiyainakmegfelel6enY( I ), Y (2), Y(3) j eloli. Ism6t hangsirlyozzuk: a nyeresdg dz, hogy a tomb elemeire Y(Z) form6ban is hivatkozhatunk;hogy ez melyik Y-t jelenti, azon mulik, hogy az trtasitds v6grehajt6s6nakpillanatitban mennyi Z ("aktu6lis") drt6ke. Ennek kihaszniiilsttval a h6rom szam rendezdsdreszolgiio szovegesalgoritmusunk most a kovetkezo(X1 ,X2, X3 bennvan a mem6riSban):
a) b) c) d) e)
0 s) h) i)
i)
Z+I Y(Z) +- Xl haY(Z) <X2, akkorY(Z) +X2 haY(Z) < X3, akkorY(Z) <- X3 haY(Z): Xl, akkor Xl <- 0, 6sne hajtsdvdgresem0-et, semg)-t haY(Z):X2, akkor X2 + 0, 6sne hajtsdvdgreg)-t X3<-0 Z 6rtdk6tnoveldmegeggyel ha Z<3,tdrjvisszab)-hez v6ge.
A pszeudok6dban irt programot rogton a folyarnatdbt'a tttain irjr-rk. A t6rgyalt osszegzoalgoritmttshoz illetSen - a seg6dp6ldak6nt ciklusszervez€,st hasonl6an- itt is lc6tvSltozatotkozlunk.
61
Y(Z) *-
Xl
Y(.2)
Y(Z)<x3
,|
Y(Z) = Xl
I Y(Z) = X2
,lr xl-0 'ri I
I x2<-
0
Y(i), Y(2),Y(3)
1--2 ) (A,rendezdsiproblima 2.nregoidirsa Foivainathhra
UL
I
si_probI6ma_I _2 algoritmus_rendezd 1 . B EX T , X Z , X 3 2. Z+-I 3. CIKLUS 3.1. Y(Z) <--X1 3.2, HA Y(Z) <X2 AKKOR 3 . 2 . r . Y ( Z )< * X 2
T{AVtsGtr Y(Z) < X3 AKKOR 3.3.1.Y(Z) <- X3 I-IAVE,GE 3.4. HA Y(Z) - Xl AKKOR 3 . 4 . 1 .X l + - 0 KULONBEN 3.4.2. HA Y(Z):X2 AKKOR 3 . 4 . 2 . 1X . 2 +- 0 KULONBEN 3.4.2.2.X3 <- 0 HAVEGE HAVEGE 3.5.Z+-Z+I AIV{EDDIGZ> 3 NE.MTE,LJESUL 4 . K r Y ( 1 ) , Y ( 2 )Y , (3) eli6r6s_vdge. 3.?
Il/,
63
a-sfil xr,x2,x3 Z= l- t6l 3-ig ( egyesevel )
Y(Z) *-- Xl Y(Z)
Y(Z) < X3
Y(Z)*- x3 i
Y(Z): Xl
X3.-
0
['ol1,i,'ilatabni (A rendezdsipr"obi6n ta 2.megold.{sa. _3)
Lr4
sijrob I6ma_3 algoritmus_rendez6 1 . B E X l , X 2 ,X 3 2. CIKLUSZ: 1-1613-ig (egyesdvel) 2.r. Y(Z) +- Xl 2.2. HA Y(Z) <X2 AKKOR 2.2.1.Y(Z) +- X2 HAVEGE 2.3 FIA Y(Z) < X3 AI{-KOR 2.3.r. Y(Z) <--X3 HAVEGE 2.4. HA Y(Z) - Xl AKKOR 2 . 4 . .1 X l + - 0 KULONBEN 2.4.2. HA Y(Z):X2 AKKOR 2 . 4 . 2 . 1 .X 2 + - A KULONBE,N 2.4.2.2.X3 <- 0 HAVEGE HAVEGE CIKLUSVEG 3. Kr Y(1),Y(2),Y(3) elj6r6s_v6ge.
Ez aprogramldnyegesenrovidebb,mint amit az l. megold6sbankaptunk. "ki akarjuk terjeszteni",vagyis h6romn5l tobb sz6mot akarunk rendezni, Ha minden ujabb szam (ndh6ny apro modosit6sonkivtil) csupdn 2 irjabb dontes leir6s,itig6nyli. mint az els6, de valami m6g mindig Megolddsunkjollehet egyszertibb, zavar6benne.Mi6rt ne lehetneXl, }i2, X3 is egy tomb h6rom eleme?Elvi akad6lynincs,de azdrt 6r'atosankell elj6rnunk.Nagy hiba lenne,ha egyszeriten rnindenXl, X2, X3 helydreX(Z)-t irn6nk.Z valoban1-t6l3-ig vdltozlk, nekunk azonbanZ minden 6rtdkdre ktilon-kulon meg kell vizsgdlni mind a h6rom X-et. Szuksdglennetehirtkdt ujabb ciklusrais (uj ciklusv6ltozoval), lehets6ges rnely'ekaz elso cikluson beliil mirkodnek,azazrogzitettZ-re Y(Z)-t rnindenX5k. szclosszehasonliti
65
x(1),x(2),x(3)
G
Y(Z)*- X(1) :
J : 2 - t o l 3 - i g ( e g y e s d v e) l
)
Y(Z)< X(r)
W -v
\!,/
J J = l-tol 3-ig
egyesevel)
y4 z):x(D
t
X(I) -d, J-
<
*
C 3
I
-
r t
lI I
l
r
l
I
\l/ Y
Z r Y(1),Y(2),Y(3)
Folyamatahrtt(A rendezdsiprobl6ma 2.megoldasa-4)
f- (r
A folyamat6braalapjfn a(pszeudo)kodol6sszintemechanikustev6kenyseg: si-prob 16ma-24 algoritmus-rendezd
L BEX(r),x(z),x(3)
l. CIKLIJS Z'- 1-t613-ig (egves6vel) 2.1. Y(z) +- X(1) 2.2. CIKLIJS I :Z-tol 3-ig (egyes6vel) 2.2.r. HA Y(Z) < X(J) AKKOR 2.2.rJ. Y(Z) <- X(J) HAVEGE CIKLUSVE,G 2.3. CIKLIJS J: 1-t613-ig (egyes6vel) 2.3.r. IIA Y(Z): X(J) AKKOR
2.3.r.r.x(J)<- o 2 . 3 . 1 . 2 .J + - 3 HAVEGE CIKLUSVEG CIKLUSVE.G 3 . K I Y ( 1 ) , Y ( 2 ) ,Y ( 3 ) algoritmus_v6ge. A program egym6sbailgyazottciklusokat tartalmaz.AV "gyes ciklusokat a megfeletbm6lys6gu - parbi6llitott (CIKLUS CIKLIJSVEG) bekezddsek j6l oivashatova,6ttckinthet6vdteszik. Szigorir szabillyminden magas szintu nyelvben,hogy k6t ciklus vagy teljesendiszjunkt legyen,vagy az egyik teljes eg6sz6benlegyen benne a m6sikban(pr6b6ljuk rnegindokolni,mi6rt kell iey lenniel). A 2.2. ciklus teljesendiszjunkt a 2.3. ciklust6l,vagyis nincs kozos utasit6suk,viszont mindkett6 val6di rdsze a 2. ciklusnak, vagyis minden utasit6suk a 2. cikluson beltil van (6s a 2. ciklusnakvan mdg egydb utasft6sa is). A cliszjunktciklusoknak lehet azonos ciklusv6ltozojuk(J), arra azonban iigyelni.inkkell, hogy az egymasbailgyazottciklusok ciklusviitozoja ne legyen azonos(Z es J). (Mi6rt?) "nem sz6p":a pl'ogramozdsi tankonyveknem javallj6k, AZ.3.I.Z.utasit6s sot, olykor kifejezettentiltj6k. Okkal: nehezenfelcierithetohib6k forr6sa lehet, erteket (r'ae)'islt ha egy cikluson beltil mi magunk modositjuk a ciklus.,'altozo bal oldaizin esettinkbena J +- 3 ciklusv altozo egy 6rt6kado utasit6s tnert a 2.3.1. logikai ciorttes szcrepel). A ciklusvhltozatazdrt modositottLrh, y(Z) -- X(J) feiteteletobbszor is teljestilkrri, az X(J) +-0 ertdkaci6r-rtasititst
Li1
elso azonbancsak egyszerszabad v6grehajtani. Ha teh6t az x(J) e 0 v6grehajt6sakorJ drteket3-ra 511iduk,a ciklusmag esetlegesujboli v6grehajt6sa "azt hiszi", hogy a ciklust m6r el6tt aktu6lis feltdtelvizsgfiat sor6n a gep ha h6romszor vdgrehajtbtta6s ezdrt kil6p a ciklusbol. Jobb lenne azonban, valamilyen m6s m6clon adn6nk a gep tudt6ra, hogy az x(J) <- 0 utasit6st a egyszer m6r vdgrehajtotta.Egy ujabb vfitoz6t, pl. M-et hasznalhatjukerre celra. M-1ek aztkelljeleznie, hogy adott Z mellett az X(J) <- 0 nullftzitst a gdp m6r a 2.3.1.-beli Y(Z) : egyszerm6r v6grehajtotta.(Ilyenkor term6szetesen Xfll felt6telvizsg6latis felesleges,teh6t 6tugorhatjuk.) M szerep6ttekintve speci6lisv61toro, rin. flag (zdszlo) azt mutatja, hogy valami megtortdnt-em6t, vagy sem. Termdszetesviilasfi6s, hogy legyen M drtdke 0, ha adott Z mellett az yA) - X(J) felt6tel m6g egyszersem teljesiilt, 6s M 6rtdke 1, ha a felt6tel egyszermdr teljestilt.Programunkteh6tigy m6dosul:
algoritmus-rendezdsiirob I6ma-25 1. BE X(1), X(2), X(3) 2. CIKLUS Z- 1-t613-ig (egyes6vel)
2.t. Y(z) +- X(l) 2.2. CIKLUS J :Z-tol 3-ig (egyes6vel) 2.2.r. HA Y(Z) < X(J) AKKOR 2.2.1J. Y(Z) +- X(J) I_IAVEGE CIKLUSVE.G 2.3. M <- 0 2.4. CIKLUS J : 1-t613-ig (egyes6vel) 2 . 4 . 1 .H A M : 0 A K K O R
2.4.r.r.HA Y(z)- x(J) AKKOR 2 . 4 . 1 . 1 . 1X. ( J )< - 0 2 . . 4 . 1. .21. M + - 1 HAVEGE,
HA\iEGE CIKLI.]SVEG CIKLIJSVEG 3. Iil Y(1),Y(2),Y(3) algoritinus_vege.
68
Z: l-t6l 3-ig ( egyesdvei ) Y(Z) *-* X(l) J: 2-tol3-ig ( egyesdvei ) Y(Z) < X(J). Y(Z) -- X(J)
J: l-t6l 3-ig ( egyesevel)
Y(Z) = X(J)
Y(l), Y(2),Y(3)
(A r*ndezesipi*b16rna 2. il.regolr;16sa'-5) Folyar,ratirbla
69
az X(J) €- 0 A 2.3. miatt M minden irjabb Z-nel kinull6zod\k, tehtfi vegyiik 6szre,hogy utasit6sta g6p minden z-re pontosan egyszerhajtja vegre. konnyen alkalmass6tehet6 N szam programunt m6r szinte teljesen 61ta16nos: felt6ve,hogy nem halad meg ahol N fut6sr6rfut6srav61tazhat rerrdez6sere, egy elore megadottfels6 haffffi. Mindos szearravan sztiks6g,hogy a programban a) b) c) d)
szdmot elsb l6p6sk6ntkdrd ezzukffieg,hogy az adattfi:t6sbanh6ny kell rendezni jeloljunk kt azN megengedettlegnagyobbdrt6k6nekmegfelelo t6rtertiletet azX( ) 6s Y( ) tornboknek olvassunkbe N szSmot az X( ) tombbe hogy a programtov6bbi r6sze villtozatlan,csak arrakell iigyelnunk, N. a ciklusokbana ciklusv6ltozok fels6 hatira 3 helyett az aktu6lis
100 K6szitsiik el a feladat 2. megoldSs6tjelento algoritmust(legfeljebb szamrendez6s6re)mindh6rom algoritmus-leir6 eszkozzell
70
x(100),Y(100) +:
100) ( ma,x.
xoBE Z: l-tolN-ig ( egyesdvel)
Y(Z)*--- X(1) J = 2-t6lN-ig ( egyesevel)
Y(z) < x(J) Y(Z) <- X (D
J = l-tdl N-ig ( egyesdvel)
Y (Z): X( J)
t r1ezeisi p rob I drna 2. lr1f::go i ci;:sa) F'o Iyam atalrra U,, r',-':
t1
ill. -kiirat6si rutinola a vonatk ozo folyam atabrardszletek: Az adatbeviteli,,
I xoBE, Firv-ie(esyesdvei)
/x0/ (
I
xoBE, YOIt: I:1-t6lN-ig
't'i
_
X ( 100), Y ( 100) Tornbfoglalis BE N (max.100) I : I - t 6 1N - i g ( e g y e s 6 v e i )
B Ex ( I ) Z: I - tol N -ig (egyesevel)
Y(Z)*-- X(l) J :2 - t6l N-ig (egYes6vel) H aY ( Z ) < X ( J ) IGEN
X (.I)
Y (Z)* M * 0
J : 1 - tol N-ig (egYes€vel) HaM:0 IGEN
H a Y( Z ) : X ( I ) . IGEN
NEM
X(I) *
0
i : 1 - tol N-ig (egyesevei)
KrY(I)
pi'obidnra2.megold6sa) (;\ rentlez:esi Stn.rlttogram
t <
a1goritmu s-a-re ndez6si j rob I6ma-m 6sodi k-m egoId6sa
ToMBFOGLALAS X(100),Y(loo) KI 'FI6nyszamoikiv6n rendezni?(max. 100)' BE, N CIKLIJS I : 1-t6li'{-ig (egyes6vel) 3.1. BE, X(I) CIKLUSVEG 4. CIKLUS Z- 1-t61N-ig (egyes6vel) 4 . L Y ( Z )e . X ( 1 ) 4.2. CIKLUS J :Z-tol N-ig (egyes6vel) 4.2.r. HA Y(Z) < X(J) AKKOR
0. 1. 2. 3.
4.2.r.r.Y(z)<-x(J) HAVEGE CIKI-USVEG 4.3. M <- 0 4.4. CIKLUS J: 1-t6lN-ig (egyesdvel) 4.4.1. HA M: O AKKOR 4.4.r.r. FIA Y(Z) - X(J) AKKOR4 . 4 . .11 . 1 . X ( J )< - 0 4 . 4 . 1 . 1 . 2M. + - 1 HAVE,GE HAVEGE, CIKLUSVEG CIKLUSVEG 5. CIKLUS I : 1-t6lN-ig (egyes6vel) Y(I) s.1. CIKLUSVEG algoritmus_vege. ellen6re- az N (Mi tortenik,ha a programhasznfioja - a figyelmeztet6s nagyobbszamotad meg?Hogyanegdszithetnenkki a valtozordsz6re100-n61 sor?) hogyetrene keriilhessen programot, hosszir,tnint a 3 ugyanolyan N sz6rnctrendezoprogramunklenyeg6ben dsa cikluskepzesneii ! Ezt a tombokhaszn6lat6nak 1. rnegoldds renclezo s,rarnot "igazi program" szdmftogdpes , & gdpjoval tobb utasftast Ez mhr koszonhetjiik. ismetelsokszor,r'aitozci l-tqtvdgre,mint alr6nyatleirtunk:azonosinijveleteket zidatolikal.Vap azollran egy
- g,r,al
74
ltiitt'anl'a:
ls' igen nagy t1rteruletetig6nyel. Minden sz6mszerepelaz X 6s azY tombben N sz6meset6nlegal6bb2*N rekeszrevan sziiks6gtink.Ha sok sz6motkiv6nunk rendezni, konnyen el6fordulhat, hogy nem f6riink el a metn6ri6ban.Nyilv6n a c6lszeru, hogy valamennyi rcndezend6 szhm egyszerre, bent legyen mem6riaban - NI rekeszreteh6t biztosan sziiks6gunkvan. Vajon nem lehetne egy-k6ttov6bbi rekesszel megoldania feladatot?
3. megold6s
Megmutatjuk,hogy N sz6motrendeznitudunk osszesenN+l rekeszben - s6t,u;, ;kdnyszersziilte" m6dszertinktov6bbi elonyokhelis j6r. Mindenesetre m6s algoritmusra van sziiks6gunk, mint gyokeresenm6s gondolatokra amivel eddig dolgoztunk.Eddigi algoritmusainkl6nyegeaz volt, hogy mindig egy adott hilmazban a legnagyobbsz6motkeresttik,vagyis pontosanutinoztuk ai- emberigondolko d f,r;t.Ez a g6pi megvalosit6sban bonyodalnrakatoko zott. Ha N szdm nagys6g szerint csokken6 sorrendben rendezve van, akkor X; sz6mok m5ris Xj+r-gyel, x1 ( Xj+r 6s egyszeriien felcserdljtik xj -t --a * * "iciss6' rendezett;bbek" , hiszen most mhr xj ) X;+r . Hasonlitsuk ossze 6s ha X;+t< Xi+z, akkor csereljtik fel X;+z-vel, X,+r-€t most X1+t-et
Xi+z-vel .
Prob61k ozntnk teh6t a kovetkezo algoritmussal :
a)
az,i valtozl drtdkelegYen1
b)
ha Xi ( Xi+r, akkor felcser6ljtik xi -t x i+t-gyel
c)
1-gyel noveljiik i 6rt61':dt
ci)
b)-re. lia i < l'{. akkoi'rrisszaterunk
'75
hogy k6t t6rol6 tartalmffi mindig egy harmadik t6rolo M6r tiszt6zi.cu?<, ez az kozbeiktat6s6valcserdlhetjiikfel ("2 az a bizonyos +1 t6rolo). Legyen 6tmeneti t6rol6 K. M6ris felrajzolhatjuk ? szoveges algoritrnus-vazlatot r6szletezo folyamat6br6t,ill. a megfelel6pszeudokodosprogramrdszletet:
I: I -t6i(N- I )-ig(egyesevel)
(I) < X(I+l (<-
x (I)
x (I+1F-
't5
K
1. CIKLUS I: 1-t6lN-l -ig (.gyes6vel) 1.1. HA X(I)<X(I+l) AKKOR 1 . 1 . 1 .K + - X ( I ) 1.1.2. X(I) +- X(I+1) 1 . 1 . 3 .X ( I + 1 )< - K HAVEGE CII
"rendez6sel6tti" sorrend
7,11,4,28,2
2 , 7, l l , 4 , 2 8
A kovetdsitilblaalakul6sa: 5
N
x1) \oi
w)
x(3) x(4) x(5)
@
\\ \{
\
@ \?
\
@l
n
@
i
\
\
\
K
\
\
\
\ t s
\l
Egyetlen dologban lehetiink csak biztosak: ha nem a legnagt'obb szhm (A ilasorliii 6ilt tegelot,akkor u l.gnugyobb sz6m egy hellyel elobbrekeriilt. eurtck legnagyobb szamraez mai nem feit6tlenul rgaz! Konstrur6ljunkllelclat az az egys:zcrugondolrit biionyit6sara!) Tov6bbi teencioinkmeghatarozasaban "arrclllepzelhetolegrosszabb esetilen" is helVcs s.git, hogy piogrurntrnknak
77
eredm6nytkell adnia. Mi az elkdpzelhet6legrosszabb eset? Az, hogy a legnagyobb szdma program indulSsakora legutols6helyen 6Il, vagyis N- 1 ne1ty.1kelleneel6bbre16pnie.Miv eI az 1. ciklus teljesvdgrehajt6sasoran a a teljes ciklustN- I -szermeg legnagyobbszhm egy hellyel tud e16re16pni, kell ismetelnunk. A l. ciklust teh6t bele6gyazntk egy mSsikciklusba,amit szintdnN- i szerhajtunkvdgre.LegyenennekciklusviitozojaZ:
Z:I
-t6l(N- I )-ig(egyesevel)
A m egfelel6pszeudok6dosv 6ltozat:
4. CIKLUS Z - 1-t61N- 1 -ig (egyes6vel) 4.1. CIKLUS I: 1-t6lN-l -ig (*gyesevel) 4.r.r. HA X(I) < X(I+l) AKKOR 4 . 1 . 1 . 1K. + - X ( I ) 4.L1.2. X(I) <--X(I+l) 4 . r . 1 . 3 .X ( I + i ) < - K HAVEGE CIKLI.JSVE.G CII{I,LJSVEG
t1 (t
t6
A Z ciklusv titozo 6rt6k6t a cikluson belul sehol nem hasznaljuk, egyszertiencsak arra szolg6l,hogy a gdp N-1 -szermegismdteljea teljes 4.1. A 4. ciklust a szo ciklr-rst.F,z a m6dsz'erigen gyakori a szamit6,stechnih6ban. "sz6ml6l6ssal val6sftjameg. mtikodociklusutasit6s" szoros6rtelm6benegy Most m6r biztosak lehetiink abban, hogy a legnagyobb szam az els6 helyen 6ll. Enn6l azonbantobb is igaz. Gyakorlatk6ppenbizonyitsukbe, hogy a 4. (ktilso) ciklusb6l kil6pve a teljes X( ) tomb - csokkenoleg- reudezvevan! (Pontosan milyen 6llit6s igaz a m6sodik legnagyobb sz6mra, a harmadik legnagyobbszdmra,stb., illetve a legkisebb szttmra?) Harmadikmegold6skdntsziiletett(szintdnlegfeljebb100 sz6mot)rendezo algoritmusunkat adjuk meg folyarnatibrilban,struktogramban6s pszeudok6dolt programform6jabanis!
79
x( roo) ( ma.x.i 0 0)
I : I - tolN-ig (egyesevei)
Z= l - t6l (N-i)-ig (egYese"'ei)
(egYesevel) I : I - t61CN-1)-ig
(I) < X(I+l
x(l).* x(I+l)l x (l+i F-
I : I - tol N-ig (egyesevel)
C$u-) ) (A renriez6sillrobl qimrr3'.i-ri*si;Ielirsa Fo11'atnai6bia.
8C
X ( 100) Tombfoglai6s BE N (max.100) I : 1 - t6i N-ig (egyesdvel)
B Ex ( r ) I - tol ( N-l ) -ig (egyesevel) I : 1 - tol ( N-l ) -ig (egyesevel)
HaX(I)<X(I+1) IGEN
t( <-x
NEM
( I)
X(I)-X(I+1) X(I+1)<--K 1 - tol N-ig (egyesevei)
K rx ( r )
(A rendez6siproblema3.megoldisa) ,-Strr.tktogram
()1 Crl
algor itmu s_a_rendezdsi jro bI 6ma-h armadi k-m egoId6sa
X(loo),Y(loo) o. ToMBFOGLALAS
1. KI 'H6nysz6motkiv5nrendezni?(max.100)' 2 . B E N 3. CIKLUS I : 1-t51N-ig (egyes6vel) 3.1. BE. X(I) CIKLUSVE,G 4. CIKLUS Z - 1-t6lN-l -ig (.gyes6vel) 4.1. CIKLUS I : 1-t61hl-l -ie (egyesdvel) 4 . 1 . 1 .H A X ( I ) < X ( I + l ) A K K O R 4 . r . 1 . 1 .K < - X ( I ) 4.r.r.2. X(I)+- X(I+l) 4 . 1 . 1 . 3X . ( I + 1 )+ - K HAVEGE, CIKLUSVEG CIKLUSVEG 5. CIKLUS I: 1-t6lN-ig (egYes6vel) 5.1. BE. X(I) CIKLUSVEG algoritmus_vdge.
A programkevesebbutasit6sbol6ll, mint a 2. megold6s,6s 2*N rekesz helyett csup6nN+l rekeszt haszn6l a rendezdshez(a, elemek felcserdldset mindig ugyanazona K rekeszenkeresztiil vegzt). Rdad6sulgyorsabb is. A rendez6shezsziiks6gesid6t jellemezhetjtik az elv6gzettosszehasonlit6sok szamaval("HA X(I) < X(I+l)").A harmadikmegold6sbana teljesrendezdshez (N-1)*(N-i) = l'.I*N esetbenmig a m6sodikban - a legrosszabb sziiks6ges, osszehasonlit6s N*(1.{-| + 2*N) - 5*.(3*}rJ-1) * 3*NxN
osszehasonlit6s,
a legobb eseiben pedig * 312*NxN osszehasonlitds. is befoli'ii"olja.) cserdlcsz"ama a r,,dgrehajtott (A fut6si idijt term6szetesen,
(.)/) dL
A m6sodikmegold6ssalirt programfut6si ideje teh6t legrosszabbesetben a harmadikprogramdnak,6s a legiobbesetbensem gyorsabb. kb. haromszorosa Mdg enn6l is nagyobb elSny azonban,hogy lszrevdtleniil tull6pttink a feladat kovetelmdnyein.A harmadik megold6s mar nem hasznalja ki azt a felt6telt, hogy a sz6mok mind hatfxazottan pozitivak. Az elso 6s rn6sodik megold6sn6lsztiks6gi.inkvolt erre, hogy a szimok kinulllzf,shval jelezhesstik: ,,ezzelmtrnem kell tdbbd foglalkoznunk".A harmadikalgoritmus - mivel nem a legrragyobbszdmotkeresi,mindig csak k6t szomsz6dossz6mrol6llapitja meg, tetszSlegessz6mok rendez6s6reis alkalmas: az inputon melyik nagyobb megie1enhetnekanegativsz6mok6sa0is.V6gtil:haa4.1.1.dont6sbena< j.i helyett csokken6helvettnovekv6 sorrendberendezi az X( ) tomb elemeit.
4.,
stb. megoldds
javftottuk. Vujon eijtrtottunk Rendez6sialgoritmusunkatldp6sr5i-l6p6sre a legjobb algoritrnushoz?Letezik-e egyfital6n ilyen? llarmadik algoritmusunk bizonyos 6rtelemben val6ban optim6lis. Nehezen k6pzelhet6 €1, hogy N szamot N+l -n6l kevesebb t6rolorekesz hasznftlat6valrcndezzunk. Mem6rialekotds szempontj6boi tehdt feltehet6en "sz6mitogdpszeru":a eidrttik az optimumot. A program rovid, tomor, cikluskdpzdsek miatt sok gepi utasit6s v6grehajt6s6t induk6lja, a 0. stb. szdm ("helyfoglalo") utasit6smegv6ltofiat'ils6val2A0, 1000, 10000, "t6githat6", amfg az adatokegyaltaldrl is alkalmas - mindaddig reirdezds6re 6116rnemrSrriha.Jrlem val6szinu, hogy ldnl'egesen befernek a renclelkezdsre lievesebbprogramsorleir6sirvalis nleg tudn6nk oldani a fuiaclatot,r'ag)'is a rs az optimumkoriil jdrunk. prograrntomorsdgeszernpontjdboi
ti:j
Mi a helyzet a fut6si id5vel? Mennyi id6 alatt vegzr el adott lnennyisegu L6ttuk, hogy 100 szdm eset6nkb. 10 000 osszehasonlit6st szam rendezds6t? 2C0 szi:n e:et,,5n4A OCCc:szeh*scnlitfst stb.i a fut6si id6 az adatok r,,i:gcz-, "fdlosiegesen" szamanakn6gyzet6veln6. R6ad6sula legtobb osszehasonlit6st vegzr el. E*, tekintve, fut6si ideje ugyanannyi, ha (v6letleniil) az input eleve "a lehet6 legrendezetlenebb".A fut6si teljesen rendezett,mint amikor az input teh6tbiztosannem optim6lis. ido szempontjAb6l Leteznek m6s rendezdsi algoritmusok is. Kedvelt megold6s pl. a kovetkezo: a rendezni kiv fxt" szttmokategyetiennagy X( ) tomb helyett kisebb - A( ), B( ), C( ), ... - tombokbeolvassukbe, pl. az els6 het szfimotaz A( )-ba, a koveikezohetetB( )-b., stb. Az A( ), B( ), C( ), ... stb. tomboket onmagukban "osszevfiogatjuk" egy Y( rendezzrik,majd a tombdk elemeit nagys6g szeint ) tombbe. Ha az A( ), B( ), C( ), ... - inrm6r rendezett tombok valamelyik6nek elso eleme6tkertilt Y( )-bu, akkor ezt az elemettoroljtik a megfelel6 tombb6l, 6s "el6regorgetji.ik".igy a rendez6s a tomb osszestdbbi eierrdt egy-egy hellyel b6rmely fdzishban"a kovetkezo legnagyobbsz6m" csak valamelyik A( ), B( ), tomb els6 eleme lehet. Ez a m6dszer fitalihan gyorsabb,mint a mi C( ), harmadik megold6sunk (fut6si ideje teh6t rovidebb), viszont hosszabb programot6s nagyobbmem6riateniletetig6nyel.Es ez tetmdszetes.Szeretndnk hangsulyozni, hogy a szftmitftstechnik6banrendszerint nincs minden szempontboloptim6lismegold6s!
4.3.Az indukt{v 6s deduht{v rnegkiizelft6siisszehasonlit6elemz6.:se a'programozilsi t6telek' tanftfsfban
programozdsi tdtelek alapveto algoritmustipusok 6ltalanos A jelentik.Jolleheta't6te1'elnevezds az 6llit6skimondasat,majd megfogalnazds6t az ezt koveto preciz bizonyit6st ebben a son'endbenmegjelenito deduktiv megkozelit6stsejtet,a kozdpfokrioktat6sbana tanulok eletkori saj6toss6gaibol kdpessdgmiatt az induktiv tirgyal6smodclt kovetkezoszerdnyebbabsztrakcios celszeriiel6iiybeirriszesitenrink.A fels6oktat6sban6rthetSm6don tobbnyire tal6lkozunk,noha a programozasitdtelek trizonl,'itiisat decluktfvtdrgl,alasrnoddal mdg ott is g1'alaan rnell6zik.
B4
Hasoniitsuk ossze p61d5ul a legegyszerubb programoz6si t6tel, az osszegz6st6tel6nekdeduktiv 6s induktiv tdrgyal6sm6diatl A dedul.;tiv iiregliize',i'teseg)' v|\tozathl - a progl'rfcoz6s: t6teleket "Sz6mitastechnika bevezet6 magyarilzat megfelel6 r6szlet6vel egyi.itt - a kozepfokon"' c. konyvb6l iddzzil<. "... Az egyestipusalgoritmttsokn6l mindig megadjuk - az fitalfinos feladatot, - a:zazt rnegold6algoritmust, - egy konkr6t feladatot, - a feladatbanszerepl6adatokmegfeleltetdsetaz S\talfinr:sfeledat adataival, - a feladatotmegold6 algoritmust.
T.1., Aq.esszeg?p.q.!e!pLq Al.telanq.q.&!a.dpL: Sz6molj,tkk\ az elemekosszeget!A sorozatot Adott egy N elemi szamsorozat. most 6s a tov6bbiakbanis azN elemti A(N) vektorbant6roljuk.
Mp.gj egvqe.qi A kes6bbifeladatoksorSnel6fordulhat,hogy a vizsg6ltsorozat szovegestipusu valtozokattart almaz,de ezeketa konkrdt programnyelvt6lval6 ftrgg6sukmiatt kiilon nemjeloljtik.
Aleqrit$u$; Elj5r5s: S::0 CiklusI- 1-tolN-ig S::S+A(I) Ciklusv6ge Eljdr6sv6ge. ' Szarnftastecltnika lrozdpfolron(Dr. Hetdnyi P6lne szerli.), Oh4lli'}i,Buiiapest,1987.,61-62.pp.
,35
87...1,.f-bladat. N napon keresztul, napontaegy alkalommalmegm6rttika h6m6rsekletet.Adjuk meg az N napos id6szakf*Iaghomdrsdkletet!
; ltple.q .lvleef.e.l.e A(N)
sorozat
Aleqritry]u$; i*lagsz6mit6s(I{, A( ), ATLAG):
S::0 CiklusI-1-t6l N-ig S::S+A(I) Ciklusv6ge ATLAG::SA{ Elj6r6svdge.
Megj egyzes:az osszegzdstdteldt alkalmazzukakkor is, ha a f'eladat A(1)* X(Z)x... {
Az aldbbiakban az osszegz6s t6tel6nek egy lehetsdges induktiv mutatjukbe. megkozelites6t
.1,.t.elada!, Egy osztfiybanN tanul6 irt fizika dolgozatot. Dolgozatjavitasut6n az eredmdnyekismeretebensz6mitsuk ki az osztal\'6tlagot! Apry.bldmaeletnzdsg: i.Jciirosztalyzatatlagatkell kiszamolni.
ti i;
n db szam(x,, xr, ... , xn) szdmtanikozepe:
) x , Xr*Xz*...*x,
t't
_
l=l
t't
Az alqoritrBusszerkeszt6se: Az osszegzorekesztartalm6'tkiindul6sk6ntnull6ra 6llitjuk (az osszegeta z6rus nem v titoztatja). osszeadando Az osszegzoutasit6s: SI"IM <- SLM + X i,gy mrikodik, hogy az osszegaddigi drtdkehez hozzhadjaa soron kov etkezoosszeadand6t,majd ezt az ui osszeget t6rolia, a kor6bbit feliilirva. Ezt az utasit6st nyilv6n N-szer kell majd vegrehajtani,amig a teljes osszeg kialakul. Ezt teh6t szfimlitl6ssalvez6relt ciklusba szervezztik, csakirgy mint az N db osszeadand6 (oszt6lyzat) szolg6lo BE X utasit6st. adatbevitel6re A ciklusbol valo ki16p6sut6n a kialakult vdgs6 osszegetaz osszeadandok darabszlmaval osztvakapjuk a keresett tftlagot.
Az algorilmusbanhaszn6ltj eloldsek Az adatok6s a keresettmennyisdgvonatkozitsitban Il, Xi, i
=)
N, X, XA
hasznaltun. osszegzorekesz tort6noosszegyiijtdsire Az osszegl6pdsrol-16p6sre neve SIJM . hasznaltr,6itoz6nel'e I . A szdrnl6lasra
9"1
v6ltozata: pszeudok6dolt Az alsoritrnus algoritmus_osztiiy 6tlag 1. KI 'H6nyosrttiyzat ifilagi$ sz6moljuk?(N:?)' 2. BE. N 3. SUM +- 0 4. CIKLUS I : 1-t6l N-ig (egyes6vel) 4.1.BE X 4.2. SUM e SUM + X CXKN,USVtrG 5. XA +- SUMAI 6. KI 'Azosfiiily-{nlag:XA:', XA algoritmus_v6ge
Az algoritmusellen6rzdseirn. kovetdsitSbl6zattal: Prob6ljukki algoritmusunkat3 osztillyzat(4,5,3) i$Iag6nakkisz6mit6s6ra!
N s I
x
L
n 1
4
3 4
0 2
5
4
9 3
1
2 4
3
XA Az algoritmushelyesenmrikodik, hiszen
t+l+3
-4,
a vart eredmdnyt
J
kaptuk.
A kovet6si tfhl|zatot tanulmanyazvaldrthato,hogy a programfut6s vdgdn az egyes v|ltozoknak csak az utols6 6rt6ke 6rhet6 €1, az N, SLII\4, I, X,, XA kozul tehatcsak valtozoktartalmamostrendre 3,12,4,3,4. Az osszeadand6k " az utolsokdntmegadott hdrmas osztflyzatraemldkszik". Ez az ara annak, hogy nregold6sunkbanindex ndlktili valtoz6val dolgoztunk, az osszes osztalyzatot ugyanabbaavaltozobaolvastuk be es felhasznitl|sut6n rendrefelulirtttk azokat feladatunkat hibdrtlanul, sot igy a. soron kovetkezovel. Kitizctt oldottr-rkffieg, hiszen a ciklusbol valo kiidpes ttt6n nent memoriatakardkosan h4irs a helvzet a kdvetkez.o voit rn5,rszilksdgunkaz egyes osztailyzetrsls'a. fe,laclatnal.
$ ?() (]
?.! p\qda!; Egy 35 f6s oszttilybanN tanul6 irt fiztka dolgozatot. Dolgoz atjavititsut6n az,eredmdnyekismeretdbensz6mitsukki az oszt6ly6tlagot! Hat6'rozzukmega sz6rastis!
J. Mesoldds
Fr-€€i;-
A probldmaelemz6se: kell kiszfmolni. N db oszt6lvzatatlae6t6s sz6rSsftt
Matematikaimodell: n db sz6m(xt, xr, ... , Xn) szamtanikozepe:
S Z O T AS A:
y -
xr * x, *. ..*x n
n
:
Z*, j= I
--:--------2--
t1
It t - -r2 - r? // - \2 /(r, t)" + (t, I)- +...(x, rf n-I V
- l
Az algoritmusszerkeszt6se: megfontol6sai term6szetesenitt is Az elozo pelda algoritmus-szerkesztdsi 'fel.^intettel szti!<sdges 6tlagtoi valo arra azonban,hogy a szor6shoz: 6r'vinyesel.:. eltdrdsekrniatt (az tttlagkiszdrnit6sautSn!)ujra szriksdgtinklesz az adatokra(az "\,elitort") ezfittalinciexesvdltozat (egym6retritornbot egyesclsztiil,vzatol:ra), haszn6lunk. I-Iurvisz.ont rnirr irgy is tonibot haszn6lunJ<,kr-rionftsirl"el az..
B9
algoritmus adatbeviteli ds adatfeldolgozitsiblokkjait. (Most l6thatjuk, hogy et az 1. feladat uremoriabiztositottjobb 6ttekinthet6s6g ezzel a szdtvfilasrtSssal nem lehetettmegval6sitani.) takardkosmegold6s6ban
Az algoritmusbanhaszn6ltielol6seb Az adatok6s a keresettmennyisdgvonatkozilsttban o, Xi, x, s
=
N, X( ), XA, XS
Az egyes osszegek l6p6srol-ldp6sretort6n6 osszegytijt6sdrehaszn6lt rin. osszegzorekeszekneve az osrtfiyzatok esetdben esetdben az ifilagtolval6 elt6rds-ndgyzetek
SUM , SQLh4 .
hasznllt (6s itt egybenindex)vdltozoneve A sz6m1616sra
Az algoritmuspszeudok6doltv6ltozata: z616s aIgor i tmu s_osztiiy i$"lag_s
o. ToMBFOGLALASX(3s)
1. KI 'H6ny osztiiyzatittlagittsz6moljuk?(l'{:?)' 2 . B E N 3. CIKLUS I : 1-t61N-ig (egyesdvel) 3.1. BE, X(I) CIKLUSVEG 4. SUM +- 0 5. CIKLUS I : 1-t6l N-ig (egyes6vel) 5.1. SUM +- SUM + X(I) CIKLUSVEG 6. XA <- SUMN 7. SQUM <- 0 8. CIKLUS [ : l-tcil F{-ig (egyesdvel) 8.1. SQUM <- $Q{Jh{+ (XO-XA)f 2 CNi{LUS1,/EG g. xs e I'JEGYZF,TGY0I<(SQ{JM/[N1))
90
I.
10. KI 'Az osztfiy-ffilag: XA: ', 11. KI 'A sz6r6s:XS: XS algoritmus_v6ge
', XA
2rusME A 2.Feladat megoldhatoindex n6lkiili villtozokkal (tomb hasznalatan61kii1)is. Hogyan? Egyszersmindcsokkenthet6-ea ciklusok szftma? (Utbaig aziths:a matematikai modell frtalakit6sa) Ha el6szor megoldunk iegal5bb kdt konkr6t p61d6t,ezek algoritmusait elemezhetjtik6s a ktiziis rdszleteket 6ltal6nosanis 6rtelmezhetjrik.A kiiziis l6nyegi mag lesz dz, amelynekabsztrakci6jaegy adottprogramozdstt6telben nyerhet megfo g almazlst.
4.4 P6lda komplex megold6sialgoritmusok kidolgozilshra
A kovetkez6kben megszerkesztjiik algoritmus6nakegy lehetsdgesv61tozatilt
Gauss(-Jordan) elimin6cro
megoldashra, 1. line6risegyenletrendszerek 2 . m6trixok multipIikativ tnverzlnek el6alIit asara, 3 . determin6nsokdrtdkdnekkisz ilmitdsftta peld6tadvaezzel arra,mikdnt oldhatunkmeg komplex 6stobbcdluprobl6rn6kat' 6s probldma-elemzdse meeold6sainak lehetsdees I . Lineariseg)'enletrenclszerek matematikaimodellie: Line6ris egyenletrendszerekrnegold6sakor tekintsulc : ekvivalens6talakitasokat
l
lblcserdl6se, (i) kdt egyenletsonencijdnek egy neln nulla valos szatniu;rl, (ii) valamelyikegyenletvd,gigszorzesa egy rnil:;ililioz. hozz.atdasa eg1'enletlionstansszorosdnali (iii) r,rilarnc;l1,ik
9i
azat nem Ezel< a mriveletek az egyenletrendszer megolci6shalin vtitonatj6k meg, az 6talakitott egyenletrendszeraz eredetivel ekvivalens, azaaz eredeti6velazonos. megold6shalm Munkankat inegkonnyithetjuk oly m6don, hogy az egyenletrendszer csal,-az egyitthatokat 6s konstansokattartalmazo irn. kibovitett eg6szehel1,s11 m6trixot irjuk le.
1 .P e l d a
.rl - 4xr= 1 3x, + 2x, =I7
fm l -
1 l ,l I ,ll, 1 L4 @ l I L4
1
I q il E l t_o
i_c
.t -
[:
s]
0
,j
[ '
[ '
LO
.xl *r?.
92
1
2. P6lda
.rr - 4xr,= t - 3 x ,+ 1 2 x , = - 3
b
4
L2
.l r
I
*ul
!
I
3 .P 6 l d a
rr - 4xr= 1 Zxr-8t, = 3
t,-
4
lu t_@
-8
' T 1* ' { ' " ' * '
0 . r , +, 0 " x ^ ''ri'-i
1 I l.
I l-
Egy line6ris egyenletrendszermegold6sa alapvetoenh6rornfelekdppen alakuihat. Az egy'enletrendszernek (i) (ii) (iii)
egyetlenmegold6savan, v6gtelensok megoldlsa van, nincs megolddsa.
Ezt a h6rom alapesetetillu srtrfijilk az el6bbiekbenmegoldott p61d6k.A tov6bbiakbanrdszletesencsak az els6 esettel foglalkozunk, az utobbi kettore adott esetbencsak mint 'rendkivtili eset'-rehivatkozunk.
el6kdszit6megfieyeldsek: Az algoritmusszerkesztds6t 'rendkfviili eset'-et Egyiel6l megfigyelhet6,hogy ielez az a t6ny, ha a Gausselimindcio(itt: 1-esfo6tl6belielemek,6salattuk csupanulla) nenl vihet6 vdgig. M6sfel6l vil6gosan kell l6tnunk, hogy ha az egyenletrendszernek egyetlenmegoldSsavan, ugy nem csak, hogy v6gigvihet6a Gauss eliminaci6, clefolytathatoa csupa 1-esfo6tl6belielemekfolotti elimin6l6ssalegeszenaddig, amig un. teljesenreduk6ltrendszertnemkapunk,ami magaa megold6s. Egy ujabb pdld6t oldunk meg erre az esetre,lehetos6getteremtve ez|ltal sztiks6ges6talakit6strnegfigyeljiik, arra,hogy a lehets6gesosszes(esetlegesen) az elimin6cio fo lyam atfrt anahzdliuk.
Figyeljrik ffi€g, hogy a Gauss-Jordanm6dszer az ekvivalens megfeleloelimin6ci6sl6p6sekr6vdn az t A I b I kibovitett 6talakit6soknak rn6trixot(INPUT)az t I lX I modositottm6trixba(OUTPUT)vrszi at.
94
P6lda
-6 6 10 0
1
[.
a,
I
L:
J
-
-J
tq ato
Ir
I
-3
lr f l-
4
L,
0 A
J
T"
0 € )
€,
[;
0
r;lr l
q
a
Ir
4
0
E
0
0
I
0
['
Al
+
10
a
0
-_rl l
Ct
e/
L,
+r
, o lJ
0
J
J
-t
13
5l
iJr'+ -l -r ? ' ln ' t J *J
" Ii ll.(+)
q
_
d,
'-' ll \
t.+
I
WJ
-10 | : l
0
tr
0
0
I
l
0
1 -
0
t
+
['
L'
I
T
A
i
I
Y
=
rta
-,: a,
95
,TI-
r l + l ll'-t
[,
l o
I
101
4
0
a
['
l -10 |
6
-
rJ
tt
r!
al
-?I
ll.(4)I
'D
0
tl
-b
6l
'l
-\
I tt
{-ll il.+ -
E
a L ,1
n6gy olyan A f5 folyamatilbra az algoritmus v6zla#rt,mutatja. F,z folyamat6br6k alprogramot tartalmaz, amelyeket a tov6bbiakban kiilon annakjelz6s6re, segit*g6vel r6szleteziinkmajd. z6szl6t(z viitozo) haszn6lunk vagyser}. vajona Gausselimin6crosikeres-e
Nxld A(I,I) BE
Ganssel.',/vagy 16
0
G - Jordanel. NXM A( I,J) KI
Rendkivtili eset
:il
\t/
t I
Stop
96
NxM A(I,-l)BE I = 1-t61N-ig( egyesevei )
J=1-t6lM-ig ( egyesdvei )
NxIvI A(I,I) KI
I: l-tol N-ig ( eg'esevel)
J=l-t6l M-ig ( eryesevel)
L)'l
Gaussel.
A
A(t.l)*0 vagy Z*
i
A(l,l) legYenll ( egyesevel)
(= (l+l)-t6l
.ti*inut I
Z=tJVAGY I>N-l
A ( l . I ): 0 A (l,I) legyen I
t l;i
A 'Gausselimin6ci6' elj6r6s feladata,hogy a foi*lo alattrelimin6l6st elv6'gezze, A f66tl6 mentdnminden elemetmeg kell vizsg6lni. amennyibenaz 1ehetsdges. el6mi Ha valamelyikuknulla lenne,irgy alkalmassorcser6velmeg kell prob6lni azt,hogyne legl,ennutrla('A(I,I)*0 vagy Z+0'nevii eljAr6s).Ha ez nem sikerlil' 'rendkiviili esetet'kell jelezni. ugy uiirrl6 d' nevri viitnzo) nullSra tllititsdval BZrmely nem nulla fd6tlobeli elem redukSlhat61-esre('A(I,I) legyen 1'nevii alprogramfeladata)6,sertcdlszertimeg is tenni, hiszenigy konnyebbdolga lesz az lelimin6l' nevri elj6r6snak. A ciklus szervez6sdvelkapcsolatban itt k6t 6rdekesmegfigyeldst tehettink. Az egyik &2, hogy miut6n nem tudjuk elore' h6nyszor leJz -ujd a ciklusmag vdgrehajtva,nem hasznftlhatunksz6ml615ssal vezerelt FOR ciklust. A flexibilis ciklusok koztil megoldSsunkban egy h6tultesztel6ciklust viiasztottunk. A rn6sik hangsiilyozftsradrdemesmomentum az, hogy az.utols6 foetl6beli elem vizsg6lata6s az ezzel kapcsolatosteendoka ciklusmagonkivtil, a ciklusbol va16ki16p6sut6n kellett, hogy helyet kupjanak, hiszenelimin6l6siteend6itt m6r nincsen. Ez az elsd hierarchiai szintti alfolyamatdbratov6bbi 3 m6sodik hierarchiai szintu elj6r6st tartalmaz,amelyek kulon folyamatthrftk segits6g6velnyernek E,gyiktik,az'A(I,I) legyen 1' nevu a'Gauss elimin6ci6'elj6r6s majd r6szletez6st. k6t kiilonboz6 hely6rol is aktivizfihat6. (I(6s6bb l6tni fogiuk, hogy az'elimin6l' 'G-Jordane1.'nevu m6sik, ugyancsak elj6r6spedig nem csak ebb61,hanem a elsohierarchiaiszintualprogrambolis hivhat6.)
99
A(IJ) * 0 vagy /<-
K-K+
0
1
A(K,I) * 0 K.f=4' 1 SOfCSefe
Z*
Z:T OR K:N
A(I,D * 0 vagyZu- A
r00
esetekbenaktivizalhatja a F,z a m6sodik hierarchiairzintri elj6r6s bizonyos 'K amelYet harmadik hierarchlaiszintenmegfogalmazotl <+I sorcsere'rutint, ugyancsak kiil on alfolyamat6br6n16szleteziink.
t(4==P1Sgrcsere
J - I-t61 M-ig
W*
A (I,J)
,t
A(I,0 <#A(KJ)
A(K4=-w
( r K@I
Sorcsere
i01
A(l,D legyen1
.A(I,! * 1 Q <---l/A(I,D
J: I-t6l M-ig ( egyesdvel)
A ( I , J )- A ( I ' D * C
A(ID legyen
I : N-t6l 2-ig ( -1)-esdvel
K:(I- I )-t61 1-ig (- 1)-es6vel
'.-) i f L W *
A 'G-Jordan e1.' eljar6st tanulm ilnyozxa meg6llapithatjuk, hogy az sokkal 'Gauss elimin6ci6', hiszen azon a ponton, amikor az egyszertibb,mint a meghiv6srakertil, biztosak lehettink abban,hogy 1) afof*loban nem lehet nulla elem, s6t valamennyifaittlobelielem 1-es;es igy az'elimin6l6s'alprogram azegyetlen,amelyreez esetbenszuks6gvan.
2) a G-Jordan elimin5lSsi folyamat ( foarll feletti nullaz6s) biztosan vdgigvihet6, kovetkezdsk6PPenszhmlftl6ssalvez6relt FOR cikius hasznflhat6. 'elimin6l'alprogram alc'liztif"sa termdszetesen A m6sodikhierarchiaiszintri 'GausseliminScio'-bol, mind pedig a mindketelimin6cioselj6rasbol(mind a 'G-Jordanel.'-b6l)kezdemdny . ezheta
elimindl Q <-- (-1)*A( K,I )
J= I-tol M-ig ( egYesevel)
A (K,J ) -
eliminai
'| /\ ''r
t u_)
A (K,I;+C*A(I'I)
Az alitbbiakbanegy hierarchia-6brasegitsdg6velfoglaljuk ossze az algoritmus valamennyir6szlet6t:
Fd folyamatihra -
BE
A(I,I)+0
/
G * Jordan
Gauss
K]
tl
A(I,I)<--1
slimin6l
sorcsere
Z. Problema-elemzds6s matematikaimodell matrix multiplikatfv inverzenek meghatarozashhoz;
Az elso r6szben a Gauss-Jordan eliminacios eliar6st mint linearis egyenletrendszerekmegolddsi m6dszerdt tixgyaltuk. Ug1'anakkor ismeretes, tomorenmdtrixegyenletkentis kezelheto.Ila hogy egy line6risegyenletrendszer teh6t a rnatrixegyenletmindk6t oldal6tbalrol megszorozzukaz egyenletrendszer megoldasat inverz6vel,ugy mindj art az egyenletrendszer egytitthatorn6trix6nak kapjuk. $sszehasonlitva egy line6ris egyenletrendszer(felt6telezve, hogy pontosanegy megold6savan) el6bbiekbenemlitett kdt ktllonbozo megoldasi elirninacio jutunk, hogy a Gauss-Jorclan arra a felismerdsl'e moclszeret lratas6banlnesfelel az egr-titthatorndtrix inverzdvelbalrol tclndno szorzasnak.
1 / \ {
I \-/ *t
l-l
xl
1 try n
4
CN ..-# n bad
l
(n .
'1
* t' ffi, 'I -i
*
,-l 8,, . 14il
"-ll
i-
-v
\
rr
t \ \t -r1
# a
I-'
kI
-
F*>
-
-
/r r-1 \l=
= 0
='H tv N -
r-': t=
t
ry
Z-
r-''r r-
Er F
,aa
r-''i x
F
-J N 'I)
l-
t^ l
-
/-7 1 -t-. .A , F P .
E
\r n
oJ
-t\l
<.ll
o
;'; ' l
t,
\d
lt
l-'-
l'
irEl >-
7 l=
rl
rl
rA
-A
X- l I
tY
r--.
!X 'ttl
rl
l
-
v
U) = Fr-
g,<
tr
(n
.-t(t
ET
t: FI
N
z
t-"m
F- ''t
. l t - r IN
z E
I
n u
|
F-i ki
I
rn
1 -{r \ d 7S
F.? ( ' r--i i - a
t z . i tJ)
z I f-l
I T
an
- i
I
S 3/ < i ll o i l l-
Fnra
f, l
'
ry -i
ID
r=l -
/-,
r
tI -
F r = - i "
'_4 -
A.
i
-\ #
''t
I-
t . _ - l
r05
s
4'
-41,
elok6szit6megfieyeldsek: Az aleoritmqq.gzerkegzt6s6t elemz6smutatja,hogy ugyanazaz algoritmus(amrt az' Az elobbi osszehas'onlit6 elscj riszben mint line6ris egyenletrenriszerekmegold6si algoritmus6t dolgoztunk ki) m6trix invert6l6s6ra is hasznalhato. Ilyenkor az algoritmus INpUT-ja az t A I t t kombinfitmhtrix, a keresettrnverz rn6trixot pedig az OUTpUT-kdnt kapott t I la-t I kombin6lt matrix m6sodik tombresz6ben 'rendkivi.ili eset' in a*. jeIzr, hogy az A-m6trix nem tal6ljuk. (Adott esetbena invert6lhato.) GAUSS- JORDA.NELIMINATIO MATRLX ITWERTALASARA
(2)
G. - J. gl.
[al L-l
t =At I= I I = f 1
P6lda
o li'(3) --
?
u
I
I
I -'
t 1 1
tl " L
:
[ :
Lo
-g
0
1
1
o
0
I
r
o o l
I
g
1
o l i t. {7-
l - t
o
,
I
r
o o l
l
r
7 -?
r
1 t..l
-'.:
o l 1 l
-2
?
* !,
, L .J l I
7
'
l - - " o1 , 1 {lr r.
l !
J
t
1
1
i l. t - t l
l
I I
I
r
ll.Irt
'
ii
l
I
J
r
"
'
..-.*..*
l t
II
II
2 , 3
I r o o l
r
l
l g : ' o l l t ' l , , l 3 z I
LI
il
I
r
?
l I
r
-o -
l
-
a
1 I
l a
3
e
,
l
@
7
z
-
-l
z
t
I
l
J
4
l
LI
7
1
7
3
-
7
l
r
t
5 7
I f
1
-
1
2 7
ll
z
1
-
= t lla-' l
7
r
t
I
;]
7
7
3
-
7
L
l
7
4'4-t = I
rl r
2
t
3
I
1
-
t T
-g 7
"!
l - * I
I
I
I
I
l-= I II t l
I
q l
. G
a
.
1 I
L
2
7
7
2
7
7
"
,
I
l
1
II
r a
f
i07
l
l
!
r l
f
v
l
n u
6s matematikaimodell determin6nskife tes6:hez: 3. Probldma-elemz6s Egy h6roinszogmfttrix deterrnin6nsakiszdmithat6a foatlobeli eletneinek szorzatakent.Ugyanez rgaznem csak fels6 vagy als6 h6romszogmatrixokndl.de b6rmely diaeonhlmf*rixeset6nis.
Ilyen specialis m6trixokhoz juthatunk, ha egy kvadratikus mdtrixot a elimin6ci6 procedur6j6nakvetunk a16.Most azonban,m6trixok Gauss(-Jordan) helyett azok determindns6r6ll6vdn sz6, az elimin6l6s soran figyelembe keil Az egyes elemi operdciok venntink a megfelel6 determinfns-tulajdons6gokat. ugyanis modosithatjaka determin6ns6rtdket. Az alAbbiakbanosszefoglaljuk, hog)' a kvadratikusm6trixon vdgzettegyeselemi mriveletekmikent modositjak 6nak ertdkdt: cletermin6ns Ha az elernimuvelet
(i) kdt sorcser6je; szdmmal; (ii) egy sorvdgigszorzdsa l"eR va1,5s egymasiksorhoz; (iii) egysorvalahanyszorosanakhozz6ad6sa ak-lior
(i) (ii) (iii)
det ( 1.,') det(A') clet( A' )
-det(A) I det(A) det(A)
108
Az aleoritpu s- szerkeszt6s! eI 6k6szitqme efi eyel6sek: Az al6bbiakbanmbgoldunk egy pdld6t abb6i a c61bol,hogy megfigyelhessuk mindazokat a lehetsdgeslatalakit6sokat,arnelyek rdv6n egy adott kvadratikus m6trixot a kiv6nt specidiis alakba reduk6lunk, pirhuzamosan vdgrehajtva a determin6nsdrtdkerevonatkozo sztiksdgeskorrekciokat'
:: i L: l
P6lda t t\
dei(A) =
-
? - 4 - 8 -1 0 1 -t
det({) =
det(d) = (-Z)'
1
1
*1
0
1 2 -1
ket sor cserej6nekhatas6ra a determinins eldjelet valt
4
-
d
8
a m6sodiksorboi kiemelheto a 2-eskozos oszto
1
1
l l. t t l
* . La
t
0
1 -1
2
-4
1
L
hozzaadlisaa mdsodikhozds az elsclsor (- 1)-szeresenek maganak azelso sornak ahozzdad6saa hamadikhoz erteket nem befolyasoljaka deterrninans
det($)
==(*z)
*1
0
t
f i 2 " * 3 t
i
t
f
a ket scr cserdjeismit a detennirtaiis eliij rri valtasdtcredmiinvezi
i
109
der({) =
(+2) .
t
0
-1
0
1
0
0
a ) 4
a
t o
t < 5
a masodiksor(-2)-szeresdnek hozziadasaa harmadi khoz erteket nem modositjaa determindns
0 0
-?
0
1
dei(A) = ( + 2 ) '
1 0
0 *
3 fejtstlk ki a determinanst elso oszioPaszerint
= ( + Z ) .f l .
t
1
0
0 - 3
- Cl'
0
-?
+ 0'
0
-1
lt
r
-
I
0 - 3
1
0
l
(+Z).i..t'(-3) * -6 = cie!(&)
Te[it eg]' fiaromszogm6trixdetenntnansrtvaloban megkaphato^ foatlobeli eleinciuek szorzatakent.
110
A'sor-redukci6'-ra ir6nyul6 elimin6lSsiprocedirramar a h6romszogforma fhzisfnal befe.jezheto (mikdnt e bemutat6 peldftnftl tettiil., ir); persze lehetnefblyatni is,'amig a diagonii alakot el nem drjtik. Noha a determin6ns mostrendelliez6stinkre kdnyslineskisz5mft6s6hozelegendSa hAromszog-forfr.ra, 611a kdsz Gauss-Jordanalgoritmus, amely az utobbi - teljesen reduk6lt verzionakfelel meg. Az elozo p6lda nregolddsi folyamatdt tanulmanyozval6thatjuk, hogy szinte ugyanazaz (els6 6s m6sodik r6szben tdrgyalt) algoritmus determin6ns kifej t6s6reis hasznftlhat6. Eredeti algoritmusunkatmilyen apro modosft6sokkal,kiegdszit6sekkel (A vilIasfi,az Olvas6rabizzuk.) tehetndnkalkalmass6determinSns-kifejt6sre? Erclemes rnegjegyez,ni, hogy ebben a harmadik alkalm azasban a 'rerrdkivtilieset'azt'1elenti, hogy a determin6nsdrtdkez6rus.
oktatSs 5. Algoritrnikus szem16letfi
N{ivel a kerd6skor imm6r kozel n6gy 6vtizedesmultra tekint vissza, n6h6nymondatot6ldozhatunkkeletkezdsekortilm6nyeire.Az 1950-esdvekben az USA-ban mint tistokos indult pfiydjfira a programazott oktat6s. Elmeleti alapjat a Skinner-i kis l6pdsekb6l 6116 inform6cio + k6rdes -+valasz "keplet" jelentette, + megerSsites(illetve konekci6) tanul6spszichologiai melyeket az erre a c6lra szerkesrteft speci6listankonyvek,iiletve oktatogepek tovabbftottatrr. A tariuioi
l l l
finomit6s6t, flexibilisebbd tdtel6t algoritmusok tov6bbi Az (human\zfi(sfi, optimalizi|Asftt) szolgalttk azok az ot 6ven at tarto kis6rletek, "A humantztit rnegtanuiando melyek eredm6nyeiegydrtelmuv6 tett6k, hogy (6talakit6si)folyamatok elsajtttitistt algoritrnusokmegkonnyithetika megol,C6si azokban a tdrgykorokben, melyek alkalmasak 6s cllszeniek algoritmikus el6ir6sok keszites6re;az algoritmikus eloir6sok transzferhathsaa t6rgykoret kepezo tantdrgyon belul 6rv6nyes, m6s tirgyal
5.1.Algoritmikus szeml6letfitanftisi-tanul6si folyamat
"Modell 6s algoritmus egytittoktatds6raa hallgat6sSgjelent6s r6szenek a kiilonbozo b6rmely okbol szuks6geis van: mindazoknak, akik elnevez6sutant6rgyakbantanultakatsajStmunkirjukkal integr6lni nem tudjek. A a tananyagnak - a kdpz6sic6i szempontj6b6l - tulzotttantdrgyi szetaptozasa kialakit6s6takad6lyozza."6 rendszerszemldlet ma m6r nelkulozhetetlen
, Dr. GyarakiF. Frigyes: Algoritmusok ds algaritntikusel6frdsokdidaktikaifelhu,sznaldsdnalc es optintalizdldsdno/':lehet6sdgei, tdzisei,Budapest,1976.15.p. Kandid6tusiertekezes g'tiitern'in1'91 5Dr.GyarakiF. Frigyes - Dr.BiszterszkyElern,ir:Didaktikui tctnulmdnt'ok Kiado, Budapest,1996' lr4iiegt'etern 6 llr.Felrete Isivrut: Jt,{cttemstiks chtil;a integralt olrtcttitsct, ds s'z(un{tdste tezisci,B'-iiiailcst,1985. 5'p. ertekezes i.,.iiirciidatusi
l1*
Az algoritmikusszeml6Ietmod kialakit6sa, az algoritmikus gondolko d6sra nevel{s fokozza iitalilban az aktat6shat6konys6gat, ugyanakkor az informatika tanitott programozhstis segiti. tant6r:gycsoportban Nem a szttmitttstechnika6s az inform atrkaval kapcsolatos tantftrgyak jeientik az egyedi^ililehetos6,get, hogy a tanulokbankialakitsuk az algoritmikus szeml6letmodot.Tapasztalatokmutatjdk, hogy a szttmitdstechnikahaszn|lata m6s tantargyakbanmindk6t oldal lehet6s6geitmegsokszorozo,tetm6kenyito megold6s6hozazt a kolcsonhat6steredm6nyez.Egy adott feladattipus61ta16nos 'probl6ma-rnodell-algoritmus' utat kell bej6rnunk, amely a szdmitastechnik6ban a progranioz6sn6lnyilv6n nem kenilhet6 ki. A nem szamitog6pesrnegold6s sor6n azonbansokszor sajnosnem igy j5runk el, j6llehet a feladatmegolddsnak ez a menetrendje biztosftja a komplex 6ttekintdst.
5.2.Pfrhuzam a taniri 6s a programoz6i tev6kenys6ghiiziitt
Fejezetiink kiindulopontj 5ul H6mori professzor 6llit6sftt rdezztik, miszerint "A szfumititstechnikaieszkozok (sz6mitog6pek) tanit6si-tanul6si folyanratban betoltott funkcioinak (alkalm az6sfunak)vtzsgilata a tanul6si folyamat elemzdsdnalapszik. A tanulSs ds tanit6s komplex tevdkenysdgek, melyek cselekvdsek,mtiveletek sorozat6rabonthat6k."' A kovetkezokbena tan6ri 6s a programoz6itev6kenys6gethasonlitjuk cissze,el6keszitveezzel az algoritmikus szeml6let oktat6si folyamatra gyakorolt hat6sainak,modszertani vonzatainakvizsgillatht.Mindezek eredm6nyek6ntv6lik majd vil6goss6, hogy ez ol
?Dr.l-linlori Miklos: Taittid"sts tanitiis ,gzftrntt6g6ltS;el, Bri,-lapest, 1984., 5.Il. ertekezestezis,:i. Ii.andidirtusi
ii:l
A leendo tandrok szhmdra - a villasztott szaktol firggetlenul - egydbk6nt is alapvet6 fontossftgu, hogy megfelel6 programozilst ismeretekkel es az algoritrnikusgondolkod6skdpessdgdvelis rendelkezzenek.GondoljttnL csak arra,hogy amikor szdmitogdppelszeretndnkmegoldaniegy feladatot,val6j aban a sz|mitog6pesprograin megirhsaazt jelenti, hogy a programoz6 "inegtanitja a szttmitos6pet"az adott feladattipusmegoldilsttra.A megold6salgoritrnusailyen drtelemben"tanit6siterv" eredm6nyek6ppen sziiletik,amib6l kovetkezik,hogy a programozo mindj6rt egyfajta tanitri tevdkenys6get is gyakorol, rnikozben persze kovetkezetesen elv6rj6k t6le "a tanitv6ny" kdpessegeinek lehet6sdgeinek figyelembevdtel6t. Erdekes lehet mdg a folyamat k6t fd finisanak anal6gi6j6ra i s r 6v rlilgftani: altalanosfolkdszillds
pr ogr amnyelvt5I fil ggetIen alg or ittnus-szer kesztds konlcrdt pr ogr amnyelvr e adaptal as
adott osztalyhozval6 alkalmazkodds
A hasonlatmegint nem csak, hogy j61 mutatja, de vitathatatlann6teszi a kdt finis elkrilontildsdt 6s sorrendis6g6t.(Ambdr igaz, hogy a programoz6 szdmdraaz "alkalmazkodits"tobb6-kev6sbe6lland6,mig atandr szamdrainkdbb valtozo feltdtelek figyelembev6teldtjelenti.) Mindenesetre a programoz6i tev6kenysdgtanit6ssalva16 kapcsolatfttvizsg6lva eszunkbejut a "docendo discimus" elve, amit Joseph Joubert (1754 - 1824), a latin szellemet ujjdelesztenisz6nddkozSfrancia klasszicista gondolkodo igy fogalmaz meg: "Aki tanit, az k6tszeresentanul.". Val6ban - nem csak, hogy tudnunk, de kell ismerntink azt, sokkal m6lyebben elmerulve, elemezgetve-boncolgatva aminek a tanitdsira vSllalkozunk. Igy kdsziilve m6sok tanit6sara, rninden alkalornmalmagunkatis 6hatatlanultanitjuk, vagyis tanulunk.
5.3.A mintap6lddkszerepe az algoritrnizdl6sta nitf si-tan ul6si folyamat6ban
Az algoritrnizii|s tanit6si-tanulAsitblyamatf* elemezvevil6goss6 valik, nernkdsz algoritmusokatkell tanitanunk,hanemsokkal inkabb hogy els6sorban azt, hogyan szuletik egy algoritmus."A megtanuland6algoritmusoknakfoleg csakaktriorvan 6rtelmukds helyuk atanittts-tanul6sfolyarnathban,amennyiben szintjen) jelennelt ezel
i ' i
a
meg."8A "szorz6titblilt"perszemajd csukott szemmelis tudni kell: 3xB :24 (goridolkod6sndlkril!); ez persze nem azt jelenti, hogy azelott valamikor ne mutatt6k(6s 6rtettiik)volna ffieg, ircgy a 3xB azt jelenti, hogr, 8r-8+8 - 6s ez persze 24. A megoldand6 feladat legyen 6letkozeli. Az algoritmus szerkeszteset rninden esetben elozze rneg a gyakorlati probldrna elemzdse a modell-alkot6s. ds ennek eredm6nyek6ppen Trsztazrrikell, milyen adatok 6llnak rendelkezdsre(INPUT) 6s milyen eredm6nyeketv6runk (OUTPUT). Az algoritmus art a pontos menetrendet (utmutat6st) jelenti, amelyet kovetve eljutunk a c6lhoz, azaz a feladat megold6sahoz.Ahhoz, hogy ezt ossze6llftsuk,nekiinlcmagunknaktudnunk kell n art a magunknakfeik,it lid;i'di:;rl.-eil rregoldani az adott feladatot.L6nyegdbe "Eu hogyan csi n6\ndm?" Ugyanakkor persze megv6laszolnunk: megolddseset6n- min djilrt gondolnunkkell arra is, hogy a gdp szamitog6pes a scldial elernibbmtiveleteket drlelmez 6s v6gez, mint az ember teend6ketennekmegfelel6en kell lebontanunk szdmdra. Az algoritmus egyes l6p6seinekfelt6r6sfha - folyamatosanmegfelel6 a tanul6kat is bevonhatjuk, ezzel biztositva a segitsdgetadva 6gra neveldsben.Nagy el6ny, hogy a kozosen fokozatoss6gotaz on6l16s rnegoldott feladatot a tanul6 igy "sajirtjhnak 6rzi", ugyanakkor ez vesz6lyt is jelenthet:a legtobbtanulo ugy v6iekedik,hogy ha valamit megertett,azt tudja is. R6 kell dbresrt.emdket, hogy a megdrt6s csak szuksdges, de nem el6gsdges felt6telea tud6snak. Vegytik egyelore csak a reproduktiv tud6st. En a legkonnyebb ellenorizni: tudja-e tires papiron reproduk6lni a kordbban kozosen mar megalkotott (ds megdrtett) rnegold6st? Ha sikertil rdvenni oket erre az azt foE itktapasztalni,hogy a megdrt6snem feltetlentiltud6s.Mi onellenorzdsre, amelyneksor6tr a teendoilyenkor?A helyesmegold6sujboli 6ttanulm6nyozasa, nrf g az is kidertilhet, hogy bizonyos pontokon a rnegdrtds setn volt megalapozott.Ezeket tisztazvalrezheti ismet ugy, hogy most mar tudj a, de ezt ismet ellen6riznikell. Az iment vdzalt "cikiusmagot"kell vdgrehajtaniujra 6s nem teljesul.Hogyan is fjra, amig a "kildpdsifelt6tel"(hib6tlanreproduk6l6s) lehetnevalaki sikeres egy ismeretlenfeladat megold6sdban,ha nehdzsdgei r.'annaka.z ismert reprodukdl6sdb an? Sajnos mi tandrok is hib6sak vagyunk abban,hogy aluldrt6kelvea reproduktfv tud6st, engedjiik kihagyni a tanit6sfolyamat6nakezt az alapvetSenfontos l6ncszemdt. tanr"rl6s Nagy ellentmonddsaz, hiszen ugyanakkor a definici6kat, tdteleliet precizenmegkoi'eteljul:,teh6t val6j iiban nem tagacljuka reprodr-rktivtanuids sztiksdgessdgi,t.Idegen nyelv tanitasakor- tanuldsakor a szava.l<,nvelv'l)r.ClvarakiIi. Frigl'cs:Algcriiinusolie;salgoritmilluseloirdsokdidalqtiiiai siurak I ehetcisr:s.ci feIIi n.szniri i san;ik d:s opti n :m;;,liziilft l9"l6,'2Cp. frici..cz'ls. I{ aridiCitu:;i 115
tani szab6lyok elsajfnitilsitt mindenki fontosnak tar\a, de rni a helyzet a memoriterekkel?Ma mintha elfelejtkezn6nkarr61,hogy a kotott szovegekszo szerinti (ugyanakkor persze minden rdszletdbenakfir elemekre szdtbontva is tudatosan 6rtett) megtanul6s6val nem egyszenien csak a nyelvtud6shoz sziiksdges kell6kekre tesztink szert, hanem annak komplex megjelendsi form6ira tdrolunk el olyan mint6kat, amelyeket rdszben vagy egiszben, sot eppen a kompon6l6si mint6k vezdrllsdvel ndr ak6r fitalakitva, bizonyos drtelemben t\at alkotva hasznosithatunk.A motiv6cio is biztosftott, ha jol megv6lasztott,a mindennapi6letbenj61 hasznosithat6anyagokat vfilasztunk ki ene a c61ra. B6rki kipr6b6lhatja, hogy ha egy t6makorben(tudatosan, rdszleteibenis drtve) idegennyelven megtanul I0-2A eredeti mondatot,akkor amire ezel<etfoiydkoilyan (aulomatikusan)tudja mondani egyszersinindkdpes lesz ar-rais, hogy ha nem is annyira folydkonyan,de szinte tetszds szerinti is gyakorlatilag hib6tlanui 6talakitott vari6ciokban a saj6t megfbgalmazits6ban tudja interpretdlnia k6rddsestdmffi az adott idcgen nyelven. Ez oriasi dolog, hiszenez implicite azt is jelenti, hogy az adottt6makorbensajdtgondolatainak kifejtds6reis kdpes.Esetiinkben a jol megviiasrtott mintapdld6k tolthetik be kirnerithetetlen sakkj6tdkban rejlo ilyen "memoriterek" szerepdt. A szellemi lehet6sdgeket aligha vitatn6 b6rki, m6gis ki 6llitan6, hogy a sakk-16p6sekelsajftitisa vagy az alap-strat6gi6k reproduktiv megtanul6sa elhagyhat6,net6nszdgyellnivalo lenne?
5.4.Az algoritrnikusfeladatrnegoldfstanftSs{nakn6h6ny kognitfv pszichol6giaivonatkozSsa 5.4.1.Produktfv 6s reprodukt{v gondolkodds (az alakldiektankdpvisel6i) szerint a gondolkod6 A Gestalt-pszichologusok " ember fitlatja" a probl6rna szerkezetdt 6s a megold6s 6rdekdben "irjrastruktur6lja" azokat.eAzelmi:let f6bb meg6llapit6sai : gondolkod6segyszerreproduktiv ds reproduktiv; a probl6mamegold6 tdsa; irjrahasznosf a kor6bbitapasztalatok a reproduktivprobldrnainegold6s a produktiv probldmamegold6sldnyeg6ben a probl6ma szerkezet6nek 6tl6tasa6s uj rastrukturalrisa; (az irn. funkcion6lis rdgzitettsdgaz i*I6t6sth6tr6ltatotenyezolehet) f*l6t6sarendszerinthinelen kovetkezik be. a prolrldiiiaszerkezetdnek
"f,/. t'J-lYScnci.", ologi:l /':: Id,cane. Fuli.T. : K-ognitil' psztr-:h h{. i!)!r'i. tiC-lp. N ;Lnzeti' l'an l;$in'r,kiaciir.l3ucllrpest"
i 1{r
A kognitiv teljesftrndnnyel kapcsolatban megiilapfthato, hogy mindenekel6tta tapasztalat az, amelynek r6v6n az ember egyre iobban, egyre nagyobb szakdrtelemmel tud dolgokat megcsin6lni, r'61ik szakdrt6v6. A kognitiv kozelmultbansz6mciskis6rlet ir6nyult arca,hogy a probl6mamegold6s is kiterjesszdk. elrn6leteit(pl. probl6mat6r-elm6letek)az emberiszakdrtelemre A sakkoz6s, ftzikai probl6rn6k megold6sa 6s a szfimitogdpesprogramoz6s tertilet6n vegzett kutat6sok eredm6nyekdnt szftmitog6pes rnodellekkel t6mogatott elm6letek is sztilettek.J.R.Andersonpdlddui a Gondolkod6s Adaptiv Vez6rl6se (GAV) kognitiv architektur6j6nakrdszek6nta keszsdgek elsajititdsfxa vonatkoz6an dolgozott ki a szakertelem sokf6le terulet6n alkalmazhet"o6ltal6nos elm6letet. Ezeknek a szak6rtelemmelfoglalkozl kutat6soknakjelent6s r6,szea tobbdkevdsbdismertlsprobl6m6k megold6s6nakmikdntjet vizsgiija, ahol valoj6ban a sematikustud6s keriil kozvetlenalkalmazlsra.
5.4.2.Analogikus probl6mamegoldfs6s kreativitis
A kreativitassal foglalkozo kutat6sok arra a k6rddsrekeresnek valaszt, hogyanvagyunk kdpesek - nyilv6n kreativ - megold6stproduk6lni olyan esetekben, amikor a probl6m6valosszefirgg6ismerettelnem rendelkezunk? Wallas klasszikusnakszamitoleir6saszerint a kreativ folyamatfo ffnisai: az el1kdsziil et f6zisa: els6probalkoz6soka megold6sra; a probldmamegfogalmazitsa, az inkubdcio fazisa: a probl6m6tfdlretesszuk,m6skdrd6sekkelfoglalkozunk; az illuminacio fdzisa: vilratlanul"beugrik" a megoldds; a verifikacio fdzisa: ellenorzese. a hirtelenbel6tottrnes-old6s
Ez a s6masajnosnem sokat6rul el a kreativcselekvdsrnogotteskognitiv fol1,a6atairol.Val6szinirsithetoazonban,hogy az analogikusgonclolkodasaz a kulcs, ameiynel
',
1P7
kreativit6s kdt nagyon is ktitonboz6 elkepzel6shalmazanalogi|jabol sziiletik. "anal6graja" egy irn. Matematikus szemmel az analogikus gondolkod6s analogilan lekepezrls,amely az ernlitett k6t elk6pzel6shalmazkozott ldtesit fogalmi szerkezetlt hozzdrendel6st:egy'adott gondolathalmaz(ale,ptartom6ny) (c6ltartom6nyra)k6pezile. egy m6si1'.ra Az analogikuslek6pezdsndir6nyjellenrz6je: az alaptartom6ny6s a celtartom6nyfogalom-,ill. tulajdons6g-elemeinek megfeleltet6se; az alaptartom6nybizonyosfogalom-,ill. tulajdonsdg-elemeit6tvissztik a c6ltartom6nyba6s ezzelott irj fogalom-,ill. tulajdons6g-szerkezeteket vezetiink be; iiltalfhan komplex (koherens, integr6lt, nem tored6kes) ismeretek kerulnek 6tvitelre (1.Gentner szisrtematikuss69-elv6t); pragmatikusc6lszenisdgnem komplex ismeret6tvitel6tis indokolhatja.
Rutherford a Naprendszer anal6gii$fn haszn6lta az atom-szerkezet modell ezdsdnll, de anal6gia az alapja Einstein f6nysug6r-meglovagl6s6ra is. Az analogikusprobldmamegold6skutat6sa vonatkoz6 gondolatkis6rlet6nek l6nyegdben azokat a kreativ tev6kenys6ggel kapcsolatos korulm6nyeket vizsgiija, amelyek kozott az emberek valoj ihan analogi6kat fedeznek fel valamely6ltalukm6r ismeft,ill. a megold6sravdro ismeretlenprobldmakozott. k6t fo irilnyzat ismeretes.Az egytk az A kreativ folyamat 6rtelmez6s6ben rijszerti produktum l6trehoz6s6tl6nyeg6benv6letlen esemdnynekk6pzeli el, amelynekvaloszintisdgdtbefoly6soljaa tud6sanyagnagys6ga(a rendelkez6sre el16 elemsz6m megszabja a lehetsdges kombin6ciok mennyis6gdt 6s komplexit6sat), valamint az otleteiraml6ssebessdge.Az fij kombin6ciok kialakit6satszigoru 6rtdkeldsnekkell kovetnie, amelyneksor6n szembesrilnek az otletek a kovetelmdnyekkel.A jelent6s kreativ termdk kiemeldse eszerint szelektivmtikoddseredmdnye.A m6sik ir6nyzat szerrntaz az alkotdsciliranyos, amelyet kezdett6l fogva korl6tok koze szorit a kitizott cdl. Ez az drtelmezdsa a. al azonositj kreativit6sttulajdonkdppena probldmamegold6ss Vajon egy algoritmusk6szftdsemelyik drtelembentekintheto kreatfv folyspatnak? V6lemdnyemszerintalapvetoenaz utlbbi drteieinben,hiszeneg)' fogva cilir6nl'os alkot6sbanval6sttl term6szetdndl algoritrnusuregkornpantilftsa rneg; azontranindgsemzdrhatjukki az elsc, a vdletlen eseritinynekkepzclt irjszeni produiiitim l6trehozhsat, amely ha adott esetben megsziiletik, a ez m/;gaklior is. lta all.:zrltnasint cdlirirnyosalhoi,lsnak"csak" "melidktermdke",
liu
a "mell6kterm6k" - objektiv 6rt6kel6sszerint (nem a c6lir6nyos aikot6s drt6kesebbnekbtzonyulhat,mint rnagaa celiranyos szempontj6boln6zve) "mell6kterm6k" mint alkot6s. Ilyen esetb'ena vdletlen esem6nykdntsztiletett igenis jelent6s kreativ termdk, pozitiv szelekci6 tdrgya lesz. Teh6t egy algoritmus k6szit6seelsosorbanc6lir6nyos alkot6s, amelyet kezdettol fogva korl6tok koz6 szorit a kitizcitt c61,ak6rh6nyszorel6fordulhat azonban,hogy a megold6si algoritmus kompon6l6s6nak folyamatdban, a l6pdsrol-ldpesre finomit6s sordnegy adott ponton akrtizott c6llal kimutathatokapcsolatbannerl 6116rn6sik,- rin. vdletlenszeru-,fumugyanakkorirjszertiproduktumis szriletik. feladatmegold6s pszichologiai vonatkozdsalal kapcsolatos A vrzsgtiodSsainkazt mutatj6k,hogy a probldmamegold6skognitiv elm6letei az algoritmikus feladatmegold6srais kiterjeszthetdk.Az algoritinihus szemi6letii megold6s az analogikus probl6mamegold6sr6vdn hozzf$itrul az algoritmikus szeml6letkiterjeszt6seheza tanitlsi-tanul6sifolyamat eg6szeben.
Iri;
Irodalom
Anderson,J.R.: The Adaptive Characterof Thought Hiltsdale,LawrenceErlbaumAssociates Cambridge,HarvardUniversityPress,1990. Barthdleffiy,J.P., Cohen,G. & Lobstein,A.: Algorithmic Complexity UCL Press,London,1996.256P. Benk6,A.p. - Bdrcesn6Nov6k,A. - Fial6n6,D6r, Zs. - Hosszti,F.- I.,ukfi;s,O. Nagy R6bertn6- 6ri, I. - Pentel6nyi,P. - Szek6rIstv6nn6: QuickBasic (Szerk.:Luk6cs,O. & Pentel6nYiP.) BDGMF jegyzet,199A.212P. B6kdsi,A. - Brtickner,H. - Dusza,A. - H6mori,M. - Kovdcs,E. . Pdrrzs,Gy.Sz[ics,E. - Varga, T.: SzitmitogdppelsegitettoktatSsfejlesztdsiir6nyzatar OMFB tanulmdny,Budapest,1982.1-90 pp. B6rcesn6Novak, A. - Fial6n6D6r, Zs. - Hossdr,F. - Luk6cs,O. NagyndFoldv6rszky,M. - Nagy Robertn6 - 6ri, I. - Penteldnyi,P.: szigorlat, ir6sbeli feladatokgy'tijtemdnye Matem atika-szdmititstechnika (Szerk.:Hossz6,F. Luk6cs,O.) SZAMALK, 1989. 162P. Biszterszky,E.: A programozottoktat6salkalmazilsilehetdsdgei6s kisdrleti fej 1eszt6se a mti szaki feIs6fokir int6 Trrlenyekben Kandid6tusi6nekez6stdzisei,1981.15 p. Biszterszky,E. - Gyaraki,F. F.: Didaktikai tanulm6nyokgyiijtemerlye MtiegyetemKiad6, Budapest,1996. B6dy,B. - Fekete,I. - Pallinger,F. - Schubert,T. - Zsigmond,A.: Sz6mitog6p-progt amozdsi utmutat6 6s p 6Id atftr MriszakiKonyvkiadS,Budapest,1981. 6A2p. Brtrckner,H. - Luk6cs, O. : A folyamat6br6ktola programozasrg, Budapest,l9B7. 356 p. Tankonyvkiad6, Buzan,T.: Use Your Hcari p. ]JBCBr:cl<s.1996.15,-t,
r20
Cotton,J.: The Theory of Learning Strategies KoganPage,London, 1995.156P. Dahl, O.J.- Dijkstra, E.W. - Hoare,C.A.R.: StnrcturedProgramming AcademicPress,London &. New York, 1972.220p. Dahl, O.J.- Dijkstra, E.W. - Hoare,C.A.R.: StrukturSltprogramozas Mtiszaki Konyvkiad6, Budapest,1978. 203 p. Dijkstra,E.W.: A Discipline of Programming Prentice-Hall,New York, 1976. Eysenck,M.W. & Keane,M.T.: CognitivePsychology PsychologyPress,[JK, 1997. 542 P. Eysenck,M.W . 8L Keane,M.T.: Kognitiv pszichol6gia NemzetiTankonyvkiad6,Budapest,1997.603 p. Fekete,I. : Sz6mit6stechnika Mriszaki Konyvkiad6, Budapest,1979Fekete,I. : Matematika6s sz6mit6stechnikaI., II. MuszakiKonyvkiad6,Budapest,1986.I.205 p., II. 300 p. integr6lt oktat6sa Fekete,I.: Matematika 6s szftmitftstechnika Kandid6tusi6rtekez6st6zisei,1986.7 p. kiserleti alkalmazasanak Fercsik,J.: Pro gramozotttechnikai berendezdsek vizsg6lataa miiszaki felsooktat6sban Kandid6tusi 6rtekez6st6zisei, 1973. Hosszir,F. - Nagyn6Foldv6rszki,M. - Nagy Robertne Fial6n6Ddr, Zs. - Pentel6nyi, P. Rudas,I.: irtmutato6sp6ldat6rI., (Rudas,I. szerk.) Matematika6s sz6mit5stechnika MuszakiKonyvkiad6,Budapest,19Bl . 5 14 p. in EnglishI. F.: Mathernatics Delr,Zs. - Ori, I. - Pentel6nyi, Fia16n6 BDlvfFjegyzet,1992.127p.
1 - r l
1^'-i
Gentnef,D.: The Mechanismsof Analogical Reasoning In Similarity and A;ralogicalReasonirg,eds.Vosniadou,S. & Ortony, A. CambridgeUniversity Press,1989. Green,T.R.: ProgrammingLanguagesas Information Structures AcademicPressLtd., London, 1990. Gries,D.: The Scienceof Programming Springer-Verlag,New York, 1981. 366 p. Griffiths, M. 8L Tagg,E.D.: The Role of Programmingin Teaching Informatics ElsevierSciencePublishers8.V., Amsterdam,199I.2I2 p. Gyaraki,F. F.: A megtanuland6algoritmusokszerepematematikaikorrepet6l6 programokk6szit6s6n6l Audio- vrzualisKozlemdnyek, 196715.36-47. pp. Gyaraki, F. F.: Algoritmusok a matematikatanitilsSban A matematikatanit6sa, 1969.janu6r,XVI. 6vf. l. szitm,l3-18. pp. Gyaraki,F. F.: Algoritmusok 6s algoritmikusel6fr6sokdidaktikai felhaszn6l6s6nak 6s optim alizfiilsfunaklehetSs6gei Kandiddtusi ertekez6s,1976. 20 P-
H5mori,M.: TanulSs6stanit6sszitmitogdppel Tankonyvkiad6,Budapest,1983. 239 p. H6mori, M.: TanulSs6s tanft6s szftmit6gdppel Kandidftusi6*ekezdst6zisei,1984.13 p. Harel,D.: Algorithmicsthe Spririt of Computing Harlow,England,1996.476p. Addison-Wesley, chnika koz6pfokon Het6nyi P51n6( szerk.) : Szdmit6ste OMIKK, Budapest,1987.275 P. T.R.G.,Samurcay,It. & Gilmore,D.J.: Hoc, J.M., Gi"t:en, FsychoIog)'of Prcgr"amining Academicllress,Lc;nrioll,i990. 290 pi.
r22
Hoyles,C. & Sutherland,R.: Logo Mathematicsin the Classroom Routledge,Londou, 1989.242 P. Knuth, D.E.: The Art of ComputerProgramming Addison-Wesley,Harlow, England,1997' 650 p' Koster, C.H.A. : Programoz6sfeli.iln{ zetben Mtiszaki Konyvkiad6,Budapest,1988.267 p' Landa, L.N.: Algoritmiziiils az oktat5sban Tankonyvkiad6,BudaPest,1969. L6n6rd,F.: A probl6mamegoldogondolkodds Akad6miai Kiad6, BudaPest,1'964. Lukdcs,O. - Pentel$nyi,P.: Ipari feladatokmatematikaistatisztikairnegold6sa szem6Iy r szfimitog6PPel XXVI. 6vf., december,1986. 541.p. G6pgy6rtSstechnol6gia, Luk6cs,O. - Pentel6nyi,P.: Mathematicsin EnglishIII. BDMF jegyzet,1993.229P. McCormick, C.B. & Pressley,M.: EducationalPsychology Longman,Harlow, England,1997. 522 P. Mclntyre, P.: TeachingStructuredProgrammingin the SecondarySchools KriegerPublishingComPanY,Malabar,Florida, l99l . 222 p. c. targy pentel6nyi,P.: Kie geszitesa Matematika6s Sz6mit6stechnika elSad6saihoz Budapest,1984.BDGMF. 136P. pentel6nyi, P.: A szitmithstechnika oktatdshvalkapcsolatosndhdnydidaktikai k6rd6s oktatoinak A mriszakifdiskol6k matematika,fizika 6s sz6mit6stechnika X. orsz6gostan6cskozasa Budapest,1986.BDGMF. 13.P.
1:3
c. Pentel6nyi,P.: M6dszertanikis6rleteka Matematika6s Sz6mftSstechnika tdrgy esti tagozatontortdn6 oktat6s6ban Jubileumitudom6nyosiildsszak 1989.BDGMF.IIT-1 19.p. Budapest,
szabiiyok"tanit6s6rol Pentel6nyiP.: M6dszertanigondolatokaz"Irrt.egr6l6si FSiskol6k matematika,frzika 6s szftmithstechnikaoktat6inak XVI. orsz6gos konferencif$a Szombathely,1992.BerzsenyiD6niel TanftrkepzoF6iskola.11.p. Pentel6nyi,P.: The Possibilitiesof Forming and DevelopingAlgorithmic Thinking when Teaching Various Subjects EngineeringEducationWorld Congress,Wien-Budapest,1996. in Educationby Communication,ed. Melezinek, A. &, Kiss, I. 525-528.p. Pentel6nyi,P.: Seg6danyagaz Informatika M6dszertanc. tantdrgyhoz BDMF elektronikusjegyzet,1996.845021.,1.09MB. Pentel6nyi,P.: Tanithat6-ea probl6mamegold6s? Gondolatokaz algoritmikusfeladatmegold6stanit6s6r6l6s az algoritmusszeml6ltet6sr6l XLV[. 6vf. m6rcius, 1997. 26-27.p. SzakoktatSs, Pentel6nyi,P.: Algoritmikus szeml6lettioktat6s 1997.53-55.p. Gdp,IL. 6vf. szeptember, Pentel6nyi,P.: SomeHistorical andProfessionalLinguistic Aspects of Teaching Algorithmic Problem Solving PhD-program BME, Szakk6pzdspedag6giai II. tudomSnyosszemindriuma,1997. 6 p. Pentel6nyi,P.: Can ProblemSolvingbe Taught? EngineeringEducation'97, IGIP Symposium,Klagenfurt, 1997. in Overinformed - Undereducated? , ed. Melezinek,A. 293-296.p. Penteldnyi,P.: Developmentof Algorithmic Thinking LigaturaLtd., Budapest,1998.253p.
't.iA | ,::-.i
pentel6nyi,p.: The possibilitiesand Methodsof the Formationand Development of Algorithmic Thinking in TechnicalTraining Thesesof DoctoralDissertation,Budapest,1998.,10 p. pentel6nyi,p.: A mintapdld6kszerepeaz algoritmrzftl5stanit6si-tanul6si folyamatftban Szemle,XV.6vf., 1999.60-64'pp' Szakk6pzesr P61ya,G.: How to Solve it? PrincetonUniversityPress,1990.253 p. Ralston,A. &, Neill, H.: Algorithms HodderHeadlinePlc., London, 1997. 186 p. Robertson,L. A.: SimpleProgramDesign NelsonITP, Cambridge,1997.203P. Shen,A.: Algorithms and Programming Basel,1997.2I7 P. Birkhauser, Skinner,B.F.: Scienceand Human Behavior New York, FreePress,1953. Stone,R.G. & Cooke,D.J.: ProgramConstruction Cambridg.UniversityPress,Cambridge,1990.372 p. Vigh, A. : Az \paroktat6stortdnete Budapest,1932. Wallas,G.: The Art of Thought New York, HarcourtBrace Jovanovich,1926. Wirth, N.: Algoritmusok + adatstrukturdk: programok MuszakiKonyvkiad6,Budapest,1982.345p.
r25
