Algoritm, systematisk procedur som producerar - i ett begränsat antal steg - svaret på en fråga eller lösningen på ett problem. Namnet härstammar från den latinska översättningen Algoritmi de numero Indorum från det muslimska matematikern al-Khwarizmi från 900-talet aritmetiska avhandling ”Al-Khwarizmi om den hinduiska räkningskonsten.”
datavetenskap: algoritmer och komplexitet
En algoritm är en specifik procedur för att lösa ett väldefinierat beräkningsproblem. Utveckling och analys av algoritmer är grundläggande
För frågor eller problem med endast en begränsad uppsättning fall eller värden finns alltid en algoritm (åtminstone i princip); den består av en tabell med värden på svaren. I allmänhet är det inte ett sådant trivialt förfarande att svara på frågor eller problem som har ett oändligt antal fall eller värden att tänka på, till exempel "Är det naturliga talet (1, 2, 3, …) en grund?" eller "Vad är den största gemensamma delaren av de naturliga siffrorna a och b?" Den första av dessa frågor tillhör en klass som heter decidable; en algoritm som producerar ett ja eller nej svar kallas en beslutsprocedur. Den andra frågan hör till en klass som kallas beräkningsbar; en algoritm som leder till ett specifikt nummersvar kallas en beräkningsprocedur.
Algoritmer finns för många sådana oändliga klasser av frågor; Euclids element, publicerade cirka 300 f.Kr., innehöll en för att hitta den största gemensamma delaren av två naturliga nummer. Varje grundskolestudent borras i långdivision, vilket är en algoritm för frågan "När delar ett naturligt tal a med ett annat naturligt tal b, vad är kvoten och resten?" Användning av denna beräkningsprocedur leder till svaret på den avgörande frågan "Delar b en?" (svaret är ja om resten är noll). Upprepad tillämpning av dessa algoritmer ger slutligen svaret på den avgörande frågan "Är en prime?" (svaret är nej om a kan delas med något mindre naturligt antal förutom 1).
Ibland kan en algoritm inte existera för att lösa en oändlig klass av problem, särskilt när någon ytterligare begränsning görs på den accepterade metoden. Till exempel, två problem från Euclids tid som krävde användning av bara en kompass och en uträtning (omarkerad linjal) - skärning av en vinkel och konstruktion av en kvadrat med ett område lika med en given cirkel - förföljdes i århundraden innan de visade sig vara omöjliga. I början av 1900-talet föreslog den inflytelserika tyska matematikern David Hilbert 23 problem för matematiker att lösa under det kommande seklet. Det andra problemet på hans lista begärde en undersökning av konsistensen hos aritmetiska axiomer. De flesta matematiker hade liten tvekan om det slutgiltiga uppnåendet av detta mål fram till 1931, då den österrikiska födda logikern Kurt Gödel visade det förvånande resultatet att det måste finnas aritmetiska förslag (eller frågor) som inte kan bevisas eller motbevisas. I huvudsak leder något sådant förslag till ett bestämningsförfarande som aldrig slutar (ett tillstånd som kallas stoppproblemet). I ett misslyckat försök att konstatera åtminstone vilka förslag som är olösliga, definierade den engelska matematikern och logikern Alan Turing rigoröst det löst förstått begreppet en algoritm. Även om Turing i slutändan bevisade att det måste existera obeslutliga förslag, blev hans beskrivning av de väsentliga funktionerna i en allmän algoritmmaskin, eller Turing-maskin, grunden för datavetenskap. Idag är frågorna om avgörbarhet och beräknbarhet centrala för utformningen av ett datorprogram - en speciell typ av algoritm.
