Architecture | Studies, essays, thesises » Algoritmus

Paláncz Béla, Építőmérnöki Informatika (2005/2006) 2. Algoritmus "Egy matematikustmegkérték, írja le azokat a lépéséket, amelyek során a jégből gőzt állíthatunk elő. Miután ezt megtette, következő feladatként megkérték írja le azokat a lépéseket, amelyek során a vízből gőzt állítunk elő. A válasza a következő volt: Annak érdekében, hogy ezt a második feladatot visszavezethessük az első feladatra,fagyasszuk a vízet jéggé, majd alkalmazzuk az első feladat megoldását." Bevezetés Az előadásban az informatika két legfontosabb fogalma kerül bemutatásra, az adat és az algoritmus. Láttuk, hogy aprobléma megoldása megfelel az információ átalakításának és új információ előállításának. Ennek során, a kiinduló információból, amelyeket az egyenletek és a mért, számszerűen ismert értékek reprezentálnak, egy eljárással, műveletek véges sorozatával előállítjuk a megoldást, az új információt.

Az információ megjelenési formáját adatnak, az átalakításhoz szükséges lépések sorozatát algoritmusnak nevezzük. Ez a szemléletmód arra szolgál, hogy a megoldást automatizálhassuk, azaz, számítógéppel elvégeztethessük. Ezzel kapcsolatban a következő kérdések megválaszolása alapvető: - hogyan lehet egy algoritmust megadni és számítógéppel végrehajtatni? - található-e minden problémára algoritmus? - hogyan lehet egy algoritmust elemezni, minősíteni? A következőkben az algoritmus fogalmát vizsgáljuk részletesebben. Az algoritmus fogalma A legegyszerűbb algoritmusok, azok a szabályok, amelyek szerint a tízes számrendszerben a négy alapműveletet elvégezzük. Ilyen szabályokat először a IX században élt arab matematikus al-Kvarizmi javasolt, akinek a nevéből származtatják az algoritmus szót. Algoritmusnak olyan egyértelmű előírást nevezünk, amely meghatározza, hogy egy adott feladatosztályhoz tartozó feladatok

megoldásakor, milyen műveleteket, milyen sorrendben kell végrehajtanunk. Az algoritmusnak végesszámú lépésben kell előállítania a megoldást Példaként tekintsük két természetes szám legnagyobb közös osztójának előállítását. Nyilván annyi ilyen feladat van ahány számpár képezhető. Elsőként nézzük a megoldást, amely a definiciót követi. Tekintsünk két számot, mondjuk, >> a = 9;b = 12; Határozzuk meg az osztóikat! (a divisiors function d=divisiors(x) k=1;r(k)=1; i=2; xf=round(x/2); while i<=xf if mod(x,i)==0 k=k+1; r(k)=i; end i=i+1; end d=r; >> da=divisiors(a) da = 13 >> db=divisiors(b) db = függvény nem beépített függvénye a Matlab-nak!) Page 5 12346 A közös osztókat a két halmaz metszete adja, >> dab=intersect(da,db) dab = 13 A közös osztók legnagyobbika pedig, >>max(dab) ans = 3 Foglaljuk össze a fenti lépéseket egy függvénybe, amelynek bemenete a két kérdéses szám, a ésb,

kimenete pedig a LKO(a,b), function y=LKO(a,b) y=max(intersect(divisiors(a),divisiors(b))); >> LKO(9,12) ans = 3 Euklidesz egy másik algoritmust javasolt, nevezetesen ha b = 0 akkor LKO(a,b) = 0 különben LKO(a,b) = LKO(b, mod(12,9)) Függvény formájában, function y=gcdR(a,b) if b==0 y=a; else y=gcdR(b, mod(a,b)); end >> gcdR(9,12) ans = 3 A beépített függvénnyel, >> gcd(9,12) ans = 3 Nyilvánvaló, hogy a függvény kommutatív >> gcd(a,b)==gcd(b,a) ans = 1 Mindhárom függvény egyenértékű, >> gcd(a,b)==gcdR(a,b) ans = 1 továbbá >> LKO(a,b)==gcd(a,b) ans = 1 Numerikus és nem-numerikus algoritmusok Az algoritmusok két nagy csoportját szokás megkülönböztetni. Az ún numerikus algoritmusokat, amelyek általában számokkal végeznek műveleteket, azaz elsősorban aritmetikai műveleteket végeznek, ellentétben a nem-numerikus műveletekkel ahol az aritmetikai műveletek szerepe minimális. Példaként lássunk egy numerikus

