Programmazione, algoritmi di

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.

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).