Algoritme

Ein algoritme i matematikk og informatikk er ei oppskrift på korleis ein kan løyse ein bestemt type problem. Ordet kjem opphavleg frå den persiske matematikaren og astronomen al-Khowarizmi (ca. 780-850)). I ei av bøkene sine beskriv han ein algoritme for korleis ein kan løyse ein klase av andregradslikningar.

Algoritmar er først og fremst eit tema i matematikk og informatikk, og vert studert i nokre spesialområde i teoretisk informatikk, som algoritmeteori, kompleksitetsteori og bereknbarheitsteori. I form av dataprogram vert algoritmar nytta til å styre datamaskinar.

Mange matematikarar og logikarar i det 19. og 20. hundreåret likte ikkje den manglande nøyaktigheita i omgrepet algoritme, og ønskte eit meir teoretisk tilfredsstillande fundament. I den første halvdelen av det 20. hundreåret vart det gjort fleire forsøk på å finne ein god definisjon. Turingmaskina til Alan Turing, Lambda-kalkulusen til Alonzo Church, rekursive funksjonar, Chomsky-grammatikken og Markov-algoritmer er alle formaliseringar av bereknbarheitsomgrepet. Det var prova at alle desse metodane er like kraftige. Alle kan emulere ein turingmaskin, og alle kan verte emulert av ei turingmaskin. Ved hjelp av turingmaskina vert følgjande formelle definisjon mogleg:

Ei berekningsoppskrift vert kalla ein algoritme om det finst ei Turing-maskin som er ekvivalent til oppskrifta og som stoppar for alle inndata som har ei løysing.

Frå denne definisjonen kan ein utleie følgjande eigenskapar:

1. Ein må kunne skrive oppskrifta med ein endeleg lang tekst.
2. Eit kvart steg i oppskrifta må kunne utførast.
3. På kvart tidspunkt kan berre ein endeleg stor lagringsplass nyttast.
4. Oppskrifta kan berre nytte eit endeleg tal på steg.

I praktiske problem krev ein vanlegvis òg at ein algoritme skal oppfylle følgjande vilkår:

1. Algoritmen må alltid gi same svar dersom inndataa er dei same.
2. Kva det neste steget i oppskrifta er må alltid vere eintydig definert.

Analyse av algoritmar er eit hovudtema i informatikk, og vert vanlegvis gjort teoretisk utan å lage konkrete implementeringar i programmeringsspråk. Den liknar difor andre matematiske område, der ein heller studerer dei grunnleggjande konsepta, enn å sjå på konkret bruk. Ein studerer difor algoritmar i ei sterkt formalisert form.

Ein deler analysen i ulike delområde. I kompleksitetsteori studerer ein ressursbruken til algoritmane, det vil seie tida det tek å køyre algoritmen og lagringsplassen som krevst. I bereknbarheitsteori studerer ein spørsmålet om ein gitt algoritme i det heile vil terminere.