Programmazione, algoritmi di

    Enciclopedia della Scienza e della Tecnica (2008)

di Alessandro Panconesi

Programmazione, algoritmi di

Il termine algoritmo denota un procedimento sistematico ed esplicitato nei suoi passi elementari per l’esecuzione di un calcolo, inteso nella sua accezione più ampia, ovvero non limitata a calcoli numerici. Nel corso del tempo il termine è diventato quasi sinonimo di procedimento di calcolo programmabile su un calcolatore, un’equivalenza che ha radici profonde. Gli algoritmi rappresentano l’anima stessa dell’informatica, oltre a essere un campo di indagine di fondamentale importanza per la matematica.

Gli algoritmi sono stati oggetto sin dall’antichità dell’attenzione dei matematici, né avrebbe potuto essere diversamente, essendo il termine sinonimo di procedimento di calcolo effettivo. Le ricerche più recenti in ambito archeologico hanno portato alla luce alcune tavolette di argilla che mostrano come alcuni algoritmi per effettuare calcoli non banali fossero noti agli antichi babilonesi.

L’origine del termine algoritmo è riconducibile al nome del grande matematico Muḥammad ibn Mūsā al-Ḫwārizmī, che visse a Baghdad tra il 780 e l’850. Non si conoscono molti episodi della sua vita. Di certo visse all’epoca del califfato di al-Ma’mūn, al quale dedicò un trattato di astronomia e l’opera sua più celebre, Kitāb al-Ǧabr wa-’l-muqābala, da cui ha origine il termine algebra. Al-Ḫwārizmī scrisse anche un trattato, di cui ci è pervenuta soltanto la traduzione in latino del XII secolo, dal titolo Algoritmi de numero Indorum. Quest’opera introduceva nel mondo occidentale due importanti conquiste scientifiche avvenute in Oriente: il sistema decimale e la concezione moderna del numero zero, entrambi sconosciuti nel mondo greco-romano. Il termine algoritmi era evidentemente la traduzione fonetica del nome al-Ḫwārizmī. Quello che per l’epoca era un neologismo assunse in seguito il suo significato attuale.

Nel contesto storico appena delineato è forse opportuno ricordare come la diffusione in Occidente di queste idee ebbe un grande impulso grazie anche all’opera di matematici italiani. Tra questi va ricordato in particolare Leonardo da Pisa detto Fibonacci, secondo alcuni perché era figlio di Bonaccio, soprannome dato al padre, secondo altri perché apparteneva alla famiglia dei Bonacci. Egli stesso racconta nel Liber abaci (1202) di esser venuto in contatto con la cultura matematica araba operando come contabile nell’uffico doganale paterno situato nel porto algerino di Bugia, l’odierna Bejaia.

Alcuni esempi molto familiari di algoritmi sono le regole di moltiplicazione e di divisione che si imparano sin dalle scuole elementari. Mentre calcoli di poche cifre possono essere elaborati anche mentalmente o con metodi ad hoc, è evidente che in generale la moltiplicazione necessita di un procedimento sistematico per poter essere eseguita.

Esempi più sofisticati di algoritmo, noti sin dall’antichità, sono quello di Euclide per la determinazione del massimo comun divisore tra due numeri e il cosidetto setaccio di Eratostene: si tratta di un algoritmo che, dato un numero N, calcola tutti i numeri primi minori di N. Un altro esempio piuttosto noto, tipicamente insegnato nella scuola media superiore, è il procedimento di Carl Friedrich Gauss per la risoluzione dei sistemi di equazioni lineari.

Più in generale il termine algoritmo si riferisce a un procedimento sistematico per il raggiungimento di un qualche obiettivo. Può essere paragonato a una ricetta di cucina: se le istruzioni vengono specificate con sufficiente precisione anche una persona alle prime armi sarà in grado di preparare una torta in modo soddisfacente.

Gli esempi riportati illustrano come un algoritmo sia un procedimento di calcolo che produce qualcosa in uscita (output) una volta che vengano specificati i dati in entrata (input). Nel caso della moltiplicazione, i dati in input sono i due numeri da moltiplicare e l’output è il risultato della moltiplicazione. Nel caso della ricetta, l’input è fornito dagli ingredienti e l’output è la torta. Quest’ultimo caso, in verità di natura metaforica, evidenzia un fatto importante: input e output non devono necessariamente essere numeri ma possono appartenere a un dominio qualsiasi. Il punto cruciale è che le istruzioni per l’ottenimento dell’output a partire dall’input siano specificate a un livello di dettaglio tale da non presentare ambiguità e da poter essere eseguite da un agente privo della conoscenza complessiva data dal contesto culturale di riferimento, vale a dire da una macchina.

