Konseptet med en "algoritme" er grunnleggende for all databehandling vitenskap og programmering. Sagt på en enkelt, er en algoritme et sett med instruksjoner som kan brukes til å løse et problem. Figur 1.1 inneholder én enkel algoritme som du kan bruke i hverdagen. Denne algoritmen brukes i baking og det er skrevet på en måte som folk flest kan forstå og følge. Den brukes til å lage kjeks, kaker, muffins, og mange andre bakevarer.
figur 1.1. 1. Bland romtemperert smør og sukker. Bland til lys og luftig. 2. Tilsett eggene til kremete smør og bland å kombinere. 3.
I en annen bolle, kombinere de flytende ingrediensene og bland å kombinere. 4. Bland mel og andre tørre ingrediensene. 5. Alternativt legge de tørre og flytende ingredienser til smør eggedosisen. Bland akkurat nok til å kombinere
Figur 1.1. Den "kremfløte metoden": en hverdag algoritme. gi kokekurs i CMPT kurs.) Likevel, algoritmen i figur 1.1 har mye til felles med de algoritmene vi skal se på i løpet av dette kurset. Vi er mer interessert i den slags algoritmer som kan gjennomføres ved hjelp av datamaskiner.
Vi vil bruke mye tid på dette kurset designe algoritmer og ha datamaskinen fullføre dem for oss
Her er en definisjon av "algoritme" at de fleste dataforskere kan leve med. [Anany Levitin, Introduksjon til The Design og analyse av algoritmer, s. 3] En algoritme er en sekvens av instruksjoner for entydige solv- ing et problem, dvs. for å oppnå en påkrevd utgang for enhver legit- Imate input i en begrenset tidsperiode. Det er noen ord du bør legge merke til om definisjonen: • entydig: Når du leser en algoritme, bør det ikke være noen spørsmålet om hva som bør gjøres.
Er dette tilfelle i figur 1.1? Hvis du forstår matlaging begreper som "lett og luftig" og "sile sam- men", så kan du sannsynligvis følge det meste av denne oppskriften. Du kan ha noe problem med det siste trinnet: du skal "vekselvis" legge de tørre og våte ingredienser. Betyr det at du bør gjøre tørr-våt-tørr? Dry-vått-tørt-vått-tørt-vått? Hvor mange tilleggene bør du gjøre? Oppskrifter i kokebøker er ofte skrevet med små uklarheter som dette enten fordi det spiller ingen rolle hva du gjør eller forfatteren er forutsatt at leseren vil vite hva de skal gjøre.
For ordens skyld er det rette i dette tilfellet trolig tørt-vått-tørt-vått-tørt. • problem: En algoritme bør alltid presentere en løsning på en bestemt problem. Hver algoritme er utformet med en spesiell gruppe av problemer i tankene. I figur 1.1