miniatura|Visualització del Garbell d'Eratòstenes, un exemple d'algorisme per tal de descartar nombres divisibles i deixar-ne només els nombres primers
Un algorismeDIEC Definició d'algorisme de l'Institut d'estudis Catalans o algoritme és un conjunt finit d'instruccions o passes que serveixen per a executar una tasca o resoldre un problema. En la vida quotidiana, s'empren algorismes en multitud d'ocasions per a resoldre diversos problemes, com per exemple tocar un instrument musical (partitures), construir un aeroplà a escala i muntar un moble prefabricat (expressats en les instruccions a seguir), fer trucs de màgia (passes per a fer el truc) o fer receptes de cuina (passes de la recepta). Alguns exemples d'algorismes a les matemàtiques són l'algorisme de la divisió per a calcular el quocient de dos nombres, l'algorisme d'Euclides per a obtenir el màxim comú divisor de dos enters positius, el mètode de Gauss per resoldre un sistema lineal d'equacions, o un algorisme que sumi els 'n' nombres primers.
Dit d'una manera més formal, un algorisme és una seqüència finita d'instruccions realitzables, no ambigües, l'execució de les quals condueix a una resolució d'un problema. Aquesta definició es pot generalitzar des del punt de vista sistèmic, si se suposa que l'algorisme pot ser dissenyat per rebre i aprofitar una determinada entrada, donant com a resultat una sortida, que pot resoldre un problema determinat.
Història Antiguitat El coneixement de l'aplicabilitat de tècniques repetitives a l'hora de resoldre problemes matemàtics prové de l'antiga Babilònia, on es troben textes en què es proposen algorismes, i on també es feien servir taules de càlcul per resoldre problemes.
Un altre exemple de l'antiguitat que també pertany a l'àmbit de les matemàtiques és l'algorisme d'Euclides per calcular el màxim comú divisor de dos enters positius. Cal destacar també el treball d'Euclides en el camp de la geometria, que fou un referent per al desenvolupament formal de l'algorísmica. Un exemple d'aplicació dels algorismes és el problema que consisteix a trobar el màxim d'un conjunt de nombres. Un exemple més complex per utilitzar aquest algorisme és el que s'explicarà a continuació utilitzant una descripció d'alt nivell.
Algorisme d'Euclides Donat un conjunt finit C de nombres, cal trobar-ne el nombre més gran. Assumim que el conjunt no és buit dels seus elements i estan numerats com
És a dir, donat un conjunt es demana trobar m tal que i per a tot element x que pertany al conjunt C. Es designa
Per trobar-ne l'element màxim, es fa la suposició provisional que el primer element (c1) és el màxim, després, es recorre el conjunt i es compara cada valor amb el valor del màxim nombre trobat fins aquell moment. En el cas que un element sigui major que el màxim, s'assigna el seu valor al màxim. Quan s'acaba de recórrer la llista, el màxim nombre que s'ha trobat és el màxim de tot el conjunt.
L'algorisme pot ser escrit d'una manera més formal en el pseudocodi següent:
Sobre la notació: "←" representa una assignació: ← significa que la variable pren el valor de ; "tornar" termina l'algorisme i retorna el valor a la seva dreta (en aquest cas, el màxim de ).
Origen del terme miniatura|Text en llatí en què la influència del matemàtic àrab es pot trobar en la primera línia: Dixit Algorizmi El terme algorisme prové del matemàtic i astrònom àrab Abu Abdullah Muhammad bin Musa al-Khwarizmi, autor de l'obra Sobre el càlcul amb nombres indis, de l'any 825. Aquesta mateixa obra va ser traduïda al llatí al , incloent-hi el nom de l'autor en forma llatina com a commemoració. Un dels primers usos d'aquest terme es troba al tractat matemàtic en vers Carmen d'Algorisme, és a dir, Cançó o Poema de l'algorisme (c.1220), del professor normand Alexandre de Villadei. Aquesta cançó fou introduïda per tal d'ensenyar el sistema numèric indi. D'aquesta manera, es desprenien mètodes de computació que simplificaven les operacions algebraiques amb els nous numerals (del zero al nou). Així, els càlculs manuals es podien fer amb més eficiència. Una altra obra que fa esment d'Al-Khwarizmi és Algorismus Vulgaris, de Johannes de Sacrobosco, obra escrita el 1250 amb la intenció d'ensenyar els numerals indis i les possibilitats de l'aritmètica que va servir per introduir aquests coneixements a les universitats.
La paraula s'estengué per Occident com al sistema introduït per l'autor basant-se en la numeració índia i les operacions fonamentals que es podien simplificar amb aquest sistema.
Desenvolupament La història del plantejament matemàtic de la teoria dels algorismes va haver de nodrir-se de diferents idees en el camp de les matemàtiques per tal d'arribar a disposar dels primers computadors.
Com a punt de partida del tractament axiomàtic de la matemàtica, és notable la tasca d'Euclides, que va formular els axiomes necessaris per desprendre la geometria amb la publicació del seu treball Elements.
El desenvolupament de l'estudi d'algorismes, el va iniciar David Hilbert el 1900, en fer la proposició de la possibilitat de disposar d'un algorisme capaç de resoldre demostracions matemàtiques; això seria, senzillament, un mètode d'esbrinar si, donada una afirmació, aquesta és verdadera o és falsa.
Un treball important que formulà les bases per tal de començar formalment la investigació de l'algorítmia, el va fer Kurt Gödel, en demostrar el 1931 en l'article ”Uber formal unentscheidbare Sätze der Principia Mathematica und verwandter a Systeme” el teorema d'incompletesa, en què s'estableix que no es pot trobar un conjunt d'axiomes que compleixin les condicions necessàries per a la proposició de Hilbert: Axiomes prou potents per a demostrar qualsevol enunciat vertader. No admeten contradiccions, de manera que les afirmacions no puguin ser certes alhora que les seves negacions ho són.
Gràcies a Hilbert i a Gödel, es va aconseguir desenvolupar l'algorítmica en paral·lel, per part de Church i d'en Turing. Per una banda, Church dedueix el càlcul lambda, mentre que Turing proposa la seva màquina, dues aplicacions en paral·lel i dutes a terme per separat. Amb aquests dos treballs, s'omple el buit necessari per a aclarir el concepte d'irresolubilitat del problema de Hilbert en el cas dels algorismes.
Aplicacions Resolució de problemes miniatura|Algorisme d'ordenació L'algorisme dona una solució genèrica a un problema i es pot emprar totes les vegades que es presenti aquest mateix problema, sempre que es disposi d'unes entrades adequades per fer-lo servir: per exemple, l'algorisme de la suma o de la divisió és genèric i independent dels nombres en què s'hagi de sumar o dividir.
Una vegada descobert un algorisme per efectuar una tasca, la realització d'aquesta ja no requereix entendre els principis en què es basa aquest algorisme, ja que el procés es redueix a seguir-ne les instruccions. Per exemple, es pot fer una divisió seguint l'algorisme sense entendre per què funciona. Es pot dir que la intel·ligència requerida per portar a terme la tasca és codificada a l'algorisme.
Les màquines algorísmiques són aquelles capaces de dur a terme algorismes, i entre aquestes estan els ordinadors. En l'àmbit dels ordinadors, els algorismes s'expressen com a programes. Els programes són algorismes codificats amb un llenguatge no ambigu, la sintaxi i semàntica del qual "entén" l'ordinador. Hi ha molts llenguatges de programació d'ordinadors, com per exemple Fortran, pascal o C.
Així, doncs, si es vol que un ordinador efectuï una tasca, primer s'ha de desenvolupar un algorisme per portar-la a terme; programar l'algorisme a la màquina consisteix a representar aquest algorisme de manera que es pugui comunicar amb ella. En altres paraules, s'ha de transformar l'algorisme conceptual en un conjunt d'instruccions i representar aquestes últimes en un llenguatge sense ambigüitat que pugui fer funcionar la màquina com es vol. Un computador és tot aparell o màquina destinada a processar informació, entenent-se per procés les successives fases, manipulacions o transformacions que sofreix la informació per a resoldre un problema determinat, seguint les instruccions d'un programa registrat.
Gràcies a la capacitat per comunicar el pensament humà mitjançant algorismes, es poden construir màquines el comportament de les quals simula intel·ligència, anomenada de manera habitual intel·ligència artificial, tot i que aquesta noció és molt discutida. El nivell d'intel·ligència que simula la màquina estarà limitat per la intel·ligència que puguem comunicar-li per mitjà d'algorismes. Les màquines només poden reproduir tasques algorítmiques. Si es trobés un algorisme per dirigir l'execució d'una tasca, es podria construir una màquina per portar-la a terme sempre que la tecnologia ho permetés. Si no es troba un algorisme, és possible que l'execució estigui fora de les capacitats de les màquines.
A la imatge d'aquesta secció, es mostra l'algorisme d'ordenació en una versió molt simple. El propòsit de l'algorisme és fer passades des del cursor inicial fins al final, marcant el menor nombre i posant-lo al principi. És clar que tots els casos tenen les mateixes operacions, ja que el recorregut és sempre el mateix, del cursor fins al final avaluant d'un a un tots els casos. Aquest exemple mostra l'avantatge d'aquestes tècniques, ja que fa servir la força bruta per a recórrer un camí i arribar a un resultat sense fer divisions.
Funcions Un algorisme es pot entendre com una funció que transforma les dades d'un problema (entrada) en les dades d'una solució (sortida). Les dades es poden representar, al seu torn, com a seqüències de bits, i en general, de símbols qualssevol. Com que cada seqüència de bits representa un nombre natural (sistema binari), els algorismes són, en essència, funcions dels nombres naturals en els nombres naturals que sí que es poden calcular. És a dir, que tot algorisme calcula una funció en què cada nombre natural és la codificació d'un problema o d'una solució (ajustant-se cadascuna de les resolucions dels problemes als algorismes utilitzats en les funcions).
Informàtica Un algorisme informàtic (o, alternativament, algoritme) és un procés seqüencial d'instruccions finites amb l'objectiu de prendre una decisió o bé trobar la solució a un problema específic. Una sèrie complexa d'algorismes informàtics ordenats i codificats mitjançant el llenguatge de la programació, esdevé un programa.
En el món de la informàtica, els algorismes són un element clau, ja que permeten al programador resoldre problemes abans d'escriure'ls en llenguatge de programació, és a dir, s'ha de resoldre el problema que ens planteja amb un algorisme abans d'escriure el codi d'un programa. Originàriament, la idea de portar el concepte d'algorisme al camp de la informàtica va ser proposada pel matemàtic anglès Alan Turing, qui va establir una base per definir els elements bàsics d'un algorisme aplicat a les ciències de la computació. Aquests, anys després, veiem que constitueixen un esquelet de processos que després es codificaran i programaran per ser realitzats per la computadora.
Un algorisme informàtic consta de tres parts: l'entrada o input, on s'introdueixen les dades que l'algorisme necessita per poder operar; el procés, la part en què l'algorisme realitza una sèrie de càlculs lògics per resoldre el problema; i la sortida o output, que són els resultats obtinguts en el procés.
Característiques Un algorisme informàtic, ha de tenir les característiques següents per ser considerat com a tal:
Ha de ser seqüencial: ha d'operar en seqüència, s'han de processar un per un. Ha de ser precís: ha d'indicar l'ordre de realització de cada pas, i no poden ser ambigus o subjectius. Ha d'estar definit: els passos han de ser independents els uns dels altres, i si l'algorisme s'aplica dues vegades, s'ha d'obtenir el mateix resultat.