sommario

1. Gli algoritmi e i fondamenti della matematica. 2. Algoritmo = Programma? 3. Algoritmi efficienti. □ Bibliografia.

Gli algoritmi e i fondamenti della matematica

Una formalizzazione della nozione intuitiva di algoritmo si è avuta in seguito a una serie di indagini sui fondamenti della matematica avvenute nella prima metà del XX secolo. La genesi di queste ricerche può essere fatta risalire alla celebre conferenza Matematische Probleme, che David Hilbert tenne al Congresso internazionale dei matematici svoltosi a Parigi nel 1900. In quell’occasione Hilbert presentò una lista di ventitre problemi aperti destinati a esercitare una grande influenza sull’intero sviluppo della matematica del Novecento. Uno degli elementi portanti della concezione hilbertiana della matematica era un ambizioso programma di meccanizzazione del procedimento deduttivo proprio del metodo assiomatico. Secondo tale metodo, la matematica procede partendo da alcune semplicissime assunzioni iniziali, gli assiomi, derivando man mano le loro conseguenze logiche attraverso l’applicazione meccanica di regole di inferenza. Hilbert e la sua scuola ritenevano che fosse possibile portare il livello di formalizzazione del metodo assiomatico a un punto tale da renderlo interamente meccanico.

Il coronamento del programma formalista hilbertiano sarebbe stato una sorta di algoritmo universale per determinare la veridicità o meno degli enunciati matematici. In termini moderni, si potrebbe dire che l’obiettivo di Hilbert era quello di costruire un calcolatore (il che come vedremo equivale a specificare un algoritmo) il quale, dato in input un enunciato – per esempio ‘esistono infiniti numeri primi’ – avrebbe dato in output la risposta ‘vero’ o ‘falso’ (‘vero’ nel caso dell’esempio). Questo progetto era una versione meno ambiziosa e ristretta alla sola matematica del sogno accarezzato da Leibniz, secondo il quale era possibile dirimere le divergenze di opinioni tra esseri umani attraverso il calcolo logico, e cioè in definitiva tramite un calcolatore. Il problema di capire se l’algoritmo universale voluto da Hilbert esistesse o meno era stato denominato Entscheidungsproblem, problema della decisione (più precisamente, si trattava di stabilire se esiste un algoritmo in grado di decidere, dato un qualunque enunciato della logica del primo ordine, se esso è universalmente valido).

Tale algoritmo universale esiste anche se solamente per ambiti ristretti della matematica. Ne sono esempi l’aritmetica di Presburger, in cui gli assiomi sono limitati a specificare le proprietà della sola operazione di addizione, o la possibilità, per lo meno in linea di principio, di automatizzare la verifica della correttezza di tutte dimostrazioni matematiche. È infatti possibile specificare un algoritmo (e quindi, come vedremo, costruire un calcolatore) tale che, dato in input un enunciato e una sua presunta dimostrazione, esso certifichi che quest’ultima sia corretta o, in caso contrario, indichi il passaggio sbagliato che ne inficia la correttezza.

Tuttavia i risultati di Kurt Gödel, Alonzo Church e Alan Turing, ottenuti negli anni Trenta, hanno mostrato l’irrealizzabilità in linea di principio del programma di Hilbert. Alla base di quei risultati vi è la formalizzazione del concetto stesso di algoritmo, basata sulla caratterizzazione precisa della nozione informale di funzione calcolabile. Una funzione f è una regola che associa a un dato x un altro valore, denotato come f(x). Per esempio la funzione f(x)=2x associa a ogni numero il suo doppio, la funzione f(x)=x2 il suo quadrato e così via. Non è necessario limitarsi ai soli numeri, si possono infatti considerare funzioni tra le più varie che operano su oggetti anche non numerici.

In generale è possibile definire funzioni per le quali non è chiaro a priori se possano essere calcolate: uno dei risultati principali ottenuti indipendentemente da Turing, Church ed Émile Post è infatti la dimostrazione dell’esistenza di funzioni definibili ma appunto non calcolabili. In particolare, il lavoro di Church e Turing mostrava come la funzione che cercava Hilbert, capace di associare a ogni enunciato matematico il valore vero o falso a seconda del caso, rientri tra queste.

