Miért?

Egyre gyorsuló világunkban az informatikában is mindent alárendelünk a minél gyorsabb fejlesztésnek. Gombamód szaporodnak a keretrendszerek, amelyek feladata a napi rutintól való megkímélés. A sok keretrendszer oktatása miatt az oktatásból is egyre jobban kimarad az algoritmikus gondolkodásra nevelés.

A hardver ugyan erősödik, de még mindig a Naumann-elvek szerint működnek és ezek között a kevésbé idézettek között ott van az is, hogy csak algoritmizálható feladatokat képesek megoldani! Ezért jó, ha az informatikus ezt észben tartja.

A fogalom eredete

Az „algoritmus” kifejezés a bagdadi perzsa-arab tudós, Muhammad ibn Músza l-Hvárizmi nevének latinos változatából (Algorithmi) ered. A Kr. u. kb. 700–1200 között eltelt időszak az arab birodalmak, kultúra, tudomány virágzásának ideje volt, ennek az időszaknak részben a mongol, részben a keresztény hódítások vetettek véget. Az arabok legnagyobbrészt a hinduktól, Európa pedig al-Hvárizmitől és utódaitól vette át nemcsak a helyiértékes, tízes rendszerű számírást (addig római számokkal illetve abakusszal, az „ókor számológépével” számoltak), hanem az alapfokú algebrai és trigonometriai ismereteket is (szöveges egyenletek felírása, megoldása).

Az akkori idők egyik legnagyobb hatású műve a térségben, talán rögtön a Korán és a 11. században az orvos Avicenna tollából keletkezett Kánon után, minden bizonnyal az al-Hvárizmi által írt „Algebra” (Al-kitab al-muktaszár fi-hiszáb al-dzsabr val-mukabala = Rövid könyv a helyrerakásról (al-dzsabr) és az összevonásról) volt. Az al-dzsabr szóból ered mai „algebra” szavunk. De al-Hvárizmi írt egy aritmetikai jellegű, a hindu tízes számrendszert ismertető könyvet is, ez csak latin fordításban maradt meg, címe így kezdődik: „Dixit Algorithmi…” („Ezt mondja al-Hvárizmi:…”). Innen eredt a latin „algoritmus” szó, ami aztán szétterjedt a többi európai nyelvben is. A 820 körül írt könyv eredetije eltűnt, a cím teljes latin fordítása a következő: „Liber Algorithmi de numero Indorum” (azaz „Algorithmus könyve az indiai számokról”). A hindu számírást ismertető könyvét az Al-Mamún kalifa (Harun ar-Rasid fia, lásd: Ezeregyéjszaka...) által épített bagdadi „Bölcsesség Házá”-ban írta. A könyvet Adelard bathi angol szerzetes fordította a XII. században, ebből a fordításból és egyéb arab eredetű forrásból ismerte meg Európa az új számírást. Az arab források miatt terjedt el az „arab számok” kifejezés, amely elfedi a hindu eredetet.

Definíció

Egy feladatmegoldás akkor tekinthető algoritmusnak, ha

1. Az eljárás minden lépése egyszerűen kivitelezhető
2. Az eljárás véges sok lépésből áll
3. Ugyanarra a bemenetre mindig ugyanazt az eredményt adja
4. Minden időpontban egyértelműen adott a következő lépés

euklideszi algoritmus (Kr. e. 300 körül)

probléma: van két egész számunk, meg akarjuk találni a legnagyobb közös osztójukat, minél kevesebb számolással

megoldás: alapötlete az, hogy a legnagyobb közös osztó nem változik, ha a nagyobb számot a két szám különbségével helyettesítjük. Ez a helyettesítés csökkenti a nagyobb számot, így a cserék ismétlésével egyre kisebb számokat kapunk, egészen addig, amíg a két szám egyenlővé nem válik. Ez az eddigi számpárok, így az eredeti számpár legnagyobb közös osztója.

252	105
147	105
42	105
42	63
42	21
21 (lnko)	21 (lnko)