9.3 Algoritmer i matematikk

Oppskrifter for a lose problemer

Nar du baker en kake, folger du en oppskrift: «bland mel og sukker, tilsett egg, ror til jevn masse, stek i 25 minutter.» Oppskriften er en steg-for-steg-instruksjon som garanterer et godt resultat -- sa lenge du folger den noyaktig.

I matematikk og programmering kaller vi slike oppskrifter for algoritmer. En algoritme er:

1. En endelig rekke med instruksjoner (den ma stoppe pa et tidspunkt)
2. Hvert steg er presist nok til a folges uten tvetydighet
3. Den tar inn inndata og gir ut utdata

Du har allerede brukt algoritmer hele livet uten a tenke over det:
- Addisjon med tiervenn: En algoritme for a legge sammen flersifrede tall
- Lang divisjon: En algoritme for a dele store tall
- Deling pa fellesfaktor: En algoritme for a forkorte broker

I dette kapittelet skal vi lære a tenke som algoritmeutviklere og bruke Python til a gjore algoritmene levende.

Flytdiagrammer -- algoritmer som bilder

For vi koder, kan det være lurt a tegne algoritmen. Et flytdiagram bruker symboler for a vise flyten:

- Ovaler: Start og slutt
- Rektangler: Handlinger (f.eks. «beregn $x + 3$»)
- Romber: Valg/beslutninger (f.eks. «er $x > 10$?» -- ja/nei)
- Piler: Viser retningen fra steg til steg

Eksempel: En algoritme for a sjekke om et tall er positivt, negativt eller null:

1. Start
2. Les inn tallet $x$
3. Er $x > 0$? → Ja: Skriv «Positivt» → Ga til 6
4. Er $x < 0$? → Ja: Skriv «Negativt» → Ga til 6
5. Skriv «Null»
6. Slutt

I Python:

x = int(input("Skriv inn et tall: "))

if x > 0:
    print("Positivt")
elif x < 0:
    print("Negativt")
else:
    print("Null")

Legg merke til hvordan flytdiagrammets «valg» (rombene) tilsvarer if/elif/else i Python. A tegne flytdiagrammet forst hjelper deg a tenke gjennom alle mulighetene for du begynner a kode.

Eratosthenes' sil -- en klassisk algoritme

En av historiens mest elegante algoritmer ble oppfunnet av den greske matematikeren Eratosthenes for over 2000 ar siden. Den finner alle primtall opp til et gitt tall.

Husk: et primtall er et tall storre enn 1 som bare er delelig med 1 og seg selv. De forste primtallene er $2, 3, 5, 7, 11, 13, 17, 19, 23, \ldots$

Algoritmen (for a finne alle primtall opp til 30):

1. Skriv opp alle tall fra 2 til 30
2. Det forste tallet (2) er et primtall. Stryk alle multipler av 2: $4, 6, 8, 10, 12, \ldots$
3. Det neste ustrukne tallet (3) er et primtall. Stryk alle multipler av 3: $6, 9, 12, 15, \ldots$
4. Det neste ustrukne tallet (5) er et primtall. Stryk alle multipler av 5: $10, 15, 20, 25, 30$
5. Fortsett til du har gått gjennom alle tall. De gjenværende (ustrukne) tallene er primtallene!

Resultatet: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$

Genialiteten er at vi ikke trenger a sjekke hvert tall individuelt -- vi «siler bort» sammensatte tall i store grupper.

Eratosthenes' sil i Python

La oss programmere denne algoritmen:

grense = 50
er_primtall = [True] * (grense + 1)
er_primtall[0] = False
er_primtall[1] = False

for i in range(2, grense + 1):
    if er_primtall[i]:
        # Stryk alle multipler av i
        for j in range(i * 2, grense + 1, i):
            er_primtall[j] = False

# Skriv ut alle primtall
primtall = []
for i in range(2, grense + 1):
    if er_primtall[i]:
        primtall.append(i)

print(f"Primtall opp til {grense}:")
print(primtall)

Resultat:

Primtall opp til 50:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Her bruker vi en liste er_primtall der hvert element starter som True. Nar vi finner en multipler, setter vi den til False. Til slutt er alle tall som fortsatt er True primtall.

range(i * 2, grense + 1, i) gir alle multipler av i: den starter pa i * 2, gar opp til grense, og hopper i steg om gangen. For $i = 3$ gir dette $6, 9, 12, 15, \ldots$

Denne algoritmen er over 2000 ar gammel, men den brukes fortsatt den dag i dag -- bare med storre tall!

Flere algoritmer i matematikk

La oss se pa to viktige algoritmer til.

Algoritme: Finn storste faktor

tall = int(input("Skriv inn et tall: "))
storste = 1

for i in range(2, tall + 1):
    if tall % i == 0:
        storste = i

print(f"Storste faktor (utenom seg selv) av {tall} er {storste}")

Denne algoritmen sjekker alle tall fra 2 til tall og husker det siste som er en faktor.

Algoritme: Euklids algoritme for storste felles faktor (SFF)

Euklid oppdaget for over 2300 ar siden at vi kan finne storste felles faktor for to tall ved a gjenta divisjon med rest:

a = int(input("Forste tall: "))
b = int(input("Andre tall: "))

original_a = a
original_b = b

while b != 0:
    rest = a % b
    a = b
    b = rest

print(f"SFF({original_a}, {original_b}) = {a}")

Eksempel: SFF(48, 18)
- $48 \div 18 = 2$ med rest $12$ → $a = 18$, $b = 12$
- $18 \div 12 = 1$ med rest $6$ → $a = 12$, $b = 6$
- $12 \div 6 = 2$ med rest $0$ → $a = 6$, $b = 0$
- Stopp! $\text{SFF}(48, 18) = 6$

Denne algoritmen er elegant fordi den alltid finner svaret og gjor det raskt -- selv for veldig store tall.

Oppsummering

Algoritmer er grunnlaget for all programmering -- og de finnes overalt i matematikken:

- Algoritme: En endelig, presis oppskrift for a lose et problem steg for steg
- Flytdiagram: Et visuelt verktoy for a planlegge algoritmer -- med ovaler (start/slutt), rektangler (handlinger) og romber (valg)
- Eratosthenes' sil: En 2000 ar gammel algoritme for a finne primtall ved a «sile bort» multipler
- Euklids algoritme: Finner storste felles faktor ved gjentatt divisjon med rest -- nyttig for a forkorte broker
- Lister: Brukes til a lagre mange verdier, for eksempel alle tall fra 2 til 50
- Stegvis tenkning: Bryt problemet ned i sma, presise steg for du koder

Det viktigste du har lært er en mate a tenke pa: dele opp problemer i sma steg, være presis i instruksjonene, og la datamaskinen gjore det tunge arbeidet. Denne algoritmiske tenkematen er nyttig langt utenfor matematikken -- den hjelper deg a lose alle slags problemer pa en systematisk mate.