Lær hva en algoritme er og hvordan du kan beskrive algoritmer på en presis måte.
Kva er ein algoritme?
Har du nokon gong følgt ei matoppskrift, bygd eit LEGO-sett etter instruksjonane, eller forklart vegen til nokon? I så fall har du allereie brukt algoritmar utan å tenkje over det. Ein algoritme er rett og slett ei presis, trinnvis skildring av korleis ei oppgåve skal utførast. Omgrepet er heilt sentralt i informatikk og programmering, men det strekkjer seg langt utover datamaskiner.
I dette kapittelet skal vi utforske kva algoritmar er, kva eigenskapar ein god algoritme har, og korleis vi kan bruke dei tre grunnleggjande kontrollstrukturane sekvens, vilkår og iterasjon til å byggje opp algoritmar som løyser reelle problem. Vi skal òg sjå korleis algoritmar kan omsetjast direkte til Python-kode.
Ordet «algoritme» kjem frå namnet til den persiske matematikaren Muhammad ibn Musa al-Khwarizmi, som levde på 800-talet. Han skreiv lærebøker om matematikk og systematiske metodar for å løyse likningar. Gjennom latinsk omsetjing vart namnet hans til «Algoritmi», og omgrepet «algoritme» vart fødd. Det er fascinerande at eit konsept som vart formalisert for over tusen år sidan, er sjølve grunnsteinen i moderne datavitskap.
Ein algoritme er ein endeleg, ordna sekvens av presise og eintydige instruksjonar for å løyse eit bestemt problem eller utføre ei bestemt oppgåve. Algoritmen tek imot inndata (input), prosesserer dei gjennom ein serie steg, og produserer utdata (output). For at noko skal kallast ein algoritme, må følgjande krav vere oppfylte: (1) kvart steg må vere klart og eintydig definert, (2) algoritmen må terminere etter eit endeleg tal steg, og (3) han må produsere eit korrekt resultat for alle gyldige inndata.
Algoritmar i dagleglivet
Du brukar algoritmar heile tida, sjølv om du ikkje tenkjer på det som det. Her er nokre eksempel:
Matoppskrift: Ei oppskrift på pannekaker er ein algoritme. Ho har inndata (ingrediensar: mjøl, egg, mjølk, sukker), ein serie instruksjonar (bland mjøl og sukker, visp inn egg, tilsett mjølk, steik i panne), og utdata (ferdige pannekaker). Kvart steg er presist skildra, og rekkjefølgja er viktig. Du kan ikkje steike deigen før du har blanda han.
Vegskildring: Når du forklarer vegen frå skulen til næraste butikk, gir du ein algoritme: «Gå ut av hovudinngangen. Ta til venstre. Gå rett fram i 200 meter. Ta til høgre ved lyskrysset. Butikken er 50 meter framme på venstre side.» Kvart steg er eintydig, og du veit når du er ferdig (du har komme til butikken).
Morgonsrutine: Å gjere seg klar om morgonen følgjer ein algoritme. Stå opp, dusj, kle på deg, et frukost, puss tennene, ta på sko, gå til bussen. Endrar du rekkjefølgja (tek på sko før du dusjar), fungerer det kanskje, men resultatet blir annleis.
Spel og strategi: Å spele eit brettspel krev at du følgjer reglar i ei bestemt rekkjefølgje. Reglane i eit spel er i praksis ein algoritme som skildrar kva som skal skje i kvart trekk.
Det som gjer algoritmar i informatikk spesielle, er at dei må vere så presise at ei datamaskin kan følgje dei. Ei datamaskin gjer nøyaktig det du ber han om. Han kan ikkje tolke, gjette eller improvisere. Difor må algoritmane vi skriv for datamaskiner, vere heilt eintydige.
Skildre ein algoritme som finn det største av tre tal a, b og c.
1. Les inn tre tal: a, b og c
2. Anta at a er det største talet (kall det «størst»)
3. Viss b er større enn «størst», oppdater «størst» til b
4. Viss 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 kva for tre tal du gir inn. Han sjekkar systematisk kvart tal og oppdaterer «størst» om nødvendig. Dette er ein viktig eigenskap ved algoritmar: dei skal gi korrekt resultat for alle gyldige inndata.
Eigenskapane til ein god algoritme
Ikkje alle instruksjonar kvalifiserer som ein algoritme. For at noko skal vere ein algoritme i informatisk forstand, må det oppfylle fleire krav:
1. Eintydigheit (presisjon)
Kvart steg i algoritmen må ha éi og berre éi mogleg tolking. Instruksjonen «tilsett litt salt» er tvitydig, for kva tyder «litt»? Ein presis instruksjon ville vere «tilsett 5 gram salt». I programmering tyder dette at kvar linje kode gjer nøyaktig éin ting, og det er ingen tvil om kva han gjer.
2. Terminering (endelegheit)
Algoritmen må alltid stoppe etter eit endeleg tal steg. Han kan ikkje gå i ei evig løkke. Instruksjonen «hald fram med å leite til du finn svaret» er problematisk, for kva om svaret ikkje finst? Ei betre formulering er «sjekk dei neste 100 tala, og rapporter om svaret vart funne eller ikkje».
3. Korrektheit
Algoritmen må produsere riktig svar for alle gyldige inndata. Det er ikkje nok at han fungerer for nokre tilfelle. Ein sorteringsalgoritme som sorterer [3, 1, 2] riktig, men feilar på [5, 5, 3], er ikkje korrekt.
4. Effektivitet
Ein god algoritme brukar ressursar (tid og minne) fornuftig. Viss du kan løyse eit problem med 10 steg i staden for 1000, er den kortare versjonen betre. Effektivitet blir spesielt viktig når vi jobbar med store datamengder.
5. Generalitet
Algoritmen bør kunne handtere ein heil klasse av problem, ikkje berre eitt spesifikt tilfelle. Ein algoritme for å finne det største talet bør fungere for 3 tal, 100 tal eller 1 million tal, ikkje berre for eitt bestemt sett av verdiar.
Alle algoritmar kan byggjast opp av tre grunnleggjande kontrollstrukturar: sekvens (instruksjonar som blir utførte i rekkjefølgje), vilkår/val (instruksjonar som blir utførte berre viss eit vilkår er oppfylt) og iterasjon/løkke (instruksjonar som blir gjentekne). Böhm og Jacopini beviste i 1966 at kvar algoritme kan uttrykkjast med berre desse tre strukturane. Dette blir kalla strukturteoremet og er eit av dei viktigaste resultata i informatikk.
Sekvens
Sekvens er den enklaste kontrollstrukturen. Instruksjonar blir utførte i rekkjefølgje, den eine etter den andre, frå topp til botn. Python-program blir køyrde sekvensielt som standard.
# Sekvens: beregn arealet av et rektangel
lengde = 8
bredde = 5
areal = lengde * bredde
print(f"Arealet er {areal} cm²")Her blir linje 1 utført først, deretter linje 2, så linje 3, og til slutt linje 4. Rekkjefølgja er avgjerande. Viss vi prøver å rekne ut arealet før vi har definert lengde og breidde, får vi ei feilmelding.
Sekvens åleine er nok til å lage enkle program, men for å løyse meir komplekse problem treng vi vilkår og løkker.
Vilkår (val)
Eit vilkår let programmet ta avgjerder. Basert på om eit vilkår er sant eller usant, vel programmet kva kode som skal køyrast. I Python brukar 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")Vilkår gjer det mogleg å lage program som reagerer ulikt på ulike inndata. Utan vilkår ville alle program gjere nøyaktig det same kvar gong dei blir køyrde, uansett kva brukaren skriv inn.
Eit kvardagseksempel på eit vilkår: «Viss det regnar, ta med paraply. Elles, la paraplyen liggje.» Programmet sjekkar eit vilkår (regnar det?) og utfører ulike handlingar basert på svaret.
Iterasjon (løkke)
Iterasjon tyder å gjenta ei gruppe instruksjonar fleire gonger. I Python har vi to typar løkker:
For-løkke blir brukt når du veit på førehand kor mange gonger du vil gjenta:
# For-løkke: skriv ut tallene 1 til 5
for i in range(1, 6):
print(i)While-løkke blir brukt når du vil gjenta så lenge eit vilkår er sant:
# 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. Utan løkker måtte du skrive same kode tusenvis av gonger for å behandle store datamengder. Med ei løkke kan du behandle éin million tal med berre nokre få linjer kode.
Eit kvardagseksempel på iterasjon: «Rør i gryta kvart femte minutt til sausen tjuknar.» Du gjentek handlinga (rører) til eit vilkår er oppfylt (sausen er tjukk nok).
Skriv ein algoritme og eit Python-program som sjekkar om eit tal frå brukaren er eit primtal.
1. Les inn eit tal n frå brukaren
2. Viss n er mindre enn 2, er det IKKJE eit primtal. Stopp.
3. For kvart tal i frå 2 til n-1:
a. Viss n er deleleg med i (n % i == 0), er n IKKJE eit primtal. Stopp.
4. Viss ingen divisor vart funnen, ER n eit primtal.
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 brukar alle tre kontrollstrukturane: sekvens (linjene blir køyrde i rekkjefølgje), vilkår (if-setninga sjekkar delbarheit), og iterasjon (for-løkka sjekkar alle moglege divisorar). Nøkkelordet break avbryt løkka tidleg viss vi finn ein divisor, noko som gjer algoritmen meir effektiv.
Ein vanleg feil blant nybyrjarar er å begynne å kode med ein gong utan å tenkje gjennom algoritmen først. Det er som å begynne å byggje eit hus utan teikningar. Ta deg tid til å skildre løysinga i naturleg språk eller som ei punktliste før du opnar kodeeditoren. Når algoritmen er klar, er det ofte overraskande enkelt å omsetje han til Python-kode.
Ei while-løkke som aldri stoppar blir kalla ei uendeleg løkke. Dette skjer når vilkåret i løkka aldri blir usant. Til dømes:
# FEIL: Uendelig løkke!
x = 1
while x > 0:
x = x + 1 # x blir bare større, aldri 0 eller negativDenne løkka stoppar aldri fordi x alltid er positiv. For å unngå dette, sørg alltid for at noko inne i løkka bringar deg nærare avslutningsvilkåret. Viss programmet ditt heng, trykk Ctrl+C for å avbryte.
Kva for éin av desse er den beste definisjonen av ein algoritme?
Kva for kontrollstruktur skildrar at instruksjonar blir utførte i rekkjefølgje, den eine etter den andre?
Kva for eigenskap tyder at ein algoritme alltid vil stoppe etter eit endeleg tal steg?
Kva skriv dette programmet ut?
tall = 10
if tall > 5:
print("Stort")
if tall > 15:
print("Veldig stort")
else:
print("Middels stort")
else:
print("Lite")Skriv ein algoritme i naturleg språk (som ei nummerert liste) og deretter i Python som reknar ut summen av alle heiltal frå 1 til n, der n er eit tal brukaren skriv inn.
Skriv eit Python-program som brukar ei while-løkke til å finne det første talet som er større enn 1000 i følgja 1, 2, 4, 8, 16, 32, ... (der kvart tal er det doble av det førre).
Skriv eit Python-program som ber brukaren om tal gjentekne gonger (med ei while-løkke). Programmet skal stoppe når brukaren skriv 0. Til slutt skal programmet skrive ut kor mange tal som vart skrivne inn (ikkje medrekna 0), summen av tala, og gjennomsnittet.
Kva skriv 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: endeleg, ordna sekvens av presise instruksjonar.
- Algoritmar i dagleglivet: oppskrifter og rutinar.
- God algoritme: presis, eintydig, endeleg og effektiv.
- Tre kontrollstrukturar: sekvens, vilkår/val og iterasjon (løkke).
- Frå algoritme til kode: omsetje til Python.
Nøkkelomgrep
| Omgrep | Forklaring |
|---|---|
| Algoritme | Ordna sekvens av presise instruksjonar |
| Sekvens | Instruksjonar i rekkjefølgje |
| Iterasjon | Gjentaking (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.