Algoritmus

al-Hvárizmi abakusza az „ókor számológépe”

Az algoritmus szó és fogalom a matematikából ered, de a számítástechnikai kultúra elterjedése, popularizálódása ültette át a köznyelvbe.

Algoritmuson vagy inkább eljáráson olyan megengedett lépésekből álló módszert, utasítás(sorozato)t, részletes útmutatást, receptet értünk, amely valamely felmerült probléma megoldására alkalmas. Például eljárást, algoritmust, receptet lehet adni egy „kombo” asztal (vagy egyéb bútor) összeszerelésére, valamilyen élelmiszer, mondjuk sajt (vagy bármilyen tejipari termék) elkészítésének módjára, a Deák térről a Lánchídhoz vezető út megtalálására, vagy éppen két egész szám legnagyobb közös osztójának kiszámolására. A számítógépes programok általában tartalmaznak algoritmusokat, ezekkel utasítják a gépet az adott feladat végrehajtására.

A konkrét algoritmus megadásához tudni kell, hogy mik a megengedett lépések. Enélkül az az egy lépés is algoritmus lehetne, hogy süssük meg a kenyeret. Csak a megengedett lépésekkel lehet az algoritmuson bonyolultsági elemzést végezni.

Az algoritmusfogalom története

al-Hvárizmi egy 1983-as szovjet bélyegen, „1200 év” felirattal

Az „algoritmus” kifejezés a bagdadi arab tudós, al-Hvárizmi (Abu Dzsafar Muhammad bin Músza al-Hvárizmi, élt kb. 780-tól kb. 845-ig, Al-Khvorizmi, Al-Khorizmi stb.) nevének eltorzított, rosszul latinra fordított változatából 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 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.

Az algoritmus történelme

Az első számítógépre írt algoritmust és programnyelvet Ada Lovelace írta meg 1842-ben a Charles Babbage által tervezett, de csak félig megépített Analitikus Gépre (ld. még számítástechnika).

Alan Turing 1937-ben írt cikket egy absztrakt automatáról, a Turing-gépről, ami az algoritmusfogalom egy lehetséges matematikai leírása. Valamivel később megjelent az első, algoritmusok hatékonyságát elemző matematikai cikk is; mely az euklideszi algoritmus időbonyolultságát vizsgálta. Ezen próbálkozásokból született meg a matematika algoritmusokat vizsgáló ága, a számítógéptudomány.

Manapság a mesterséges intelligencia kutatása és az ezzel és a számítógéptudománnyal jelentős közösséget és átfedéseket tartalmazó kognitív tudomány létrejöttének és divatossá válásának hatására az algoritmusfogalom az egyik legkiemeltebb és dinamikusan kutatott absztrakt fogalommá vált.

Az informatikában és a matematikában

Az algoritmus a matematika és az informatika fontos fogalma. Az elméleti informatika egyes részterületei foglalkoznak velük, így az algoritmuselmélet, a bonyolultságelmélet és a kiszámíthatóságelmélet. Számítógépes programok is így vezérlik a számítógépeket.

Algoritmus és program

Az algoritmusok többféleképpen is formálisan reprezentálhatók. Ezek az algoritmusok az absztrakt objektumtól a konkrét számítógépi programig terjednek. Az absztrakció eltekint a gép jellemzőitől; a számítógépes program az algoritmus konkrét, az adott gép lehetőségeihez igazított alakja. Tekintik az algoritmusokat Turing-gépekre írt programoknak is. Itt a Turing-gép fogalma önmagában is absztrakt: egy ideális matematikai gép.

Az első számítógépes program

Az első, számítógépre kigondolt algoritmust Ada Lovelace írta 1843-ban Charles Babbage analitikai gépére a Bernoulli-számok kiszámítására, tehát ő tekinthető az első programozónak. Mivel a gép nem épült meg, ezt az algoritmust nem tudták rá implementálni.

Turing-gépek és algoritmusfogalom

