Che cos'è un algoritmo?

La parola “algoritmo” è comunemente usata per riferirsi al funzionamento opaco dei motori di ricerca e dei social network.

Ma di cosa stiamo parlando esattamente? Che cos’è un algoritmo? Questa nozione ha attraversato la storia, da Euclide agli algoritmi del GAFAM. Gli algoritmi possono risolvere qualsiasi problema? Che garanzie abbiamo sul loro comportamento? Quali sono i loro impatti sociali?

Nel IX^° secolo in Persia

L’etimo fa risalire la storia degli algoritmi allo studioso persiano Muhammad Ibn Mūsā al-Khuwārizmī, che intorno all’anno 800 pubblicò i primi libri di testo per la risoluzione di equazioni. I suoi metodi, all’origine dell’algebra, riguardano tipicamente problemi pratici di calcolo: questioni di ereditarietà o di misurazione.

Le sue opere sono state tradotte in latino nel XII^° secolo e reso popolare da celebrità come il matematico italiano Leonardo Fibonacci. È il suo nome, latinizzato in “algorithmus” che è all’origine del termine “algoritmo“. Quasi un millennio prima di lui, Euclide aveva descritto negli elementi un metodo per calcolare il massimo comun divisore di due numeri.

Nel XX^° secolo, la nozione di rami algoritmo costruite della matematica

Ma dobbiamo aspettare fino all’inizio del XX^° secolo, prima che la nozione di algoritmo diventi formalizzata. Nel suo famoso discorso al Secondo Congresso Internazionale dei Matematici di Parigi nel 1900, il matematico tedesco David Hilbert propone 23 problemi aperti, 23 sfide per la comunità matematica, le cui affermazioni avranno una notevole influenza sullo sviluppo della matematica nei decenni successivi.

Il decimo problema riguarda l’esistenza di un “metodo mediante il quale, mediante un numero finito di operazioni, si potrà determinare l’esistenza di una soluzione in numeri interi di un’equazione polinomiale a coefficienti interi” (le equazioni “Diofantee” ). È infatti l’esistenza di un algoritmo che è coinvolto.

È attraverso il lavoro del fondatore di Alan Turing e Alonzo Church, tra gli altri, che gli algoritmi diventano oggetti matematici a sé stanti. Nel suo articolo del 1936, Alan Turing dà la sua definizione di “calcolabilità” di una funzione: deve esistere una macchina che dia il suo valore in un numero finito di passaggi elementari, guidati da un sistema di transizioni e dal contenuto di un nastro, che svolge il ruolo della memoria. È la famosa “macchina di Turing“.

Alan Turing comprende il legame tra la calcolabilità di una funzione e la dimostrabilità di un’asserzione matematica in un sistema di assiomi. L’informatica teorica diventa una branca della matematica.

Un dispositivo che materializza la macchina fittizia di Turing, la definizione matematica di un algoritmo. Wikimedia

Il potere degli algoritmi è circoscritto, e alcuni problemi si dimostrano indecidibili: non esiste alcun algoritmo per risolverli. Nel 1970 Julia Robinson e Youri Matiiassevitch risolsero finalmente il decimo problema di Hilbert: la risoluzione delle equazioni diofantee è un problema indecidibile!

Negli anni ’70 stabiliamo gerarchie di problemi secondo il tempo e lo spazio che un algoritmo richiede per risolverli: nota come la teoria della complessità.

Come si presenta un algoritmo?

Gli algoritmi sono spesso paragonati alle ricette di cucina: una serie di istruzioni precise che consentono di ottenere un risultato in un numero finito di passaggi.

Questa immagine è corretta, ma nasconde indubbiamente un aspetto fondamentale, il fatto che un algoritmo riceve dati da elaborare (numeri, testo, relazioni), e alcune istruzioni sono condizionate: i passaggi seguiti dipendono da questi dati, e le esecuzioni possono seguire un corso difficile da prevedere. Queste istruzioni possono essere date in varie forme ben definite (diagramma di flusso, linguaggio di descrizione), o anche, con la dovuta cura, in linguaggio naturale.

Abbiamo tutti imparato l’algoritmo per moltiplicare due numeri alle scuole elementari, senza l’ausilio di alcun formalismo avanzato. Gli algoritmi sono in linea di principio destinati ad essere implementati sotto forma di programma, in un linguaggio di programmazione comprensibile da un computer. Ma l’algoritmo esiste indipendentemente da questa traduzione.

