Építészet | Tanulmányok, Esszék » Gépi algoritmus, számítógépi program

Paláncz Béla, Építőmérnöki Informatika (2005/2006) 3. Gépi algoritmus - számítógépi program "A tervező nem akkor tudja, hogy tökéleteset alkotott, ha már nincs mit hozzátenni, hanem ha nincs mit elvenni " Antoine de Saint-Exupéry Bevezetés Az informatika központi kérdése, hogy miként hajhatunk végre egy algoritmust számítógéppel.A digitális számítógépek az információt bináris (0,1) formában "értelmezik". Ennek megfelelően, ha egy számítást meg akarunk valósítani, akkor géppel bináris formában kell közölni, hogy mivel mit kell csinálnia. Következésképpen az adatokat (mivel) és a végrehajtandó programot (hogyan, mit) is bináris reprezentációban kell megadni. Neumann János volt az, aki azt javasolta, hogy az adatokat és programokat egy helyen, a gép memóriájában tárolják. Tekintsünk egy egyszerű algoritmust, egy aritmetikai műveletet, d = (a + b) / 2 - c Ennek a számítógépi megvalósítását a

következőképpen képzelhetjük el. Itt a bináris számok helyett most tízes számrendszerbeli számokat alkalmaztunk. Tételezzük fel, hogy az input (a, b, c) és output (d) adatok az alábbi memória címeken helyezkednek el, Cím 06 07 08 09 Tartalom a b 2 c Maga a program pedig az alábbi memória címeken található, Cím 01 02 03 04 Tartalom 1 06 07 10 4 10 08 10 2 10 09 10 00 Azaz, első utasításként a 06 rekesz tartalmát adjuk (jele 1) hozzá a 07 rekesz tartalmához és az eredményt tegyük a 10 rekeszbe. Majd a 10 rekesz tartalmát osszuk (jele 4) el a 08 rekesz tartalmával és az eredményt tegyük 10 rekeszbe. Végül a 10 rekesz tartalmából vonjuk (jele 2) le a 09 rekesz tartalmát és tegyük az eredményt a 10 rekeszbe és fejezzük be a műveletek végrehajtását. Természetesen, ha így kellene leírnunk egy algoritmust akkor az nagyon fáradságos munka lenne. Ma már elegendő a következő utasításokat megadni, >> a = b; b = 34; c = 8;

>> d = (a + b)/2 - c d = 14 Tehát az algoritmus lépéseit a matematikában megszokott módon írhatjuk le, amelyet a számítógép "lefordít" magának a saját bináris nyelvére. Számítógépi programnak az algoritmus számítógép által értelmezhető (interpretálható) megjelenési formáját (reprezentácíóját) nevezzük. Programszerkezetek Az algoritmusok leírása általában nem oldható meg az utasítások egyszerű, egymásutáni (szekvenciális) felsorolásával. Gondoljunk például az euklideszi algoritmusra, ahol egyrészt az, hogy milyen műveletet kell elvégeznünk, egy feltétel igaz vagy hamis voltától függ, ha a > b akkor a:= a - b ha b > a akkor b:= b - a másrészt az, hogy meddig végezzük a megfelelő kivonások ismétlését, szintén egy feltételtől függ, ha a = b akkor leállás Az ún. struktúrális programozási forma három alapvető programszerkezetet alkalmaz, amellyel számítógépen megvalósítható

algoritmusok többsége leírható. Ezek a szekvencia, az elágazás és az ismétlés. Szekvencia Mint már láttuk, ez a legegyszerűbb programszerkezet. Itt az utasítások ( az algoritmus lépéseinek programszintre lebontott egysége) egyszerűen egymást követően kerülnek végrehajtásra. Elágazás Az elágazás általános alakja, IF feltétel THEN utasítás(ok) ELSE utasítás(ok); END Példaként tekintsük az ún. Collatz sorozat képzési szabályát, amely egy pozitív egészből (n) kiindulva a következő szabály alapján állítja elő a sorozat következő tagját, HA n páros AKKOR n / 2 KÜLÖNBEN 3 n + 1 function y = c(n) if mod(n, 2) == 0 y = n/2; else y = 3*n + 1; end >> c(3) ans = 10 >> c(34) ans = 17 Számlálással vezérelt ismétlés A számítógépi programok esetén gyakorta előfordul, hogy adott utasítást vagy utasításokat ismételten végre kell hajtani. Ha előre ismerjük az ismétlések számát akkor számlálással