Sok matematikust zavart a 19. és a 20. században az algoritmus fogalmának pontatlansága. Ez számos definíciókísérlethez vezetett a 20. század első felében. A kiszámíthatóság fogalmának formalizálására szolgál a Turing-gép (Alan Turing), a regisztergép, a lambda-kalkulus (Alonzo Church), a rekurzív függvények, a Chomsky-nyelvtanok és a Markov-algoritmusok.

Alan Turing és a többi matematikus megmutatta, hogy ezekkel a módszerekkel ugyanazokat a függvényeket lehet kiszámolni. Szimulálhatók Turing-géppel és szimulálhatnak Turing-gépet.

Turing-géppel formális definíció adható az algoritmus fogalmára:

Egy probléma megoldására adott utasítássorozat akkor tekinthető algoritmusnak, ha van egy vele ekvivalens Turing-gép, ami minden megoldható bemenetre megáll.

A definícióból levezethetők az algoritmusok közös tulajdonságai:

1. Az eljárás egyértelműen leírható véges szöveggel.
2. Az eljárás minden lépése ténylegesen kivitelezhető.
3. Az eljárás minden időpontban véges sok tárat használ.
4. Az eljárás véges sok lépésből áll.

Ezek alapján az algoritmus fogalmát gyakorlatilag a következőkre korlátozzák:

1. Az algoritmus ugyanarra a bemenetre mindig ugyanazt az eredményt adja.
2. Minden időpontban egyértelműen adott a következő lépés.

Ezek az utóbbiak determinisztikus algoritmusok, de vannak nem determinisztikus algoritmusok is.

Church–Turing-tézis

A Church–Turing-tézis így szól:

Minden intuitívan kiszámítható probléma kiszámítható Turing-géppel.

Ezáltal a kiszámíthatóságot úgy definiálják, hogy egy probléma pontosan akkor kiszámítható, ha van hozzá egy algoritmus, azaz egy megfelelően programozott Turing-gép véges időben meg tudná oldani.

Absztrakt automaták

A Turing-gépek jól harmonizálnak az ugyanannyira absztrakt kiszámítható függvényekkel. A valóban fellépő problémák azonban ennél sokkal bonyolultabbak, ezért más, a Turing-géppel ekvivalens gépeket javasoltak. Ezek a gépek nehezebb parancsokat gyorsabban tudnak végrehajtani, például képesek Fourier-transzformálni egy lépésben.

Más gépek párhuzamosan több műveletet is végrehajthatnak, így adnak össze két vektort egy lépésben.

A valódi számítógép egy modellje: Az ilyen gépen az algoritmus

• véges hosszúságú programmal adható meg
• lépésenként végrehajtható
• bizonyos állapotokra leáll, de nem kell mindig leállnia – értelmes példák a prímszámokat kereső algoritmusok vagy az operációs rendszerek
• lépésenként csak véges sok állapot változhat
• lépésenként csak véges sok állapot vehető számításba.

Tulajdonságok

• Determináltság: az algoritmus determinált, ha ugyanazokra a kezdőállapotokra és ugyanarra a bemenetre ugyanazt az eredményt adja.
• Determinisztikus: az algoritmus determinisztikus, ha minden időpontban egyértelmű, hogy mi lesz a következő lépés. Ilyen például a buborékrendezés és az euklideszi algoritmus.

Minden determinisztikus algoritmus determinált algoritmus, de megfordítva nem. Például a gyorsrendezés véletlen választással determinált, de nem determinisztikus algoritmus.

Az elméleti informatika foglalkozik nem determinisztikus algoritmusokkal, amik azonban direkt módon nem valósíthatók meg a valódi számítógépeken.

Végesség

• statikus végesség: az algoritmus leírása véges
• dinamikus végesség: az algoritmus minden időpontban véges tárat használ
• termináltság: az algoritmus futása minden bemenetre véget ér

Vannak kivételek a termináltság alól: ilyenek a vezérlőrendszerek, operációs rendszerek, és sok más interaktív program. Amíg a felhasználó nem utasítja a számítógépet, hogy vége, addig ezek a programok folyamatosan futnak. Donald Knuth javaslata szerint ezeket az algoritmusokat számítógéppel támogatott módszereknek nevezzük (Computational Methods).

