Articles

Come siamo arrivati qui? La storia degli algoritmi.

Fino a poco tempo fa, gli algoritmi erano un dominio degli informatici. Ma ora, sono entrati nelle nostre vite e stanno diventando pervasivi. Algoritmo non è più una parola straniera. Il trading algoritmico, i pregiudizi algoritmici, l’algoritmo di Facebook, persino la guerra algoritmica – tutti questi termini sono diventati parte del nostro vocabolario negli ultimi anni. Alcune persone arrivano a sostenere che viviamo in una nuova era: l’era dell’algoritmo. Ma gli algoritmi non sono così nuovi. Li abbiamo usati, consapevolmente o meno, per centinaia e migliaia di anni. Gli algoritmi sono semplicemente descrizioni specifiche di azioni passo dopo passo che devono accadere per raggiungere un particolare risultato. Sono uno degli strumenti più comuni di condivisione della conoscenza.

Praticamente ogni processo di insegnare a qualcuno come fare qualcosa usa algoritmi.

Alcuni aspetti degli algoritmi sono cambiati negli ultimi decenni. In particolare, l’introduzione dei computer significa che molti algoritmi oggi sono drammaticamente più complessi di quanto avremmo mai potuto immaginare in passato. Come si sono evoluti gli algoritmi per essere così sofisticati oggi rispetto al passato? Diamo un breve sguardo alla loro storia.

Algoritmi che guidano le azioni umane

Un francobollo emesso il 6 settembre 1983 in Unione Sovietica, per commemorare il 1200° compleanno (approssimativo) di al-Khwārizmī; via Wikimedia Commons

Il termine algoritmo deriva dal nome di Muhammad ibn Mūsā al’Khwārizmī, un matematico persiano del IX secolo. Il suo nome latinizzato, Algoritmi, significava “il sistema di numeri decimali” e fu usato in questo senso per secoli. La nozione moderna di algoritmo è emersa in inglese nel diciannovesimo secolo, ed è diventata più comunemente usata a partire dagli anni ’50, innescata dall’emergere dei primi computer disponibili in commercio.

Molto prima che gli algoritmi ottenessero il loro nome moderno, però, erano comunemente creati e usati.

I primi algoritmi furono catturati su carta nell’Antica Grecia. Studiosi come Nicomaco di Gerasa o Euclide stavano creando i mattoni della matematica moderna. Per facilitare la comprensione e l’applicabilità delle loro idee, espressero molte di esse come azioni passo dopo passo.

Nicomaco di Gerasa introdusse il Setaccio di Eratostene. Il setaccio è usato ancora oggi dagli studenti che imparano a scrivere un codice informatico efficiente. Ha aiutato a semplificare il processo di identificazione dei numeri primi. I numeri primi sono numeri naturali, maggiori di uno, che non possono essere formati dalla moltiplicazione di due numeri naturali più piccoli. Per esempio, quattro non è un numero primo perché può essere formato moltiplicando due per due. Cinque, al contrario, è un numero primo, perché nessun numero naturale più piccolo di cinque può essere moltiplicato per formare cinque. Mentre non è troppo difficile identificare i primi numeri primi (per esempio 2, 3, 5, 7, 11, 13, 17, 19, 23 e 29), trovare grandi numeri primi richiede molto tempo. E i grandi numeri primi sono essenziali nella crittografia. Il setaccio di Eratostene fornisce istruzioni passo dopo passo per rimuovere rapidamente tutti i numeri non primi da un insieme definito di numeri (per esempio tra 1 e 10.000) fino a quando rimangono solo numeri primi. Oggi, ci sono numerosi algoritmi disponibili, che semplificano il compito di identificare tali numeri. Il setaccio di Eratostene ha dato inizio a tutta una famiglia di algoritmi che hanno lo stesso obiettivo e stanno diventando migliori (più veloci, o che richiedono meno passaggi) nell’individuare i numeri primi.

Sieve di Eratostene di SKopp su Wikipedia tedesca