algoritmust, amely egy szám négyzetgyökét állítja elő. A négyzetgyökvonás valójában egy másodfokú egyenlet megoldását jelenti, hiszen egy a szám Page 6 négyzetgyökét a következő egyenlet definiálja, Az egyenlet megoldására az ún. Heron algoritmust alkalmazhatjuk, azaz ahol, Definiáljuk ezt az algoritmust szintén egy függvény formájában, function y=Sqrt(a,i) if i==0 y=a; else y=0.5*(Sqrt(a,i-1)+a/Sqrt(a,i-1)); end >> format long >> Sqrt(2,2) ans = 1.416666666666 Növelve az iterációs lépések számát a közelítés egyre jobb lesz, >> error3=abs(Sqrt(2,3)-sqrt(2)) error3 = 2.123901414519125e-006 >> error5=abs(Sqrt(2,5)-sqrt(2)) error5 = 2.220446049250313e-016 Azaz 15 tizedesjegyre 5 iteráció után már nincs eltérés. Mekkora a hiba 30 tizedesjegy pontosság esetén? Ennek meghatározását a Maple-ben végezzük el! function y=gyok(a,n) if n==0 y=a; else y=(gyok(a,n-1)+a/gyok(a,n-1))/2; end; Először végezzük

el a számítást 10 illetve 20 jegy pontossággal >> digits(10) >> error=abs(sqrt(2)-gyok(sym(2),sym(3))) error = -2^(1/2)+577/408 >> vpa(error) ans = .2124e-5 >> error=abs(sqrt(2)-gyok(sym(2),sym(5))) Page 7 error = -2^(1/2)+886731088897/627013566048 >> vpa(error) ans = 0. >> digits(20) >> vpa(error) ans = 0. majd 30 tizedesjegyre >> digits(30) >> vpa(error) ans = .89929e-24 >> error=abs(sqrt(2)-gyok(sym(2),sym(7))) error = 4946041176255201878775086487573351061418968498177/3497379255757941172020851852 070562919437964212608-2^(1/2) >> digits(30) >> vpa(error) ans = 0. >> digits(50) >> vpa(error) ans = 0. >> digits(100) >> vpa(error) ans = .29e-97 Minden iterációs lépésszámhoz adható egy tizedesjegyszám, amelyre a hiba zérusnál nagyobb, azaz csak közelítő megoldás adható. Ez a jelenség alapvetően jellemző a numerikus algoritmusokra, azaz csak közelítő megoldást

eredményeznek. A nem-numerikus algoritmusokra egy példa, egy lista maximális elemének megkeresése. function s=maxi(v) n=length(v);s=v(1); for i=2:n if v(i)>s s=v(i); end end Legyen egylista a következő, >> a=[1 -23 89 1 123 -81] a = 1-23891123-81 >> maxi(a) ans = 123 vagy egy másik lista esetén, ahol a lista elemei karakterek, >> b=[k; j; s; p;a] b = k j s Page 8 p a >> maxi(b) ans = s Az algoritmusok tulajdonságai Mivel egy feladat megoldása különböző algoritmusokkal lehetséges, ezért valamilyen szempont (ok) szerint érdemes minősíteni őket. Általában az alábbi három tulajdonságot szokták vizsgálni Hatásosság A hatásosság alatt azon feladatosztály nagyságát értjük, amelynek elemeire az algoritmus alkalmazható. Az egyik algoritmus hatásosabb a másiknál, ha az általa megoldható feladatok osztálya bővebb, mint a másik algoritmus által megoldható feladatok osztálya. Tekintsünk egy egyszerű példát.

