algoritmo
algoritmo
algoritmo procedimento sistematico di calcolo, oggi per lo più destinato a essere eseguito da un automa esecutore quale un computer. Il termine deriva dal nome latinizzato del matematico di cultura araba Muḥammad ibn Mūsā, detto al-Khuwārizmī dalla sua regione di origine (il Khorasan), autore del trattato al-Kitāb al-mukhtasar fi hisab al-giabr wa’l-muqābala (Manuale di calcolo per completamento e riduzione) dal cui titolo deriva la parola «algebra». L’algoritmo è una sequenza finita di passi che specificano le operazioni necessarie per risolvere un problema: le istruzioni definiscono le operazioni logiche e algebriche da eseguire su un insieme di dati per ottenere un risultato e si distinguono in istruzioni per i dati di ingresso, istruzioni per l’elaborazione dei dati e istruzioni per la comunicazione dei risultati. Un algoritmo deve possedere alcune proprietà formali:
• finitezza (numerica e temporale): deve avere un numero finito di istruzioni e le operazioni indicate in ciascuna di esse devono essere eseguite in un tempo finito e per un numero finito di volte;
• non ambiguità: l’interpretazione delle istruzioni deve essere univoca;
• eseguibilità: deve essere possibile eseguire le istruzioni con l’automa di cui si dispone;
• determinismo: a ogni passo della procedura deve essere univocamente determinata l’istruzione da eseguire.
Esistono molti modi per descrivere gli algoritmi: liste e sequenze di istruzioni, descrizioni in linguaggio naturale, diagrammi di flusso. Quest’ultima rappresentazione (→ algoritmo, rappresentazione di un) contiene:
• le informazioni relative all’insieme dei dati di ingresso {xi} per i = 1, …, n;
• la sequenza delle operazioni da effettuare, descritte da una funzione ƒ(xi), definita su tutti i valori xi in ingresso;
• le soluzioni {yj} per j = 1, ..., m, che rappresentano l’insieme dei valori in uscita. In generale m ≠ n.
Una particolare configurazione degli ingressi e delle uscite di un algoritmo è chiamata istanza: un problema con il suo procedimento risolutivo è l’unione di tutte le possibili istanze; a partire da un insieme di dati noti (istanza del problema) si giunge alla conoscenza di dati non noti (soluzione dell’istanza specificata). Si può quindi dire che un algoritmo è un procedimento che consente di calcolare un risultato in uscita sulla base dei dati in ingresso.
Per esempio, il problema della ricerca del massimo comune divisore fra due numeri interi a e b, indicato simbolicamente con mcd(a, b), può essere risolto utilizzando l’algoritmo euclideo (→ Euclide, algoritmo di) che si basa sulla proprietà che se due numeri naturali a, b, con a > b, sono divisibili per un terzo numero x, allora anche il resto della divisione intera tra a e b, indicato con mod(a, b), è divisibile per lo stesso numero x. Attraverso un numero finito di divisioni successive con resto si ottengono valori sempre più piccoli, sino a giungere al risultato finale in cui il mcd cercato è uguale a mod(r, 0), essendo r il resto dell’ultima divisione intera effettuata. Si possono formalizzare queste operazioni utilizzando una particolare forma di linguaggio chiamato → linguaggio algoritmico, destinato a essere eventualmente codificato in un particolare → linguaggio di programmazione comprensibile a un automa esecutore quale è il computer:
All’interno di un algoritmo possono comparire strutture che guidano e controllano l’ordine del flusso delle istruzioni secondo tre modalità principali, dette strutture di controllo: la → sequenza, l’→ alternativa, l’→ iterazione. Nell’esempio precedente alcune operazioni sono ripetute più volte e la loro esecuzione è controllata da un meccanismo di arresto, che ne consente l’interruzione al verificarsi di una data condizione (le operazioni continuano «mentre» il valore della variabile b è maggiore di 0; si interrompono quando diviene 0). Si definisce iterativo un algoritmo in cui compare un ciclo di istruzioni la cui esecuzione viene ripetuta (iterata) un numero controllato di volte. Se, quindi, per calcolare il valore v di una espressione si utilizza un algoritmo iterativo, si ottiene, a ogni i-esima iterazione, un diverso valore vi. Si costruisce così una successione finita di valori {vi}. Questa può consentire di ottenere il valore esatto ricercato oppure, se è parte di una successione convergente infinita, il valore approssimato del suo limite (→ successione, convergenza di una). In questo secondo caso, il valore ottenuto conterrà, quindi, un → errore che, in generale, diminuisce all’aumentare del numero di iterazioni. Sia che si raggiunga un valore esatto, sia che ci si approssimi a esso, un algoritmo di questo tipo è detto algoritmo iterativo convergente.
Un metodo di costruzione di un algoritmo, di specifico interesse e raffinatezza, si ha quando è possibile individuare particolari procedure che richiamando sé stesse consentono di giungere al risultato. Il procedimento avviene così per ricorsione e l’algoritmo è detto ricorsivo. Per esempio, per il calcolo dei termini ƒi della successione di → Fibonacci, si osserva che ogni termine, dal terzo in poi, è uguale alla somma dei due che lo precedono. Si può allora descrivere costruttivamente i primi n termini di tale successione con un algoritmo ricorsivo: l’n-esimo termine della successione è dato dall’espressione ƒn = ƒn−1 + ƒn−2. Il termine di indice n −1 è a sua volta ottenuto come ƒn−1 = ƒn−2 + ƒn−3 e così via, fino a giungere ai valori di ƒ1 e ƒ2, che sono assegnati e uguali a 1.
Lo schema dell’algoritmo è quindi realizzato attraverso una procedura ricorsiva (che qui è indicata con il nome «fibo»):
La controparte formale della teoria generale degli algoritmi, nella quale viene precisata la nozione di operazione e di procedura calcolabile, è la teoria della → ricorsività (teorema di → Böhm-Jacopini).