Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

1.5. Az algoritmus fogalma

1.5. Az algoritmus fogalma

Az adatainkon általában különféle műveleteket, átalakításokat szoktunk végezni azzal a céllal, hogy ezáltal közvetlenül nem kiolvasható összefüggéseket, eredményeket kapjunk. A tevékenységeket logikai sorrendbe rakva az algoritmus matematikai fogalmához kerülünk közelebb. Az algoritmus mély matematikai fogalom. Mi nem adunk precíz definíciót rá, mivel ebben a könyvben erre nincs szükségünk. Azok számára, akiket a téma mélyebben érdekel ajánlhatjuk a [4], [5], [6], [7] könyveket.

Most megadunk egy heurisztikus (nem tudományos) definíciót az algoritmus fogalmára.

1.16. Definíció. Az algoritmus egy meghatározott számítási eljárás, a számítási probléma megoldási eszköze.

Az algoritmus pontos előírás, amely megad egy tágan értelmezett számítási folyamatot. Az algoritmus valamely előre meghatározott adathalmaz valamely tetszőleges kiinduló eleméből kezdve az ezen elem által meghatározott eredmény elérésére törekszik. Lehet, hogy a lépések sorozata azzal szakad meg, hogy nincs eredmény. Az algoritmus is tekinthető egy fekete doboznak, melynek a bemenetére adjuk a probléma, a feladat kiinduló adatait, a kimenetén pedig megjelennek a végeredmények, ha vannak, vagy az jelenik meg, hogy nincsenek. Az algoritmus fekete dobozának belső szerkezete azonban érdekelni fog minket ebben a könyvben. Az algoritmusnak véges idő alatt (véges sok lépés után) véget kell érnie.

1.13. Példa. Négyzetgyök kiszámítása egy számból papíron kézzel.

Határozzuk meg az számot megadott számú értékes jegy pontosságig, ahol valós szám. Egy kézi algoritmus az alábbi formulára építkezve adható:

Az algoritmus leírása (ez az algoritmus épít a szám reprezentációjára, azaz arra, hogy helyiértékes számrendszert használunk):

[1.] Az szám számjegyeit a tizedesvesszőtől balra és jobbra kettes csoportokra osztjuk.

[2.] A balszélső (első) csoportnak vesszük az egyjegyű négyzetgyökét és az eredménybe írjuk.

[3.] A kapott egyjegyű szám négyzetét kivonjuk az első csoportból.

[4.] A maradék mellé leírjuk a következő kétjegyű csoportot, ha van. (A tizedesvesszőt követően mindig lehet zérust, vagy zéruspárokat írni, ha már nem lennének tizedesjegyek.)

[5.] Az eddig kapott eredmény kétszereséhez hozzáillesztünk egy próbaszámjegyet, majd az így kapott számot a próbaszámjeggyel megszorozva a szorzatot kivonjuk a 4. pontnál kapott legutóbbi maradék és következő csoport által meghatározott számból. A próbaszámjegy a lehető legnagyobb olyan számjegy legyen, amely még nemnegatív különbséget ad.

[6.] A próbaszámjegyet az eredményhez hozzáírjuk új számjegyként.

[7.] Ha a pontosság megfelelő, akkor leállunk, egyébként a 4-es pontnál folytatjuk.

1.14. Példa. Konkrét számpélda a kézi négyzetgyökvonás algoritmusára, működésének bemutatása.

Számítsuk ki az értékét! A szám csoportokra osztása: 14 42 48 04. Az algoritmus további lépései az alábbi táblázatban találhatók. A próbajegyeket és a hozzáírt csoportot aláhúztuk.

Kiolvasható, hogy . Az eredmény pontos, mivel a végső maradék zérus.

1.15. Példa. Számítsuk ki az értékét négy tizedes jegyre!

A szám csoportokra osztása: 2, 00 00 00 00.

. Ezen közelítés négyzete a 2-től csak 0,00003896-tal kevesebb.

A tárgyalt algoritmus kellemes, az eredmény jegyei egymás után egyenként jönnek elő. Neuralgikus pont viszont a próbajegyek helyes megválaszásának a kérdése, Igaz, ez a probléma megoldódik, ha a számításokat kettes számrendszerben végezzük. Mégsem ragaszkodunk a négyzetgyökvonás ezen módjához, mivel itt lényeges a szám reprezentációja. Adunk egy másik algoritmust, amely lényegesen jobb mutatókkal rendelkezik. Ez az algoritmus az úgynevezett Newton módszernek egy speciális esete. Ez az algoritmus nem számjegyenként csalja elő a végeredményt, hanem egy számsorozatot képez, amely meglehetősen gyorsan konvergál a végeredményhez. Nem árt persze kellően jó kezdő közelítésből kiindulni. Érdemes megjegyezni, hogy ha a módszer által képzett sorozatban valamely elem már tartalmaz értékes jegyeket a megoldást leíró szám elejéből, akkor minden további elemben az értékes jegyek száma legalább duplájára nő a megelőzőhöz képest. Maga az algoritmus egyszerű és jól programozható, valamint nem igényli a szám reprezentációját. Íme (a leírásban az alkalmazó előre rögzít egy számot, amit nak nevezünk):

[1.] Választunk egy tetszőleges pozitív valós számot és legyen . (Az mindig megfelelő, csak esetleg a kapott sorozat kezdetben lassan kezd közelíteni a megoldáshoz.)

[2.] Képezzük az

számot és értékét eggyel növeljük.

[3.] Ha , akkor megállunk és , egyébként pedig folytatjuk a 2-es pontnál.

1.16. Példa. Határozzuk meg az értékét négy tizedesjegyre, azaz legyen !

Heurisztikus meggondolásból válasszuk kezdőértéknek az számot!

1.17. Példa. Határozzuk meg az értékét négy tizedesjegyre, azaz legyen !

Mivel , ezért válasszuk a kezdő közelítést -nek!