Le ricerche di Gödel, Church e Turing, insieme a quelle di altri studiosi, vertevano dunque su una formalizzazione del concetto intuitivo di algoritmo. Mentre Church e collaboratori costruivano il lambda-calcolo e Gödel definiva le funzioni ricorsive, Turing formulò la formalizzazione più riuscita in quanto catturava in modo estremamente semplice e intuitivo i requisiti essenziali di un processo di calcolo. Nel suo celebre articolo On computable numbers, with an application to the Entscheidungsproblem del 1936, egli mise a punto un dispositivo ideale oggi noto come macchina di Turing. Nelle sue intenzioni essa non era che la formalizzazione di un processo di calcolo svolto da un essere umano (proprio a quest’ultimo si riferiva la parola computer, utilizzata nell’articolo originale di Turing), ma in sostanza si trattava di una versione astratta un po’ rudimentale di un moderno calcolatore. Più precisamente, una singola macchina di Turing è un calcolatore che ha a disposizione una memoria illimitata e sul quale gira uno specifico programma. Definendo calcolabile una funzione se esiste una macchina di Turing in grado di calcolarla, Turing mostrò che la funzione voluta da Hilbert non ne ammette alcuna, ovvero che è impossibile costruire un computer in grado di determinare la verità o la falsità di ogni enunciato della matematica.

La macchina astratta concepita da Turing è talmente semplice da prestarsi naturalmente a una realizzazione concreta. Le vicende storiche e culturali che hanno portato alla costruzione dei primi calcolatori sono molto complesse, ma è indubbio che il contributo dato dalle ricerche svolte nell’ambito dei fondamenti della matematica sia stato essenziale.

Oltre che alla realizzazione pratica dei primi calcolatori, le ricerche sui fondamenti della teoria degli algoritmi qui delineate hanno posto le basi per altri importanti sviluppi dell’informatica moderna. Per esempio, il lambda-calcolo è il prototipo di vari linguaggi di programmazione funzionale come il LISP e l’ML, mentre la macchina di Turing è una delle astrazioni fondamentali alla base della teoria della complessità computazionale.

Il lavoro di Turing mostra una precisa corrispondenza matematica tra il concetto di algoritmo e quello di programma per computer, al punto che essi possono considerarsi equivalenti. Questa visione trova ulteriore conferma nel fatto che gli altri formalismi introdotti per catturare la nozione di algoritmo, come appunto il lambda-calcolo e le funzioni ricorsive, definiscono esattamente lo stesso insieme di funzioni: se una funzione è calcolabile con una macchina di Turing lo è anche attraverso questi altri formalismi e viceversa. Questa coincidenza ha portato alla formulazione della tesi di Church, un’ipotesi di natura filosofica secondo la quale ogni funzione calcolabile (in senso non formalizzato) lo è attraverso una macchina di Turing; ciò è equivalente ad affermare che l’insieme delle funzioni calcolabili coincide con quelle che lo sono tramite un calcolatore.Algoritmo = Programma?

Sebbene i concetti di algoritmo e di programma siano in buona misura coincidenti, nell’ambito dell’informatica, da un punto di vista tecnico, è bene tenerli separati. Si consideri per esempio il seguente semplice (e assai inefficiente) algoritmo per determinare se un dato numero intero positivo n dato in input è primo: controllare, per ogni numero i compreso tra 2 e n−1, se i divide n. Se un tale divisore i esiste allora n non è primo, altrimenti lo è.

Questo algoritmo può essere specificato in maggior dettaglio in questo modo:

Input: un numero positivo n.

Output: Si! se n è primo e No! altrimenti:

1) Si assegni a i il valore 2.

2) Se i divide n ed n≠2 allora No!

3) Si incrementi i di 1.

4) Se in si torni al passo 2, altrimenti Si!

Di seguito vediamo una cosiddetta implementazione (realizzazione) dell’algoritmo nel linguaggio di programmazione C:

void isPrime(int n) {

     int i;

     for (i = 2 ; i ⟨= n − 1 ; i++)

              if ( n % i == 0 ) {

                           printf(“No!”);

                           return;

              }

      printf(“Si!”);

}

Quella che segue è un’implementazione dello stesso algoritmo nel linguaggio di programmazione ML (il programma restituisce vero o falso anziché Si! e No!):

let isPrime n =

     let rec check n k =

               if (k >= n) then (n > 1)

               else if (n mod k == 0) then false

               else check n (succ k)

     in check n 2;;

