Intuitivamente si dispone di un algoritmo per risolvere un problema se si ha un elenco finito di istruzioni tali che:
1) a partire dai dati iniziali le istruzioni sono applicabili in maniera rigorosamente deterministica, cioè in modo che ad ogni passo sia sempre possibile stabilire univocamente quale è l’istruzione che deve essere applicata al passo successivo;
2) si disponga di un criterio univoco per stabilire quando si è raggiunto uno stato finale, quando cioè il processo deve considerarsi terminato e il risultato, se esiste, è stato ottenuto. Uno stato finale deve sempre essere raggiungibile in un numero finito di passi.
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:
- finitezza, ovvero la sequenza delle istruzioni di un algoritmo deve essere finita;
- effettività, ovvero ogni algoritmo deve portare ad un risultato.
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à e i limiti dei metodi effettivi.
Esempi di algoritmi
Sono esempi di algoritmi:
• le regole delle quattro operazioni matematiche;
• il metodo euclideo per il calcolo del massimo comun divisore;
• il metodo delle tavole di verità per stabilire se un’espressione logica è una tautologia.
Un altro esempio di algoritmo
Calcolare il M.C.D. (massimo comun divisore) di due numeri naturali diversi da zero
1. Scomporre i numeri in fattori primi
2. Scegliere i fattori comuni
3. Scegliere quelli con esponente più piccolo
4. Moltiplicare tra loro i numeri scelti
