Lær hva en algoritme er og hvordan du kan beskrive algoritmer på en presis måte.
Hva er en algoritme?
Har du noen gang fulgt en matoppskrift, bygget et LEGO-sett etter instruksjonene, eller forklart veien til noen? I så fall har du allerede brukt algoritmer uten å tenke over det. En algoritme er rett og slett en presis, trinnvis beskrivelse av hvordan en oppgave skal utføres. Begrepet er helt sentralt i informatikk og programmering, men det strekker seg langt utover datamaskiner.
I dette kapittelet skal vi utforske hva algoritmer er, hvilke egenskaper en god algoritme har, og hvordan vi kan bruke de tre grunnleggende kontrollstrukturene sekvens, betingelse og iterasjon til å bygge opp algoritmer som løser reelle problemer. Vi skal også se hvordan algoritmer kan oversettes direkte til Python-kode.
Ordet «algoritme» kommer fra navnet til den persiske matematikeren Muhammad ibn Musa al-Khwarizmi, som levde på 800-tallet. Han skrev lærebøker om matematikk og systematiske metoder for å løse likninger. Gjennom latinsk oversettelse ble navnet hans til «Algoritmi», og begrepet «algoritme» ble født. Det er fascinerende at et konsept som ble formalisert for over tusen år siden, er selve grunnsteinen i moderne datavitenskap.
En algoritme er en endelig, ordnet sekvens av presise og entydige instruksjoner for å løse et bestemt problem eller utføre en bestemt oppgave. Algoritmen tar imot inndata (input), prosesserer dem gjennom en serie steg, og produserer utdata (output). For at noe skal kalles en algoritme, må følgende krav være oppfylt: (1) hvert steg må være klart og entydig definert, (2) algoritmen må terminere etter et endelig antall steg, og (3) den må produsere et korrekt resultat for alle gyldige inndata.
Algoritmer i dagliglivet
Du bruker algoritmer hele tiden, selv om du ikke tenker på det som det. Her er noen eksempler:
Matoppskrift: En oppskrift på pannekaker er en algoritme. Den har inndata (ingredienser: mel, egg, melk, sukker), en serie instruksjoner (bland mel og sukker, visp inn egg, tilsett melk, stek i panne), og utdata (ferdige pannekaker). Hvert steg er presist beskrevet, og rekkefølgen er viktig. Du kan ikke steke deigen før du har blandet den.
Veibeskrivelse: Når du forklarer veien fra skolen til nærmeste butikk, gir du en algoritme: «Gå ut av hovedinngangen. Ta til venstre. Gå rett frem i 200 meter. Ta til høyre ved lyskrysset. Butikken er 50 meter fremme på venstre side.» Hvert steg er entydig, og du vet når du er ferdig (du har kommet til butikken).
Morgensrutine: Å gjøre seg klar om morgenen følger en algoritme. Stå opp, dusj, kle på seg, spis frokost, puss tennene, ta på sko, gå til bussen. Endrer du rekkefølgen (tar på sko før du dusjer), fungerer det kanskje, men resultatet blir annerledes.
Spill og strategi: Å spille et brettspill krever at du følger regler i en bestemt rekkefølge. Reglene i et spill er i praksis en algoritme som beskriver hva som skal skje i hvert trekk.
Det som gjør algoritmer i informatikk spesielle, er at de må være så presise at en datamaskin kan følge dem. En datamaskin gjør nøyaktig det du ber den om. Den kan ikke tolke, gjette eller improvisere. Derfor må algoritmene vi skriver for datamaskiner, være helt entydige.
Beskriv en algoritme som finner det største av tre tall a, b og c.
1. Les inn tre tall: a, b og c
2. Anta at a er det største tallet (kall det «størst»)
3. Hvis b er større enn «størst», oppdater «størst» til b
4. Hvis c er større enn «størst», oppdater «størst» til c
5. Skriv ut «størst»
Implementasjon i Python:
# Finn det største av tre tall
a = int(input("Skriv inn tall a: "))
b = int(input("Skriv inn tall b: "))
c = int(input("Skriv inn tall c: "))
storst = a
if b > storst:
storst = b
if c > storst:
storst = c
print(f"Det største tallet er {storst}")Kjøring:
Skriv inn tall a: 7
Skriv inn tall b: 15
Skriv inn tall c: 3
Det største tallet er 15Legg merke til at algoritmen fungerer uansett hvilke tre tall du gir inn. Den sjekker systematisk hvert tall og oppdaterer «størst» om nødvendig. Dette er en viktig egenskap ved algoritmer: de skal gi korrekt resultat for alle gyldige inndata.
Egenskapene til en god algoritme
Ikke alle instruksjoner kvalifiserer som en algoritme. For at noe skal være en algoritme i informatisk forstand, må det oppfylle flere krav:
1. Entydighet (presisjon)
Hvert steg i algoritmen må ha én og bare én mulig tolkning. Instruksjonen «tilsett litt salt» er tvetydig, for hva betyr «litt»? En presis instruksjon ville være «tilsett 5 gram salt». I programmering betyr dette at hver linje kode gjør nøyaktig én ting, og det er ingen tvil om hva den gjør.
2. Terminering (endelighet)
Algoritmen må alltid stoppe etter et endelig antall steg. Den kan ikke gå i en evig løkke. Instruksjonen «fortsett å lete til du finner svaret» er problematisk, for hva om svaret ikke finnes? En bedre formulering er «sjekk de neste 100 tallene, og rapporter om svaret ble funnet eller ikke».
3. Korrekthet
Algoritmen må produsere riktig svar for alle gyldige inndata. Det er ikke nok at den fungerer for noen tilfeller. En sorteringsalgoritme som sorterer [3, 1, 2] riktig, men feiler på [5, 5, 3], er ikke korrekt.
4. Effektivitet
En god algoritme bruker ressurser (tid og minne) fornuftig. Hvis du kan løse et problem med 10 steg i stedet for 1000, er den kortere versjonen bedre. Effektivitet blir spesielt viktig når vi jobber med store datamengder.
5. Generalitet
Algoritmen bør kunne håndtere en hel klasse av problemer, ikke bare ett spesifikt tilfelle. En algoritme for å finne det største tallet bør fungere for 3 tall, 100 tall eller 1 million tall, ikke bare for ett bestemt sett av verdier.
Alle algoritmer kan bygges opp av tre grunnleggende kontrollstrukturer: sekvens (instruksjoner som utføres i rekkefølge), betingelse/valg (instruksjoner som utføres bare hvis en betingelse er oppfylt) og iterasjon/løkke (instruksjoner som gjentas). Böhm og Jacopini beviste i 1966 at enhver algoritme kan uttrykkes med bare disse tre strukturene. Dette kalles strukturteoremet og er et av de viktigste resultatene i informatikk.
Sekvens
Sekvens er den enkleste kontrollstrukturen. Instruksjoner utføres i rekkefølge, den ene etter den andre, fra topp til bunn. Python-programmer kjøres som standard sekvensielt.
# Sekvens: beregn arealet av et rektangel
lengde = 8
bredde = 5
areal = lengde * bredde
print(f"Arealet er {areal} cm²")Her utføres linje 1 først, deretter linje 2, så linje 3, og til slutt linje 4. Rekkefølgen er avgjørende. Hvis vi prøver å beregne arealet før vi har definert lengde og bredde, får vi en feilmelding.
Sekvens alene er nok til å lage enkle programmer, men for å løse mer komplekse problemer trenger vi betingelser og løkker.
Betingelse (valg)
En betingelse lar programmet ta avgjørelser. Basert på om en betingelse er sann eller usann, velger programmet hvilken kode som skal kjøres. I Python bruker vi if, elif og else:
# Betingelse: sjekk om et tall er positivt, negativt eller null
tall = int(input("Skriv inn et tall: "))
if tall > 0:
print("Tallet er positivt")
elif tall < 0:
print("Tallet er negativt")
else:
print("Tallet er null")Betingelser gjør det mulig å lage programmer som reagerer ulikt på ulike inndata. Uten betingelser ville alle programmer gjøre nøyaktig det samme hver gang de kjøres, uansett hva brukeren skriver inn.
Et hverdagseksempel på en betingelse: «Hvis det regner, ta med paraply. Ellers, la paraplyen ligge.» Programmet sjekker en betingelse (regner det?) og utfører ulike handlinger basert på svaret.
Iterasjon (løkke)
Iterasjon betyr å gjenta en gruppe instruksjoner flere ganger. I Python har vi to typer løkker:
For-løkke brukes når du vet på forhånd hvor mange ganger du vil gjenta:
# For-løkke: skriv ut tallene 1 til 5
for i in range(1, 6):
print(i)While-løkke brukes når du vil gjenta så lenge en betingelse er sann:
# While-løkke: gjett et tall
hemmelig = 7
gjett = 0
while gjett != hemmelig:
gjett = int(input("Gjett tallet (1-10): "))
print("Riktig! Du gjettet riktig!")Iterasjon er ekstremt kraftig. Uten løkker ville du måtte skrive samme kode tusenvis av ganger for å behandle store datamengder. Med en løkke kan du behandle én million tall med bare noen få linjer kode.
Et hverdagseksempel på iterasjon: «Rør i gryta hvert femte minutt til sausen tykner.» Du gjentar handlingen (rører) til en betingelse er oppfylt (sausen er tykk nok).
Skriv en algoritme og et Python-program som sjekker om et tall fra brukeren er et primtall.
1. Les inn et tall n fra brukeren
2. Hvis n er mindre enn 2, er det IKKE et primtall. Stopp.
3. For hvert tall i fra 2 til n-1:
a. Hvis n er delelig med i (n % i == 0), er n IKKE et primtall. Stopp.
4. Hvis ingen divisor ble funnet, ER n et primtall.
Python-kode:
# Sjekk om et tall er et primtall
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 # Ingen grunn til å sjekke flere
if er_primtall:
print(f"{n} ER et primtall")
else:
print(f"{n} er IKKE et primtall")Kjøring:
Skriv inn et tall: 17
17 ER et primtall
Skriv inn et tall: 12
12 er IKKE et primtallDenne algoritmen bruker alle tre kontrollstrukturene: sekvens (linjene kjøres i rekkefølge), betingelse (if-setningen sjekker delbarhet), og iterasjon (for-løkken sjekker alle mulige divisorer). Nøkkelordet break avbryter løkken tidlig hvis vi finner en divisor, noe som gjør algoritmen mer effektiv.
En vanlig feil blant nybegynnere er å begynne å kode umiddelbart uten å tenke gjennom algoritmen først. Det er som å begynne å bygge et hus uten tegninger. Ta deg tid til å beskrive løsningen i naturlig språk eller som en punktliste før du åpner kodeeditoren. Når algoritmen er klar, er det ofte overraskende enkelt å oversette den til Python-kode.
En while-løkke som aldri stopper kalles en uendelig løkke. Dette skjer når betingelsen i løkken aldri blir usann. For eksempel:
# FEIL: Uendelig løkke!
x = 1
while x > 0:
x = x + 1 # x blir bare større, aldri 0 eller negativDenne løkken stopper aldri fordi x alltid er positiv. For å unngå dette, sørg alltid for at noe inne i løkken bringer deg nærmere avslutningsbetingelsen. Hvis programmet ditt henger, trykk Ctrl+C for å avbryte.
Hvilken av følgende er den beste definisjonen av en algoritme?
Hvilken kontrollstruktur beskriver at instruksjoner utføres i rekkefølge, den ene etter den andre?
Hvilken egenskap betyr at en algoritme alltid vil stoppe etter et endelig antall steg?
Hva skriver dette programmet ut?
tall = 10
if tall > 5:
print("Stort")
if tall > 15:
print("Veldig stort")
else:
print("Middels stort")
else:
print("Lite")Skriv en algoritme i naturlig språk (som en nummerert liste) og deretter i Python som beregner summen av alle heltall fra 1 til n, der n er et tall brukeren skriver inn.
Skriv et Python-program som bruker en while-løkke til å finne det første tallet som er større enn 1000 i følgen 1, 2, 4, 8, 16, 32, ... (der hvert tall er det dobbelte av det forrige).
Skriv et Python-program som ber brukeren om tall gjentatte ganger (med en while-løkke). Programmet skal stoppe når brukeren skriver 0. Til slutt skal programmet skrive ut hvor mange tall som ble skrevet inn (ikke medregnet 0), summen av tallene, og gjennomsnittet.
Hva skriver dette programmet ut?
resultat = 0
for i in range(1, 5):
if i % 2 == 0:
resultat += i * 2
else:
resultat += i
print(resultat)Oppsummering
I dette kapittelet har du lært:
- Algoritme: endelig, ordnet sekvens av presise instruksjoner.
- Algoritmer i dagliglivet: oppskrifter og rutiner.
- God algoritme: presis, entydig, endelig og effektiv.
- Tre kontrollstrukturer: sekvens, betingelse/valg og iterasjon (løkke).
- Fra algoritme til kode: oversette til Python.
Noekkelbegreper
| Begrep | Forklaring |
|---|---|
| Algoritme | Ordnet sekvens av presise instruksjoner |
| Sekvens | Instruksjoner i rekkefølge |
| Iterasjon | Gjentakelse (løkke) |
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.