algoritm

En algoritm är, inom matematiken och datavetenskapen, en ändlig uppsättning (mängd) otvetydiga instruktioner som efter exekvering löser ett problem. Algoritmen startar i ett givet tillstånd (starttillstånd) och når resultatet (sluttillstånd) inom ett ändligt antal steg. Varje steg måste vara tydligt och precist definierat, på så sätt att utomstående ska kunna exekvera algoritmen och verifiera ett resultat. Ytterligare är effektivitet viktigt, det vill säga varje steg måste vara elementärt och exakt, samt gå att beräkna inom en ändlig tidsram. Det yttersta kriteriet för effektiva algoritmer är dess beräkningskomplexitet, något som mäts i antalet beräkningssteg som krävs för att nå ett resultat. Vanligtvis är det tidskomplexitet som mäts för att särskilja algoritmer, som uppmäts i tidsmängd beroende på problemstorleken. Det går även att mäta minneskomplexitet där man mäter hur mycket minne som krävs för att lösa ett problem. Utifrån ett problems algoritm kan man klassificera problem efter svårighetsgrad i så kallade komplexitetsklasser. Med klasser för tidskomplexitet är det möjligt att avgöra vilka problem som går att lösa inom en rimlig tid. Informellt illustreras algoritmer ofta som ett recept (även om många algoritmer är mycket mer komplexa än recept). Konceptuellt blir då ingredienser indata, receptet själva algoritmen och maträtten ett resultat. Men istället för att blanda eller koka finns det andra grundläggande steg i algoritmer. Man brukar räkna de fyra räknesätten och de logiska operationer på sanningsvärden som grundläggande operationer, man säger att de är atomära. Dessutom krävs att man till minne kan både läsa och skriva data. Det är ett mycket känt bevis av Alan Turing för vilka operationer som krävs för att kunna beräkna vilken funktion som helst. 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.[källa behövs] De flesta algoritmer implementeras som datorprogram, då man strukturerar dem i programform. För att uttrycka program används programspråk som är formella språk med samtliga nödvändiga operationer för att uttrycka en godtycklig beräkningsbar funktion. Ordet algoritm bör ej förväxlas med den matematiska termen logaritm.