Algoritme

Fra Wikipedia, den frie encyklopædi

En algoritme er en utvetydig og abstrakt beskrivelse af, hvordan en specifik type problem løses terminerende.

En algoritme er en opskrift til at løse et problem af en bestemt type, som leverer en løsning uanset den konkrete problemsituations udseende. Et eksempel kunne være en præcis beskrivelse af, hvordan man sorterer et spil kort, uanset hvordan de enkelte kort ligger fra udgangspunktet.

[redigér] Sortering af kort

Hvis vi som eksempel skal beskrive hvordan man sorterer et spil kort, uanset udgangspunktet, kunne det gøres på følgende måde:

1. Tag et tilfældigt kort fra bunken.
2. Gå nu bunken igennem - alle dem som er højere end dit tilfældige kort, lægger du i en bunke til venstre, og dem som er mindre i en bunke til højre.
3. Læg dit tilfældige kort i den venstre bunke.
4. Hvis der er mere end to kort i bunkerne, gentag pkt 1 til 3 for begge af de to bunker. Sørg for, at når de enkelte bunker deles, bliver begge de nye bunker sammen på samme side.
5. Hvis der er to kort i bunken, læg det højeste øverst, og læg bunken ovenpå den bunke den blev delt fra.

Denne algoritme kalder sig selv på den måde, at man skal udføre den igen og igen på mindre og mindre bunker (indtil man kun har to kort i bunkerne, så lægger man dem sammen igen).

[redigér] Anvendelse

Det ovenstående eksempel kan forekomme besværligt og mærkeligt til at forklare, hvordan man sorterer en stak kort. Men selvom det for et menneske er en intuitiv opgave, er en computer nødt til at få sine ordrer meget utvetydigt. Hvis man formulerer ovenstående algoritme i et programmeringssprog, vil programmet være istand til at sortere et (fiktivt) spil kort.

Sorteringsalgoritmer er meget anvendt eksempel på algoritmer, da de er eksemplariske og helt logiske af natur. Derudover bruges algoritmer også til optimeringsopgave i planlægningen af eks. fly-ruter, skemalægning til skoler osv. Denne type algoritmer kaldes heuristikker. Kort kan der nævnes simuleret nedkøling og genetiske algoritmer, som er typer af heuristikker.

Man finder adskillige eksempler på algoritmer i vores hverdag. Madopskrifter, monteringsinstruktioner og brugsanvisninger kan betragtes som algoritmer. De er dog kun nogenlunde logisk opstillede, og de fleste har prøvet at skulle samle et møbel efter en instruktion, som er mangelfuld. Andre har forsøgt sig med madopskrifter, der går ud fra som en selvfølge, at f.eks. delalgoritmen "opbagning" er velkendt for alle. For brugsanvisninger (eksempelvis på pesticider) gælder der et ikke-håndhævet lovkrav om, at de skal være éntydige og umiddelbart forståelige.

[redigér] Kompleksitet

Beregningskompleksiteten af en algoritme beskriver hvor lang tid det teoretisk vil tage at løse et problem af en given størrelse. Man taler om at en algoritme kører i tid O(n²) for at løse en problem instans af størrelse n. Det vil her sige at køretiden af algoritmen vil være kvadratisk afhængig af inddataen størrelse, groft sagt svarer det til at hvis du har dobbelt så mange kort der skal sorteres tager det 4 gange så lang tid. En simpel sorterings algoritme af kort, hvor man tager et kort ud af en blandet bunke og placerer det i en ordnet bunke vil køre i O(n²). Sorterings algoritmen nævnt foroven er noget mere avanceret og vil køre i O(n * lg(n)) tid. Dette kunne svare til at dobbelt så mange kort ville tage 3 gange så lang tid at sortere (dette vil dog afhænge af mange faktorer, men forholdene er ikke urealistiske). Det er derfor en stor fordel at bruge mere effektive algoritmer, da det løser problemer hurtigere.

Sorteringsalgortimer vil normalt køre i polynomiel tid, deet vil sige at deres køretid kan beskrives af et polynomie i deres inddatas størrelse, n. Specielt svære problemer kan køre i eksponentiel tid, det kunne svare til at hvis du vil løse et problem af størrelse 21 i stedet for af størrelse 20, kan det tage dobbelt så lang tid. Køretiden eksploderer altså med større inddata. Den [rejsende handelsmands problem] er et eksempel på et sådan problem, disse kaldes også NP-hårde.