Algoritm

Algoritm on astmeline tegevusjuhis, juhend või eeskiri mingi tegevuse sooritamiseks või eesmärgi saavutamiseks. Kõige sagedamini kasutatakse seda terminit matemaatilise ülesande lahendamiseks mõeldud eeskirja kohta. Algoritmi esitust mingis formaalses keeles, tavaliselt programmeerimiskeeles või masinakoodis, nimetatakse arvutiprogrammiks.

Sõna "algoritm" tuleb 9. sajandi araabia matemaatiku Muḩammad ibn Mūsā al-Khwārizmī hüüdnimest "al-Horazmi" ('horezmlane') tema sünnilinna, praeguses Usbekistanis asuva Hiiva tolleaegse nime järgi. Al-Horazmi tööd tõlgiti 12. sajandil ladina keelde ja autorinimeks märgiti Algorithmi. Selle töö kaudu jõudis Lääne-Euroopasse mitu võrrandite lahendamise eeskirja, mis kõik algasid fraasiga "Nõnda kõneles Algorithmi ...". Selle järgi hakatigi üksikasjalikke tegutsemisjuhiseid algoritmideks kutsuma.

Mittematemaatiliste algoritmidega puutume kokku iga päev, näiteks kokaraamatus olevad retseptid või sõbrale jäetud juhised kohtumispaika jõudmiseks. Algoritmid on ka koolis õpetatavad mitmekohaliste arvude kirjaliku liitmise, lahutamise, korrutamise ja jagamise eeskirjad.

Esimesed katsed anda algoritmile matemaatiliselt range kuju tehti 1920. aastatel. Esmalt arvati, et formaliseerimiseks kõlbab lihtrekursiivne funktsioon. 1928 avaldas Wilhelm Ackermann näite funktsioonist, mis on algoritmiliselt arvutatav, kuid ei ole lihtrekursiivne. 1930. aastatel lõid Alonzo Church ja Stephen Kleene lambdaarvutuse. Sel ajal lõid ka Alan Turing ja Emil Leon Post Turingi masina ning Kurt Gödeli ja Jacques Herbrand võtsid kasutusele täisrekursiivse funktsiooni mõiste.

Rekursiivne algoritm

Rekursiivne algoritm ehk iseenesessepöörduv algoritm on algoritm, mis kutsub töö käigus välja iseennast. Leidub programmeerimiskeeli, milles puudub tsüklikäsk ja milles tsükkel realiseeritakse reeglina rekursiooni kaudu, näiteks Prolog.

Väga suure korduste arvu korral on parem realiseerida iteratiivne algoritm, sest igal enesessepöördumisel eraldatakse rekursiivsele alamprogrammile mälu ja kui rekursiooni sügavus (iseenesessepöördumiste arv) ületab miljoni piiri, on märgatav kiiruse eksponentaalne erinevus.

Vaata ka

Välislingid

Algoritmid ja nende keerukus
4. Algoritm ja plokkskeem Programmeerimise algkursus, Tartu Ülikool
Dictionary of Algorithms and Data Structures (inglise keeles)
Special Interest Group on Algorithms and Computation Theory (inglise keeles)
MIT 6.046J / 18.410J Introduction to Algorithms – Fall 2005 (inglise keeles)