Az algoritmusok befejezése eldönthetetlen. Ez a megállási probléma.

Algoritmusok elemzése

Az algoritmusok kutatása és elemzése az informatika és a számítástudomány feladata. Többnyire elméletileg, konkrét programnyelv használata nélkül végzi. Ez a módszer más matematikai területekéhez hasonlít, ahol az elemzés inkább a szóban forgó koncepciókról, mint a konkrét környezetekről szól. Az elemzéshez az algoritmusokat erősen formalizálják, és a formális szemantika eszközeivel vizsgálják.

Az algoritmusok tár-és időigényével a bonyolultságelmélet foglalkozik, és az eredményeket aszimptotikusan adja meg. Ezeket az igényeket a bemenet hosszának függvényében számítja.

Az algoritmusok futásának befejeződését és az eredményes véget érést a kiszámíthatóságelmélet tárgyalja.

Típusok és példák

A legrégibb ismert nem triviális algoritmus az euklideszi algoritmus, amely két egész szám legnagyobb közös osztóját határozza meg. Speciális algoritmustípusok az approximációs algoritmusok (közelítő eljárások), a véletlen algoritmusok, a genetikus algoritmusok (fejlődési lehetőséggel) és a mohó algoritmusok.

Az algoritmusok nem kizárólag matematikai és informatikai jelenségek:

Folyamat	Végrehajtó	Algoritmus	Tipikus utasítás
Kalácssütés	Pék	Recept	Vegyél 500 gramm lisztet / Nyújtsd ki a tésztát
Dallam lejátszása	Énekes, zenész	Hangsorozat	Fájl:Notengruppe.png
Mobiltelefonálás	Hívó	Használati utasítás	Nyomd meg a # gombot
Rádió összeszerelése	Rádiószerelő	Kapcsolási terv és szerelési útmutató	Kösd össze a T1 tranzisztor bázisát a T5 kollektorával
Kasszírozás a boltban	Pénztáros	Használati utasítás	Írd be a 237,37-ot

Problémamegoldás

A fogalom pontosítása, változatai

I. probléma: terv és végrehajtás

Az algoritmus létrehozásának első lépése általában egy cél kitűzése, amit egy probléma vetett fel. Ezután el lehet kezdeni megalkotni azt az algoritmust, amely a problémát megoldja, vagyis adott kezdőállapotokból mindig az elérendő állapotok valamelyikébe kerül.

Példa:

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: euklideszi algoritmus

A megoldás megtalálásához általában a tapasztalat és a probléma részekre bontása vezet. Ugyanakkor sok olyan feladat van, amire nem adható algoritmus, ezeknél vagy nem vagyunk minden szükséges információ birtokában, vagy ellentmondás található a probléma megfogalmazásában. Utóbbi elkerülésében segíthet, ha a problémát is formálisan specifikáljuk.

Nyitott problémákra nincs algoritmus

Rengeteg számítástechnika könyvben és feladatgyűjteményben szerepel bevezető feladatként olyasmi, mint ez: ”Írjunk algoritmust egy levél postán való feladására!” ld. itt.

A legfőbb baj az ilyen feladatokkal, hogy nem oldhatóak meg egyértelműen. Ez persze önmagában véve nem baj. Valójában az a baj, hogy a feladat megoldásához nem rendelkezünk elég információval, például: hol a posta, és hol vagyok én, egyáltalán milyen tárgyakat kell figyelembe venni az odajutáshoz stb.

III. Probléma: Részletesség és egyértelműség – elemi lépések

Ha adott egy probléma(osztály), amelynek megoldására eljárást szeretnénk adni, nem árt tisztázni, milyen körültekintően kell az eljárást megtervezni, mennyire legyen részletes a megadott recept. Ez függ az adott szituációtól. Például ha egy kisgyermeket küldünk a postára feladni a levelet, akkor esetleg az eljárás részeként a lelkére kötjük: ha autóutat kell kereszteznie, okvetlenül a zebrát használja, nehogy átszaladjon az úttesten!