Per comprendere la portata degli algoritmi nelle nostre vite moderne, dobbiamo distinguere le loro famiglie

Per comprendere meglio i problemi e le sfide attuali relativi agli algoritmi, è importante identificare il loro ambito e le proprietà che siamo in grado di garantire sui loro risultati e sul loro comportamento. Una tipologia di algoritmi è essenziale per questa comprensione.

Possiamo innanzitutto distinguere una famiglia di algoritmi così onnipresenti nella nostra vita quotidiana da essere diventati quasi invisibili. Si tratta di algoritmi esatti per compiti perfettamente definiti, il cui risultato è facilmente verificabile:

moltiplicare due numeri,
ordinare un elenco di nomi in ordine alfabetico,
archiviare e recuperare informazioni in modo efficiente,
convertire un segnale analogico in un segnale digitale,
interpretare un programma.

Questi sono gli algoritmi fondamentali studiati fin dagli albori dell’informatica.

Tuttavia, non sono da meno oggetto di ricerche attuali, tanti misteri rimangono intorno alla complessità di alcune operazioni fondamentali. L’esatta complessità del problema della moltiplicazione di due interi, ad esempio, è teoricamente ancora aperta: attualmente non siamo in grado di dimostrare che la moltiplicazione richieda necessariamente più tempo dell’addizione! L’algoritmo di moltiplicazione più noto è stato pubblicato solo di recente.

Gli algoritmi di ottimizzazione sono una seconda importante famiglia. Risolvono problemi in cui si cerca di identificare dei parametri o una configurazione che massimizzi o minimizzi un valore, chiamata “funzione obiettivo“. Le applicazioni concrete consistono, ad esempio, nella ricerca del percorso più breve tra due punti, nella schedulazione delle fasi di un progetto per ridurne al minimo la durata, nella scelta delle posizioni delle antenne per coprire una determinata area a un costo inferiore, o quella dei parametri dei router di una rete per ridurre al minimo la latenza.

Gli obiettivi degli algoritmi di queste due famiglie sono quantificabili e i loro risultati sono garantiti matematicamente. I metodi formali consentono di verificare rigorosamente le proprietà di un algoritmo. Gli algoritmi di ottimizzazione lineare sono compresi.

Una terza famiglia di algoritmi più specializzata è quella degli algoritmi crittografici, destinati a garantire la sicurezza delle comunicazioni e delle transazioni. Questa sicurezza è spesso basata su presupposti legati alla complessità dei problemi algoritmici. Il famoso algoritmo RSA (dal nome dei suoi inventori: Ronald Rivest, Adi Shamir e Leonard Adleman), ad esempio, basa la sicurezza delle transazioni di commercio elettronico sul presupposto che non esiste un algoritmo efficiente per scomporre un numero nei suoi fattori primi.

Alcune procedure risultanti dalla ricerca sull’intelligenza artificiale, invece, non si sottopongono facilmente ad analisi rigorose.

Gli algoritmi stanno cambiando in natura con l’intelligenza artificiale

Tra questi, gli algoritmi di classificazione cercano di collocare i dati ricevuti come input in una categoria corrispondente a una realtà esterna. Un algoritmo di riconoscimento animale, ad esempio, riceverà in input un’immagine sotto forma di una matrice di pixel, e dovrà determinare se questa immagine rappresenta un gatto o un delfino. Questo compito non è formalmente ben definito: si può probabilmente trovare un quadro ambiguo per il quale le risposte date dagli umani potrebbero essere diverse. La correttezza di questi algoritmi dipende da una realtà esterna, che non è formalizzata, e la loro accuratezza, o precisione, può essere stabilita solo sperimentalmente.

Allo stesso modo, gli algoritmi di previsione cercano di anticipare l’evoluzione di determinate quantità misurate nel mondo fisico o dei comportamenti di una popolazione. Sono utilizzati ad esempio in finanza per prevedere l’evoluzione dei mercati, o nel marketing, per presentare ai visitatori di un sito Web i prodotti o le pubblicità che più probabilmente attireranno la loro attenzione. La rilevanza dei risultati è qui ancora una volta convalidata empiricamente, e non matematicamente. Tanto che nel 2006, la società Netflix ha lanciato un concorso per migliorare le prestazioni del suo algoritmo di previsione della valutazione dei film, con un premio di un milione di dollari.