Euclide, l’altro studioso menzionato sopra, molto più noto di Nicomaco di questi tempi, introdusse un algoritmo per identificare il massimo comune denominatore di due numeri. Di nuovo, un compito non sempre facile, ma essenziale in molte situazioni. L’algoritmo di Euclide ha contribuito a rendere questo calcolo facile. Perché l’algoritmo di Euclide è utile? Immaginate di avere una stanza delle dimensioni esatte di 612 per 2006 centimetri che ha bisogno di un nuovo pavimento. L’algoritmo di Euclide vi aiuterà a trovare la dimensione delle piastrelle quadrate più grandi che coprirebbero ordinatamente il pavimento. La risposta, data dall’algoritmo, è 34 cm per 34 cm, risultante in una disposizione di 18 piastrelle per 59. Naturalmente, ogni piastrellista vi dirà che la risposta è sbagliata e che non avete idea di cosa state facendo perché l’algoritmo non considera la larghezza della malta e non lascia spazio per essa. Non temete: anche questo si può calcolare, ed espresso ordinatamente come un algoritmo.

Algoritmi che guidano le azioni delle macchine

Nel corso delle diverse centinaia di anni che seguirono, molti altri algoritmi furono creati e catturati sulla carta. Sono stati poi utilizzati da individui e seguiti passo dopo passo. Il primo algoritmo destinato ad essere eseguito su una macchina fu creato da Ada Lovelace (nata Byron) e pubblicato nel 1843.

Ada Byron, quattro anni. Presto diventerà la prima programmatrice di computer al mondo. Dall’artista: Alfred, Comte d’Orsay. Immagine digitale; Somerville College, Oxford – Somerville College, Oxford, Public Domain, https://commons.wikimedia.org/w/index.php?curid=44246375

Ada era un personaggio intrigante. Nacque nel 1815 come unica figlia legittima del poeta Lord Byron. Sviluppò un grande talento in matematica. E poiché l’amore per la poesia era chiaramente nei suoi geni, riuscì in qualche modo a sviluppare ed equilibrare sia l’amore per la scienza che per la poesia. Ada autodefinì la sua mentalità come “scienza poetica”. Essendo un’abile matematica, conobbe Charles Babbage, che è spesso chiamato “il padre dei computer”, grazie alle sue invenzioni. Entrambi svilupparono un rapporto di lavoro e di amicizia. Ada era molto interessata ad uno dei progetti di Charles – il Motore Analitico.

Un diagramma del Motore Analitico. By ArnoldReinhold – Own work, CC BY 4.0, https://commons.wikimedia.org/w/index.php?curid=69497631

Il Motore Analitico era un computer meccanico – una macchina che automatizzava i calcoli. Era il Motore Analitico per il quale scrisse il primo algoritmo. Il suo lavoro era una formula che mostrava come configurare il Motore per calcolare una particolare sequenza complessa di numeri, chiamati numeri di Bernoulli. La formula è ora ampiamente riconosciuta come il primo algoritmo informatico della storia.

Ada non si limitò solo ai puri calcoli matematici. Dato che viveva nel diciannovesimo secolo, era una vera visionaria.

Mentre molti dei suoi contemporanei vedevano i primi computer meccanici principalmente come dei “number-crunchers”, lei si chiedeva cosa ci fosse oltre l’esecuzione dei calcoli. Era curiosa del più ampio potenziale dei computer meccanici come strumenti di collaborazione. Sperava di vedere computer che avrebbero dato potere agli umani molto di più che non solo attraverso l’automazione dei calcoli.

Il diagramma di Lovelace dalla “nota G”, il primo algoritmo informatico pubblicato, di Ada Lovelace – http://www.sophiararebooks.com/pictures/3544a.jpg, Public Domain, https://commons.wikimedia.org/w/index.php?curid=37285970

Purtroppo, la costruzione del Motore Analitico non fu completata prima della morte di Ada, e così lei non fu mai in grado di vedere il suo algoritmo in azione. Purtroppo, il motore analitico non è stato costruito fino ad oggi. Un altro progetto di Charles Babbage, il Difference Engine №2, è stato costruito dal London Science Museum solo nel 1991. È stato dimostrato che è funzionale, utilizzando materiali e tecnologie disponibili a Charles Babbage. Sembra che Babbage sia stato solo sfortunato quando si è trattato di far costruire i suoi progetti. Altre implementazioni parziali del lavoro di Charles esistono altrove, ma sfortunatamente non possiamo eseguire l’algoritmo di Ada Byron su un vero motore analitico.

Il diciannovesimo secolo divenne un’era di “algoritmi incorporati nelle macchine”.

