Algoritme, procediment sistemàtic que produeix -en un nombre finit de passos- la resposta a una pregunta o la solució d’un problema. El nom deriva de la traducció llatina, Algoritmi de numero Indorum, del tractat aritmètic del matemàtic musulmà del segle IX al-Khwarizmi "Al-Khwarizmi sobre l'art hindú de comptar".
informàtica: algoritmes i complexitat
Un algorisme és un procediment específic per resoldre un problema computacional ben definit. El desenvolupament i l'anàlisi d'algorismes és fonamental
Per a preguntes o problemes amb només un conjunt finit de casos o valors, sempre existeix un algorisme (almenys en principi); consisteix en una taula de valors de les respostes. En general, no és un procediment tan banal respondre a preguntes o problemes que tingui un nombre infinit de casos o valors a considerar, com ara "El nombre natural (1, 2, 3, …) és primer?" o "Quin és el màxim divisor comú dels nombres naturals a i b?" La primera d’aquestes preguntes pertany a una classe anomenada decidible; un algorisme que produeix una resposta sí o no s’anomena procediment de decisió. La segona pregunta pertany a una classe anomenada computable; un algorisme que condueix a una resposta de número determinada s’anomena procediment de càlcul.
Existeixen algoritmes per a moltes classes infinites de preguntes; Els elements d'Euclides, publicats al voltant de 300 aC, contenien un per trobar el màxim divisor comú de dos nombres naturals. Cada estudiant de primària es perfora en una divisió llarga, que és un algoritme per a la pregunta "Al dividir un nombre natural a per un altre número natural b, quins són el quocient i la resta?" L'ús d'aquest procediment computacional condueix a la resposta a la pregunta decidida "Divideix b?" (la resposta és sí si la resta és zero). L’aplicació repetida d’aquests algoritmes acaba produint la resposta a la pregunta decidida “És un valor primordial?” (la resposta és que si a és divisible per un nombre natural més reduït a més d'1).
De vegades no pot existir un algorisme per resoldre una classe infinita de problemes, especialment quan es fa una altra restricció al mètode acceptat. Per exemple, dos problemes de l’època d’Euclides que requerien l’ús només d’una brúixola i una recta (regla no marcada) —el·leccionar un angle i construir un quadrat amb una àrea igual a un cercle determinat— es van perseguir durant segles abans que es demostrés que era impossible.. Al tombant del segle XX, l’influent matemàtic alemany David Hilbert va proposar 23 problemes per als matemàtics a resoldre al segle que ve. El segon problema de la seva llista va demanar una investigació de la consistència dels axiomes de l'aritmètica. La majoria dels matemàtics tenien poc dubtes de la consecució d’aquest objectiu fins al 1931, quan el lògic austríac Kurt Gödel va demostrar el sorprenent resultat que hi ha d’haver proposicions (o preguntes) aritmètiques que no es poden demostrar ni rebutjar. Essencialment, qualsevol proposta d’aquest tipus condueix a un procediment de determinació que no s’acaba mai (condició coneguda com el problema d’aturada). En un esforç infructuós per determinar almenys quines proposicions són insolvables, el matemàtic i logístic anglès Alan Turing va definir amb rigor el concepte d'un algorisme algoritzat. Tot i que Turing va acabar demostrant que hi hauria d’haver proposicions indiscutibles, la seva descripció de les característiques essencials de qualsevol màquina d’algoritmes de propòsit general, o màquina de Turing, va esdevenir el fonament de la informàtica. Avui, els problemes de decisibilitat i computabilitat són fonamentals en el disseny d'un programa informàtic: un tipus especial d'algorisme.
