9.1 Hva er en algoritme? | Matematikk 1P

Lær hva algoritmer er, hvordan de brukes i hverdagen og i matematikk, og hvordan vi kan beskrive dem med flytskjema og pseudokode.

45 min

8 oppgaver

AlgoritmeFlytskjemaPseudokodeSteg-for-steg

Du leser den tradisjonelle versjonen

Din fremgang i kapitlet

0 / 8 oppgaver

Kapitlets plass i kurset

Brukes videre i

9.2Programmering med Python

Algoritmer er overalt

Hver gang du følger en oppskrift for å lage pannekaker, bruker du en algoritme. Når du forklarer noen veien til skolen, beskriver du en algoritme. Når du sorterer en kortstokk fra lavest til høyest, følger du en algoritme.

En algoritme er rett og slett en presis, steg-for-steg-beskrivelse av hvordan man løser et problem eller utfører en oppgave. Det som gjør algoritmer spesielle, er at de er så tydelige at hvem som helst (eller en datamaskin) kan følge dem og komme frem til riktig resultat.

I dette kapittelet skal vi se på hva som kjennetegner en god algoritme, og lære ulike måter å beskrive algoritmer på.

Algoritme

En algoritme er en endelig, ordnet sekvens av entydige instruksjoner som løser et bestemt problem eller utfører en bestemt oppgave. En algoritme har disse egenskapene: - Endelig : Den stopper etter et bestemt antall steg. - Entydig : Hvert steg er klart definert, uten rom for tolkning. - Input : Den kan ta inn data (men trenger ikke). - Output : Den gir et resultat.

Algoritmer i hverdagen

Her er noen eksempler på algoritmer vi bruker daglig, uten å tenke over det:

Oppskrift for kokt egg:
1. Fyll en kjele med vann.
2. Sett kjelen på platen og kok opp vannet.
3. Legg egget forsiktig i det kokende vannet.
4. Vent i 4 minutter (bløtkokt) eller 8 minutter (hardkokt).
5. Ta egget opp med en skje og kjøl det under kaldt vann.

Veibeskrivelse:
1. Gå ut døren og ta til venstre.
2. Gå rett frem i 200 meter.
3. Ta til høyre ved lyskrysset.
4. Bygningen er den tredje på venstre side.

Legg merke til at begge eksemplene har noe til felles: de har en klar rekkefølge, hvert steg er tydelig, og de fører til et bestemt resultat.

✏️Eksempel 1: Divisjonsalgoritmen

Beskriv en algoritme for å utføre heltallsdivisjon av 47 med 6 (finn hvor mange ganger 6 går opp i 47, og hva resten blir).

Algoritme for heltallsdivisjon:

1. Start med dividenden (47) og divisoren (6).
2. Sett telleren til 0.
3. Så lenge dividenden er større enn eller lik divisoren:
- Trekk divisoren fra dividenden: $47 - 6 = 41$
- Øk telleren med 1.
4. Gjenta steg 3:
- $41 - 6 = 35$ , teller = 2
- $35 - 6 = 29$ , teller = 3
- $29 - 6 = 23$ , teller = 4
- $23 - 6 = 17$ , teller = 5
- $17 - 6 = 11$ , teller = 6
- $11 - 6 = 5$ , teller = 7
5. Nå er dividenden (5) mindre enn divisoren (6), så vi stopper.

Svar: $47 \div 6 = 7$ med rest $5$ (fordi $7 \cdot 6 + 5 = 47$ ).

✏️Eksempel 2: Euklids algoritme for største felles faktor

Finn største felles faktor (GCD) av 48 og 18 ved hjelp av Euklids algoritme.

Euklids algoritme:
Gjenta følgende: Del det største tallet på det minste. Erstatt det største tallet med resten. Stopp når resten er 0.

1. Del 48 på 18: $48 = 2 \cdot 18 + 12$ (rest 12)
2. Del 18 på 12: $18 = 1 \cdot 12 + 6$ (rest 6)
3. Del 12 på 6: $12 = 2 \cdot 6 + 0$ (rest 0)

Resten er 0, så vi stopper. Det siste tallet vi delte med er 6.

Svar: Største felles faktor av 48 og 18 er $\text{GCD}(48, 18) = 6$ .

Vi kan sjekke: $48 = 6 \cdot 8$ og $18 = 6 \cdot 3$ , og 8 og 3 har ingen felles faktorer.

Flytskjema

Et flytskjema er en visuell fremstilling av en algoritme. Vi bruker ulike symboler:

