Begrebet "algoritme" er grundlæggende for alle datalogi og programmering. Enkelt sagt en algoritme er et sæt af instruktioner, der kan anvendes til at løse et problem. Figur 1.1 indeholder en simpel algoritme, som du kan bruge i hverdagen. Denne algoritme bruges i bagning og det er skrevet på en måde, som de fleste mennesker kan forstå og følge. Det bruges til at lave småkager, kager, boller og mange andre bagte varer.
Figur 1.1. 1. Kombiner stuetemperatur smør og sukker. Bland indtil let og luftigt. 2. Tilsæt æggene til det skumme smør og bland til at kombinere. 3.
I en anden skål, kombinere de flydende ingredienser og bland at kombinere. 4. Sigt sammen mel og andre tørre ingredienser. 5. Alternativt tilføje de tørre og flydende ingredienser til smør-æggemassen. Bland lige nok til at kombinere
Figur 1.1:. Den "creaming-metoden": en dagligdags algoritme. giver madlavning lektioner i CMPT kurser.) Alligevel algoritmen i figur 1.1 har en masse til fælles med de algoritmer vi vil se på i løbet af dette kursus. Vi er mere interesserede i den slags algoritmer, som kan være afsluttet ved computere.
Vi vil bruge en masse tid i dette kursus designe algoritmer og have computeren fuldføre dem for os
Her er en definition af "algoritme", at de fleste dataloger kan leve med:. [Anany Levitin, Introduktion til Design & analyse af algoritmer, s. 3] En algoritme er en sekvens af entydige anvisninger som skal løse et problem, dvs for at opnå en påkrævet output for enhver legitim input i en endelig mængde tid. Der er et par ord, du bør bemærke om definitionen: • entydig: Når du læser en algoritme, bør der ikke være nogen pågældende om, hvad der bør gøres. Er dette tilfældet i figur 1.
1? Hvis du forstår madlavning udtryk som "lys og fluffy" og "finkæmme sam- men", så kan du sikkert følge det meste af denne opskrift. Du har måske nogle problemer med det sidste trin: du skulle "skiftevis" tilføj de tørre og våde ingredienser. Betyder det, at du bør gøre tør- våd-tør? Tør-våd-tør-våd-tør-våd? Hvor mange tilføjelser bør du gøre? Opskrifter i kogebøger ofte skrevet med små uklarheder som dette, enten fordi det er ligegyldigt, hvad du gør, eller spørgeren antager, at læseren vil vide, hvad de skal gøre. For posten, det rigtige i dette tilfælde er sandsynligvis tør-våd-tør-våd-tør.
• Problem: En algoritme skal altid præsentere en løsning på et partic- ular problem. Hver algoritme er designet med en bestemt gruppe af problemer i tankerne. I figur 1.1,