Algoritme

Algoritme (middelalderlatin algorithmus, via gresk arithmos, «tall»)«algoritme», NAOB 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.«algorithm», Merriam-Webster 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«Algorithm | CodeGlossary», GitHub Pages (referert til som automatisert beslutningstaking)«What is Automated Decision-Making (ADM)?», Symbio6 og utlede gyldige slutninger (referert til som automatisert resonnement).«What is Automated Reasoning?», Amazon Web Services

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.Blair, Ann; Duguid, Paul; Goeing, Anja-Silvia; Grafton, Anthony (2021): Information: A Historical Companion, Princeton: Princeton University Press, s. 247. Således ble alghoarismi eller algorismi latiniseringen av Al-Khwarizmis navn; teksten starter med uttrykket Dixit Algorismi, eller «Så snakket Al-Khwarizmi».Grossman, David A.; Frieder, Ophir (2004): Information Retrieval: Algorithms and Heuristics, 2. utg., ISBN 1402030045. 

På gammelfransk ble algorismus til augorime, som dannet grunnlaget fra den eldste engelske formen av ordet, augrim.Ayto, John (1990): Dictionary of Word Origins, Bloomsbury Reference, s. 16. 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 algorithmic language (algoritmisk språk).«algorithm (n.)», Online Etymology Dictionary

 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


Kategori:Programmering
Kategori:1000 artikler enhver Wikipedia bør ha
Kategori:Matematisk logikk