Un algoritmo è insomma un processo di calcolo specificato a un livello di dettaglio tale che, per un essere umano, tutti i passi del calcolo sono privi di ambiguità. Quando si passa alla programmazione, l’algoritmo deve essere specificato a un livello di dettaglio ulteriore (o, come si dice in gergo, implementato) per poter essere eseguito da una macchina. Così come esistono interpretazioni diverse di una stessa partitura, implementazioni diverse di uno stesso algoritmo possono portare a programmi tra loro diversi, scritti in linguaggi di programmazione diversi.Algoritmi efficienti

Le indagini sui fondamenti della matematica ponevano l’accento su ciò che è calcolabile in linea di principio, senza limiti di spazio e di tempo e quindi, paradossalmente, in questo contesto l’indagine si concentrava su quegli insiemi di numeri e su quelle funzioni che non sono calcolabili. L’avvento dei calcolatori moderni e il conseguente sviluppo dell’informatica contemporanea hanno invece spostato l’attenzione su quelle funzioni che sono calcolabili in modo efficiente.

È noto infatti che esistono moltissime funzioni calcolabili in linea di principio ma che necessitano di un tempo di calcolo talmente elevato da essere, di fatto, non calcolabili anche per input di dimensioni estremamente modeste.

Per un dato problema computazionale di interesse, la moderna teoria degli algoritmi procede quindi in parallelo su due fronti. Da un lato si cerca di mettere a punto algoritmi, e quindi in ultima analisi programmi, sempre più efficienti per il problema computazionale studiato. Dall’altro si cerca di determinare i cosidetti lower bounds, limiti inferiori oltre i quali è impossibile andare in termini di efficienza.

La moderna teoria degli algoritmi è un campo molto vasto della ricerca contemporanea. Dato che lo scopo ultimo dell’informatica è quello di realizzare praticamente e rendere fruibili gli algoritmi che vengono proposti per la risoluzione di vari problemi, non è sorprendente che essa rappresenti una delle strutture portanti della disciplina.

Le ramificazioni dell’informatica, e con essa della teoria degli algoritmi, si estendono profonde in molte altre discipline come la fisica, la matematica, l’economia, la biologia, la farmaceutica, la medicina e altre ancora.

Ogni disciplina scientifica ha ormai una sua dimensione computazionale, dove la progettazione di algoritmi entra in modo significativo. Per citare un solo esempio tra i più rappresentativi, il sequenziamento del genoma umano è potuto avvenire soltanto grazie all’uso massiccio di mezzi di calcolo per l’esecuzione dei sofisticati algoritmi progettati allo scopo.

Oggi la teoria degli algoritmi si sviluppa in varie direzioni, tra le quali in particolare lo sviluppo di algoritmi efficienti, indissolubilmente legato alla progettazione di appropriate strutture per organizzare i dati che intervengono nel calcolo. Tra le ramificazioni interne più interessanti della disciplina vanno menzionati lo studio di algoritmi per le macchine parallele, gli algoritmi distribuiti per le reti di calcolatori come internet e le telecomunicazioni e infine gli algoritmi probabilistici, che utilizzano nel corso del calcolo una moneta elettronica. Nonostante l’apparente indeterminatezza proveniente dal ricorrere al caso, tali algoritmi hanno comportamenti rigorosamente predicibili e prestazioni spesso assai migliori di quelle ottenibili con procedimenti di calcolo puramente deterministici. Questo tipo di algoritmi trova utilizzo in molti ambiti applicativi importanti, come per esempio le reti di calcolatori e il test di primalità, che è alla base della crittografia moderna.bibliografia

Harel, Feldman 2004: The spirit of computing, 3. ed., edited by David Harel, Yshdai Feldman, New York, Addison-Wesley, 2004.

Hodges 1983: Hodges, Andrew, Alan Turing: the enigma, New York, Simon and Schuster, 1983 (trad. it.: Storia di un enigma: vita di Alan Turing, Torino, Bollati Boringhieri, 1991).

Luccio, Pagli 1999: Luccio, Fabrizio - Pagli, Linda, Algoritmi, divinità e gente comune, Pisa, ETS, 1999.

Nagel, Newman 1958: Nagel, Ernest - Newman, James R., Gödel’s proof, New York-London, New York University Press, 1958 (trad. it.: La prova di Gödel, 2. ed., Torino, Bollati Boringhieri, 1992).

Singh 1999: Singh, Simon, Codici e segreti, Milano, Rizzoli, 1999 (ed. orig.: The code book, New York, Doubleday, 1999).

Invia articolo Chiudi