Algoritmus
A Wikipédiából, a szabad lexikonból.
 |
Ezt a szócikket át kellene olvasni, ellenőrizni a szövegét, tartalmát. További részleteket a cikk vitalapján találhatsz. |
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 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.
Tartalomjegyzék |
[szerkesztés] Példa algoritmusra
Képzeljük el, hogy épp a Deák-téren álldogálunk a 47-es villamosra várva, és turisták szimpatikus kis csoportja útbaigazítást kér tőlünk, hogyan tudnának elgyalogolni egy közeli postáig. Semmi baj, a következőket lehet mondani nekik:
* Menjenek át a túloldalra, oda ni, a közeli zebrán vagy aluljárón. * Forduljanak jobbra, ott a Városház utca, ez az első útba eső keresztutca lesz, menjenek rajta végig az első kereszteződésig, aztán balra kell fordulni, * Menjenek, ajjaj! hány utcát is (tegyük fel, hogy nem jut eszünkbe!)? Mindegy, menjenek azon az utcán egyenesen, amelybe fordultak, és két-három kereszteződés múlva ott lesz büszkeségünk, a Magyar Posta! * Ezután elbúcsúzunk. Az útbaigazításnak vége.
Ez így, pusztán önmagában (legalábbis tudományos értelemben) nem tekinthető algoritmusnak, mert nem egy egzakt, formális nyelven lett megfogalmazva.
[szerkesztés] Problémamegoldás
Fő szócikk: Probléma[szerkesztés] A fogalom pontosítása, változatai
[szerkesztés] 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, ami 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, minnél kevesebb számolással
megoldás: euklidészi 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.
[szerkesztés] 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.
[szerkesztés] II. Probléma: Általános és konkrét megkülönböztetése
[szerkesztés] 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 pl. 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.
[szerkesztés] IV. Probléma: Determinisztikus és indeterminisztikus 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, 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 egyértelműen tegyük ezt 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, roporgó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.
[szerkesztés] Azaz
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.
A fogalomnak rengeteg matematikai szigorúságú megfogalmazása is adható, ezt a kiszámíthatóságelmélet c. cikk tárgyalja.
[szerkesztés] Az algoritmusfogalom története
Mindenekelőtt szóljunk e furcsa szó eredetéről. Az „algoritmus” kifejezés a bagdadi arab tudós, Al-Hvárizmi (Abú Ja'far Mohammed ibn Musa al-Khwarizmi, élt kb. 780-tól kb. 845-ig, Al-Khvorizmi, Al-Khorizmi stb. néven is emlegetik, az arab nevek magyarra átírása nem egységes) 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ámító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 Algorismus szó, ami aztán szétterjedt a többi európai nyelvben is.
Az első számítógépre írt algoritmust és programnyelvet Ada Byron í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 1936-ban í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.
[szerkesztés] Lásd még
- Probléma
- kiszámíthatóság
- kiszámíthatóságelmélet
- Az algoritmusok hatékonyságának elemzése → számításelmélet;
- Az algoritmusok felhasználása keresési problémák megoldásánál -> 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, Tili-Toli, Tic Tac Toe
- Az algoritmusfogalom egy matematikai szigorúságú értelmezése -> absztrakt automata és Turing-gép;
- Az algoritmusfogalom egy értelmezése a kognitív tudomány szemszögéből -> produkciós rendszer
- Lásd még pszeudokód.
[szerkesztés] Források
- Gregorics Tibor: Mesterséges Intelligencia c. könyve és előadásai;
- Lőrincz András: Tanulórendszerek c. előadása;
- Számtá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 .
[szerkesztés] Külső hivatkozások
Based on work by