Algoritmi, systemaattinen menettely, joka tuottaa - äärellisessä määrässä vaiheita - vastauksen kysymykseen tai ongelman ratkaisuun. Nimi johtuu yhdeksännen vuosisadan muslimimatemaatikon al-Khwarizmin aritmeettisen tutkielman ”Al-Khwarizmi koskien hindulaskentataitoa” latinalaisesta käännöksestä Algoritmi de numero Indorum.
tietojenkäsittelytiede: Algoritmit ja monimutkaisuus
Algoritmi on erityinen menetelmä hyvin määritellyn laskennallisen ongelman ratkaisemiseksi. Algoritmien kehittäminen ja analysointi on olennaista
Kysymyksissä tai ongelmissa, joissa on vain rajallinen tapausten tai arvojen joukko, algoritmi on aina olemassa (ainakin periaatteessa); se koostuu vastausten arvotaulukosta. Yleensä ei ole niin vähäpätöinen menettely vastata kysymyksiin tai ongelmiin, joissa on ääretön määrä käsiteltäviä tapauksia tai arvoja, kuten "Onko luonnollinen luku (1, 2, 3, …) alkuluku?" tai "Mikä on luonnollisten lukujen a ja b suurin yhteinen jakaja?" Ensimmäinen näistä kysymyksistä kuuluu luokkaan nimeltä decidable; algoritmia, joka tuottaa kyllä tai ei vastauksen, kutsutaan päätöksentekomenetelmäksi. Toinen kysymys kuuluu luokkaan nimeltä laskettava; algoritmia, joka johtaa tiettyyn numerovastaukseen, kutsutaan laskentamenetelmäksi.
Monille sellaisille äärettömille kysymysluokille on olemassa algoritmeja; Euclid's Elements, julkaistu noin 300 bc, sisälsi yhden kahden luonnollisen luvun suurimman yhteisen jakajan löytämiseksi. Jokainen ala-asteen oppilaan tehtävänä on porata pitkä jako, mikä on algoritmi kysymykseen ”Kun jaat luonnollisen luvun a toisella luonnollisella numerolla b, mitkä ovat osamäärät ja loput?” Tämän laskennallisen proseduurin käyttö johtaa vastaukseen ratkaisevaan kysymykseen ”Jako b jakaa a?” (vastaus on kyllä, jos loppuosa on nolla). Näiden algoritmien toistuva soveltaminen tuottaa lopulta vastauksen ratkaisevaan kysymykseen ”Onko ensisijainen?” (vastaus on ei, jos a on jaollinen millä tahansa pienemmällä luonnollisella numerolla paitsi 1).
Joskus algoritmia ei voi olla olemassa ääretön ongelmaluokan ratkaisemiseksi, etenkin kun hyväksytylle menetelmälle tehdään joitain lisärajoituksia. Esimerkiksi kahta Euclidin aikakautta koskevaa ongelmaa, jotka vaativat vain kompassin ja suoraviivaisen (merkitsemättömän viivaimen) käyttöä - kulman rakentuminen ja neliön rakentaminen, jonka pinta-ala vastaa tiettyä ympyrää - etsittiin vuosisatojen ajan, ennen kuin niiden osoitettiin olevan mahdoton. 1900-luvun vaihteessa vaikutusvaltainen saksalainen matemaatikko David Hilbert ehdotti matemaatikoille 23 ongelmaa tulevan vuosisadan ratkaisemiseksi. Hänen luettelonsa toinen ongelma pyysi tutkimaan aritmeettisten aksioomien johdonmukaisuutta. Useimmilla matemaatikoilla oli vähän epäilyksiä tämän tavoitteen saavuttamisesta vuoteen 1931 saakka, kun itävaltalainen syntynyt logisti Kurt Gödel osoitti yllättävän tuloksen, että on oltava aritmeettisia ehdotuksia (tai kysymyksiä), joita ei voida todistaa tai kiistää. Pohjimmiltaan mikä tahansa tällainen ehdotus johtaa määritysmenettelyyn, joka ei lopu (tilanne, jota kutsutaan pysähtymisongelmaksi). Englantilainen matemaatikko ja logistiikka Alan Turing määritteli ankarasti yrittäessään selvittää ainakin, mitkä ehdotukset ovat ratkaisemattomia, algoritmin tiukasti ymmärretyn käsitteen. Vaikka Turing päätyi todistamaan, että on olemassa päättämättömiä ehdotuksia, hänen kuvauksestaan minkä tahansa yleiskäyttöisen algoritmikoneen tai Turingin koneen olennaisista ominaisuuksista tuli tietotekniikan perusta. Nykyään päätöksenteko- ja laskettavuuskysymykset ovat keskeisiä tietokoneohjelman suunnittelussa - erityinen algoritmityyppi.
