Algoritm, süsteemne protseduur, mis loob - piiratud arvu sammude jooksul - vastuse küsimusele või probleemi lahendusele. Nimi tuleneb 9. sajandi moslemite matemaatiku al-Khwarizmi aritmeetilisest traktaadist “Al-Khwarizmi: Hindu arvestamise kunstist” ladinakeelses tõlkes Algoritmi de numero Indorum.
arvutiteadus: algoritmid ja keerukus
Algoritm on konkreetne protseduur täpselt määratletud arvutusprobleemi lahendamiseks. Algoritmide väljatöötamine ja analüüs on ülioluline
Ainult piiratud juhtumite või väärtustega komplekti kuuluvate küsimuste või probleemide korral on algoritm alati olemas (vähemalt põhimõtteliselt); see koosneb vastuste väärtuste tabelist. Üldiselt ei ole küsimus või probleem, millele tuleb arvestada lõpmatul hulgal juhtumeid või väärtusi, näiteks nii tühine protseduur, nagu näiteks: "Kas naturaalarv (1, 2, 3, …) on peamine?" või "Mis on naturaalarvude a ja b suurim jagaja?" Neist esimene kuulub klassi, mida nimetatakse otsustatavaks; algoritmi, mis annab jah või ei vastuse, nimetatakse otsustusprotseduuriks. Teine küsimus kuulub klassi, mida nimetatakse arvutatavaks; algoritmi, mis viib konkreetse arvu vastuseni, nimetatakse arvutusprotseduuriks.
Paljude selliste lõpmatute küsimuste klasside jaoks on olemas algoritmid; Eukleidi elemendid, avaldatud umbes 300 bc, sisaldasid ühte kahe naturaalarvu suurima ühise jagaja leidmiseks. Iga põhikooliõpilane õpitakse pikaks jagunemiseks, mis on algoritm küsimusele “Naturaalarvu a jagamisel teise naturaalarvuga b, mis on jaotis ja ülejäänud?” Selle arvutusprotseduuri kasutamine annab vastuse otsustatavale küsimusele “Kas b jagab a?” (vastus on jah, kui ülejäänud osa on null). Nende algoritmide korduv rakendamine annab lõpuks vastuse otsustatavale küsimusele “Kas peamine?” (vastus on eitav, kui a on jagatud väiksema naturaalarvuga peale 1).
Mõnikord ei saa algoritmi eksisteerida lõpmatu klassi probleemide lahendamiseks, eriti kui aktsepteeritud meetodile seatakse veel mõned piirangud. Näiteks kaks Euclidi ajast pärit probleemi, mis nõudsid ainult kompassi ja sirgjoone kasutamist (märgistamata joonlauda) - nurga korrastamist ja ruudu ehitamist, mille pindala oleks võrdne antud ringiga - lahendati sajandeid enne, kui need osutusid võimatuks. 20. sajandi vahetusel tegi mõjukas saksa matemaatik David Hilbert ettepaneku matemaatikutele järgmisel sajandil lahendada 23 probleemi. Tema nimekirja teine probleem palus uurida aritmeetika aksioomide järjepidevust. Enamikul matemaatikutest oli selle eesmärgi saavutamises kuni 1931. aastani vähe kahtlusi, kui Austrias sündinud loogik Kurt Gödel näitas üllatavat tulemust, et peavad olema aritmeetilised ettepanekud (või küsimused), mida ei saa tõestada ega ümber lükata. Põhimõtteliselt viib iga selline väide määramisprotseduurini, mis ei lõpe kunagi (seisund, mida tuntakse peatamisprobleemina). Inglise matemaatik ja loogik Alan Turing määratles algoritmi lahtiselt mõistetava kontseptsiooni ebaõnnestunult vähemalt selle osas, millised väited on lahendamatud. Ehkki Turing tõestas lõpuks, et eksisteerivad vaieldamatud ettepanekud, sai tema kirjeldus mis tahes üldotstarbelise algoritmi masina ehk Turingi masina olulistest tunnustest infotehnoloogia alustalaks. Tänapäeval on arvutiprogrammi kavandamisel kesksel kohal otsustamis- ja arvutatavusküsimused - eriliigiline algoritm.
