Algoritme

Fra Wikipedia, den frie encyklopedi

I matematikk og informatikk er en algoritme en presis beskrivelse av en serie operasjoner som skal utføres for å løse en type problemer. Ordet kommer fra navnet til matematikeren og astronomen al-Khowarizmi (ca. 780 - 850). Han skrev flere bøker, blant annet boken Al-jabr wa'l muqabalah. Den inneholder en oppskrift - eller en algoritme - for hvordan bestemte annengradsligninger kan løses.

[rediger] 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.

  1. Oppskriften må kunne beskrives med en endelig tekst.
  2. Hvert skritt i oppskriften må kunne utføres.
  3. På ethvert tidspunkt kan kun et endelig stort minne benyttes.
  4. Oppskriften kan bare bruke et endelig antall skritt.

[rediger] Eksempel: Euklids algoritme

Euklids algoritme ble beskrevet rundt 300 f. Kr., og brukes for å finne største felles faktor til to naturlige tall A og B:

  1. Anta at A er det største av de to tallene A og B. (Hvis ikke, byttes tallene om.)
  2. Sett A := A - B.
  3. Hvis A og B er ulike, gå tilbake til skritt 1. Hvis de er like, avslutt algoritmen. Dette tallet er den største felles faktor til A og B.

Eksempel:'

Vi vil finne den største felles faktor til tallene 21 og 15. Vi bruker Euklids algoritme som beskrevet:

  1. A = 21, B = 15. Vi setter A = 21 - 15 = 6.
  2. A = 15, B = 6. Vi setter A = 15 - 6 = 9.
  3. A = 9, B = 6. Vi setter A = 9 - 6 = 3.
  4. A = 6, B = 3. Vi setter A = 6 - 3 = 3.
  5. A = B = 3. Vi avslutter algoritmen, med resultatet at største felles faktor til 21 og 15 er 3.