Notasjon

Det er i hovedsak to måter å beskrive algoritmer som skal utføres av en datamaskin:

Med "fri" tekst, ofte kalt pseudokode eller kvasikode
I et formelt definert programmerings- eller beskrivelsesspråk, f.eks. Java eller IDL (eksakt kode)

Hva man bruker, er avhengig av formålet. Med pseudokode kan det være lettere å få fram store linjer der hvor eksakt kode blir for detaljert. Faren med pseudokode er at det blir for lite nøyaktig, og det er lett å introdusere tvetydigheter. I det virkelige liv brukes ofte en kombinasjon av de to beskrivelsesteknikkene.

Vi skal nå se på noen generelle retningslinjer for gode algoritmebeskrivelser.

Generelle elementer

En algoritmebeskrivelse bør inneholder stort sett disse elementene:

Input

Mange algoritmer er avhengig av å bli servert et materiale de skal bearbeide.
Euklids algoritme: To heltall A og B.

Output

Hvis en algoritme skal levere fra seg et resultat, må dette spesifiseres.
Euklids algoritme: Et heltall.

Lokale variabler

Som oftest trenger man lokale variabler, og disse må beskrives med type og navn.
Euklids algoritme: To heltall TMP og D.

Tilordninger

Innholdet i variablene endres ved tilordninger.
Euklids algoritme: I steg 4 får D en ny verdi, og i steg 5 settes så A til verdien av D.

Funksjonskall

I følge god programmeringsskikk brytes kompliserte problemer ned til et sett av enklere prosedyrer eller funksjoner. Derfor vil de fleste algoritmer benytte seg av slike "hjelperutiner" som typisk er beskrevet for seg.
Euklids algoritme: Vi kunne godt ha formulerte steg 4 som et funksjonkall. f.eks.:

   4. Sett D til mod(A, B)

der mod(A, B) er en funksjon som regner ut restverdien vi får ved dele A med B (A modulo B).

Logiske tester

Algoritmer er helt avhengige av logiske tester, f.eks. for å kunne stoppe algoritmen når vi har kommet fram til en løsning.
Euklids algoritme: I steg 3 spør man om B er lik null, og hvis det er tilfelle går vi ut av gjennomføringsdelen.

Løkker

De fleste algoritmer kunne ikke formuleres uten forskjellige former for løkker. Løkkene gjør at en sekvens av steg utføres flere ganger. I hver iterasjon blir typisk nye verdier for en eller flere variablr beregnet.
Euklids algoritme: Løkka består av trinnene 2 til 6, og er beskrevet ved hjelp av en "gå-til" mekanisme.

Kommentarer

I de fleste tilfeller bør man bruke kommentarer som i vanlige ordelag forklarer hva som skjer. En god vane kan være å først skrive ned algoritmen i kommentarform, uansett om man skal formulere den i pseudokode eller eksakt kode.

Euklids algoritme kunne f.eks. uttrykkes slik på kommentarnivå:

	1   // Hent inn to heltall
	2   // Gå i løkke:
		   // Hvis det minste tallet er 0 returnes det største som løsningen
		   // Del det største tallet på det minste,
		   // og ta vare på restverdien og det minste tallet
		   // Gjør en iterasjon til med de nye tallene
	3   // Avslutt

Man må på en eller annen måte markere at det er kommentarer det er snakk om. Her er det brukt "//" som er vanlig i f.eks. Java og C++, men man kan jo bruke hva som helst bare man er konsistent og alltid bruker samme notasjon.

Pseudokode

Det finnes utrolig mange ulike måter å skrive pseudokode på. Det viktigste er at man prøver å være så utvetydig og eksakt som mulig. Det er dermed viktig notasjonen blir brukt på en konsistent måte. Notasjonen må som et minimum omfatte standardelementene i en algoritme.

Euklids algoritme ble beskrevet på en vanlig forekommende og greit forståelig form for pseudokode. Merk at den hierarkiske nummereringen gjør det lett å se f.eks. løkker og blokker i logiske tester.

Her kommer nok en variant av Euklids Algoritme. Vi definerer først en rutine som sørger for at to heltall kommer i stigende rekkefølge (OBS: Her antar vi at input kommer som referanser, se Java).

OrdneHeltall _____________________________________________ Input: Heltall A, Heltall B Output: Heltall A, Heltall B 1 Hvis A er mindre enn B: 1.1 Sett et heltall TMP lik A 1.2 Sett A lik B 1.3 Sett B lik TMP 2 Stopp

Deretter formulerer vi SFF-funksjonen:

StørsteFellesFaktor _____________________________________________ Input: Heltall A, Heltall B Output: Heltall 1 OrdneHeltall(A, B) 2 Så lenge B er større enn 0 2.1 Sett A lik A modulo B 2.2 OrdneHeltall(A, B) 3 Returner A

Merk at dette ikke er den eneste måten å skrive pseudokode på, men et eksempel på hvordan det kan gjøres på en eksakt og konsistent måte, og som dekker de vikigste elementene i en algoritme.

Eksakt kode

Eksakt kode bør være mer eller mindre kompilerbar. Vi ser først på en versjon blandet med pseudokode. Det er hensiktsmessig å skille ut pseudokoden fra den eksakte koden, f.eks. ved å sette den mellom '<' og '>'. Pass på å ikke blande sammen pseudokode og kommentarer.

... public int SFF(int A, int B) { // Sørger for at A er størst < Hvis A er mindre enn B: Bytt om A og B > // Gå i løkke helt til B blir null // I hver iterasjon setter vi A lik restverdien vi får ved å dele A på B while (B > 0) { // Finner restverdien < A settes til A modulo B > // Sørger for at A er størst hele tiden } // B er blitt null, og da er A løsningen. Magic :-) return A; } ....

java

Da gjenstår det bare å bytte ut pseudokoden med eksakt kode, og vi har en kjørbar og korrekt (håper vi) algoritme:

... public int SFF(int A, int B) { if (A < B) { int TMP = A; A = B; B = TMP; } while (B > 0) { A = A % B; if (A < B) { int TMP = A; A = B; B = TMP; } } return A; } ....