vezérelt ismétlésről beszélünk. Ennek általános szerkezete, FOR ciklus változó FROM ciklus változó kezdőértéke TO ciklus változó végértéke ciklusmag: utasítás(ok) ; END A ciklus változó egészszám és rá értékadó utasítás a cikluson belül nem végezhető. Tegyük fel, hogy egy lista elemeinek összegét kell előállítani, >> >> >> >> L = [1 2 56 - 11 89]; s=0; for i = 1 : 5 s = s + L(i); end s s = 137 Feltétellel vezérelt ismétlés Van olyan eset, amikor nem ismerjük előre az ismétlések számát, ismerünk azonban egy feltételt, amely fentállása esetén az ismétlés végrehajtandó, ellenkező esetben befejezendő. A feltétellel vezérelt ismétlés általános szerkezete, WHILE feltétel utasítás(ok) ; END Állítsuk elő egy adott n számhoz tartozó Collatz sorozatot, amelynek utolsó eleme 1. >> n = 5; >> while n ~= 1 n = c(n); display(n); end n = 16 n = 8 n = 4 n = 2 n = 1

Programtervezés módszerei A programok tervezésénél, a program írásánál, egyrészt azokat a szempontokat vehetjük figyelembe, amelyeket az algoritmusok minősítésénél már megismertünk, azaz a hatékonyság (rövid futási idő), hatékonyság (minél általánosabb használhatóság). Ezeken kívül nagyon fontos, hogy a megírt program könnyen áttekinthető legyen, az esetleges hibákat aránylag kevés munkával ki tudjuk javítani, valamint a már megírt program más megírandó programok számára építőkőként felhasználható legyen. A programírásnál a rövid és jól követhető, világos program gyakran elsőbbséget élvez a rövid futási idővel szemben, lásd rekurzió. Modularitás A modularitás elve abból az algoritmus tervezési technikából ered, amely alapján a megoldandó problémát részfeladatokra bontjuk, majd a részfeladatokat külön kezelve, azokat további részfeladatokra bontjuk, azaz a feladat megoldásának lépéseit

fokozatosan finomítjuk. A modul maga, mint önálló programozási egység, csak az input és output változókon keresztül lép kapcsolatba a "külvilággal", azaz a program más moduljaival, eltekintve bizonyos, ún. globális tipusú, azaz minden modul által hozzáférhető változóktól. A mai programozási nyelvekben a modul megjelenési formája a függvény, amelynek, mint azt a matematikában megszoktuk, van neve és argumentuma. Például az ismert trigonometrikus függvényt tekintve, sin(x) A függvény neve sin az argumentuma pedig x. A függvény argumentumában szereplő változók képviselik az input adatokat és a függvény neve, mint változó adja vissza az eredményt, azaz az outputot. >> z = pi/2 z = 1.5708 >> sin(z) ans = 1 Az eredményt, az outputot, célszerű mindig egy (vagy több) változóhoz hozzárendelni, annak érdekében, hogy azzal további számításokat tudjunk végezni. >> u = sin(z); >> y = 5*u^2 - 3.5

y = 1.5000 A modularitással kapcsolatban három fontos fogalompárral kell megismerkednünk: - formális és aktuális paraméter - lokális és globális változó - cím és értékszerinti paraméterátadás Formális paraméternek nevezzük azokat az inputváltozókat, amelyekkel definiáljuk a modult. Az aktuális paraméterek pedig azok, amelyekre alkalmazzuk. Két szám összeadására írjunk egy modult, function y = add(a, b) y = a + b; Itt a és b változókat nevezzük formális paramétereknek. Legyen most u1 és u2 aktuális paraméter >> u1 = 45.6; u2 = 812; >> add(u1, u2) ans = 53.7200 Lokális változónak azt a változót nevezzük, amelyet csak a modulon belül értelmezünk. function y = add(a, b) w = a + b; y = w; A MATLAB a nem input változót automatikusan lokális változónak tekinti, >> w ?? ? Undefined function or variable w. >> add(4, 5) ans = 9 >> w ?? ? Undefined function or variable w. A globális változó, ezzel

