11.1 Algoritmer og pseudokode

Fra kakeoppskrift til algoritme

Har du noen gang bakt en kake? Da har du allerede brukt en algoritme uten a vite det. En kakeoppskrift er nemlig en steg-for-steg-beskrivelse av hva du skal gjore for a oppna et bestemt resultat -- akkurat som en algoritme i matematikken.

En algoritme er en presis, endelig oppskrift for a lose et problem. Den har tre viktige egenskaper: den er presis (hvert steg er entydig beskrevet), den er endelig (den stopper etter et endelig antall steg), og den er generell (den fungerer for alle gyldige inndata, ikke bare ett spesifikt tilfelle).

Du bruker faktisk algoritmer i matematikk hele tiden. Nar du deler to tall med lang divisjon, folger du en algoritme. Nar du finner fellesnevner, folger du en algoritme. I dette kapittelet skal vi se narmere pa hvordan vi kan beskrive slike fremgangsma ter pa tre ulike mater: med vanlig tekst, med flytdiagrammer og med pseudokode. Vi skal ogsa utforske noen klassiske algoritmer, som Euklids algoritme for a finne storste felles divisor og boblsortering for a sortere en liste.

La oss starte med noe enkelt. Tenk deg at du har tre tall -- $a$, $b$ og $c$ -- og du vil finne det storste av dem. Hvordan vil du ga frem? En mulig algoritme er:

1. Sett $\text{storst} = a$
2. Hvis $b > \text{storst}$, sett $\text{storst} = b$
3. Hvis $c > \text{storst}$, sett $\text{storst} = c$
4. Na er $\text{storst}$ det storste av de tre tallene

La oss teste med $a = 7$, $b = 12$, $c = 5$. Forst setter vi storst $= 7$. Sa sjekker vi: er $12 > 7$? Ja, sa storst $= 12$. Er $5 > 12$? Nei, sa storst er fortsatt $12$. Svaret er $12$. Enkelt og presist!

Flytdiagrammer -- algoritmer du kan se

Noen ganger er det lettere a forsta en algoritme hvis du kan se den. Det er her flytdiagrammer kommer inn. Et flytdiagram er en grafisk fremstilling av en algoritme der vi bruker standardiserte symboler:

- Oval (avrundet rektangel): Start og stopp
- Rektangel: Prosess eller beregning
- Diamant (rombe): Beslutning -- et ja/nei-sporsmal
- Parallellogram: Inn- eller utdata
- Pil: Viser retningen flyten gar i

Flytdiagrammer er spesielt nyttige nar det er forgreninger (if/else) eller lokker (gjentakelser), fordi du kan folge pilene og se noyaktig hva som skjer.

La oss lage et flytdiagram som sjekker om et tall er partall eller oddetall. Vi starter med [Start], gar til [Les inn tall n], sa til en diamant [Er n delelig med 2?]. Hvis ja, folger vi pilen til [Skriv ut "Partall"] og deretter [Stopp]. Hvis nei, gar vi til [Skriv ut "Oddetall"] og deretter [Stopp].

Matematisk sjekker vi dette med modulo-operasjonen: $n \mod 2 = 0$ betyr at $n$ er et partall. For eksempel: $14 \mod 2 = 0$, sa 14 er et partall.

Pseudokode -- skriv algoritmen som nesten-kode

Mellom vanlig tekst og ekte programmeringssprak finnes pseudokode. Det er en forenklet, uformell mate a skrive en algoritme pa som ligner et programmeringssprak, men som er skrevet pa vanlig sprak slik at den er lett a forsta.

De vanligste elementene i pseudokode er:
- LES / SKRIV: For inn- og utdata
- SETT / LA: For a tilordne verdier
- HVIS ... SA ... ELLERS: For betingelser (forgreninger)
- GJENTA ... MENS / FOR ... TIL: For lokker (gjentakelser)
- RETURNER: For a gi tilbake et resultat

La oss skrive pseudokode for a beregne summen $1 + 2 + 3 + \ldots + n$:

LES n
SETT sum = 0
FOR i = 1 TIL n
    SETT sum = sum + i
SLUTT FOR
SKRIV "Summen er " + sum

Hvis vi tester med $n = 5$: Vi starter med sum $= 0$. Sa legger vi til 1 (sum $= 1$), deretter 2 (sum $= 3$), deretter 3 (sum $= 6$), deretter 4 (sum $= 10$), og til slutt 5 (sum $= 15$). Summen av tallene fra 1 til 5 er $15$.

Vi kan sjekke med formelen: $\displaystyle \frac{n(n+1)}{2} = \frac{5 \cdot 6}{2} = 15$. Stemmer!

Legg merke til at pseudokode ikke trenger a folge strenge syntaksregler. Den bor bare vare presis nok til at noen kan oversette den til et ekte programmeringssprak.

Euklids algoritme -- 2300 ar gammel og fortsatt genial

