Algoritme

**Algoritme** (middelalderlatin *algorithmus*, via gresk *arithmos*, «tall») er i matematikk og informatikk en presis beskrivelse av en begrenset sekvens eller matematisk instruksjoner som skal utføres for å løse et eller flere problemer. Hvis en prosess er *algoritmisk*, kan den skrives som en serie operasjoner som kan utføres gjennom beregninger.

Algoritmer brukes som spesifikasjoner for å utføre beregninger og databehandling. Mer avanserte algoritmer kan bruke betingelser for å avlede kodeutførelsen som spesifiserte handlinger trinn for trinn gjennom ulike ruter (referert til som automatisert beslutningstaking) og utlede gyldige slutninger (referert til som automatisert resonnement).

Mindre formelt er en algoritme enhver skrittvis prosedyre på en oppgave, gitt at oppgaven kan løses ved et endelig antall steg.

Algoritmer er også brukt i programmering, hvor kode vil følge spesifikke operasjoner for å bli gjennomført av en datamaskin. En algoritme kan ofte også inneholde variabler som trenger mellomregning. Et eksempel på dette kan være pseudokode brukt til programmeringsspråk.

## Etymologi
Ordet «algoritme» har en kompleks etymologi, og kommer fra navnet til den persiske matematikeren og astronomen på 800-tallet, Muhammad ibn Musa al-Khwarizmi. På begynnelsen av 1100-tallet dukket det opp latinske oversettelser av al-Khwarizmis tekster som involverte det hindu-arabiske tallsystemet og aritmetikk, for eksempel *Liber Alghoarismi de practica arismetrice*, tilskrevet Johannes Hispalensis, og *Liber Algorismi de numero Indorum*, tilskrevet Adelard fra Bath. Således ble *alghoarismi* eller *algorismi* latiniseringen av Al-Khwarizmis navn; teksten starter med uttrykket *Dixit Algorismi*, eller «Så snakket Al-Khwarizmi». 

På gammelfransk ble *algorismus* til *augorime*, som dannet grunnlaget fra den eldste engelske formen av ordet, *augrim*. Rundt 1230 er det dokumentert i bruk på engelsk, og deretter av Geoffrey Chaucer i 1391, som tok i bruk det franske uttrykket i engelsk. Det forble ordet i referanse til arabiske tallsystem på engelsk, men på slutten av 1600-tallet ble det alternative versjonen, *algorithm*, fremmet og som hadde sitt opphav av påvirkning fra det greske ordet ἀριθμός (*aritmos*, «tall»), jf. aritmetikk), ble det latinske ordet endret til algoritme. Fra 1930-tallet fikk ordet sitt nåværende innhold, matematiske prosedyrer trinn for trinn i bruk dataprosessing. Algol som er navnet på et programmeringsspråk, fikk sitt navn på slutten av 950-tallet fra *algo*rithmic *l*anguage (algoritmisk språk).

## Formell definisjon
Mange matematikere og logikere i det 19. og 20. århundret hadde problemer med at begrepet algoritme ikke hadde noen nøyaktig matematisk definisjon. I den første halvdelen av 1900-tallet, ble det gjort mange forsøk på å finne en presis definisjon. Turingmaskinen til Alan Turing, lambda-kalkulusen til Alonzo Church, rekursive funksjoner, Chomsky-grammatikker, og Markov-algoritmer, er alle formaliseringer av beregnbarhetsbegrepet.

Det ble bevist at alle disse metodene er like kraftige. Alle kan bli emulert av en turingmaskin, og omvendt kan hver av dem selv emulere en turingmaskin.

Ved hjelp av begrepet turingmaskin, kan man formulere den følgende formelle definisjonen av begrepet algoritme:

*En oppskrift for beregning av løsningen til et problem er en algoritme hvis det finnes en turingmaskin som er ekvivalent til oppskriften, og som stopper for enhver inndata som har en løsning.*

Fra denne definisjonen kan følgende egenskaper avledes:
# Oppskriften må kunne beskrives med en endelig tekst.
# Hvert skritt i oppskriften må kunne utføres.
# På ethvert tidspunkt kan kun et endelig stort minne benyttes.
# Oppskriften kan bare bruke et endelig antall skritt.

Euklids algoritme for å finne største felles faktor til to tall, er et eksempel på en algoritme.

## Referanser


## Eksterne lenker
* 
* Weisstein, Eric W.: "Algorithm, *MathWorld*.
* Dictionary of Algorithms and Data Structures, *National Institute of Standards and Technology*