Algoritme, systematisk procedure, der producerer - i et begrænset antal trin - svaret på et spørgsmål eller løsningen på et problem. Navnet stammer fra den latinske oversættelse, Algoritmi de numero Indorum, fra det 9. århundrede muslimske matematiker al-Khwarizmis aritmetiske afhandling "Al-Khwarizmi om den hinduistiske regning af regning."
datalogi: Algoritmer og kompleksitet
En algoritme er en specifik procedure til løsning af et veldefineret beregningsproblem. Udvikling og analyse af algoritmer er grundlæggende
For spørgsmål eller problemer med kun et begrænset sæt sager eller værdier eksisterer der altid en algoritme (i det mindste i princippet); den består af en tabel med værdier for svarene. Generelt er det ikke en sådan triviel procedure at besvare spørgsmål eller problemer, der har et uendeligt antal sager eller værdier at overveje, såsom "Er det naturlige tal (1, 2, 3, …) et vigtigt?" eller "Hvad er den største fællesdeler af de naturlige tal a og b?" Det første af disse spørgsmål hører til en klasse kaldet decidable; en algoritme, der producerer et ja eller nej svar kaldes en beslutningsprocedure. Det andet spørgsmål hører til en klasse, der kaldes computbar; en algoritme, der fører til et specifikt nummersvar, kaldes en beregningsprocedure.
Algoritmer findes for mange sådanne uendelige klasser af spørgsmål; Euclids elementer, der blev offentliggjort omkring 300 f.Kr., indeholdt en til at finde den største fælles skiller med to naturlige tal. Hver folkeskole studerende bores i lang opdeling, som er en algoritme til spørgsmålet "Når vi deler et naturligt tal a med et andet naturligt tal b, hvad er kvotienten og resten?" Brug af denne beregningsmetode fører til svaret på det afgørelsesmæssige spørgsmål "Deler b en?" (svaret er ja, hvis resten er nul). Gentagen anvendelse af disse algoritmer producerer til sidst svaret på det afgørelsesmæssige spørgsmål "Er en prime?" (svaret er nej, hvis a kan deles med et mindre naturligt antal udover 1).
Nogle gange kan der ikke findes en algoritme til løsning af en uendelig klasse af problemer, især når der foretages en yderligere begrænsning af den accepterede metode. For eksempel blev to problemer fra Euclids tid, der kun krævede brug af et kompas og en udrangerning (umærket lineal) - beskæring af en vinkel og konstruering af en firkant med et område, der var lig med en given cirkel - forfulgt i århundreder, før de blev vist at være umulige. Ved århundredeskiftet foreslog den indflydelsesrige tyske matematiker David Hilbert 23 problemer for matematikere at løse i det kommende århundrede. Det andet problem på hans liste bad om en undersøgelse af konsistensen af aritmetikens aksiomer. De fleste matematikere var ikke i tvivl om den eventuelle opnåelse af dette mål indtil 1931, da den østrigsk-fødte logiker Kurt Gödel demonstrerede det overraskende resultat, at der skal eksistere aritmetiske forslag (eller spørgsmål), som ikke kan bevises eller modbevises. I det væsentlige fører ethvert sådant forslag til en bestemmelsesprocedure, der aldrig slutter (en tilstand, der er kendt som stop-problemet). I en mislykket indsats for i det mindste at konstatere, hvilke påstande, der er uopløselige, definerede den engelske matematiker og logiker Alan Turing grundigt det løst forståede begreb om en algoritme. Selvom Turing endte med at bevise, at der skal eksistere ubestemte forslag, blev hans beskrivelse af de væsentligste træk ved en hvilken som helst generel algoritmemaskine eller Turing-maskine grundlaget for datalogi. I dag er spørgsmålene om beslutningstid og beregbarhed centrale for designet til et computerprogram - en speciel type algoritme.
