right|thumb|260px|Ibn Músza al-Hvárizmi abakusza, a „középkor számológépe” 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 thumb|right|Al-Hvárizmi egy 1983-as szovjet bélyegen, „1200 év” felirattal
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 bélyegkép|Példa egy algoritmus reprezentációjára: az euklidészi algoritmus folyamatábrája 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: Az eljárás egyértelműen leírható véges szöveggel. Az eljárás minden lépése ténylegesen kivitelezhető. Az eljárás minden időpontban véges sok tárat használ. 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: Az algoritmus ugyanarra a bemenetre mindig ugyanazt az eredményt adja. 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 Adj egy C- és egy D-hangotMobiltelefonálás Hívó Használati utasítás Nyomd meg a # gombotRá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ávalKasszírozás a boltban Pénztáros Használati utasítás Írd be a 239-et
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.
Probléma, példány és megoldás
Egy algoritmus tervezésekor meg kell különböztetni a problémát, annak egy konkrét példányát és a példányra adott megoldást. A probléma az általános feladatleírás, a példány egy konkrét bemenet, a megoldás pedig az adott bemenethez tartozó helyes kimenet. A „rendezzünk növekvő sorrendbe egy számsorozatot” probléma egy példánya lehet a 8, 3, 5, 1 sorozat; ennek egyik helyes megoldása az 1, 3, 5, 8 sorozat.