Algoritmer
Definisjon
Under følger en generell definisjon på en algoritme:
Algoritme:
En algoritme er en beskrivelse av hvordan man løser et veldefinert problem med en presist formulert sekvens av et endelig antall enkle,
utvetydige og tidsbegrensede steg.
Legg merke til at denne definisjonen ikke begrenser algoritmer til datamaskinenes verden. Vi omgir oss med algoritmer hele dagen, vi bruker de for å pusse tennene og til å ta ut penger i minibanken. Algoritmer kan beskrives i et hvilket som helst slags språk, både Swahili og Java duger. Det viktigste er at vi beskriver en algoritme på en utvetydig måte, slik at alle de (personer eller datamaskiner) som utfører algoritmen vil gjøre eksakt det samme, og at algoritmen virker på samme måte selv om vi endrer dataene (materialene) algoritmen arbeider ut fra. De fleste dataprogrammer, med unntak av de som er basert på visse teknikker innen kunstig intelligens, utfører sine oppgaver ved hjelp av algoritmer.
Ordet "algoritme" kommer fra etternavnet til den kjente matematikeren
Al-Khwarizmi (f. 780, Bagdad).
Legg også merke til at en algoritme må ha en klar stoppbetingelse. Hvis ikke risikerer vi å gå inn i en evig løkke,
algoritmen terminerer aldri, og løser dermed ikke problemet vårt.
Euklid
Euklid var en annen stor matematiker (Alexandria, 300 f. Kr.), som bla.a. kom fram til en effektiv måte å beregne
største felles faktor (SFF) for to gitte heltall (SFF for 6 og 9 er 3, for 24 og 84 er SFF lik 12).
Den såkalte Euklids Algoritme kan beskrives slik:
1 Gitt to positive heltall A og B
2 Hvis A er mindre enn B:
2.1 Sett et heltall TMP lik A
2.2 Sett A lik B
2.3 Sett B lik TMP
3 Hvis B er lik 0:
3.1 Gå til 7
4 Sett et heltall D lik resten man får ved å dele A på B (D = A mod B)
5 Sett A lik D
6 Gå til 2
7 Verdien av A er løsningen
8 Stopp
Anatomi
Som en god fortelling har en algoritme gjerne en innledende del (hode), en gjennomføringsdel (kropp) og en avslutning (hale). I innledning opprettes nødvendige variable og datastrukturer, og vi gjør klar dataene våre til behandling. Deretter utføres en sekvens av steg som gjerne går i en eller flere løkker. Stoppbetingelsen gjør at vi kommer ut av gjennomføringsdelen, og i avslutningen setter vi sammen løsningen vi er kommet fram til, leverer den fra oss og avslutter.
I Euklids algoritme er steg 1 innledningen, det at vi rett og slett definerer to variable som inneholder oppgitte verdier (input). Steg 2 til 6 er selve gjennomføringen. Steg 6 gjør at vi går i løkke, og stoppbetingelsen i steg 3 gjør at algoritmen terminerer. Avslutningen skjer i steg 7 og 8, der vi kommer fram til svaret (output), og avslutter.
