Algoritam, sustavni postupak koji daje - u ograničenom broju koraka - odgovor na pitanje ili rješenje problema. Naziv potječe od latinskog prijevoda, Algoritmi de numero Indorum, aritmetičkog traktata muslimanskog matematičara al-Khwarizmija iz 9. stoljeća „Al-Khwarizmi o hinduističkoj umjetnosti obračuna“.
informatika: Algoritmi i složenost
Algoritam je specifičan postupak za rješavanje dobro definiranog računarskog problema. Razvoj i analiza algoritama je temeljna
Za pitanja ili probleme sa samo ograničenim nizom slučajeva ili vrijednosti algoritam uvijek postoji (barem u načelu); sastoji se od tablice vrijednosti odgovora. Općenito, nije tako beznačajan postupak odgovaranja na pitanja ili probleme koji imaju beskonačan broj slučajeva ili vrijednosti, poput "Je li prirodni broj (1, 2, 3, …) glavni?" ili "Koji je najveći zajednički djelitelj prirodnih brojeva a i b?" Prvo od ovih pitanja pripada klasi koja se zove decidable; algoritam koji proizvodi odgovor da ili ne zove se odlučivanjem. Drugo pitanje pripada klasi koja se zove computable; algoritam koji vodi do odgovora na određeni broj zove se postupak računanja.
Algoritmi postoje za mnoge takve beskonačne klase pitanja; Euclidovi Elementi, objavljeni oko 300 bc, sadržavali su jedan za pronalaženje najvećeg zajedničkog djelitelja dvaju prirodnih brojeva. Svaki je učenik osnovne škole izbušen u dugoj podjeli, što je algoritam za pitanje "Kada podijelim prirodni broj a s drugim prirodnim brojem b, koji su kvocijent i ostatak?" Upotreba ovog računačkog postupka dovodi do odgovora na odlučujuće pitanje „B b dijeli a?“ (odgovor je da ako je ostatak nula). Ponavljana primjena ovih algoritama na kraju daje odgovor na odlučno pitanje "Je li glavni?" (odgovor je ne ako je a 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 napravi neko daljnje ograničenje prema prihvaćenoj metodi. Na primjer, dva problema iz Euklidovog vremena koja su zahtijevala korištenje samo kompasa i ravnala (neoznačeni vladar) - ispitivanje kuta i konstrukcija kvadrata s površinom jednakim zadanom krugu - tragala su stoljećima prije nego što se pokazalo da nisu mogući, Na prijelazu 20. stoljeća utjecajni njemački matematičar David Hilbert predložio je 23 problema za rješavanje matematičara u narednom stoljeću. Drugi problem na njegovom popisu zatražio je ispitivanje konzistentnosti aritmetike aksioma. Većina matematičara nije imala nikakve sumnje u moguće postizanje tog cilja sve do 1931. godine, kada je logičar Kurt Gödel rođen u Austriji pokazao iznenađujući rezultat da moraju postojati aritmetičke sugestije (ili pitanja) koja se ne mogu dokazati ili opovrgnuti. U osnovi, svaki takav prijedlog dovodi do postupka utvrđivanja koji se nikada ne završava (uvjet poznat kao problem zaustavljanja). U neuspješnom pokušaju da utvrdi barem koje su tvrdnje nerešive, engleski matematičar i logičar Alan Turing strogo je definirao slabo shvaćen koncept algoritma. Iako je Turing na kraju dokazao da moraju postojati nedodirljivi prijedlozi, njegov opis bitnih značajki bilo kojeg algoritma stroja opće namjene ili Turingovog stroja postao je temelj računalne znanosti. Danas su pitanja decidabilnosti i obradivosti središnja u dizajnu računalnog programa - posebne vrste algoritama.