szemben a modulon kivül is értelemezett, így adatátadásra is alkalmas. function y = add(a, b) global w; w = a + b; y = w; Legyen most, >> w ?? ? Undefined function or variable w. >> add(7, 8) ans = 15 >> w ?? ? Undefined function or variable w. >> global w >> w w = 15 >> w = 34 w = 34 >> w w = 34 >> add(7, 7) ans = 14 >> w w = 14 Az adatátadás során az aktuális változó értékét átadjuk a formális változónak. Ennek egyik módja, hogy az aktuális változót "átnevezzük" és mint formális változók kezeljük (címszerinti átadás). A másik, a mai programnyelvekben alkalmazott módszer, amikor az aktuális változó tartalmát átmásoljuk egy többnyire lokális változóba és ezt tekintjük formális paraméternek (értékszerinti átadás). A Collatz sorozat egy rákövetkező tagjának számítására alkalmas modul, function y = ali(x) x = x/2; y = x; A modul alakja és a programszerkezetek

konkrét alakja az egyes programozási nyelvekben eltérhet. Egyik modul felhasználható egy másik modul elkésztéséhez. Például tegyük fel, hogy rendelkezünk egy modullal, amely két síkbeli pont távolságát határozza meg, xy1:=[x1, x1] és xy2:=[x2, y2]. function y = dist(xy1, xy2) y = sqrt((xy1(1) - xy2(1))^2 + (xy1(2) - xy2(2))^2); Legyenek a két pont koordinátái (0,0) és (1,1), >> a = [0 0]; b = [1 1]; >> dist(a, b) ans = 1.4142 Írjunk, most egy olyan modult, amely meghatározza egy sokszög kerületét, ha ismerjük a csúcsok koordinátáit. A koordinátákat egy listába helyezzük el úgy, hogy az első csúcs koordinátai a lista végén is szerepelnek. Például egy origó középonttú négyzet esetén, H := [[1, -1], [1, 1], [-1, 1], [1, -1], [1, -1]] function y=circ(L) n=length(L)-1; s=0; for i=1:n s=s+dist(L(i,:),L(i+1,:)); end; y=s; Legyen tehát az input, >> H=[1 -1;1 1;-1 1;-1 -1;1 -1] H = 1 1 -1 -1 1 -1 1 1 -1 -1 >>

circ(H) ans = 8 A moduláris programszerkezetnek a legfontosabb előnyei: 1) Egyszerre, egymástól függetlenül is dolgozhatnak ugyanazon feladat részfeladatain. 2) Egy modul önmagában is ellenőrizhető, tesztelhető, így könnyebb a hibákat javítani. 3) Egy modul más feladat részfeladatainál is felhasználható, programkönytárakat hozhatunk létre. Rekurzió A rekurzív technika jellemzője, hogy a modul önmagát hívja, csak más változokkal. Példaként határozzuk meg a Fibonacci számokat, amelyek definiciója a következő, F(n+1) = F(n) + F(n-1) ahol F(1) = F(2) =1 Az n-edik Fibonacci szám előállítása a következő rekurzív modullal lehetséges, function y=fibor(n) disp(n); if or(n==1,n==2) y=1; else y=fibor(n-1)+fibor(n-2); end; Például az F(4) értéke, >> fibor(4) ans = 3 A modul müködését jól láthatjuk, ha nyomon követjük a végrehajtás egyes lépéseit, >> fibor(4) 4 3 2 1 2 A gép az alábbi fák járja be Ugyanez

iteratív módon megírva function y=fibo(n) f1=1;f2=1; if or(n==1,n==2) y=1; return end for i=3:n f3=f1+f2; f1=f2; f2=f3; end; y=f3; Ezzel >> fibo(7) ans = 13 A rekurzív megoldás általában egyszerűbb, elegánsabb, mint az iteratív, de futási ideje jóval hosszabb és igen nagy a komplexitása is. >> n=1000:2000:9000 n = 1000 3000 5000 7000 9000 >> for i=1:5 tic; fibo(n(i));t(i)=toc;end >> t t = 0.0001 0.0005 0.0012 0.0018 0.0025 >> n=5:5:25 n = 5 10 15 20 25 >> for i=1:5 tic; fibor(n(i)); t(i)=toc;end >> t t = 0.0002 0.0013 0.0144 0.1771 1.7830 Ennek oka az, hogy a rekurzí kiértékelés során a számítógép egy speciális adatszerkezet, a vermet alkalmazza arra, hogy lebontsa a feladatot az ún.báziskritériumig A Fibonacci sorozat esetében ez az F(1) = F(2) =1 és a lebontás lényegében egy bináris fa felépítése.A báziskritériumot elérve, visszafelé haladva, a fa csomópontjainak numerikus

