Algoritam , sustavni postupak koji daje - u konačnom broju koraka - odgovor na pitanje ili rješenje problema. Naziv potječe od latinskog prijevoda, Algoritmi brojevi Indijanaca , muslimanskog matematičara iz 9. stoljeća al-Khwarizmi Aritmetika rasprava Al-Khwarizmi u vezi s hinduističkom umjetnošću obračuna.
Za pitanja ili probleme sa samo konačnim skupom slučajeva ili vrijednosti an algoritam uvijek postoji (barem u principu); sastoji se od tablice vrijednosti odgovora. Općenito, nije tako trivijalan postupak za odgovaranje na pitanja ili probleme koji imaju beskonačno broj slučajeva ili vrijednosti koje treba uzeti u obzir, kao što je Je li prirodni broj (1, 2, 3, ...) do premijera? ili Koji je najveći zajednički djelitelj prirodnih brojeva do i b ? Prvo od ovih pitanja pripada klasi koja se naziva prihvatljivom; algoritam koji daje odgovor da ili ne naziva se postupak odluke. Drugo pitanje pripada klasi koja se naziva izračunati; algoritam koji vodi do određenog brojevnog odgovora naziva se računskim postupkom.
Algoritmi postoje za mnoge takve beskonačne klase pitanja; Euklidova Elementi , objavljeno oko 300bce, sadržavao je jedan za pronalaženje najvećeg zajedničkog djelitelja dva prirodna broja. Svaki učenik osnovne škole vježba se u dugoj podjeli, što je algoritam za pitanje Nakon dijeljenja prirodnog broja do drugim prirodnim brojem b , koliki je količnik i ostatak? Korištenje ovog računarskog postupka dovodi do odgovora na odgovorno pitanje Da li b podijeliti do ? (odgovor je da ako je ostatak nula). Ponovljena primjena ovih algoritama na kraju daje odgovor na pitanje koje je moguće riješiti do premijera? (odgovor je negativan ako do je djeljiv s bilo kojim manjim prirodnim brojem osim 1).
Ponekad algoritam ne može postojati za rješavanje beskonačne klase problema, posebno kada se na prihvaćenu metodu izvode neka daljnja ograničenja. Primjerice, dva problema iz Euklidova vremena koja su zahtijevala upotrebu samo kompasa i ravnala (neoznačeno ravnalo) - odsijecanje kuta i konstrukcija kvadrata površine jednake danoj kružnici - bavila su se stoljećima prije nego što se pokazalo da su nemogući . Na prijelazu u 20. stoljeće, utjecajni njemački matematičar David Hilbert predložio je 23 problema koje bi matematičari trebali riješiti u nadolazećem stoljeću. Drugi problem s njegova popisa tražio je istragu dosljednosti aksioma aritmetike. Većina matematičara nije sumnjala u konačno postizanje ovog cilja sve do 1931. godine, kada je austrijski logičar Kurt Gödel pokazao iznenađujući rezultat da moraju postojati aritmetički prijedlozi (ili pitanja) koji se ne mogu dokazati ili opovrgnuti. U osnovi, svaki takav prijedlog dovodi do postupka utvrđivanja koji nikad ne završava (uvjet poznat kao problem zaustavljanja). U neuspjelom naporu da utvrditi barem koji su prijedlozi nerješivi, engleski matematičar i logičar Alan Turing rigorozno je definirao slabo razumljiv koncept algoritma. Iako je Turing na kraju dokazao da moraju postojati neodlučne tvrdnje, njegov opis bitnih značajki bilo kojeg stroja algoritma opće namjene ili Turingova stroja postao je temelj informatika . Danas su pitanja čitljivosti i izračunljivosti središnja za dizajn računalnog programa - posebne vrste algoritma.