Képzeljük csak el megint, hogy az iskolában vagyunk, és az informatikatanár feladja a következő feladatot: „Írjunk algoritmust egy levél postán való feladására!” Mi van, ha egy megoldó csak annyit ír megoldásként: „Egyszerűen adjuk postára a levelet!” Mivel, ha e feladatot csak önmagában nézzük, nincsenek világosan megfogalmazott kritériumok arra, hogy mi számít „algoritmusnak”, azaz mikor fogadható el egy megoldás, bizony ezt az egyszerű és használhatatlan választ is el kell fogadnunk. Ez a válasz ugye „túl egyszerű”. De nem fogalmaztuk meg, milyen mélységben kell az algoritmust megkonstruálnunk, azaz mik azok az elemi lépések, amelyekből mint egy puzzle, össze fog állni az algoritmus. Persze nehéz elképzelni, hogy egy-egy tanuló ilyesféle algoritmusokat ír majd (hacsak nem viccből):

• 1). Álljunk fel a székből;
• 2). Vegyünk lélegzetet;
• 3). Forduljunk az ajtó felé;
• 4). Vegyünk lélegzetet megint;
• 5). Tegyük a kezünket a kilincsre.
• …
• 1023). Tegyük a kezünket a posta bejáratának a kilincsére;
• 1024). Vegyünk lélegzetet;
• … stb.,

de ezeket a „túl bonyolult”, és a probléma megoldása szempontjából alapvetően irreleváns, fölösleges lépéseket tartalmazó megoldásokat is el kell fogadnunk megoldásként.

Helyeseljük e feladat kitűzését az algoritmus köznapi fogalmának pontatlanságára való rámutatás, azaz épp a fent vázolt problematika bemutatása okából és céljából, de természetesen helytelen, ha a tanulók megoldásait valamilyen általunk jónak gondolt, „elegendő” pontosságú megoldáshoz mérve akarjuk értékelni.

Egy megfelelő egyértelműséggel megfogalmazott problémát akkor oldottunk meg, ha először rögzítjük, milyen elemi lépéseket engedünk meg, és ezután konstruálunk eljárást. Ez az eljárás olyan utasítássorozat, amelynek minden eleme egy-egy megengedett elemi lépés. Egy másféle felfogásban azt is mondhatjuk: egy algoritmust mindig egy adott nyelven kell megfogalmaznunk, melyet előre rögzítenünk kell; ez nem más, mint az elemi lépések neveiből mint szavakból összetett mondatokból álló nyelv. Lásd még absztrakt automata.

Általában feltesszük az elemi lépésekről, hogy

• függetlenek, egyik sem állítható össze például néhány más lépés egymásutánjaként;
• relevánsak, azaz mindegyik lépés legalább egyszeri végrehajtása valóban szükséges a probléma megoldásához;
• teljes rendszert alkotnak, azaz a probléma megoldásához szükséges valamennyi elemi lépést felsoroltuk.

IV. Probléma: Determinisztikus és nem determinisztikus eljárások

Egy igazán „tipikus” algoritmusnak nemcsak előre meghatározott lépésekből kell állnia, de a végrehajtás minden helyzetében egyértelműen azt is meg kell határoznunk, hogy az aktuális lépés végrehajtása után mi is legyen a következő lépés. Ez triviálisan hangzik, de lényeges, hogy ezt egyértelműen tegyük meg. Egy algoritmus nem tartalmazhat „határozatlan” lépéseket: ha egy adott lépés során többféle végrehajtási mód merül fel, akkor is ki kell választanunk valamelyiket, ha a többi mód ezzel egyenértékű.

