Algoritm

Fran Wikipedia

Flodesscheman ger en grafisk representation av algoritmer.

Iranske matematikern Khwarizmi, som namngett Algoritm, pa ett sovjetiskt frimarke.

Den har artikeln behover fler eller battre kallhanvisningar for att kunna verifieras.
Motivering: Finns bara kallor om inledande texten och om en detaljuppgift (2016-09)
Atgarda genom att lagga till palitliga kallor (garna som fotnoter). Uppgifter utan kallhanvisning kan ifragasattas och tas bort utan att det behover diskuteras pa diskussionssidan.

En algoritm ar, inom matematiken och datavetenskapen, en andlig uppsattning (mangd) otvetydiga instruktioner som efter exekvering loser ett problem.^[1] Algoritmen startar i ett givet tillstand (starttillstand) och nar resultatet (sluttillstand) inom ett andligt antal steg. Varje steg maste vara tydligt och precist definierat, pa sa satt att utomstaende ska kunna exekvera algoritmen och verifiera ett resultat. Dessutom ar effektivitet viktigt, det vill saga varje steg maste vara elementart och exakt, samt ga att berakna inom en andlig tidsram. Det yttersta kriteriet for effektiva algoritmer ar dess berakningskomplexitet, nagot som mats i antalet berakningssteg som kravs for att na ett resultat. Vanligtvis ar det tidskomplexitet som mats for att sarskilja algoritmer, som uppmats i tidsmangd beroende pa problemstorleken.^[2] Det gar aven att mata minneskomplexitet dar man mater hur mycket minne som kravs for att losa ett problem.^[3] Utifran ett problems algoritm kan man klassificera problem efter svarighetsgrad i sa kallade komplexitetsklasser. Med klasser for tidskomplexitet ar det mojligt att avgora vilka problem som gar att losa inom en rimlig tid.^[4]

Informellt illustreras algoritmer ofta som ett recept (aven om manga algoritmer ar mycket mer komplexa an recept). Konceptuellt blir da ingredienser indata, receptet sjalva algoritmen och matratten ett resultat. Men istallet for att blanda eller koka finns det andra grundlaggande steg i algoritmer. Man brukar rakna de fyra raknesatten och de logiska operationer pa sanningsvarden som grundlaggande operationer, man sager att de ar atomara. Dessutom kravs att man till minne kan bade lasa och skriva data. Det ar ett mycket kant bevis av Alan Turing for vilka operationer som kravs for att kunna berakna vilken funktion som helst.^[2]

Ursprunget for begreppet algoritm uppstod som ett satt att beskriva procedurer for att losa matematiska problem som exempelvis att finna den gemensamma delaren for tva tal eller att multiplicera tva tal. Begreppet formaliserades 1936 genom Alan Turings turingmaskin och Alonzo Churchs lambdakalkyler, som i sin tur lade grunden for datavetenskapen.^{[kalla behovs]}

De flesta algoritmer implementeras som datorprogram, da man strukturerar dem i programform. For att uttrycka program anvands programsprak som ar formella sprak med samtliga nodvandiga operationer for att uttrycka en godtycklig berakningsbar funktion.

Ordet algoritm bor ej forvaxlas med den matematiska termen logaritm.

Komplexitetsanalys

[redigera | redigera wikitext]

For manga problem finns flera algoritmer att valja mellan. De anvander olika instruktioner och kan krava olika mycket resurser som antal steg, eller operationer, och storlek pa minne, for att losa samma problem. Ett annat ord for algoritmens resursberoende ar komplexitet. For att pa ett meningsfullt satt kunna jamfora algoritmer ar det viktigt att man specificerar en berakningsmodell som ar rimlig for det problem som ska losas. Om man vill implementera en snabb multiplikation av stora tal kanske man valjer att rakna antalet elementara additioner och multiplikationer, medan den som valjer mellan sorteringsalgoritmer antagligen foredrar att rakna antalet jamforelser som utfors. For de allra flesta tillampningar anvander man sig idag av modellen Random Access Machine dar man ger alla minnesreferenser samma kostnad (enhetskostnad) och alla elementara operationer ocksa anses ha samma kostnad.