Definiáljuk az alábbi függvényt, function y=f1(x) y=sin(x)/x; >> f1(-1.2) ans = 0.77669923830602 >> f1(2.1) ans = A függvény, mint algoritmus, az x = 0 helyen nincs értelmezve, >> f1(0) Warning: Divide by zero. > In f1 at 2 ans = NaN Egy másik függvény, mint algoritmus, amelynélaz x = 0 helyhez, mint helyettesítési értékhez ahatárértéket rendeljük, >> syms x >> limit(sin(x)/x) ans = 1 function y=f2(x) if x~=0 y=f1(x); else y=1; end >> f2(2.1) ans = 0.41105207935661 >> f2(0) ans = 1 A fenti függvények sorrendje a hatásosság növekvő skáláján f1(x) < f2(x). Hatékonyság Bizonyos algoritmusok gyorsabbak, kevesebb műveletet vagy memóriát igényelnek, mint mások. Ilyen szempontból beszélhetünk, futási idő, illetve műveleti hatékonyságról, valamint memóriafelhasználási hatékonyságról. Egy algoritmus hatékonyabb a másiknál ha gyorsabb, kevesebb egyenértékű művelettel végzi el a feladat

megoldását, illetve kevesebb a memória Page 9 igénye, mint a másik algoritmusnak. Példaként tekintsük egy n-ed fokú polinom adott x = x0helyen történő kiértékelésének a feladatát. Az első algoritmust, nevezzük közvetlen kiértékelésnek, function y=poli(a,n,x) s=0; for i=1:n+1 s=s+a(i)*x^(i-1); end y=s; Egy 8-ad fokú polinom esetén, >> a=1:9 a = 123456789 >> syms x >> poli(a,8,x) ans = 1+2*x+3x^2+4x^3+5x^4+6x^5+7x^6+8x^7+9x^8 A második algoritmus az ún. Horner elrendezés, >> horner(poli(a,8,x)) ans = 1+(2+(3+(4+(5+(6+(7+(8+9*x)x)x)x)x)x)x)x Maple segítségével, mindkét esetben előállíthatjuk a kiértékeléshez szükséges műveletek számát. Most lehetőség van a Matlab-ból hívni a Maple-t. >> maple(codegen[cost],poli(a,8,x)) ans = 8*additions+36multiplications >> maple(codegen[cost],horner(poli(a,8,x))) ans = 8*additions+8multiplications Mivel a szorzási műveletek közel egy nagyságrenddel több

időt igényelnek, mint az összeadás, nyilvánvaló, hogy a második algoritmus a hatékonyabb. A Horner elrendezést alkalmazó függvény: function y=poliH(a,n,x) s=a(n+1); for i=1:n s=s*x+a(n+1-i); end y=s; A két függvény nyilván egyenértékű. Például >> poli(a,8,x)==expand(poliH(a,8,x)) ans = 1 Végezzünk el egy numerikus kísérletetn = 1 000 000 és x0= 99/100 esetére, és hasonlítsuk össze a futási időket. >> tic; a=1:1000001;poli(a,1000000,99/100);t=toc;t t = 0.59599166933228 Page 10 >> tic; a=1:1000001;poliH(a,1000000,99/100);t=toc;t t = 0.02822565437786 Jól látszik, hogy közelítően egy nagyságrendi különbség adódik a futási időben a két algoritmus között. Komplexitás Egy algoritmus komplexitását, azzal mérjük, hogy a feladat méretének növelésével, milyen arányban növekszik a megoldáshoz szükséges idő. Tekintsük az első n pozitív egészszám összegzésének feladatát. Ismert, hogy Gauss 9 éves

korában a következő algoritmust alkalmazta, >> syms n i >> maple(factor(simplify(sum(i,i=1.n)))) ans = 1/2*n(n+1) Azaz egy összeadás, egy osztás és egy szorzás, függetlenül a feladat méretétől, azaz az összeadandó számok számától. A direkt összeadás esetén n - 1 darab összeadásra van szükség, nevezetesen1 + 2 + 3 +.+ n, A direkt módszer function y=summi(n) s=0; for i=1:n s=s+i; end; y=s; A Gauss módszer function y=Gaussum(n) y=n*(n+1)/2; Nézzük a direkt módszer futási idejének alakulását n = 1 000 000 ésn = 25 000 000 között, 6 000 000 lépésközzel. Először az általános modul function y=timesum(n0,dn,n) k=1; for i=n0: dn: n tic; summi(i); t=toc; r(k)=t; tic; Gaussum(i); t=toc; q(k)=t; k=k+1; end; y=[r;q]; >> timesum(1000000,6000000,25000000) ans = 0.009700682011560173102254 0.000000000000000000000000 >> n=[1 7 13 19 25];t=[97 682 1156 1731 2254]; >> plot(n, t,d); Page 11 1. ábra A végrehajtási idő és

