Algoritme, systematisk prosedyre som produserer - i et begrenset antall trinn - svaret på et spørsmål eller løsningen på et problem. Navnet stammer fra den latinske oversettelsen, Algoritmi de numero Indorum, fra det 9. århundre muslimske matematikeren al-Khwarizmi sin aritmetiske avhandling "Al-Khwarizmi om den hinduiske reckoningskonsten."
informatikk: algoritmer og kompleksitet
En algoritme er en spesifikk prosedyre for å løse et veldefinert beregningsproblem. Utvikling og analyse av algoritmer er grunnleggende
For spørsmål eller problemer med bare et begrenset sett med tilfeller eller verdier, eksisterer det alltid en algoritme (i det minste i prinsippet); den består av en tabell med verdier av svarene. Generelt er det ikke en så bagatellmessig prosedyre å svare på spørsmål eller problemer som har et uendelig antall saker eller verdier å ta i betraktning, for eksempel "Er det naturlige tallet (1, 2, 3, …) et hovedmål?" eller "Hva er den største fellesdeleren av de naturlige tallene a og b?" Det første av disse spørsmålene tilhører en klasse som kalles desidable; en algoritme som produserer et ja eller nei-svar kalles en beslutningsprosedyre. Det andre spørsmålet tilhører en klasse som heter computable; en algoritme som fører til et spesifikt tallbesvarelse kalles en beregningsprosedyre.
Algoritmer eksisterer for mange slike uendelige spørsmålsklasser; Euclids elementer, utgitt omtrent 300 f.Kr., inneholdt en for å finne den største fellesdeleren med to naturlige tall. Hver barneskoleelev blir boret i langdivisjon, som er en algoritme for spørsmålet "Når vi deler et naturlig tall a med et annet naturlig tall b, hva er kvoten og resten?" Bruk av denne beregningsmetoden fører til svaret på det avgjørbare spørsmålet "Deler b a?" (svaret er ja hvis resten er null). Gjentatt anvendelse av disse algoritmene gir etter hvert svaret på det avgjørelige spørsmålet "Er en førsteklasses?" (svaret er nei hvis a kan deles med noe mindre naturlig tall foruten 1).
Noen ganger kan det ikke eksistere en algoritme for å løse en uendelig klasse problemer, spesielt når noen ytterligere begrensninger er gjort på den aksepterte metoden. For eksempel ble det fulgt to problemer fra Euclids tid som krever bruk av bare et kompass og en rettetang (umerket linjal) - å strekke en vinkel og konstruere en firkant med et område lik en gitt sirkel - i århundrer før de viste seg å være umulige. På begynnelsen av 1900-tallet foreslo den innflytelsesrike tyske matematikeren David Hilbert 23 problemer for matematikere å løse i det kommende århundre. Det andre problemet på listen hans ba om en undersøkelse av konsistensen av aritmetikkens aksiomer. De fleste matematikere var i liten grad i tvil om den eventuelle oppnåelsen av dette målet frem til 1931, da den østerrikskfødte logikeren Kurt Gödel demonstrerte det overraskende resultatet at det må eksistere aritmetiske proposisjoner (eller spørsmål) som ikke kan bevises eller motbevises. I hovedsak fører enhver slik proposisjon til en bestemmelsesprosedyre som aldri slutter (en tilstand kjent som stoppingsproblemet). I en mislykket innsats for å konstatere i det minste hvilke proposisjoner som er uløselige, definerte den engelske matematikeren og logikeren Alan Turing nøye det løst forståtte konseptet til en algoritme. Selv om Turing endte med å bevise at det må eksistere ubestemmelige proposisjoner, ble beskrivelsen hans av de vesentligste egenskapene til enhver generell algoritmaskin, eller Turing-maskin, grunnlaget for informatikk. I dag er spørsmålene om avgjørbarhet og beregbarhet sentrale i utformingen av et dataprogram - en spesiell type algoritme.
