3.2. Az algoritmus tulajdonságai

Az előbb láthattunk egy algoritmust, de mi alapján dönthetjük el egy utasítássorozatról, hogy az algoritmust alkot vagy sem? Az alábbiakban azokat a követelményeket, jellemzőket soroljuk fel, melyek az algoritmusok sajátosságai.

Végesség: Az algoritmus futása véges sok lépés után befejeződik. Esetünkben r kisebb mint n, azaz n értéke folyamatosan csökken az algoritmus végrehajtása során, és pozitív egészek egyre fogyó sorozata egyszer véget ér.

Meghatározottság: Az algoritmus minden egyes lépésének pontosan definiáltnak kell lennie. Miután az élőnyelvi megfogalmazás esetenként nem egyértelmű, használhatunk különféle programnyelveket, ahol mindennek pontos, egyértelműen definiált jelentése van. A következő fejezetben ismertetjük a Turing-gépet, melyet akár használhatnánk is az algoritmusok leírására, ám az ilyen nyelven írt programok hosszúak, és nehezen érthetőek lennének. Ezért a későbbiekben az algoritmusokat pszeudokódban adjuk meg. Ez a kód igen közel áll a Pascal programnyelvű kódokhoz, ám a változók deklarálásától, és minden olyan hasonló szerkezettől, melyek az algoritmus megértését nem befolyásolják, eltekintünk.

Bemenet/Input: Az algoritmus vagy igényel vagy sem olyan adatokat, amelyeket a végrehajtása előtt meg kell adni. Az input mindig bizonyos meghatározott halmazból kerülhet ki, esetünkben m és n pozitív egész szám.

Kimenet/Output: Az algoritmushoz egy vagy több output tartozhat, amelyek meghatározott kapcsolatban állnak az inputtal. Esetünkben az output az n utolsó értéke lesz, ami az input értékeknek legnagyobb közös osztója.

Elvégezhetőség: Elvárjuk, hogy az algoritmust végre lehessen hajtani, azaz a végrehajtható utasítások elég egyszerűek ahhoz, hogy egy ember papírral és ceruzával véges idő alatt pontosan végrehajthassa. Például a végtelen tizedestörtek osztása nem ilyen, mert ez végtelen lépéssorozat.

Univerzális: Az algorimusnak működnie kell tetszőleges (a feltételeknek megfelelő) bemeneti értékek esetén. Az euklideszi algoritmusunk természetesen tetszőleges pozitív számpárnak meghatározza a legnagyobb közös osztóját.

Ezek alapján tekinthetjük az algoritmust egy számolási probléma megoldásának. A probléma megfogalmazása általánosságban meghatározza a kivánt bemenet/kimenet kapcsolatot. Az algoritmus egy specifikus számolási eljárást ír le ennek a kapcsolatnak eléréséhez. A legnagyobb közös osztó problémájának egy esete a 119, 544 számpár. Egy eset az összes olyan bementő adatból áll, amelyek szükségesek a probléma megoldásának számításához. Egy algoritmust helyesnek nevezünk, ha minden konkrét bemenetre helyes kimenetet ad és megáll.