kiértékelése a második, a numerikus eredményt szolgáltató fázis. Vannak olyan esetek, amikor az iteratív megoldás nagyon bonyolult, lásd Hanoi tornyai. Program végrehajtása A program végrehajtása a programnyelvtől függően lehetséges ún. interpreter módban, hardverlebegőpontos ( a számítógép közvetlenül a processzor utasításkészletét használja) vagy szerkesztett (compiled) verzióban. Az utóbbi két esetben a programban szereplő változók típusát pontosan meg kell adni, deklarálni kell. Mivel az eljárás neve is, mint változó szerepel ezért szükség van az eljárás nevének típusára is. A Matlab közvetlenül nem ad lehetőséget szerkesztett verzió alkalmazására. Ehhez a C nyelv használata szükséges (MEX file). Itt a Maple-ben mutatunk példát a hardver-lebegőpontos megoldásra és a szerkesztett megoldásra, mivel a Maple saját szerkesztővel és fordítóval rendelkezik és képes közvetlenül végrehajtható ún. *.DLL

file-ok létrehozására Az interpreter változat > > > > > > > po:=proc(a,n,x) local s,i; s:=0; for i from 1 to n do s:=s+a[i]*x^(i-1); od; s end proc: A hardver-lebegőpontos megoldás egy n-1-ed fokú polinom kiértékelésére, > p:=proc(a::Array( datatype = float[ 8 ),n::integer,x::float)::float; local s::float,i::integer; > s:=0.0; > for i from 1 to n do > s:=s+a[i]*x^(i-1); > od; > s > end proc: ] Ennek a modulnak a szerkesztett verziója: > cp := Compiler:-Compile( p ); cp := proc( ) option call external, define external( m335ba7f51913b1d5a021d915c947156c, MAPLE , LIB = "C:DOCUME~1ADMINI~1LOCALS~1TempAdministrator-1 300 m335ba7f51913b1d5a021d915c947156cirbx50dp.dll" ); call external(0, 148377616, true, args) end proc Legyen most egy kiértékelendő polinom fokszáma n1, az együtthatók tömbje a1 és a kiértékelés helye x = 0.99 > n1:=50000: > a1:=Array(1.n1,u->evalf(u),datatype=float[8]): >

time(po(a1,n1,0.99)); 3 .171 > time(p(a1,n1,0.99)); 3 .141 > time(evalhf(p(a1,n1,0.99))); 0 .109 > time(cp(a1,n1,0.99)); 0 .015 Láthajuk, hogy azt interpreter módban mindkét alak azonos futási időt igényel. Az evalhf (evaluation with hardver-floating-point) függvénnyel az interpreter módban is egy nagyságrenddel csökken a futási idő. A szerkesztett verzió kiértékelése pedig még ehhez képest is egy nagyságrenddel kisebb időt igényel. Azaz általánosan is igaz, hogy a szerkesztett verzió gyakorlatilag két nagyságrenddel gyorsabb, mint az interpreter verzió. Funkcionális programozás A funkcionális programozás esetén nem írunk modult, hanem megpróbáljuk az algoritmust beépített függvények segítségével leírni. Ennek előnye kettős Egyrészt jóval egyszerűbb és áttekinthetőbb lesz a programunk, amely lényegében egy függvénydefinicióra egyszerűsödik, tehát kevesebb a programozási munka. Másrészt, miután a

beépített függvények általában magaszintű nyelven profi szoftverfejlesztők által írt modulok, amelyeket beépítettek a alkalmazói rendszerbe, így sokkal gyorsabb a végrehajtásuk is. Először az általunk írt M-file, function y=evalpoly(a,n,x) s=0; for i=1:n s=s+a(i)*x^(i-1); end; y=s; >> tic; evalpoly(a,50000,0.99); t=toc;t t = 0.0574 Majd tekintsük az előbbi polinom helyettesítési értékét kiszámító függvény helyett, a funkcionális alakot, >> a=1:50000; >> tic; polyval(a,0.99);t=toc;t t = 0.0078 Nagyságrendileg kisebb futási idő, gyakorlatilag nincs programozás és mindenki, aki alapvető matematikai kultúrával rendelkezik érti miről van szó. A mérnök akkor jár el helyesen, ha lehetőség szerint ezt a "programozási módszert" választja! Még egy megjegyzés a végrehajtás sebességét illetően, az, hogy a Matlab beépített verziója gyorsabb, mint a Maple szerkesztett verziója. Programozási hibák A

