Algoritmisk tenkning i problemløsing

Tre krav skiller en algoritme fra en løs beskrivelse: hvert steg må være ENTYDIG (ingen tolkning), rekkefølgen må være bestemt, og den må STOPPE etter endelig mange steg. «Kok opp vann» duger som oppskrift til middag, men ikke som algoritme: «varm vannet til det koker, maks $10$ minutter» gjør det. Framgangsmåten når du skal lage en: løs problemet én gang for hånd, skriv ned nøyaktig hva du gjorde, og bytt så de konkrete tallene med variabler.

abc-formelen

$x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$

Diskriminanten

$D = b^2 - 4ac$

abc-formelen som algoritme
Steg	Handling
1	Les av a, b og c
2	Regn ut b² - 4ac
3	Er den negativ: stopp, ingen løsning
4	Regn ut de to x-verdiene
5	Skriv ut svaret

Tips

Test algoritmen på et tilfelle du kan svaret på FØR du bruker den på noe nytt. Finner du feilen der, sparer du deg for å mistolke et ukjent svar.
Skriv stegene i punktliste før du skriver kode. Nesten alle programmeringsfeil i 1T er egentlig tenkefeil som ble synlige først i koden.
Løs én bit om gangen. Står du fast på et sammensatt problem, del det i mindre biter som hver kan løses for seg: «les inn tallene», «regn ut diskriminanten», «avgjør antall løsninger», «skriv ut svaret». Hver bit blir kort nok til å teste alene, og du finner feil i den ene biten uten å lete gjennom hele algoritmen. Det er nøyaktig samme idé som å regne en lang oppgave i delsvar i stedet for i ett jafs.

Eksempel: Fra hånd-regning til algoritme

Beskriv en algoritme som avgjør om et helt tall $n$ er et primtall, og bruk den på $n = 91$ .

Løsning:

Vi skal avgjøre om $n = 91$ er et primtall, og løser først for hånd: et primtall er kun delelig med $1$ og seg selv, så vi må teste divisorer
det holder å teste opp til $\sqrt{n}$ , for en større divisor må ha en mindre partner
for $n = 91$ er $\sqrt{91} \approx 9{,}5$ , så vi tester $2, 3, 5, 7$
$91$ er ikke delelig med $2, 3$ eller $5$ , men $91 = 7 \cdot 13$
algoritmen stopper med én gang den finner en divisor. Tallet $91$ er ikke et primtall.

Algoritmen kjørt på n = 91
Divisor	Går opp?	Handling
2	nei	fortsett
3	nei	fortsett
5	nei	fortsett
7	ja	stopp: ikke primtall

Alternativ forklaring/metode: Simuler endring steg for steg

Alternativ metode – innenfor pensum, men ikke hovedmetoden her

Euler-steg for modellering

Skal du modellere noe som endrer seg over tid, en bestand, en temperatur, en saldo: kan du dele opp problemet i identiske, gjentatte steg: finn endringen akkurat NÅ, legg den til, og gjenta. Regelen er $y_{ny} = y_{gammel} + y' \cdot \Delta t$ . En bestand på $100$ dyr vokser med $10\ \%$ av bestanden per tidssteg ( $y' = 0{,}1y$ ), med $\Delta t = 1$ : steg 1 gir $y' = 0{,}1 \cdot 100 = 10$ , så $y_{ny} = 100 + 10 = 110$ → steg 2 gir $y' = 0{,}1 \cdot 110 = 11$ , så $y_{ny} = 121$ → steg 3 gir $y' = 0{,}1 \cdot 121 = 12{,}1$ , så $y_{ny} = 133{,}1$ . Samme dekomponerings-idé som abc-formelen delt i biter, bare at «biten» her gjentas mange ganger i en løkke.

Euler-steg: bestand på 100, vekst 10 % per steg
Steg	y' = 0,1 · y	y_ny = y + y'
0		100
1	10	110
2	11	121
3	12,1	133,1

Alternativ forklaring/metode: Finn største felles faktor med Euklids algoritme

