Vad är en algoritm?

Begreppet "algoritm" är grundläggande för alla datavetenskap och programmering. Enkelt uttryckt är en algoritm en uppsättning instruktioner som kan användas för att lösa ett problem. Figur 1.1 innehåller en enkel algoritm som du kan använda i vardagen. Denna algoritm används i bakning och det är skrivet på ett sätt som de flesta människor kan förstå och följa. Det används för att göra kakor, tårtor, muffins, och många andra bakade varor.

Figur 1,1. 1. Kombinera rumstemperatur smör och socker. Blanda tills ljuset och fluffigt. 2.

Tillsätt ägg till stuvad smör och blanda att kombinera. 3. I en annan skål, kombinera de flytande ingredienserna och blanda att kombinera. 4. Sikta samman mjöl och andra torra ingredienser. 5. Alternativt lägga till torra och flytande ingredienser till smör äggsmeten. Blanda bara tillräckligt för att kombinera Omdömen

Figur 1.1. Den "utarmning metod": en vardaglig algoritm. ger matlagningskurser i CMPT kurser.) Ändå algoritmen i Figur 1.1 har en hel del gemensamt med de algoritmer vi kommer att titta på under den här kursen.

Vi är mer intresserade av vilka typer av algoritmer som kan fyllas av datorer. Vi kommer att tillbringa mycket tid i den här kursen designa algoritmer och med datorn slutföra dem för oss Omdömen

Här är en definition av "algoritm" att de flesta datavetare kan leva med. [Anany Levitin, Introduktion till The Design & analys av algoritmer, s. 3] En algoritm är en sekvens av entydiga instruktioner för solv- ing ett problem, dvs för att erhålla en önskad effekt för någon legitima ingång i en ändlig mängd tid.

Det finns några ord som du kommer att märka om definition: • entydig: När du läser en algoritm, bör det finnas någon fråga om vad som bör göras. Är detta fallet i figur 1.1? Om du förstår matlagning termer som "ljus och fluffig" och "sålla tillsam- mans", då kan du förmodligen följa det mesta av detta recept. Du kanske har några problem med det sista steget: du är tänkt att "omväxlande" lägga de torra och våta ingredienser.

Betyder det att du bör göra torr- våt-torr? Torr våt torr våt torr våt? Hur många tillägg bör du göra? Recept i kokböcker är ofta skrivna med små tvetydigheter som antingen eftersom det inte spelar någon roll vad du gör eller författaren utgår från att läsaren vet vad de ska göra. För att undvika missförstånd, är det rätta i detta fall förmodligen torr våt torr våt torr. • problem: En algoritm bör alltid presentera en lösning på en av dem ular problem. Varje algoritm är