Algoritm
Från Rilpedia
En algoritm är inom matematiken och datavetenskapen begränsad uppsättning (mängd) väldefinierade instruktioner för att lösa en uppgift, som från givna utgångstillstånd (starttillstånd) med säkerhet leder till något givet sluttillstånd. Den kan också beskrivas som en systematisk procedur för hur man genom ett begränsat antal steg utför en beräkning eller löser ett problem. Beräkningskomplexiteten och hur effektiv implementation man kan göra av algoritmen är viktigt i databeräkningar och beror på användningen av lämpliga datastrukturer.
Informellt illustreras algoritmer ofta som ett recept (även om många algoritmer är mycket mer komplexa än recept). Algoritmer har ofta olika steg som upprepas (itereras) eller innebär val enligt regler som specificeras i algoritmen. Dessa val kan till exempel göras utifrån jämförelser av olika storheter och logiska operationer på sanningsvärden. Algoritmer kan i sin tur bestå av andra algoritmer för att skapa mer komplexa algoritmer.
Ursprunget för begreppet algoritm uppstod som ett sätt att beskriva procedurer för att lösa matematiska problem som exempelvis att finna den gemensamma delaren för två tal eller att multiplicera två tal. Begreppet formaliserades 1936 genom Alan Turings Turingmaskin och Alonzo Churchs lambdakalkyler, som i sin tur lade grunden för datavetenskapen.
De flesta algoritmer kan implementeras som datorprogram eller åtminstone simuleras av datorprogram. I många programeringsspråk så implementeras algoritmer som funktioner eller procedurer (metoder).
Innehåll |
Komplexitetsanalys
För många problem finns flera algoritmer att välja mellan. De använder olika instruktioner och kan kräva olika mycket resurser som antal steg, eller operationer, och storlek på minne, för att lösa samma problem. Ett annat ord för algoritmens resursberoende är komplexitet. För att på ett meningsfullt sätt kunna jämföra algoritmer är det viktigt att man specifierar en beräkningsmodell som är rimlig för det problem som ska lösas. Om man vill implementera en snabb multiplikation av stora tal kanske man väljer att räkna antalet elementära additioner och multiplikationer, medan den som väljer mellan sorteringsalgoritmer antagligen föredrar att räkna antalet jämförelser som utförs. För de allra flesta tillämpningar använder man sig idag av modellen Random Access Machine där man ger alla minnesreferenser samma kostnad (enhetskostnad) och alla elementära operationer också anses ha samma kostnad.
Hur många steg eller hur mycket minne en algoritm behöver är olika för olika indata. Även med en enkel beräkningsmodell är det ofta ett oöverstigligt problem att uppskatta hur många operationer eller hur mycket minne en algoritm behöver, räknat som funktion av indatas storlek. Därför väljer man oftast att diskutera en algoritms asymptotiska tids- eller minnes-komplexitet, det vill säga hur antalet steg växer som funktion av indatastorleken.
Det man antagligen mest är intresserad av är en algoritms förväntade komplexitet. Tyvärr är detta ofta mycket svårt att studera, och kräver dessutom många antaganden om de indata man har. (Vilken sannolikhetsfördelning har talen som ska multipliceras?) Mer praktiskt, och ofta mycket avslöjande, är att göra en värsta-fallet-analys där man tittar på hur komplexiteten blir när man har som mest ogynnsamma omständigheter.
Implementeringsnära effektivitetsanalys
Effektiviteten bedöms i tre olika avseenden:
1 - Den algoritm är effektivast som löser problemet på kortast tid.
- För att mäta tiden kan det därför vara nödvändigt att testköra varje algoritm på en hel uppsättning olika problem och därefter poängsätta varje algoritm efter hur den skötte sig jämfört med de övriga.
2 - Den algoritm är effektivast, som löser problemet med minst resurser.
- I datorsammanhang handlar det oftast om hur mycket minne algoritmen tar i anspråk för att lösa ett problem.
3 - Den algoritm är effektivast, som är minst komplicerad.
- Detta är oftast (men inte alltid) liktydigt med mängden kod, som går åt till att beskriva algoritmen.
Genom att testköra olika algoritmer på lämpligt sätt kan man relativt lätt avgöra vilken av en given grupp algoritmer, som är effektivast med avseende på det första och andra kriteriet. Genom att analysera koden för varje algoritm kan man också avgöra vilken som är effektivast med avseende på det andra och tredje kriteriet. Bäst är naturligtvis om man kan visa att en viss algoritm är den effektivaste i samtliga tre avseenden. Det är däremot mycket svårt att avgöra om den algoritm man tagit fram är den absolut effektivaste av alla möjliga algoritmer. Även för mycket enkla algoritmer är sådana bevis så svåra att genomföra att man i regel måste nöja sig med 'det bästa hittills'.
Exempel
En av de enklaste algoritmerna går ut på att finna det största talet i en (osorterad) lista med tal. Lösningen kräver att man tittar på varje tal i listan, men endast en gång. Beskriven i ord lyder algoritmen som följer:
- Anta att det första talet är störst och notera det talet.
- Ta ställning till varje återstående tal i listan och om något är större än det dittills största talet, notera det i stället för det tidigare noterade talet.
- När hela listan gåtts igenom är det senast noterade talet det största .
Här följer en mer formell beskrivning av algoritmen i pseudokod:
Algoritm StörstaTal
Invärden: En icke-tom lista, L, som innehåller tal.
Resultat: Det största numret i listan, L.
största ← L0
för varje tal i listan L≥1, upprepa
om tal > största, så
största ← tal
returnera största
Algoritmer är inte begränsade till Datalogi eller beräkningar utan kan även användas till annan problem-lösning. Exempelvis matlagning:
Algoritm Makaroner Invärden: Makaroner, kastrull, vatten, spis, sil, tallrik Resultat: Färdig-lagade makaroner, klara att äta. Fyll kastrull till hälften med vatten. -- fyll(kastrull, vatten, storlek(kastrull) / 2) Häll i makaroner i kastrull. -- häll(makaroner, kastrull) Placera kastrull på spis och aktivera spis. -- placera(kastrull, spis) && aktivera(spis) Låt koka tills makaroner är mjuka. -- medan(makaroner != mjuka) vänta Ta av kastrull från spis och häll ut innehåll i sil. -- placera(kastrull, !spis) && häll(kastrull, sil) Häll i makaroner från sil på tallrik. -- häll(sil, tallrik) Ät makaroner -- ät(makaroner)
För ett mer komplext exempel, se Euklides algoritm, vilken är en av de äldsta algoritmerna.
Etymologi
Ordet algoritm kommer ursprungligen från namnet på den arabiska matematikern al-Khwarizmi. Genom tiderna har ordet förändrats och kombinerats med grekiskans arithmo's som betyder siffra och beräkning.
Berömda algoritmer
Se även
