Già il titolo fa prevedere un percorso lungo e avventuroso nella storia della scienza e dell’umanità. Ogni giorno lavoriamo, o abbiamo a che fare con pc, smartphone o similari senza avere per questo, la percezione con che cosa abbiamo a che fare o quale sia stato il lungo percorso storico che ci ha portato a questo.
Una domanda affascinante è: “Come fa la sonda pathfinder a mandarci immagini dal pianeta Marte così nitide e precise?”
Un’altra domanda può essere questa: “cosa c’entra il grande filosofo Liebniz con la trasmissione di queste foto?” Leibniz immagina che i suoi studi avrebbero portato all’invio di foto da marte? Potremmo continuare così per molto tempo, facendo insorgere la necessità di trovare un “fil rouge” che ci possa accompagnare in quest’avventura matematico-storica.
Individuato questo “fil rouge” bisogna porre particolare attenzione ai nodi concettuali, cercando di dirimerli al meglio per focalizzare poi i punti salienti di questa avventura. L’uomo ha sempre avuto la necessità di fare calcoli, fin dai tempi più remoti. Ogni corso di matematica, dalle elementari alle superiori, inizia con la necessità di contare (computare) e misurare, un esempio per tutti gli antichi egizi.
Con il passare del tempo l’umanità si è trovata alle prese con diversi sistemi numerici, tutti con pregi e difetti o complessità intrinseche che innalzavano a rango di “sacerdoti” chi possedeva queste nozioni.
La prima grande figura storica, che ci introduce nell’era informatica (ovviamente senza saperlo) è Leonardo Pisano detto il Fibonacci (Pisa, settembre 1175 circa – Pisa, 1235 circa).
Nel 1202 pubblicò, e nel1228 riscrisse (lo fece pubblicare solo dopo la sua morte però, lasciandolo nel suo testamento) il Liber abbaci, opera in quindici capitoli con la quale introdusse per la prima volta in Europa (nel capitolo I) le nove cifre, da lui definite “indiane”, e il segno 0 (gli altri popoli non utilizzavano questo simbolo perché non ne sentivano il bisogno) che in latino è chiamato zephirus, adattamento dell’arabo sifr, ripreso a sua volta dal termine sanscrito śūnya, che significa “vuoto”. Zephirus in veneziano divenne zevero ed infine comparve l’italiano “zero”. Per mostrare ad oculum l’utilità del nuovo sistema egli pose sotto gli occhi del lettore una tabella comparativa di numeri scritti nei due sistemi, romano e indiano. Fibonacci espose così per la prima volta in Europa la numerazione posizionale indiana(adottata poi dagli arabi).
È stato un grandissimo matematico, a lui si deve la serie di Fibonacci e altre importanti studi nel campo della matematica tra i quali il concetto di algoritmo.
ALGORITMO
Un algoritmo è un procedimento che risolve un determinato problema attraverso un numero finito di passi elementari. Il termine deriva dalla trascrizione latina del nome del matematico persiano al-Khwarizmi che è considerato uno dei primi autori ad aver fatto riferimento a questo concetto. L’algoritmo è un concetto fondamentale dell’informatica, anzitutto perché è alla base della nozione teorica di calcolabilità: un problema è calcolabile quando è risolvibile mediante un algoritmo. Inoltre, l’algoritmo è un concetto cardine anche della fase di programmazione dello sviluppo di un software: preso un problema da automatizzare, la programmazione costituisce essenzialmente la traduzione o codifica di un algoritmo per tale problema in programma, scritto in un certo linguaggio, che può essere quindi effettivamente eseguito da un calcolatore rappresentandone la logica di elaborazione.
Definizione
Nel secolo scorso, il concetto di algoritmo venne formalizzato per risolvere il problema matematico della “decisione” (Entscheidungsproblem), posto da David Hilbert nel 1928, e altre successive formalizzazioni giunsero con lo sviluppo dei concetti di “calcolabilità effettiva” e di “metodo effettivo”. Le formalizzazioni matematiche più famose sono le funzioni ricorsive di Gödel–Herbrand–Kleene del 1930, 1934 e 1935; il Calcolo Lambda diAlonzo Church e la Formulation 1 di Emil Post del 1936; e, infine, la Macchina di Alan Turing del 1936–37 e 1939. Nonostante ciò, una definizione del concetto di algoritmo che sia formale e non tecnica manca tuttora e si è pertanto costretti ad accontentarsi dell’idea intuitiva di algoritmo come:
“una sequenza ordinata e finita di passi (operazioni o istruzioni) elementari che conduce a un ben determinato risultato in un tempo finito“.
Modelli formali
La definizione di algoritmo appena riportata è piuttosto informale, mentre era necessario disporre di una definizione più rigorosa per trattare il concetto di algoritmo con strumenti matematici. Al tal fine sono stati definiti alcuni modelli matematici di algoritmo, fra i quali uno dei più celebri è la macchina di Turing. Essa rappresenta una sorta di computer ideale corredato di un programma da eseguire, ma, rispetto a un computer ideale, la macchina di Turing ha un funzionamento estremamente più semplice cosicché il suo funzionamento possa essere facilmente descritto in termini matematici, facendo uso di concetti come insieme, relazione e funzione.
La macchina di Von Neumann, che è il modello di architettura sottostante a tutti i computer attuali, è equivalente, in termini di potere di calcolo, alla macchina di Turing. In altre parole, è stato dimostrato che un certo problema può essere risolto da un computer (opportunamente programmato) se e solo se esso può essere risolto anche da una macchina di Turing. Oltre alla macchina di Turing, proposta da Alan Turing nel 1936, nello stesso periodo altri matematici hanno elaborato diverse rappresentazioni formali del concetto di algoritmo, fra i quali ricordiamo, per esempio, il lambda calcolo. Dopo alcuni anni, emerse che tutti questi modelli erano equivalenti: i problemi che una macchina di Turing poteva risolvere erano gli stessi che poteva risolvere una macchina di von Neumann.
Da questi risultati, tra l’altro, scaturì la tesi di Church-Turing, che afferma che qualsiasi algoritmo sia modellabile con una macchina di Turing. In altri termini, questa tesi sostiene che è sostanzialmente impossibile cercare di immaginare un modello di algoritmo più potente e, di conseguenza, che nessuna macchina potrà mai risolvere problemi che una macchina di Turing non possa risolvere in linea di principio. Non si tratta di un teorema dimostrato matematicamente, poiché la tesi stabilisce l’eguaglianza di due concetti, l’algoritmo e la macchina di Turing, ma il primo non possiede una definizione formale. La tesi è oggi generalmente condivisa, sebbene i progressi nelle ricerche nel settore dell’ipercomputazione sembrino talvolta metterla in discussione.
Proprietà fondamentali degli algoritmi
Dalla precedente definizione di algoritmo si evincono alcune proprietà necessarie, senza le quali un algoritmo non può essere definito tale:
- i passi costituenti devono essere “elementari”, ovvero non ulteriormente scomponibili (atomicità);
- i passi costituenti devono essere interpretabili in modo diretto e univoco dall’esecutore, sia esso umano o artificiale (non ambiguità);
- l’algoritmo deve essere composto da un numero finito di passi e richiedere una quantità finita di dati in ingresso (finitezza)
- l’esecuzione deve avere termine dopo un tempo finito (terminazione);
- l’esecuzione deve portare a un risultato univoco (effettività).
Così, ad esempio, “rompere le uova” può essere considerato legittimamente un passo elementare di un “algoritmo per la cucina” (ricetta), ma non potrebbe esserlo anche “aggiungere sale quanto basta” dato che l’espressione “quanto basta” è ambigua, e non indica con precisione quali passaggi servano per determinare la quantità necessaria. Un passo come “preparare un pentolino di crema pasticcera” non può considerarsi legittimo perché ulteriormente scomponibile in sotto-operazioni (accendere il fuoco, regolare la fiamma, mettere il pentolino sul fornello, ecc.) e anche perché contenente ambiguità (non specifica quanto grande deve essere il pentolino, quanto deve essere riempito di crema e così via). Al contrario, “continuare a mescolare a fuoco vivo fino a quando il composto non assume colore bruno” è un’istruzione accettabile di tipo iterativo, che comporta un numero finito di operazioni (le rimestate) sebbene tale numero non sia conoscibile a priori, perché dipendente da ciò che è chiamato input (il grado di umidità della farina nel composto, il vigore della fiamma, ecc.). All’istruzione non elementare di preparazione della crema potrebbe, però, essere associato a un opportuno rimando a un’altra sezione del ricettario, che fornisca un sotto-algoritmo apposito per questa specifica operazione. Questo suggerisce che, per comodità d’implementazione, gli algoritmi possano essere modulari, ovvero orientati a risolvere specifici sotto-problemi, e gerarchicamente organizzati. Inoltre, una ricetta che preveda la cottura a microonde non può essere preparata da un esecutore sprovvisto dell’apposito elettrodomestico; questo rimanda al problema della realizzabilità degli algoritmi, ovvero della loro compatibilità con le risorse materiali e temporali a disposizione. Infine, possono darsi più algoritmi validi per risolvere uno stesso problema, ma ognuno con un diverso grado di efficienza.
L’algoritmo viene generalmente descritto come “procedimento di risoluzione di un problema”. In questo contesto, i “problemi” che si considerano sono quasi sempre caratterizzati da dati di ingresso (input) variabili, su cui l’algoritmo stesso opererà per giungere fino alla soluzione. Per esempio, il calcolo del massimo comune divisore fra due numeri è un esempio di “problema”, e i suoi dati di ingresso, variabili di volta in volta, sono i due numeri in questione. A un non matematico questa potrebbe apparire come una “famiglia di problemi” (il problema di calcolare il massimo comune divisore fra 10 e 15, il problema di calcolarlo fra 40 e 60, fra 35 e 95, e così via). Il matematico e l’informatico identificano con la parola “problema” l’intera famiglia e con “istanza” o “x” ciascuno dei quesiti specifici ottenuti fissando due particolari valori. Data questa premessa, un algoritmo risolve un problema se per qualunque istanza del problema esso produce in un tempo finito la soluzione desiderata, ovvero un certo risultato o dato in uscita (output) a partire da dei dati in ingresso (input).
Se questa idea aveva già una certa importanza per il calcolo matematico, l’avvento dell’informatica l’ha arricchita di una nuova importanza, ed è infatti con l’informatica che il termine “algoritmo” ha iniziato a diffondersi. Difatti, se per ottenere un certo risultato (risolvere un certo problema) esiste un procedimento infallibile, che può essere descritto in modo non ambiguo fino ai dettagli, e conduce sempre all’obiettivo desiderato in un tempo finito, allora esistono le condizioni per affidare questo compito a un computer, semplicemente introducendo l’algoritmo in questione in un programma scritto in un opportuno linguaggio comprensibile alla macchina.
Inizialmente un algoritmo può essere descritto attraverso l’uso di un diagramma di flusso o ricorrendo a uno pseudocodice. Successivamente, nella fase di programmazione l’algoritmo così scritto verrà tradotto in linguaggio di programmazione a opera di un programmatore sotto forma di codice sorgente dando vita al programma che sarà eseguito dal calcolatore, eventualmente dopo un’ulteriore traduzione in linguaggio macchina. Particolare rilevanza teorica in tale ambito assume il Teorema di Böhm-Jacopini che afferma che qualunque algoritmo può essere implementato utilizzando tre sole strutture, la sequenza, la selezione e il ciclo (iterazione), da applicare ricorsivamente alla composizione di istruzioni elementari. Nella pratica corrente il programmatore professionista nel suo lavoro svolge automaticamente questo processo di traduzione scrivendo direttamente il codice sorgente necessario nelle suddette modalità avendo già trovato la soluzione al problema dato.
cosa ne pensi?