C’erano un sacco di questi, che automatizzavano ogni sorta di azioni umane. Se avevi bisogno di un disegno intricato su un pezzo di tessuto, Joseph Marie Jacquard, un tessitore e mercante francese, aveva una soluzione per te: il telaio Jacquard. Permetteva ai produttori di tessuti di produrre modelli sofisticati usando una serie di schede perforate che istruivano un telaio su come tessere. In modo simile, le prime centrali telefoniche utilizzavano sofisticati dispositivi meccanici per collegare le telefonate. Essi seguivano automaticamente le istruzioni passo dopo passo per far sì che due persone si parlassero. Queste macchine, sia i telai che le centrali telefoniche, erano all’avanguardia all’epoca, e sono ancora impressionanti fino ad oggi. È difficile non ammirare i livelli di intricatezza di alcune di queste macchine. Tuttavia, tutti questi dispositivi erano ancora puramente meccanici. Erano fatti di leve, interruttori, alberi. Facevano molto rumore. Ed erano molto lontani da ciò che oggi chiamiamo computer.

Algoritmi su computer di uso generale

Non è stato fino agli anni ’30 che abbiamo visto le prime menzioni di algoritmi in computer elettronici (non meccanici). Alan Turing fu tra i primi scienziati che catturarono formalmente come gli individui eseguivano i calcoli. L’obiettivo di Turing era quello di catturare un processo generale, piuttosto che uno specifico per un compito particolare come l’identificazione dei numeri primi o il calcolo del massimo comune divisore. Il processo generale poteva quindi essere usato per eseguire compiti specifici. Il lavoro concettuale di Turing ha portato allo sviluppo di quella che oggi è conosciuta come la Macchina di Turing. La macchina di Turing, a sua volta, ha portato all’emergere dei computer di uso generale. Il prefisso “general purpose” è essenziale qui. Contrariamente alle macchine precedenti, i nuovi computer avrebbero eseguito serie arbitrarie di istruzioni. Potevano essere usati per scopi non previsti dai loro creatori. In altre parole: Il lavoro di Turing ha portato allo sviluppo di computer su cui possiamo installare ed eseguire applicazioni.

Nessun Flappy Bird sul tuo smartphone senza il concetto di macchina di Turing.

Decenni dopo, gli algoritmi sono diventati estremamente sofisticati. Così sofisticati, infatti, che spesso ci risulta impossibile spiegare il loro funzionamento. Nel ventesimo secolo molti preferivano pensare agli algoritmi dei computer come a delle scatole nere. Non era necessario capire come funzionassero esattamente. Tutto ciò di cui ci si preoccupava erano gli input – ciò che entrava nella scatola nera – e gli output – ciò che ne usciva. Questa semplificazione era una scelta. Nel ventunesimo secolo, per alcuni algoritmi, questa non è più una scelta: gli esseri umani non possono spiegare esattamente come gli algoritmi raggiungono particolari risultati, e quindi siamo costretti a pensare a questi algoritmi come a scatole nere, o forse magiche. Un gruppo di tali algoritmi sono alcuni degli algoritmi di intelligenza artificiale. Possiamo spiegare i loro principi. Per esempio, possiamo dire che un algoritmo utilizza una rete neurale artificiale. Possiamo anche spiegare come la rete è stata creata, e come l’input ha portato ad un particolare output. Quello che non possiamo spiegare, tuttavia, è perché questo particolare risultato è stato l’output dell’algoritmo, al di là di una pura spiegazione meccanica. Eric L. Loomis, la cui durata dell’incarcerazione dipendeva da un algoritmo, ha cercato di capire perché l’algoritmo COMPAS lo ha valutato come un criminale ad alto rischio. Era semplicemente impossibile. La sofisticazione degli algoritmi è spesso schiacciante. E questo è solo l’inizio.

Viviamo in un mondo dove gli algoritmi sono ovunque – non solo sulla carta o nella nostra mente, ma controllano macchine, computer e robot.

Sono piccoli, onnipresenti e – almeno in alcuni casi – inspiegabili.

Una definizione più formale di un algoritmo è “una specifica non ambigua di come risolvere una classe di problemi” o “un insieme autonomo di operazioni da eseguire passo dopo passo”

www.oed.com/view/Entry/4959

A ottobre 2018, il più grande numero primo conosciuto è 277.232.917- 1, un numero con 23.249.425 cifre. Solo per verificare se questo singolo numero è primo ci sono voluti sei giorni di calcolo non-stop su un computer domestico contemporaneo. (https://www.mersenne.org/primes/press/M77232917.html)