- Oval (avrundet rektangel): Start og stopp
- Rektangel: En handling eller beregning
- Rombe (diamant): Et valg / en betingelse (ja/nei)
- Piler: Viser rekkefølgen

Flytskjema gjør det lett å se strukturen i en algoritme, spesielt når det er valg og gjentakelser involvert.

Eksempel: Flytskjema for å sjekke om et tall er partall

[Start] → [Les inn tallet n] → <Er n delelig med 2?>
                                    |              |
                                   Ja             Nei
                                    |              |
                              [Skriv "Partall"] [Skriv "Oddetall"]
                                    |              |
                                    → → [Stopp] ← ←

Pseudokode

Pseudokode er en måte å skrive algoritmer på med vanlig tekst, uten å bruke et bestemt programmeringsspråk. Det er en mellomting mellom naturlig språk og programkode.

Her er pseudokode for å sjekke om et tall er partall:

LES inn tallet n
HVIS n er delelig med 2
    SKRIV "Tallet er partall"
ELLERS
    SKRIV "Tallet er oddetall"

Og her er pseudokode for å finne det største tallet i en liste:

LES inn en liste med tall
SETT størst = første tall i listen
FOR hvert tall i listen:
    HVIS tall > størst
        SETT størst = tall
SKRIV størst

Pseudokode bruker innrykk for å vise hvilke instruksjoner som hører sammen, akkurat som i ekte programmering.

Iterasjon og betingelser

Iterasjon (gjentakelse/løkke) betyr å gjenta en gruppe instruksjoner flere ganger. Vi bruker ord som FOR og SÅ LENGE (WHILE). Betingelse (valg) betyr å utføre forskjellige instruksjoner avhengig av om noe er sant eller usant. Vi bruker ord som HVIS ... ELLERS (IF ... ELSE). Disse to byggesteinene, sammen med sekvens (instruksjoner etter hverandre), er alt vi trenger for å beskrive enhver algoritme.

✏️Eksempel 3: Pseudokode for å summere tallene 1 til 100

Skriv pseudokode for å beregne summen $1 + 2 + 3 + \ldots + 100$ .

Pseudokode:

SETT sum = 0
FOR n = 1 TIL 100:
    SETT sum = sum + n
SKRIV "Summen er: ", sum

Gjennomgang:
- Vi starter med sum = 0.
- Løkken kjører for n = 1, 2, 3, ..., 100.
- For hver verdi av n legger vi n til sum.
- Etter løkken har vi: sum $= 1 + 2 + 3 + \ldots + 100 = 5050$ .

Vi kan sjekke med formelen: $\displaystyle \frac{100 \cdot 101}{2} = 5050$ ✓

📝Oppgave 9.1

Hvilke av disse er eksempler på algoritmer?

📝Oppgave 9.2

Skriv en algoritme (i pseudokode) for å avgjøre om et tall er positivt, negativt eller null.

📝Oppgave 9.3

Bruk Euklids algoritme til å finne største felles faktor (GCD) av 84 og 36. Vis alle stegene.

Når du har skrevet en algoritme i pseudokode, er det korte veien til å gjøre den om til et dataprogram. Pseudokode ligner på ekte programkode, men bruker vanlig norsk i stedet for engelske nøkkelord.

I neste kapittel skal vi lære å skrive algoritmer i programmeringsspråket Python, som er et av de enkleste språkene å komme i gang med.

📝Oppgave 9.4

Skriv pseudokode for en algoritme som finner det minste tallet i en liste med fem tall. Bruk en løkke.

Oppsummering

I dette kapittelet har du lært:

- Algoritme: En endelig, ordnet sekvens av entydige instruksjoner som løser et problem.
- Pseudokode: En uformell måte å skrive algoritmer på, uavhengig av programmeringsspråk.
- Flytskjema: Grafisk fremstilling av en algoritme med bokser og piler.
- Byggesteiner: Sekvens (steg etter steg), valg (hvis/ellers) og iterasjon (løkker).

Nøkkelbegreper

Begrep	Forklaring
Algoritme	Steg-for-steg-oppskrift som løser et problem
Pseudokode	Algoritme skrevet i klartekst
Iterasjon	Gjentakelse (løkke)
Betingelse	Test som avgjør hvilken vei algoritmen tar

Eksempel: Euklids algoritme

- Gjenta: erstatt det største tallet med resten av divisjonen, til resten er

0

. Siste divisor er største felles faktor.

Repetisjonsoppgaver

Din fremgang

0deloppgaver0 / 4 oppgaver

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.