En av de eldste kjente algoritmene i verden er Euklids algoritme, oppkalt etter den greske matematikeren Euklid som beskrev den rundt 300 f.Kr. Tenk pa det -- en algoritme som er over 2300 ar gammel, og som fortsatt brukes i dag!

Euklids algoritme finner den storste felles divisor (SFD) av to tall. Den storste felles divisor av to tall $a$ og $b$ er det storste tallet som gar opp i begge. Vi skriver $\text{SFD}(a, b)$. For eksempel er $\text{SFD}(12, 8) = 4$ fordi 4 er det storste tallet som deler bade 12 og 8.

Algoritmen er overraskende enkel:

1. Hvis $b = 0$, er $\text{SFD}(a, b) = a$. Stopp.
2. Beregn resten $r = a \mod b$.
3. Sett $a = b$ og $b = r$.
4. Ga til steg 1.

I pseudokode:

LES a, b
GJENTA MENS b ≠ 0
    SETT r = a mod b
    SETT a = b
    SETT b = r
SLUTT GJENTA
SKRIV "SFD er " + a

La oss prove med $\text{SFD}(48, 18)$. Forst: $48 \mod 18 = 12$, sa vi setter $a = 18$, $b = 12$. Neste runde: $18 \mod 12 = 6$, sa $a = 12$, $b = 6$. Neste: $12 \mod 6 = 0$, sa $a = 6$, $b = 0$. Stopp! $\text{SFD}(48, 18) = 6$.

Vi kan sjekke: $48 = 6 \cdot 8$ og $18 = 6 \cdot 3$. Stemmer! Euklids algoritme er ogsa nyttig for a forkorte broker -- du deler teller og nevner med SFD. For eksempel: $\displaystyle \frac{48}{36}$ forkortes ved a finne $\text{SFD}(48, 36) = 12$, sa $\displaystyle \frac{48}{36} = \frac{4}{3}$.

Boblsortering -- nar tall bobler opp pa riktig plass

Sortering er en av de vanligste oppgavene i programmering. Hver gang du soker etter noe pa nettet, sorterer et digitalt musikkbibliotek eller rangerer en tabell, brukes sorteringsalgoritmer bak kulissene.

En av de enkleste sorteringsalgoritmene er boblsortering (bubble sort). Navnet kommer av at de storste verdiene gradvis "bobler" opp til riktig posisjon, litt som luftbobler i vann. Ideen er:

1. Ga gjennom listen og sammenlign hvert par av naboelementer
2. Hvis to naboer er i feil rekkefolgje, bytt dem
3. Gjenta til hele listen er sortert

La oss sortere listen $[5, 3, 8, 1, 2]$:

Runde 1: Vi sammenligner 5 og 3 -- $5 > 3$, bytt! $\rightarrow [3, 5, 8, 1, 2]$. Sa 5 og 8 -- ok. Sa 8 og 1 -- bytt! $\rightarrow [3, 5, 1, 8, 2]$. Sa 8 og 2 -- bytt! $\rightarrow [3, 5, 1, 2, 8]$. Na har 8 "boblet" opp til riktig plass!

Runde 2: $3 < 5$, ok. $5 > 1$, bytt! $\rightarrow [3, 1, 5, 2, 8]$. $5 > 2$, bytt! $\rightarrow [3, 1, 2, 5, 8]$.

Runde 3: $3 > 1$, bytt! $\rightarrow [1, 3, 2, 5, 8]$. $3 > 2$, bytt! $\rightarrow [1, 2, 3, 5, 8]$.

Runde 4: $1 < 2$, ok. Ingen bytter -- ferdig! Sortert liste: $[1, 2, 3, 5, 8]$.

Boblsortering er kanskje ikke den mest effektive algoritmen for store datamengder, men den er enkel a forsta og viser grunnprinsippet bak sortering.

Oppsummering

I dette kapittelet har vi sett at algoritmer er overalt -- fra kakeoppskrifter til avansert matematikk. Her er det viktigste du bor ta med deg:

- En algoritme er en presis, endelig oppskrift for a lose et problem. Den ma vare presis, endelig og generell.
- Flytdiagrammer bruker standardiserte symboler (ovaler, rektangler, diamanter, parallellogrammer) for a visualisere algoritmer grafisk.
- Pseudokode er en uformell tekstbeskrivelse av en algoritme som ligner et programmeringssprak, med elementer som LES, SKRIV, SETT, HVIS, GJENTA og FOR.
- Euklids algoritme finner storste felles divisor (SFD) ved gjentatt divisjon med rest. Den er over 2300 ar gammel og brukes fortsatt i dag.
- Boblsortering sorterer en liste ved a sammenligne og bytte naboer gjentatte ganger, slik at de storste verdiene "bobler" opp til riktig plass.
- Modulo ($a \mod b$) gir resten ved heltallsdivisjon og er et sentralt verktoy i mange algoritmer.