3.1 Hva er en algoritme?

Du har alltid brukt algoritmer

Har du fulgt en matoppskrift, bygget et LEGO-sett etter instruksjonene eller forklart veien til noen? Da har du brukt algoritmer uten å tenke på det. En algoritme er rett og slett en presis, trinnvis beskrivelse av hvordan en oppgave skal utføres. Ordet kommer fra navnet til den persiske matematikeren al-Khwarizmi fra 800-tallet, som i latinsk oversettelse ble til «Algoritmi».

Mer presist er en algoritme en endelig, ordnet rekke av entydige instruksjoner som løser et problem. Den tar imot inndata, prosesserer dem steg for steg, og gir utdata. En pannekakeoppskrift passer perfekt: inndata er ingrediensene, instruksjonene er blandingen og stekingen, og utdata er pannekakene. En veibeskrivelse er en algoritme – «gå ut, ta til venstre, rett fram 200 meter» – og det er morgenrutinen din også. Rekkefølgen betyr noe; du kan ikke steke deigen før den er blandet.

Det som gjør algoritmer i informatikk spesielle, er at de må være så presise at en datamaskin kan følge dem. Maskinen gjør nøyaktig det du ber om – den kan ikke tolke, gjette eller improvisere. Derfor må algoritmene vi skriver for datamaskiner være helt entydige. Vil du for eksempel finne det største av tre tall, antar du først at det første er størst, og oppdaterer deretter hvis et av de andre er større:

storst = a
if b > storst:
    storst = b
if c > storst:
    storst = c

Det fine er at denne algoritmen gir riktig svar uansett hvilke tre tall du gir den.

Hva skiller en god algoritme fra en dårlig?

Ikke alle instruksjoner er algoritmer. For å kvalifisere må flere krav være oppfylt. Entydighet betyr at hvert steg har én eneste tolkning – «tilsett litt salt» duger ikke, men «tilsett 5 gram salt» gjør det. Terminering betyr at algoritmen alltid stopper etter et endelig antall steg; den kan ikke gå i en evig løkke. Korrekthet betyr at den gir riktig svar for alle gyldige inndata, ikke bare noen. Effektivitet betyr at den bruker tid og minne fornuftig – kan du løse noe på 10 steg framfor 1000, er det bedre. Og generalitet betyr at den håndterer en hel klasse problemer, enten du gir den 3 tall eller en million.

Det vakre er at all denne kompleksiteten kan bygges av bare tre kontrollstrukturer. Sekvens er instruksjoner som utføres i rekkefølge, fra topp til bunn – som når du regner ut et areal: definer lengde, definer bredde, gang dem sammen, skriv ut. Betingelse (valg) lar programmet ta avgjørelser med if, elif og else, som å sjekke om et tall er positivt, negativt eller null. Iterasjon (løkke) gjentar instruksjoner, enten med en for-løkke når du vet antallet, eller en while-løkke som kjører til en betingelse endres. I 1966 beviste Böhm og Jacopini at enhver algoritme kan uttrykkes med bare disse tre – det kalles strukturteoremet.

Alle tre i ett: primtallssjekken

La oss bygge en algoritme som bruker alle tre kontrollstrukturene samtidig – en sjekk på om et tall er et primtall (et tall større enn 1 som bare er delelig med 1 og seg selv). Algoritmen i ord: les inn et tall n; er n mindre enn 2, er det ikke primtall; ellers, sjekk hvert tall fra 2 til n-1, og er n delelig med noen av dem, er det ikke primtall; finner du ingen divisor, er n et primtall.

Oversatt til Python:

n = int(input("Skriv inn et tall: "))
if n < 2:
    print(f"{n} er IKKE et primtall")
else:
    er_primtall = True
    for i in range(2, n):
        if n % i == 0:
            er_primtall = False
            break
    if er_primtall:
        print(f"{n} ER et primtall")
    else:
        print(f"{n} er IKKE et primtall")

Ser du de tre strukturene? Sekvensen er linjene som kjøres i rekkefølge. Betingelsen er if-setningene som sjekker delbarhet. Iterasjonen er for-løkken som prøver alle mulige divisorer. Et lite, men viktig grep er break: så snart vi finner én divisor, vet vi at tallet ikke er primtall, og vi avbryter løkken i stedet for å sjekke resten. Det gjør algoritmen mer effektiv – nettopp en av egenskapene til en god algoritme.

Oppsummering

En algoritme er en endelig, ordnet rekke entydige instruksjoner for å løse et problem – fra al-Khwarizmis likninger til dagens pannekakeoppskrifter og veibeskrivelser. For datamaskiner må de være helt presise, fordi maskinen ikke kan gjette.

En god algoritme er entydig, terminerer, er korrekt, effektiv og generell. Og uansett hvor komplekst problemet er, kan løsningen bygges av bare tre kontrollstrukturer: sekvens, betingelse og iterasjon – akkurat som strukturteoremet sier. Primtallssjekken viste alle tre i aksjon, og break-grepet minnet oss om at effektivitet teller. Med dette har du grunnlaget for å oversette enhver oppskrift til kjørbar kode.