Lo sviluppo di questi algoritmi si basa molto su modelli probabilistici, ma anche su strutture difficili da analizzare in modo rigoroso. È il caso in particolare degli algoritmi delle reti neurali artificiali utilizzati in quello che oggi viene chiamato “deep learning“, con riferimento al numero di strati utilizzati in queste reti. Queste reti codificano implicitamente la memoria dei dati forniti durante una fase di apprendimento e consentono di classificare nuovi dati in ingresso.

Cosa possiamo pretendere dagli algoritmi?

L’onnipresenza degli algoritmi è legittimamente oggetto di paure. Quali garanzie possiamo richiedere?

Un primo tipo di garanzia riguarda l’efficienza. Quanto tempo dobbiamo aspettare per una risposta? Quanta memoria dovremmo avere? Queste domande sono ben studiate e hanno formulazioni e risposte rigorose ma parziali. Le lacune nella nostra comprensione della complessità algoritmica, in particolare, lasciano aperta la possibilità di attacchi senza precedenti che mettono a rischio la crittografia basata sull’algoritmo RSA.

La tradizionale questione della performance è strettamente legata alle questioni del consumo di risorse, che hanno impatti ecologici. Possiamo dare a questa domanda un quadro più ampio e interrogarci sulle risorse consumate dal software e dai server. Nel campo degli algoritmi crittografici, alcuni meccanismi alla base del funzionamento delle criptovalute, in particolare il principio della “prova di lavoro”, hanno un impatto energetico drammatico.

Quando gli obiettivi sono facilmente verificabili, come nel caso di un algoritmo di ordinamento, o quantificati esplicitamente, come nel caso di un algoritmo di ottimizzazione, si ha una misura oggettiva della qualità della soluzione. Nel caso degli algoritmi di ottimizzazione, invece, la scelta della funzione obiettivo, la quantità da ottimizzare, può avere un notevole impatto umano.

Domande etiche

Le questioni di equità e trasparenza degli algoritmi di classificazione e previsione stanno diventando pressanti. In un libro che è diventato un classico, Cathy O’Neil mette in guardia sugli eccessi dei sistemi decisionali nei campi della giustizia, dell’azione di polizia, delle assicurazioni, della valutazione degli insegnanti, tra gli altri.

L’algoritmo di Gale-Shapley, utilizzato dalla piattaforma Parcoursup, soddisfa le proprietà di ottimalità, ma assicura anche che non sia possibile un comportamento strategico da parte dei richiedenti.

I metodi di apprendimento supervisionato per la classificazione consistono convenzionalmente in una raccolta di esempi, di coppie “input-output“, che si spera possano essere generalizzati, in modo che un nuovo dato di input possa essere associato a una risposta input-output che abbia senso. Fornendo solo esempi noti durante queste fasi di apprendimento, inculchiamo nel sistema tutti i bias presenti di fatto negli esempi disponibili, e insegniamo così alla macchina a riprodurli. Questo è il tema del documentario Coded Bias, che racconta l’esperienza di uno studente del MIT con gli algoritmi di riconoscimento facciale.

La natura a volte inesplicabile dei risultati finisce per spiegare il recente spostamento semantico della parola algoritmo: da semplice metodo di calcolo, l’algoritmo viene percepito come una scatola nera onnipotente, il cui funzionamento interno è inaccessibile, e le cui risposte finiscono per sostituire alla realtà. Questa percezione può essere spiegata in particolare dalla rinascita dei metodi delle reti neurali, la cui complessità sfida ogni analisi formale. I successi sperimentali nei compiti affidati a reti profonde sono innegabili e affascinanti. Ma alcuni esperimenti mostrano la loro fragilità: i ricercatori hanno dimostrato che modificando impercettibilmente alcuni pixel ben scelti di un’immagine, possiamo cambiare completamente la risposta fornita. In assenza di una risposta esplicita (“è un gatto perché ha le orecchie a punta e i baffi”), sorgono domande di fiducia e responsabilità.

La comunità di ricerca in intelligenza artificiale e machine learning ha affrontato questioni di equità e spiegabilità: lo sviluppo di metodi di apprendimento che includano criteri di equità (equità nell’IA) è in pieno svolgimento, mentre il campo dell’intelligenza artificiale “spiegabile” (IA spiegabile) si occupa della responsabilità per i risultati e della fiducia.

Al-Khuwārizmī sarebbe stato sicuramente sorpreso dalla posterità del suo cognome!