programozás egyesek szerint művészet, mások szerint egyszerű, mechanikus tevékenység. Bárhogyan is legyen, mindig célszerű szemelőtt tartani a következő szempontokat: a) A számítógép nem ember, tehát csak azt hajtja végre és úgy, ahogy azt a program utasításai számára előírják, általában nem rendelkezik előfelételezésekkel, amit mi sokszor természetesnek tekintünk. b) Ragaszkodik a hibátlan szintaktikához. c) Bármilyen jó is a programunk, ha a bemenő adatok hibásak, az eredmény is az lesz (garbage in garbage out). A fentieknek megfelelően a program lehet szintaktikailag hibás, mert a programnyelv szabályait nem tartottuk be. Ilyenkor általában a program nem is fut le Lehet a program szintaktikailag hibátlan, de szemantikailag hibás, azaz fut, de mást számol, mint amit mi szeretnénk, mert az adott matematikai kifejezésnek nem megfelelő utasítást írtunk a programban vagy ami még rosszabb, bizonyos speciális eseteket nem

kezeltünk le. Végül, lehet a programunk szintaktikailag és szemantikailag is hibátlan, ha a bemenő adatok hibásak az eredmény is az lesz. Végül ne feledjük azt, hogy hasonlóan ahhoz a közmondáshoz, miszerint nem az a legény aki nagyot üt, hanem az aki azt állja, nem az a nagy dolog ha valaki hibátlan programot ír, hanem az ha valaki megtalálja a hibát. Epilogus A programozással kapcsolatos ismeretek messze meghaladják nem csupán egy előadás, de a teljes szemeszter terjedelmét is, tehát a mérnök feladata nem is az, hogy programokat írjon. Manapság az olyan integrált programrendszerek, mint a Mathcad, Maple, Mathematica és MATLAB nagyszámú beépített, azaz a rendszer fejlesztői által megírt függvénnyel rendelkeznek, amelyek megfelelő használata tekinthető a mérnöki feladatának. Ezzel kapcsolatban, tehát a mérnöknek meg kell tudni fogalmaznia a problémáját fizikailag, műszakilag és matematikailag. Továbbá a

számítástechnikai ismeretek birtokában meg kell határoznia a megfelelő algoritmust úgy, hogy ilyen rendszerek függvényeit alkalmazni tudja a legkevesebb programozási munka befektetésével. Ezeknek a függvényeknek az értelmes használata szükségessé teszi, hogy tisztában legyen az adott függvény által megvalósított algoritmus előnyeivel, hátrányaival és korlátaival. Ehhez elkerülhetetlen a numerikus módszerek alapvető ismerete. Mivel a mérnöki gyakorlatban elsősorban különböző alternatívák (változatok) gyors és gyakorta egyszeri vizsgálatára van szükség, ezért az integrált rendszerekben történő funkcionális programozást kell elsősorban előnyben részesíteni, hiszen itt a programozási (nem az algoritmizálási) munka elhagyagolható illetve kiméretete a teljes mérnöki tevékenység mértékével összhangban van. A magaszintű nyelvekre szoftverfejlesztés esetében van szükség, amikor egy programot, mint terméket kell

előállítani, amelyet több száz alkalmazó, több száz vagy ezer alkalommal fog lefuttatni. Ellenőrző kérdések 1. Mit nevezünk számítógépi programnak? 2. Írjon programot egy magas és egy "alacsony szintű" nyelven egy egyszerű aritmetikai kifejezés kiértékelésére! 3. Milyen programszerkezeteket ismer? Jellemezze őket! 4. Adjon példát az egyes programszerkezetek megvalósítására! 5. Mit értünk a modularitás elvén? Milyen fogalompárokat definiálhatunk ezzel kapcsolatban? 6. Milyen előnyei vannak a modularitás megvalósításának? 7. Mit nevezünk rekurziónak? Melyek az előnyei és hátrányai? 8. Milyen programvégrehajtási módokat ismer? Előnyök és hátrányok? 9. A modern, integrált rendszerekben milyen programozási módszert célszerű alkalmazni és miért? 10. Milyen programozási hibákat különböztethetünk meg? 11. Mi különbség szoftverfejlesztés célú és a mérnöki feladatmegoldás céljából végzett

programozás között?