Algoritmus

Az algoritmus szó és fogalom a görög rytmus az ismétlődő rend, áramlás szóból eredeztethető. Az algo előtag pedig Muhammad ibn Músza al-Hvárizmi 8. században élt perzsa matematikus nevével köthető össze, de a számítástechnikai kultúra elterjedése, népszerűsödése ültette át a köznyelvbe.

Algoritmuson vagy eljáráson olyan megengedett lépésekből álló módszert, utasítás(sorozatot), 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

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.

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.

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

Bővebben: 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.

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:

Problémamegoldás

Az algoritmikus problémamegoldás célja, hogy egy megoldandó feladatot olyan pontosan fogalmazzon meg, hogy arra végrehajtható, ellenőrizhető és elemezhető eljárást lehessen adni. A számítástudományban a probléma általában nem egyetlen konkrét kérdést, hanem feladatok egy osztályát jelenti: a probléma meghatározza a megengedett bemeneteket, az elvárt kimeneteket és a közöttük fennálló kapcsolatot; az algoritmus pedig egy konkrét eljárás ennek a kapcsolatnak az előállítására.

Például a „számítsuk ki két pozitív egész szám legnagyobb közös osztóját” egy jól meghatározott számítási probléma: a bemenet két pozitív egész szám, a kimenet pedig az a legnagyobb pozitív egész, amely mindkettőt osztja. Erre ad megoldást az euklideszi algoritmus. Hasonlóan, a rendezési probléma bemenete elemek sorozata, kimenete pedig ugyanazon elemek valamilyen előírt rendezés szerinti sorozata.

Számítástechnikai algoritmusok

Számos számítástechnikai algoritmus létezik, amelyek különböző feladatok megoldására szolgálnak. Az alábbiakban kategóriákra bontva ismertetek néhány fontos algoritmust:

Kapcsolódó szócikkek

• 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 .
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022). Introduction to Algorithms (angol nyelven) (4. ed.). Cambridge, Massachusetts: MIT Press. ISBN 978-0-262-04630-5.{{cite book}}: CS1 karbantartás: ref az alapértelmezés duplikátuma (link)
• Knuth, Donald E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (angol nyelven) (3. ed.). Reading, Massachusetts: Addison-Wesley. ISBN 978-0-201-89683-1.{{cite book}}: CS1 karbantartás: ref az alapértelmezés duplikátuma (link)
• Pólya, György (1945). How to Solve It (angol nyelven). Princeton: Princeton University Press.{{cite book}}: CS1 karbantartás: ref az alapértelmezés duplikátuma (link)
• Sipser, Michael (2013). Introduction to the Theory of Computation (angol nyelven) (3. ed.). Boston: Cengage Learning. ISBN 978-1-133-18779-0.{{cite book}}: CS1 karbantartás: ref az alapértelmezés duplikátuma (link)
• Motwani, Rajeev; Raghavan, Prabhakar (1995). Randomized Algorithms (angol nyelven). Cambridge: Cambridge University Press. ISBN 978-0-521-47465-8.{{cite book}}: CS1 karbantartás: ref az alapértelmezés duplikátuma (link)

Jegyzetek

További információk

• Alice és Bob - 6. rész: Alice és Bob a kiszámíthatóság határán
• Alice és Bob - 7. rész: Alice és Bob egymillió dolláros kérdése
• Alice és Bob - 8. rész: Alice és Bob biztonsága
• 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 Archiválva 2013. május 15-i dátummal a Wayback Machine-ben
• 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 Archiválva 2011. szeptember 24-i dátummal a Wayback Machine-ben