Talán egy-két példán keresztül világosabb lesz. A szakácskönyvek gyakran tartalmaznak ilyen kitételeket: „sózzuk ízlés szerint”, „kb. 30 percig süssük”. Az első utasítással még nincs nagy baj, mert feltételezhető, hogy az ételkészítőnek vagy a fogyasztó társaságnak van meghatározott ízlése, és ennek függvényében a sózás mértéke is meg van határozva. Ez az utasítás felfogható mint egy feltételes elágazás (if <feltétel> then do <utasítások> else do <utasítások>): ha sósan szeretjük, bőven sózzunk, ellenben ne annyira. De „körülbelül 30 percig”… nos, ilyen a matematikában (a jelenlegi standard felfogás szerint) végképp nincs. Itt már semmilyen, többé-kevésbé egyértelműen eldönthető feltétel sem szabályozza a sütés időtartamát, lényegében véletlen választási lehetőségünk van. Természetesen a „süssük, amíg jó piros, ropogós nem lesz” már egy fokkal egyértelműbb utasítás, de egy matematikus számára még ez sem tökéletes.

A véletlennek a hagyományos algoritmuselméletben nincs szerepe, bár manapság a számítástudomány algoritmusfogalma ilyen irányba is bővült. Egyelőre annyiban maradunk, hogy egy „hagyományos” algoritmus nem tartalmazhat véletlen választási lehetőséget: vagyis determinisztikus.

Levonhatjuk és le is kell vonnunk a tanulságot: ha egy probléma nyílt, nincs egyértelműen megfogalmazva, nem mindenki ugyanazt érti rajta, akkor arra nem adható algoritmus. Az algoritmus ugyanis a probléma egyértelmű megoldásának útmutatóját jelenti, ez beletartozik a definícióba. Ha pedig már a probléma sem egyértelmű, akkor a megoldás sem lehet az.

Lásd még

• Az algoritmusok hatékonyságának elemzése → számításelmélet;
• mesterséges intelligencia;
• Az algoritmusok gyakorlati alkalmazásának egy területe a játékelmélet (aminek és a mesterséges intelligencia kutatásának vannak átfedései). Néhány egyszerűbb feladat algoritmikus megoldása: királynőprobléma, "Hanoi tornyai" probléma
• Az algoritmusfogalom egy matematikai szigorúságú értelmezése → absztrakt automata és Turing-gép
• pszeudokód.
• algoritmikus művészet

Források

• Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – Eine Einführung. 2. Auflage. Oldenbourg Wissenschaftsverlag, München 2007, ISBN 978-3-486-58262-8.
  • Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. MIT Press, Boston 2001, 2002, 2003. ISBN 0-262-53196-8. (engl. Orig.-Fass.)
• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Pearson Studium, München 2002. ISBN 3-8273-7020-5.
• Donald E. Knuth: A számítógépprogramozás művészete. Bd 1–3. Addison Wesley, Reading Mass. 1998, ISBN 0-201-48541-9.
• Thomas Ottmann, Peter Widmayer: Algorithmen und Datenstrukturen. 4. kiadás. Spektrum Akademischer Verlag, Heidelberg 2002, ISBN 3-8274-1029-0.
• Anany Levitin: Introduction to The Design and Analysis of Algorithms Addison Wesley, ISBN 0-321-36413-9
• Gregorics Tibor: Mesterséges Intelligencia c. könyve és előadásai;
• Lőrincz András: Tanulórendszerek c. előadása;
• Számítástechnikai feladatgyűjtemény. Tankönyvkiadó, Bp., 1980.
• Jozef Hvoreczký – Jozef Kelemen: Ötlettől az algoritmusig. Középiskolai Szakköri Füzetek. Tankönyvkiadó, Bp., 1987. ISBN 963-17-9882-8 .

További információk

• Problémamegoldásról
• A hét algoritmusa (Különböző szerzők algoritmusai részletesen; az informatika napjára kiadva)
• Algoritmusok az informatikában
• Dictionary of Algorithms and Data Structures des NIST (angolul)
• Definíció és lényegi tulajdonságok, Nils Adermann szakdolgozata, 2005 (PDF).
• A valódi számítógép modellje Sequential Abstract State Machine (seq. ASM)
• Programozni egyszerű! Programozás alapjai kezdőknek