a feladat mérete közötti kapcsolat n szám összeadása esetén Azaz, mint az várható volt, lineáris az n növekedésével. A Gauss módszer esetén viszont az idő független a műveletek számától. Vigyázzunk, hogy ne keverjük össze a hatékonyságot és a komplexitást. A komplexitást mindig a fenti görbe meredeksége méri, amely a direkt módszer esetén 1, a Gauss módszer esetén 0. Vannak olyan algoritmusok, amelyek komplexitása igen nagy. Vegyük példának a Hanoi tornyainak nevezett algoritmust. A megoldandó probléma a következő: Adott három rúd, A, B és C. Az A rúdon n darab korong, amelyek átmérője alulról felfelé csökkenő. Azaz az alul elhelyezkedő korong átmérője a legnagyobb A feladat az, hogy a B rúd felhasználásával helyezzük át a korongokat a C rúdra úgy, hogy - mindig csak egy korongot helyezhetünk át egy lépésben - csak kisebb korongot helyezhetünk rá egy nagyobbra A megoldás algoritmusa ún. rekurzióval adható meg,

azaz 1) A felső n - 1 darab korongot áthelyezzük A-ról B-re a C felhasználásával 2) Az n-edik korongot áthelyezzük A-ról C-re 3) Az n - 1 darab korongot áthelyezzük B-ről C-re az A felhasználásával Például ha n = 2 akkor 1) A - B 2) A - C 3) B - C Például az 1) lépést úgy vezethetjük vissza az eredeti feladatra, hogy az A lesz az A, a B lesz a C és a C lesz a B, valamint n = n-1. Az algoritmust megvalósító program, function Hanoi(n,a,b,c) arrow=->; global lista if n==1 lista=strcat(lista,a,arrow,c,:); else Hanoi(n-1,a,c,b); lista=strcat(lista,a,arrow,c,:); Hanoi(n-1,b,a,c); end; Page 12 Például n = 2 esetén, a műveletek száma 22 -1 = 3 >> global lista; >> lista= ; >> Hanoi(2,A,B,C) >> lista lista = A->B:A->C:B->C: Ha n = 3, >> lista= ; >> Hanoi(3,A,B,C) >> lista lista = A->C:A->B:C->B:A->C:B->A:B->C:A->C: A műveletek száma már 23 - 1 = 7 lesz. Ha n = 4 >> lista=

; >> Hanoi(4,A,B,C) >> lista lista = A->B:A->C:B->C:A->B:C->A:C->B:A->B:A->C:B->C:B->A:C->A:B->C:A->B:A->C:B->C A műveletek száma már 24 - 1 = 15 lesz. >> n = 2:10; >> m=2.^n-1; >> plot(n,m); 2. ábra A Hanoi - tornyai algoritmus komplexitása Page 13 Ennek az algoritmusnak a komplexitása már exponenciális. Például 25 korong áthelyezéséhez szükséges műveletek száma: >> 2^25-1 ans = 33554431 Epilógus A polinomiális időben végrehajtható algoritmusokat, ahola műveletek száma arányos np-vel ahol n a probléma mérete ésegy p pozitív egész, még praktikusan megoldhatónak nevezzük a mai számítógépekkel. A polinomiálisnál nagyobb ún NPkomplexitású algoritmusok megoldása általánosanértelemben, azaznagy n-re,nem lehetséges. Például annak eldöntése, hogy egy irányítatlan gráfban létezik -e olyan körpálya, amely a gráf minden csúcsán egyszer halad

keresztül NP komplexitású probléma. Ellenőrző kérdések 1. Adja meg az algoritmus definicióját! 2. Adjon meg két algoritmust a legnagyobb közös osztó meghatározására! 3. Mutasson példát a numerikus és nem-numerikus algoritmusokra! 4. Milyen tulajdonságai alapján értékelhetjük az algoritmusokat? 5. Mutasson példát a algoritmus tulajdonságainak jellemzésére! 6. Mit nevezünk NP komplexitású algoritmusnak és hol alkalmazzák? Page 14