9.1 Hva er en algoritme? | Matematikk 1P

Oppskriften du følger uten å vite det

Hver gang du lager pannekaker etter en oppskrift, bruker du en algoritme. Når du forklarer en venn veien til skolen, beskriver du en algoritme. Og 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 presisjonen: De er så tydelige at hvem som helst -- eller en datamaskin -- kan følge dem og komme fram til riktig resultat. Mer formelt er en algoritme en endelig, ordnet sekvens av entydige instruksjoner som løser et bestemt problem. Fire egenskaper kjennetegner den: Den er endelig og stopper etter et bestemt antall steg. Hvert steg er entydig, uten rom for tolkning. Den kan ta inn data -- input -- og den gir et resultat -- output.

Tenk på en veibeskrivelse: «Gå ut døren og ta til venstre. Gå rett fram i 200 meter. Ta til høyre ved lyskrysset. Bygningen er den tredje på venstre side.» Klar rekkefølge, tydelige steg, et bestemt resultat -- alle algoritmens kjennetegn på plass. I dette kapittelet skal vi se hva som gjør en algoritme god, prøve noen klassiske matematiske algoritmer, og lære to måter å skrive dem ned på: flytskjema og pseudokode.

To klassikere: divisjon og Euklid

La oss se algoritmetenkningen brukt på ekte matematikk. Hvordan finner du ut hvor mange ganger 6 går opp i 47 -- uten å kunne svaret? En enkel algoritme: Trekk 6 fra 47 igjen og igjen, og tell hvor mange ganger du klarer det før resten blir mindre enn 6. Vi får $47 \to 41 \to 35 \to 29 \to 23 \to 17 \to 11 \to 5$ -- sju subtraksjoner, og så står vi igjen med 5, som er mindre enn 6. Altså: $47 \div 6 = 7$ med rest 5. Kontrollen stemmer: $7 \cdot 6 + 5 = 47$ . Hvert steg var entydig, og prosessen stoppet av seg selv -- en ekte algoritme.

Den andre klassikeren er over 2300 år gammel: Euklids algoritme for å finne største felles faktor av to tall. Oppskriften: Del det største tallet på det minste, og erstatt det største med resten. Gjenta til resten er 0 -- da er det siste tallet du delte med, svaret.

La oss finne største felles faktor av 48 og 18. Først: $48 = 2 \cdot 18 + 12$ , rest 12. Så: $18 = 1 \cdot 12 + 6$ , rest 6. Til slutt: $12 = 2 \cdot 6 + 0$ -- rest 0, og vi stopper. Det siste tallet vi delte med var 6, så største felles faktor av 48 og 18 er 6. Sjekk: $48 = 6 \cdot 8$ og $18 = 6 \cdot 3$ , og 8 og 3 har ingen felles faktorer. En eldgammel algoritme -- fortsatt i bruk i datamaskiner verden over.

📝Oppgave Quiz 1

Å tegne og skrive algoritmer

Hvordan deler du en algoritme med andre? To verktøy dominerer. Det første er flytskjemaet -- en visuell fremstilling der hver figur har sin betydning: En oval markerer start og stopp, et rektangel er en handling eller beregning, en rombe (diamant) er et valg med ja/nei-svar, og pilene viser rekkefølgen. Vil du sjekke om et tall er partall, tegner du: start, les inn tallet, rombe med spørsmålet «er tallet delelig med 2?», og to piler ut -- ja-pilen til «skriv partall», nei-pilen til «skriv oddetall», før begge møtes i stopp.

Det andre verktøyet er pseudokode: algoritmen skrevet med vanlige ord, uavhengig av programmeringsspråk -- en mellomting mellom norsk og programkode. Samme partallssjekk blir: LES inn tallet n. HVIS n er delelig med 2, SKRIV «partall», ELLERS SKRIV «oddetall». Innrykk viser hva som hører sammen, akkurat som i ekte kode.

Uansett verktøy bygges alle algoritmer av tre byggesteiner. Sekvens: instruksjoner etter hverandre. Valg (betingelse): ulike veier avhengig av om noe er sant -- ordene HVIS og ELLERS. Og iterasjon (løkke): å gjenta instruksjoner -- ordene FOR og SÅ LENGE. Med disse tre kan enhver algoritme beskrives. Et eksempel som bruker alle: SETT sum lik 0, FOR n fra 1 til 100, SETT sum lik sum pluss n. Etter løkken er summen $1 + 2 + \ldots + 100 = 5050$ -- som du kan kontrollere med formelen $\displaystyle \frac{100 \cdot 101}{2}$ . I neste kapittel oversetter vi pseudokoden til ekte Python.

📝Oppgave Quiz 2

Fortellingen om oppskriftene

Fra pannekakerøre til Euklid: En algoritme er en endelig, ordnet sekvens av entydige instruksjoner som løser et problem -- med input inn og output ut. Du har fulgt divisjonsalgoritmen som fant $47 \div 6 = 7$ med rest 5, og Euklids algoritme som fant største felles faktor av 48 og 18 ved å dele og beholde resten til den ble null.

Du har også fått to språk å uttrykke algoritmer i: flytskjemaet med ovaler for start og stopp, rektangler for handlinger og romber for valg -- og pseudokoden, som skriver algoritmen i klartekst med HVIS, ELLERS, FOR og innrykk.

Og viktigst av alt: Alle algoritmer, uansett hvor avanserte, bygges av bare tre byggesteiner -- sekvens, valg og iterasjon. Det er disse tre du skal bruke når pseudokoden i neste kapittel blir til ekte Python-kode.