Az algoritmus olyan tervezési és gyártási szabályok és technikák, amelyek részt vesznek az algoritmusok meghatározásában és tervezésében , vagyis a probléma megoldásának szisztematikus folyamata, hogy pontosan leírják az algoritmikus probléma megoldásának lépéseit .
A „algoritmus” származik a neve a matematikus Al-Khwarizmi (Latinized a középkorban a Algoritmi ), amely a IX -én században írt első szisztematikus munkával megoldást nyújt a lineáris egyenletek és másodfokú . A néma h, amelyet az etimológia nem igazol, deformációból származik, összehasonlítva a görög (ριθμ ) ς-val (arithmós). Az "algoritmus" adta az "algoritmust". Az "algoritmus" szinonimát, egy régi szót, amelyet például Wronski használt 1811-ben, még mindig használják.
Az első megtalált algoritmusok a babilóniaiakhoz , Kr. E. III . Évezredig nyúlnak vissza . Kr . U. Példák segítségével leírják a számítási módszereket és az egyenletek megoldásait .
Egy híres algoritmus az egyik található a Book 7 az Elements of Euclid , és az úgynevezett euklideszi algoritmus . Megtalálja két szám legnagyobb közös osztóját vagy GCD-jét . Különösen figyelemre méltó, hogy kifejezetten tartalmaz egy iterációt, és hogy az 1. és a 2. tétel igazolja helyességét .
Archimédész volt az, aki először javasolt egy algoritmust a π kiszámításához .
Az első rendszerezett algoritmus az Al-Khwârizm perzsa matematikus , 813 és 833 között aktív. Abrégé du computation by helyreállítás és összehasonlítás című munkájában az összes másodfokú egyenletet tanulmányozza, és algoritmusok tábornokai adják meg a felbontásukat. A babilóniaiakhoz hasonló módszereket alkalmaz , de szisztematikus magyarázataiban különbözik, ahol a babiloniak csak példákat hoztak fel.
Averroès andalúz tudós ( 1126 - 1198 ) olyan érvelési módszert idéz fel, ahol a tézist lépésről lépésre, iteratív módon finomítják, egészen bizonyos konvergenciáig, és ez egy algoritmus előrehaladásával összhangban. Ugyanakkor a XII . Században Adelard bath szerzetes bevezette a latin kifejezést az Algorismusra , Al Khwarizmi néven. Ez a szó 1554-ben ad algoritmust franciául .
A XVII . Században néhány utalás bepillanthat René Descartes algoritmikus módszerébe a Discourse on Method ( 1637 ) által javasolt általános megközelítésben , különösen akkor, amikor a francia matematikus második részében azt javasolta, hogy "osszák meg az egyes nehézségeket, amelyeket vizsgálja meg, a lehető legtöbb részben, és amennyire szükséges a jobb megoldásukhoz. " Descartes megközelítése anélkül, hogy kifejezetten felidézné a hurokfogalmak iterációját vagy dichotómiáját , a logikát hajlamosítja a program fogalmának befogadására , a szó 1677-ben született franciául .
1843-ban Ada Lovelace matematikus és a számítástechnika úttörője, Lord Byron lánya és Charles Babbage asszisztense végrehajtotta az algoritmus első megvalósítását program formájában ( Bernoulli-számok kiszámítása ).
A tizedik Hilbert-probléma, amely a David Hilbert által 1900-ban Párizsban felvetett 23 probléma listájának része, egyértelműen algoritmikus probléma. Ebben az esetben a válasz az, hogy nincs algoritmus, amely válaszolna a felmerült problémára.
Az algoritmikus XX . És XXI . Század a formalizmus matematikai alapjaira, például a turingi gépekre , amelyek lehetővé teszik annak pontos meghatározását, hogy mit jelentenek a "lépések" alatt a "specifikus" és "egyértelműek", és amelyek tudományos keretet nyújtanak a algoritmusok tulajdonságai. A választott formalizmus szerint azonban különböző algoritmikus megközelítéseket kapunk ugyanazon probléma megoldására. Például , rekurzív Algorithmics párhuzamos Algorithmics vagy kvantum számítástechnikai vezetnek előadások algoritmusok eltérnek az iteratív Algorithmics.
Az algoritmika főként a XX . Század második felében fejlődött ki , mint a számítógépes programozás koncepcionális támogatása az informatika fejlődésében ebben az időszakban. Donald Knuth , a Számos programozás művészete című értekezés szerzője, amely nagyszámú algoritmust ír le, másokkal együtt segített elemzésük matematikai alapjainak megalapozásában.
A főnév algoritmus kijelöli az algoritmusok létrehozásához használt összes módszert. A kifejezést melléknévként is használják.
Egy algoritmus egy probléma megoldását írja le az elvégzendő műveletek láncának formájában .
Az informatikusok gyakran alkalmazzák a végrehajtási anglicizmust, hogy utaljanak az algoritmus programozási nyelvben történő megvalósítására . Ez a megvalósítás végrehajtja az algoritmus alkotó műveleteinek átírását, és meghatározza ezen műveletek meghívásának módját. Ezt a számítógépes nyelvű írást gyakran jelöli a „ kódolás ” kifejezés is. " Forráskódról " beszélünk a szöveg kijelölésére, amely alkotja a programot és végrehajtja az algoritmust. A kód a használt nyelv absztrakciós szintjétől függően többé-kevésbé részletes, ahogy a főzési receptnek a szakács tapasztalatai szerint többé-kevésbé részletesnek kell lennie.
Számos formális vagy elméleti eszközt fejlesztettek ki az algoritmusok leírására, tanulmányozására, tulajdonságaik kifejezésére és összehasonlításukra:
Az algoritmikusan megvalósított fogalmak, például N. Wirth megközelítése szerint a legelterjedtebb nyelvek (Pascal, C stb. ) Számára, kevés számban vannak. Két osztályba tartoznak:
Ez a felosztás néha nehezen érzékelhető bizonyos nyelvek ( Lisp , Prolog …) esetében, inkább a rekurzió fogalmán alapulva, ahol bizonyos ellenőrzési struktúrák implicitek, és ezért látszólag eltűnnek.
Ez a három fogalom: "korrekció", "teljesség", "befejezés" összefügg egymással, és tegyük fel, hogy algoritmust írnak egy probléma megoldására.
A felmondás annak biztosítása, hogy az algoritmus véges idő alatt véget ér. A felmondás igazolása általában szigorúan csökkenő pozitív egész függvényt tartalmaz az algoritmus minden egyes lépésénél.
Tekintettel az algoritmus befejezésének garanciájára, a helyesség igazolásának biztosítania kell, hogy ha az algoritmus eredmény megadásával fejeződik be, akkor ez az eredmény valóban megoldást jelent a felmerülő problémára. A helyesség bizonyítékai általában egy logikai specifikációt tartalmaznak, amelyet a probléma megoldásaival kell ellenőrizni. A helyesség igazolása tehát abból áll, hogy megmutatja, hogy az algoritmus eredményei megfelelnek ennek a specifikációnak.
A teljesség igazolása garantálja, hogy egy adott problématerületnél az algoritmus, ha befejeződik, megadja a problématerület megoldási halmazát. A teljesség igazolásához meg kell határozni a problémateret és a megoldási teret, hogy aztán megmutassuk, hogy az algoritmus valóban előállítja a másodikat az elsőtől.
A pontos algoritmus költségének kiszámításakor a fő matematikai fogalmak a dominancia fogalmai ( O (f (n) , "nagy o" jelöléssel ), ahol f az n matematikai függvénye , az információ mennyiségét jelölő változó ( bitekben , rekordok száma stb. ), amelyet az algoritmus használ. Az algoritmikában gyakran találunk ilyen típusú bonyolultságokat:
Értékelés | Komplexitás típusa |
---|---|
állandó bonyolultság (függetlenül az adatok méretétől) | |
logaritmikus bonyolultság | |
lineáris komplexitás | |
kvázi-lineáris komplexitás | |
másodfokú összetettség | |
köbös összetettség | |
polinom komplexitás | |
kvázi polinom komplexitás | |
exponenciális összetettség | |
faktor komplexitás |
Anélkül, hogy belemennénk matematikai részletekbe, egy algoritmus hatékonyságának kiszámítása ( algoritmikus bonyolultsága ) két fontos mennyiség megtalálásából áll. Az első mennyiség az alaputasítások számának alakulása a feldolgozandó adatok mennyisége szerint (például egy rendezési algoritmus esetében ez a rendezni kívánt adatok száma), amelyet előnyben részesítenek a mért végrehajtási időnél másodpercek alatt (mert ez utóbbi attól a géptől függ, amelyen az algoritmust futtatják). A második becsült mennyiség a számítások elvégzéséhez szükséges memória mennyisége. Az algoritmus bonyolultságának kiszámítása azon idő vagy tényleges memóriamennyiség alapján, amelyet egy adott számítógép az algoritmus végrehajtásához igénybe vesz, nem veszi figyelembe az algoritmus belső felépítését, sem az algoritmus sajátosságait. a munkaterhe, a processzora sebessége, az adatokhoz való hozzáférés sebessége, az algoritmus végrehajtása (amely véletlenszerűséggel járhat) vagy a memóriaszervezése, a végrehajtás ideje és a memória mennyisége nem lesz azonos.
Gyakran a teljesítményt "a legrosszabb esetben" vizsgálják, vagyis olyan konfigurációkban, mint a futásidejű vagy a legnagyobb memória . Az algoritmus hatékonyságának értékelésében van egy másik szempont is: „átlagos” teljesítmény. Ez feltételezi az algoritmus adatainak statisztikai eloszlásának modelljét, míg az elemzési technikák megvalósítása a kombinatorika és az aszimptotikus értékelés meglehetősen finom módszereit vonja maga után, különös tekintettel a komplex elemzés generáló sorozatainak és fejlett módszereinek alkalmazására . Mindezek a módszerek analitikai kombinatorika néven vannak csoportosítva .
A komplexitás egyéb értékelései, amelyek általában meghaladják a fent javasolt értékeket, és amelyek az algoritmikus problémákat (nem pedig algoritmusokat) bonyolultsági osztályokba sorolják , megtalálhatók az algoritmusok komplexitásának elméletéről szóló cikkben .
Néhány jelzés az algoritmusok hatékonyságáról és torzításairólAz algoritmikus hatékonyság gyakran csak aszimptotikusan ismert, vagyis az n paraméter nagy értékeire . Ha ez a paraméter elég kicsi, akkor a nagyobb aszimptotikus összetettségű algoritmus a gyakorlatban hatékonyabb lehet. Így egy 30 soros tömb rendezéséhez (ez egy kicsi paraméter) nem szükséges olyan fejlett algoritmust használni, mint például a gyors rendezés (átlagosan az egyik aszimptotikusan leghatékonyabb rendezési algoritmus): l A legkönnyebben írható rendezési algoritmus legyen elég hatékony.
Két azonos összetettségű számítógépes algoritmus között a kevesebbet foglaló memóriát fogjuk használni. Az algoritmikus bonyolultság elemzése felhasználható egy algoritmus memóriafoglalásának értékelésére is. Végül egy algoritmust kell választani, nem pedig egy másikat, azon adatok alapján, amelyeket bemenetként vár el. Így a gyors rendezés , amikor az első elemet választjuk pivotnak, katasztrofálisan viselkedik, ha egy már rendezett értéklistára alkalmazzuk. Ezért nem ésszerű használni, ha várhatóan a program már szinte rendezett bemeneti listaként fogad, vagy véletlenszerűen kell kiválasztania a forgatást.
Egyéb figyelembe veendő paraméterek:
Az algoritmus néhány stratégiát dolgozott ki a problémák megoldására:
Bizonyos problémák esetén az algoritmusok túl bonyolultak ahhoz, hogy ésszerű idő alatt eredményt érjenek el, még akkor is, ha fenomenális számítási teljesítményt lehetne használni. Ezért arra késztetnek bennünket, hogy nem szisztematikus módon keressük a megoldást ( Las Vegas-i algoritmus ), vagy elégedjünk meg az optimális megoldáshoz a lehető legközelebb álló megoldással, egymást követő tesztek folytatásával ( Monte-Carlo algoritmus ). Mivel nem minden kombinációt lehet kipróbálni, néhány stratégiai döntést meg kell hozni. Ezek a választások, amelyek általában nagyon függenek a kezelt problémától, alkotják az úgynevezett heurisztikát . A heurisztika célja tehát nem az összes lehetséges kombináció kipróbálása, hanem ésszerű időn belül és más módon, például véletlenszerű sorsolások végrehajtásával megoldást találni. A megoldás lehet pontos (Las Vegas) vagy hozzávetőleges (Monte-Carlo). Az Atlantic City algoritmusai viszont valószínűleg hatékonyan adják meg a valószínűleg helyes választ (mondjuk a tévedés százmilliós esélyével) a feltett kérdésre.
Így használják a sakk vagy a go játékprogramok (csak néhányat említve) gyakran a játékos élményét modellező heurisztikát. Néhány víruskereső szoftver heurisztikára támaszkodik az adatbázisukban nem szereplő számítógépes vírusok felismerésére , az ismert vírusokra való hasonlóságra támaszkodva, ez egy példa az Atlantic City algoritmusára. Hasonlóképpen, a SAT-problémát, amely az NP-teljes probléma archetípusa és ezért nagyon nehéz, praktikus és hatékony módon oldja meg a heurisztika fejlesztése .
Számos klasszikus algoritmus létezik, amelyeket problémák megoldására vagy egyszerűbben a programozási módszerek bemutatására használnak. További részletekért lásd a következő cikkeket (lásd még az algoritmusok listáját ):