Intuitivamente si dispone di un algoritmo per risolvere un problema se si ha un elenco finito di istruzioni tali che:
Il termine deriva dal nome del matematico persiano Al-Khwarizmi (780 – 850 ca) in quanto egli fu uno dei primi a far riferimento esplicito al concetto di algoritmo nel suo “Libro della matematica orientale”.
Dalla definizione di algoritmo è possibile evincere le due proprietà fondamentali di un algoritmo:
Un algoritmo deve inoltre essere non ambiguo, cioè le sue istruzioni devono essere comprensibili a chiunque le voglia applicare.
Per le caratteristiche di finitezza e di determinismo, un algoritmo si presta a essere automatizzato, cioè ad essere eseguito da una macchina opportunamente progettata.
La teoria della calcolabilità nasce nella terza decade del nostro secolo con l’esigenza, nata nell’ambito degli studi di logica, di fornire un equivalente rigoroso del concetto intuitivo di algoritmo, e di indagare le possibilità ed i limiti dei metodi effettivi.
Esempi di algoritmi
Sono esempi di algoritmi:
Un altro esempio di algoritmo
Calcolare il m.c.m. (minimo comune multiplo) di due numeri naturali diversi da zero