2.7 Algoritmer og problemløsning

Oppskriften kommer før maten

Tenk på en god kokk. Før hun begynner å hakke løk og tenne komfyren, har hun en oppskrift i hodet: hva som skal gjøres, i hvilken rekkefølge, og hvordan det skal henge sammen. Uten oppskriften blir det kaos på kjøkkenet. Slik er det også med programmering. Selve koden er bare den siste delen -- tilberedningen. Det som kommer først, er tenkningen, planen, oppskriften. Og den oppskriften kaller vi en algoritme.

En algoritme er en presis, trinnvis beskrivelse av hvordan et problem skal løses. Det fine er at en algoritme finnes uavhengig av programmeringsspråk; den er ren tankegang. Først når du har algoritmen klar, oversetter du den til Python eller et annet språk. Mange nybegynnere hopper rett til koden og roter seg bort -- de prøver å lage maten uten oppskrift. En god programmerer planlegger først.

I denne fortellingen skal vi øve opp den algoritmiske tenkningen. Vi skal lære å beskrive løsninger med pseudokode og flytskjemaer før vi koder. Og vi skal se nærmere på hvordan maskinen faktisk gjør to av sine vanligste oppgaver: å søke etter noe i en liste, og å sortere ting i rekkefølge.

Å skrive oppskriften før koden

La oss si at vi skal finne det største tallet i en liste. Før vi koder, beskriver vi løsningen i pseudokode -- en uformell oppskrift på vanlig norsk, uten strenge syntaksregler. Den kan se slik ut: Sett «største» lik det første tallet. Gå deretter gjennom resten av listen, og hvis et tall er større enn «største», sett «største» lik det tallet. Til slutt: returner «største». Enkelt, leselig, og ikke bundet til noe språk.

Fordelen med pseudokode er at du kan tenke klart over selve logikken uten å snuble i parenteser og kolon. Når oppskriften er klar, blir oversettelsen til Python nesten mekanisk: storste = liste[0], deretter for tall in liste[1:]: med en if-sjekk inni, og til slutt return storste. Pseudokoden var planen; Python-koden er bare planen utført.

Noen ganger er det enda klarere å tegne algoritmen, og da bruker vi et flytskjema -- et diagram med standardiserte symboler. En oval markerer start og slutt. Et rektangel er en prosess, altså noe som skal gjøres. En diamant, eller rombe, er et beslutningspunkt med ja- og nei-utganger. Et parallellogram brukes for inn- og utdata, altså når vi leser eller skriver noe. Og piler viser flyten -- veien gjennom algoritmen. Et flytskjema gir et fugleperspektiv på hvordan løsningen henger sammen, og er spesielt nyttig når logikken har mange forgreininger.

Å lete i en haug

En av de mest grunnleggende oppgavene en datamaskin gjør, er å søke -- å finne ut om noe finnes i en samling, og hvor. Den enkleste metoden kalles lineært søk, og den fungerer akkurat som du ville lett gjennom en bunke papirer: ett for ett, fra topp til bunn, til du finner det du leter etter.

I Python ser et lineært søk slik ut: vi går gjennom listen med for i in range(len(liste)):, og sjekker hvert element mot målet vi leter etter. Finner vi det, returnerer vi posisjonen. Søker vi etter 9 i listen [4, 7, 2, 9], returnerer funksjonen 3, fordi 9 ligger på indeks 3. Finner vi det aldri, returnerer vi gjerne -1 som et signal om «ikke funnet».

Men hvor effektivt er dette? Her kommer et viktig begrep inn: vi tenker på verste tilfelle. Hva om elementet ligger helt sist i listen, eller ikke finnes i det hele tatt? Da må vi sjekke alle elementene før vi vet svaret. For en liste med n elementer betyr det i verste fall n sammenligninger. For en kort liste spiller dette ingen rolle, men for en liste med en million elementer begynner det å merkes. Det er nettopp slike vurderinger -- hvor mye arbeid en algoritme krever i verste fall -- som skiller en gjennomtenkt løsning fra en treig en. For sorterte lister finnes det smartere metoder, som binærsøk, der man halverer søkeområdet for hvert steg.

Å sortere ved å la naboer bytte plass

Den andre klassiske oppgaven er sortering -- å ordne elementer i rekkefølge, for eksempel tall fra minst til størst. Det finnes mange sorteringsalgoritmer, men en av de enkleste å forstå kalles boblesortering. Navnet kommer av at de store tallene sakte «bobler» oppover mot slutten av listen, som luftbobler i vann.

Ideen er forbløffende enkel: gå gjennom listen og sammenlign hvert par av naboer. Hvis venstre nabo er større enn høyre, bytt dem om. Gjenta dette flere ganger, og litt etter litt havner alt på riktig plass. I Python bruker vi en nøstet løkke -- en ytre som gjentar prosessen, og en indre som vandrer gjennom listen og bytter naboer. Selve byttet skjer elegant med liste[j], liste[j + 1] = liste[j + 1], liste[j], som bytter to verdier i én operasjon. Sorterer vi [64, 34, 25, 12], ender vi opp med [12, 25, 34, 64].

Men her må vi være ærlige: boblesortering er enkel å forstå, men den er ikke særlig effektiv. Med den nøstede løkken gjør den svært mange sammenligninger, og for store lister blir den treg. Derfor brukes den nesten aldri i praksis -- den er først og fremst et lærestykke. I virkeligheten lar vi Python gjøre jobben med den innebygde funksjonen sorted(), som bruker langt smartere algoritmer under panseret. Men ved å forstå boblesortering ser du hvordan en maskin faktisk kan ordne kaos til orden, steg for steg.

Oppsummering

Vi har øvd opp den algoritmiske tenkningen og lært at oppskriften kommer før koden. En algoritme er en presis, trinnvis løsning, uavhengig av språk, og vi planlegger den med pseudokode på vanlig norsk eller med flytskjemaer og deres standardsymboler -- oval for start/slutt, rektangel for prosess, diamant for beslutning, parallellogram for inn- og utdata.

Vi så også hvordan maskinen utfører to klassiske oppgaver. Lineært søk leter ett element av gangen, og bruker i verste fall n sammenligninger -- en påminnelse om at effektivitet teller. Boblesortering ordner en liste ved å bytte naboer gjentatte ganger; den er lett å forstå, men for treg til praktisk bruk, der vi heller bruker sorted(). Det viktigste du tar med deg, er vanen med å tenke gjennom løsningen før du skriver en eneste linje kode.