Hur manga steg eller hur mycket minne en algoritm behover ar olika for olika indata. Aven med en enkel berakningsmodell ar det ofta ett ooverstigligt problem att uppskatta hur manga operationer eller hur mycket minne en algoritm behover, raknat som funktion av indatas storlek. Darfor valjer man oftast att diskutera en algoritms asymptotiska tids- eller minneskomplexitet, det vill saga hur antalet steg vaxer som funktion av indatastorleken.

Det man antagligen mest ar intresserad av ar en algoritms forvantade komplexitet. Tyvarr ar detta ofta mycket svart att studera, och kraver dessutom manga antaganden om de indata man har. (Vilken sannolikhetsfordelning har talen som ska multipliceras?) Mer praktiskt, och ofta mycket avslojande, ar att gora en varsta-fallet-analys dar man tittar pa hur komplexiteten blir nar man har som mest ogynnsamma omstandigheter.

Implementeringsnara effektivitetsanalys

[redigera | redigera wikitext]

Effektiviteten bedoms i tre olika avseenden:

1 - Den algoritm ar effektivast som loser problemet pa kortast tid.

For att mata tiden kan det darfor vara nodvandigt att testkora varje algoritm pa en hel uppsattning olika problem och darefter poangsatta varje algoritm efter hur den skotte sig jamfort med de ovriga.

2 - Den algoritm ar effektivast, som loser problemet med minst resurser.

I datorsammanhang handlar det oftast om hur mycket minne algoritmen tar i ansprak for att losa ett problem.

3 - Den algoritm ar effektivast, som ar minst komplicerad.

Detta ar oftast (men inte alltid) liktydigt med mangden kod, som gar at till att beskriva algoritmen.

Genom att testkora olika algoritmer pa lampligt satt kan man relativt latt avgora vilken av en given grupp algoritmer som ar effektivast med avseende pa det forsta och andra kriteriet. Genom att analysera koden for varje algoritm kan man ocksa avgora vilken som ar effektivast med avseende pa det andra och tredje kriteriet. Bast ar naturligtvis om man kan visa att en viss algoritm ar den effektivaste i samtliga tre avseenden. Det ar daremot mycket svart att avgora om den algoritm man tagit fram ar den absolut effektivaste av alla mojliga algoritmer. Aven for mycket enkla algoritmer ar sadana bevis sa svara att genomfora att man i regel maste noja sig med 'det basta hittills'.

Exempel

[redigera | redigera wikitext]

Bubbelsortering

En av de enklaste algoritmerna gar ut pa att finna det storsta talet i en (osorterad) lista med tal. Losningen kraver att man tittar pa varje tal i listan, men endast en gang. Beskriven i ord lyder algoritmen som foljer:

Anta att det forsta talet ar storst och notera det talet.
Ta stallning till varje aterstaende tal i listan och om nagot ar storre an det dittills storsta talet, notera det i stallet for det tidigare noterade talet.
Nar hela listan gatts igenom ar det senast noterade talet det storsta.

Har foljer en mer formell beskrivning av algoritmen i pseudokod:

Algoritm StorstaTal Invarden: En icke-tom lista, L, som innehaller tal. Resultat: Det storsta talet i listan, L. storsta - L₀ for varje tal i listan L_>=1, upprepa om tal > storsta, sa storsta - tal returnera storsta

Algoritmer ar inte begransade till datalogi eller berakningar utan kan aven anvandas till annan problemlosning. Ett recept for en matratt kan till exempel innehalla en beskrivning, en algoritm, av hur man lagar ratten.

For ett mer komplext exempel, se Euklides algoritm, vilken ar en av de aldsta kanda matematiska algoritmerna.

Etymologi

[redigera | redigera wikitext]

Ordet algoritm kommer fran arabiska och ursprungligen fran namnet pa den persiska (iranska) matematikern Mohammad ibn Musa, kallad al-Khwarazmi, "mannen fran Kharazm" (idag Chiva i Uzbekistan)^[5], som levde i Baghdad ca 780-850 e.Kr. Genom tiderna har ordet forandrats och kombinerats med grekiskans arithmo's som betyder siffra och berakning.