algoritmo

Matematica

Termine, derivato dall’appellativo al-Khuwārizmī («originario della Corasmia») del matematico Muḥammad ibn Mūsa del 9° sec., che designa qualunque schema o procedimento sistematico di calcolo (per es. l’a. euclideo, delle divisioni successive, l’a. algebrico, insieme delle regole del calcolo algebrico ecc.). Con un a. si tende a esprimere in termini matematicamente precisi il concetto di procedura generale, di metodo sistematico valido per la soluzione di una certa classe di problemi. Come esempio consideriamo un a. che codifica un comportamento assai comune, quello di una persona che confronta due parole. Esprimeremo questo a. in un linguaggio naturale un po’ rigido, tenendo presente che questa descrizione informale dell’a. è il punto di partenza anche per il disegno di nuovi algoritmi. A volte si usa, per lo stesso scopo, una rappresentazione grafica equivalente, il cosiddetto diagramma di flusso (➔ flowchart).

confronta (due stringhe di caratteri, S₁ e S₂, dando come risultato 0 se sono diverse, 1 se sono uguali)

1. Se S₁ e S₂ hanno lunghezza differente finisci ponendo risultato = 0, altrimenti

2. sia L la lunghezza di S₁ e S₂.

3. Per ciascuno dei valori di j da 1 a L esegui i seguenti passi:

4. confronta il carattere j-mo di S₁ con il carattere j-mo di S₂:

5. se sono diversi finisci ponendo risultato = 0, altrimenti

6. passa al successivo valore di j (se non sono esauriti).

7. Una volta esauriti i valori di j finisci dichiarando risultato = 1.

Si noti come l’a. riceva dei dati in ingresso (input) costituiti da due stringhe di caratteri di un alfabeto precisato e di lunghezza qualsiasi, producendo dei dati in uscita (output) che, in questo caso, sono le cifre 0 o 1.

Proprietà fondamentali di un algoritmo

Effettività. Un a. deve essere effettivamente eseguibile da un esecutore, che diciamo automa; l’automa deve poter riconoscere cioè le parti minime della descrizione dell’a. ossia deve accettare il linguaggio in cui l’a. è espresso; le frasi ben formate di questo linguaggio si dicono istruzioni.

Finitezza di espressione. Anche se si possono pensare procedure la cui definizione non finisce mai (per es. la rotta di una nave) per il semplice fatto che la lista delle istruzioni aumenta continuamente, nella nozione di a. si tende a non comprendere questo tipo di procedure; un a. è dunque una successione finita di istruzioni da eseguire; con un numero finito di istruzioni si può naturalmente descrivere anche un procedimento molto lungo (eventualmente anche infinito, come nelle divisioni che danno un numero periodico, o in certe radici quadrate).

Finitezza di calcolo. Nel concetto di a. è solitamente inclusa la condizione di terminazione della procedura per qualsiasi situazione dei dati iniziali all’interno di un certo dominio.

Determinismo. A ogni passo dell’esecuzione della procedura deve essere definita una e una sola operazione da eseguire successivamente. La condizione 1.1 è praticamente irrinunciabile; la 1.2, la 1.3 e la 1.4 possono essere rese meno stringenti o abbandonate del tutto, dando luogo a concetti più generali di quello di algoritmo. In particolare l’abbandono della condizione 1.4 porta al concetto di a. non deterministico.

Teorie degli algoritmi

Si possono distinguere due linee di pensiero. Da un lato si cerca di precisare il concetto di operazione effettiva (realizzabile cioè mediante a.). Su questa linea si sviluppano il concetto di funzione ricorsiva, la definizione delle funzioni mediante l’operatore di astrazione lambda e i sistemi di combinatori di H.B. Curry. Dall’altro si cerca di caratterizzare in modo astratto il procedimento di calcolo. Si hanno in questo modo la teoria delle macchine di A. Turing, la teoria degli a. normali di A.A. Markov, e i sistemi di produzioni di E.L. Post. L’aspetto convergente e interessante delle varie teorie degli a. sta nel fatto che esse sono state dimostrate equivalenti. È possibile costruire delle macchine di Turing che calcolano una qualsiasi funzione ricorsiva, dei sistemi di Post che eseguono il calcolo di una qualsiasi macchina di Turing ecc. Questo è una conferma empirica della cosiddetta tesi di A. Church, secondo cui le funzioni computabili mediante a. sono tutte e sole le funzioni ricorsive generali. Non sono state sinora trovate smentite a questa tesi, in quanto in nessun altro modo rigoroso di costruzione formale di a. è stato possibile creare a. non calcolabili mediante una funzione ricorsiva generale.

Informatica

In informatica si definisce a. una sequenza finita di operazioni elementari, eseguibili facilmente da un elaboratore che, a partire da un insieme di dati I (input), produce un altro insieme di dati O (output) che soddisfano un preassegnato insieme di requisiti. Spesso i requisiti vengono distinti in due categorie: i vincoli, ossia requisiti che devono essere soddisfatti in ogni caso, e gli obiettivi, ossia requisiti che devono essere soddisfatti il meglio possibile secondo un qualche criterio specificato. Un a. è caratterizzato essenzialmente da due elementi: la complessità computazionale, relativa al numero di operazioni elementari necessarie per produrre l’output (direttamente legato al tempo di calcolo necessario per eseguire l’a.), e l’approssimazione, relativa a quanto vengono soddisfatti gli obiettivi secondo il criterio specificato. Dalla metà degli anni 1980 le tecniche algoritmiche hanno subito notevoli evoluzioni sotto diversi aspetti: una migliore utilizzazione delle crescenti possibilità offerte dai moderni mezzi di elaborazione (in particolare sfruttando in modo adeguato le possibilità di parallelismo, sia attraverso l’esecuzione simultanea di operazioni analoghe, come nell’elaborazione vettoriale, sia attraverso l’uso di opportune reti di elementi di elaborazione, quali, per es., le reti neurali, generalmente calibrate su specifiche applicazioni); l’uso di strutture dati più sofisticate adatte alle particolari classi di problemi trattati; l’uso di euristiche più potenti e flessibili di quelle usate precedentemente (sfruttando a fondo i concetti di ricerca locale con memoria, inserendo spesso alcuni elementi di tipo probabilistico). Gli a. basati su queste nuove tecniche raramente consentono di garantire a priori in modo esatto un assegnato livello di approssimazione, ma consentono in genere di raggiungere soluzioni molto buone, dando in molti casi garanzie a posteriori di tipo statistico.