Tilleggsinformasjon – ikke pensum på dette nivået

Euklids algoritme (historisk eksempel)

Forutsetninger:

Ikke pensum i seg selv (KM403 nevner ingen navngitte klassiske algoritmer), tatt med som et konkret, historisk eksempel på at «entydig, bestemt rekkefølge, stopper» (kriteriene i forklaringen over) er nøyaktig hva som gjør en 2300 år gammel oppskrift til en algoritme like mye som en moderne én.

Den eldste kjente algoritmen som fortsatt brukes i dag: for å finne største felles faktor (SFF) til to tall, del det største tallet på det minste og se på RESTEN. Bytt så ut det største tallet med det minste, og det minste med resten. Gjenta til resten blir $0$ . Da er det forrige tallet SFF-en. Den STOPPER garantert, fordi resten blir mindre for hver runde, og en synkende følge av hele tall (større enn eller lik $0$ ) må til slutt nå $0$ .

SFF(84, 36) med Euklids algoritme
Stort tall	Lite tall	Rest ved divisjon
84	36	84 = 2 · 36 + 12
36	12	36 = 3 · 12 + 0
		Rest 0 → SFF = 12

Alternativ forklaring/metode: Tilnærme en kvadratrot med Herons metode

Tilleggsinformasjon – ikke pensum på dette nivået

Herons metode (historisk eksempel)

Forutsetninger:

Ikke pensum i seg selv, av samme grunn som Euklids algoritme over, et historisk eksempel på samme gjenta-til-svaret-stabiliserer-seg-idé som Euler-steget over og Newtons metode i neste undertema, bare nesten 2000 år eldre.

Brukt til å regne ut kvadratrøtter for hånd lenge før kalkulatorer fantes: gjett en startverdi $x$ for $\sqrt{a}$ , regn ut et bedre gjett med $x_{ny} = \frac{1}{2}\left(x + \frac{a}{x}\right)$ , og gjenta til svaret slutter å endre seg. Hvert gjett blir automatisk nærmere den sanne kvadratroten, en algoritme kan altså gi et STADIG BEDRE svar i stedet for det eksakte svaret med én gang.

Tilnærme kvadratroten av 10, start x = 3
Steg	x	x_ny = 0,5(x + 10/x)
0	3	3,1667
1	3,1667	3,1623
2	3,1623	3,1623

Oppgaver

Prøv minst én oppgave på hvert nivå.

Lett(3)

L-21Må en algoritme stoppe etter endelig mange steg?

Vis fasit

En algoritme må terminere
ja, den må stoppe

L-22Er «regn litt til det ser riktig ut» en algoritme?

Vis fasit

«ser riktig ut» kan tolkes ulikt
nei, steget er ikke entydig

L-23Hvor mange divisorer må du teste for å avgjøre om $49$ er primtall?

Vis fasit

For 49 er kvadratroten 7
test til og med 7

Middels(3)

M-21Er $91$ et primtall?

Vis fasit

$91 : 7 = 13$
nei, $91$ er ikke et primtall

M-22Hvorfor holder det å teste divisorer opp til $\sqrt{n}$ ?

Vis fasit

Kvadratroten av n er grensen
en divisor over den har en partner under
det holder å teste opp til roten

M-23Hva er diskriminanten til $x^2 + 2x - 3 = 0$ ?

Vis fasit

$a = 1$ , $b = 2$ , $c = -3$
$D = 4 - 4 \cdot 1 \cdot (-3) = 4 + 12 =$ $16$

Vanskelig(3)

V-21Hva bør algoritmen gjøre hvis diskriminanten er negativ?

Vis fasit

En negativ diskriminant gir ingen reell rot
stopp og meld ingen løsning

V-22Hva kalles det å dele et problem i mindre biter?

Vis fasit

Å dele 1 problem i flere små deler
hver del løses for seg
dekomponering

V-23En algoritme tester ALLE tall opp til $n$ for å sjekke primtall. Er den riktig, og er den god?

Vis fasit

Alle tall opp til n gir riktig svar, men testing til roten holder
riktig, men treg