Breve e universale storia degli algoritmi

Luigi Laura

• Editore: LUISS University Press
• Anno: 2021
• ISBN:
  9788861056435
• Argomento: Computer Science
• Categoria: Programming Algorithms

L’algoritmo è un procedimento che risolve un determinato problema attraverso un numero finito di passi elementari. Una sequenza di processi che sembrerebbe restare nel freddo territorio dei numeri, e che si esprime in un linguaggio informatico incomprensibile ai più. Eppure questi algoritmi controllano l’andamento dei mercati azionari, scelgono il prezzo di un biglietto aereo, progettano una serie tv o decidono quali sono le notizie, le pubblicità e i contenuti che ci interessa di più vedere sui nostri social network. Partendo dalle origini e ripercorrendo le tappe che da Babilonia a Google hanno segnato la loro ascesa, Breve e universale storia degli algoritmi mostra come la loro importanza non sia da ricercare nelle infinite possibilità del calcolo numerico, ma nell’enorme impatto sulla società moderna e nel potere derivante dalla gestione di flussi di dati e informazioni, che con l’esplosione della rivoluzione digitale hanno portato gli algoritmi ad essere lo strumento più potente mai esistito nelle mani del nuovo capitalismo. Uno strumento neutro però, che può generare progresso o distruzione solo nella misura in cui siamo noi a volerlo.

Introduzione

Gli algoritmi oggi controllano tantissimi aspetti delle nostre vite: ci sono algoritmi che cercano per noi informazioni sul web, che decidono i prezzi dei biglietti aerei e quali pubblicità vedremo su Internet, algoritmi che progettano serie tv, algoritmi che ci guidano passo passo nel raggiungere una destinazione usando un navigatore o un programma su uno smartphone, algoritmi che decidono quali notizie vediamo nei social network.

Ma cosa è, esattamente, un algoritmo? Sono state proposte diverse definizioni, di cui parleremo in maggior dettaglio in seguito; per il momento possiamo dire che un algoritmo è simile a una ricetta: è un procedimento per giungere a un risultato (ad esempio, una torta) a partire da dati o informazioni in ingresso (gli ingredienti). Questa metafora ci consente anche di chiarire la relazione tra programmi e algoritmi: gli algoritmi sono la parte teorica di un programma per computer e esistono indipendentemente dall’essere stati implementati in uno o più programmi; questo è simile a quello che avviene per le ricette, che rappresentano la parte teorica della cucina: una ricetta esiste indipendentemente dal fatto che sia stata implementata (preparando il piatto corrispondente) una o più volte.

Da un punto di vista storico, i primi algoritmi di cui abbiamo traccia risalgono a circa 4000 anni fa, nell’antico Egitto e a Babilonia, ed erano essenzialmente algoritmi di calcolo numerico, come gran parte degli algoritmi fino al secolo scorso.

Ma la vera grande rivoluzione che ha portato gli algoritmi a diffondersi non ha a che fare con il calcolo numerico, bensì con due fattori: la capacità di manipolare informazioni di qualsiasi natura, non solo numeri, e la diffusione dei computer e il loro collegamento nell’artefatto più complesso realizzato dall’uomo – il World Wide Web, la rete di documenti e contenuti che si poggia su Internet, la rete di reti di computer.

In questo libro ripercorriamo le tappe dell’incredibile ascesa al potere degli algoritmi: nel capitolo seguente cercheremo di comprendere meglio cosa sia un algoritmo, con esempi di algoritmi creati da personaggi che non vi aspettereste, come Giulio Cesare, Edgar Allan Poe e Sherlock Holmes, solo per citarne alcuni. I due capitoli successivi descrivono, per sommi capi, le idee e le persone che hanno portato alla creazione del computer, ovvero di una macchina in grado di eseguire qualsiasi algoritmo, di Internet e del World Wide Web. Nel quarto capitolo parleremo degli algoritmi usati dai colossi dei nostri giorni: Google, Facebook, Amazon e Netflix; come vedremo, i loro sistemi sono accomunati dal fatto di cercare di capire cosa ci piaccia.

Poi affronteremo aspetti di cui si parla poco: fino a ora ci siamo concentrati sull’interazione tra le persone e gli algoritmi, ma cosa succede quando gli algoritmi interagiscono tra di loro? Vedremo anche come sia possibile costruire, tramite algoritmi, un sistema monetario decentralizzato (Bitcoin) basato su una tecnologia interessantissima ma al tempo stesso piena di insidie, la Blockchain. Infine, parleremo dei recentissimi progressi nel campo dell’intelligenza artificiale, ottenuti con idee algoritmiche che risalgono alla metà del secolo scorso ma che solo oggi, disponendo di potenza di calcolo adeguata e grandi quantità di dati (i famigerati Big Data), si stanno manifestando.

Per i lettori più arditi, in appendice riportiamo alcuni esempi di programmi in diversi linguaggi di programmazione; alla fine di ogni capitolo trovate un indovinello algoritmico, la cui soluzione è proprio un algoritmo. Se volete verificare la correttezza della soluzione trovata, o non siete riusciti a risolverli, le soluzioni sono alla fine di questo libro.

capitolo 1

Dixit Algorizmi

L’informatica riguarda i computer

non più di quanto l’astronomia riguardi i telescopi.

Edsger Wybe Dijkstra

Metodo. Procedura. Regola (o insieme di regole). Procedimento. Questi sono alcuni dei nomi con i quali ci riferiamo comunemente ad algoritmi veri e propri. E di solito usiamo il termine algoritmo solo per indicare qualcosa collegato a attività informatiche, anche molto diverse tra di loro: “gli algoritmi controllano i mercati azionari”, “gli algoritmi decidono i prezzi dei biglietti aerei” e “un algoritmo sceglie la tua anima gemella”.

Nell’immaginario collettivo, alla parola algoritmo è associato un alone di mistero: cosa faccia, e quindi cosa sia, un algoritmo, non è dato saperlo. Se poi proviamo a cercare su Internet, o nei testi di informatica, troviamo definizioni che non sembrano essere di grande aiuto: Wikipedia propone, ad esempio, “un algoritmo è un procedimento che risolve un determinato problema attraverso un numero finito di passi elementari”. la definizione è sicuramente corretta, ma in parecchi rimarrà il dubbio: come fanno questi passi elementari a controllare i mercati azionari, scegliere il prezzo di un biglietto aereo o, addirittura, trovarci l’anima gemella?

Per rispondere alla domanda qui sopra (ma senza grosse garanzie per quello che riguarda la vostra anima gemella) dobbiamo innanzitutto chiarire cosa sia, esattamente, un algoritmo.

una semplice moltiplicazione

Facciamo un passo indietro di circa ottocento anni e immaginiamo di essere intorno all’anno 1200, nell’antica repubblica di Pisa, una delle principali repubbliche marinare dell’epoca. Avete appena concluso una vendita, ben 35 tessuti in seta al buon prezzo di 12 denari per ogni tessuto. Per calcolare il prezzo totale dovete fare una semplice moltiplicazione; usando la notazione in vigore al tempo, ovvero i numeri romani, possiamo scrivere:

XXXV × XII = ??

Qui ci accorgiamo che abbiamo un problema, non sappiamo fare la moltiplicazione con il sistema di numerazione romano: all’epoca, in effetti, per le operazioni matematiche usavano un abaco, ovvero uno strumento di calcolo simile, in alcune sue versioni, a un pallottoliere. Noi invece abbiamo imparato già alle elementari come fare le moltiplicazioni, con il metodo chiamato “in colonna”, che mostriamo in Figura 1.1.

Il calcolo del prodotto di due numeri viene ricondotto al calcolo di prodotti semplici (il primo numero per ogni cifra del secondo numero) e di somme. Abbiamo quindi risolto un problema (calcolo del prodotto di due numeri) usando dei passi elementari (prodotto di un numero per una cifra e semplici somme): abbiamo appena usato un algoritmo! Un algoritmo che conoscete fin dalle scuole elementari ma che probabilmente non avete mai chiamato con questo nome!

Con questo algoritmo chiunque è in grado di calcolare il prodotto di due numeri, indipendentemente da quanto siano grandi. Chiaramente, più grandi sono i numeri e maggiore sarà, in generale, il tempo necessario a calcolare il loro prodotto.

Figura 1.1: Moltiplicazione in colonna

La scelta di questo algoritmo come primo esempio non è casuale: viene descritto nell’opera Algoritmi de Numero Indorum di Al-Khuwarizmi. In questa opera fondamentale, scritta in arabo con il titolo Kitab al-hisab al-hindi presumibilmente intorno all’anno 825, ma di cui a noi sono giunte solo traduzioni in latino, l’autore illustra il sistema di numerazione indiano, che usa un simbolo speciale per indicare lo zero, e le regole per fare le quattro operazioni e per il calcolo delle frazioni. Questa opera, nelle sue diverse traduzioni, avrà grande diffusione in tutta Europa e dalla latinizzazione del nome di Al-Khuwarizmi nasce il termine algoritmo.

Il fatto che le cifre indiane siano arrivate in Europa attraverso Al-Khuwarizmi chiarisce perché spesso ci si riferisca a esse con il nome di cifre arabe (o anche cifre indo-arabe).

il liber abaci di fibonacci

Tra le traduzioni dell’opera di Al-Khuwarizmi c’è un testo scritto nel 1202 da un matematico pisano, Leonardo Pisano detto Fibonacci: il Liber Abaci, ovvero il Libro dell’Abaco, inteso come calcolo. Fibonacci non si limita a una semplice traduzione dell’opera di Al-Khuwarizmi ma, come lui stesso ammette nel Liber Abaci, integra la conoscenza della matematica indiana e araba, ottenuta leggendo le opere di Al-Khuwarizmi, con la matematica euclidea. Il risultato è un testo di importanza fondamentale in quanto, per la prima volta, la materia viene esposta in maniera didattica dedicata non ai matematici ma ai commercianti, che erano infatti i veri destinatari del testo.

Secondo Pietro Cossali, autore di quella che viene considerata la prima opera di storia della matematica scritta in italiano, pubblicata in due volumi nel 1797 e nel 1799, il Liber Abaci è stato il principale artefice della diffusione delle conoscenze dell’algebra e dell’aritmetica moderne: da Pisa ha raggiunto tutta la Toscana, e in particolare Firenze; da qui si è diffuso in tutta Italia, compresa Venezia che ha contribuito a farlo conoscere in tutta Europa. La prima edizione del Liber Abaci, quella del 1202, è andata persa; a noi è giunta la seconda versione dell’opera, scritta da Fibonacci nel 1228.

In questa seconda versione Fibonacci ha aggiunto del materiale, tra cui probabilmente anche i famosi numeri omonimi (numeri di Fibonacci), ovvero i numeri della sequenza (o successione)

1, 1, 2, 3, 5, 8, 13, 21,…

Come possiamo vedere, a parte i primi due numeri (entrambi 1), ogni numero è la somma dei due che lo precedono. Questa sequenza ha moltissime proprietà matematiche, comprese relazioni con la sezione aurea e con il Triangolo di Tartaglia; alcune moderne strutture dati informatiche (Heap di Fibonacci) sono state ispirate proprio da questa sequenza.

Grazie alla diffusione di quest’opera, i numeri indiani hanno gradualmente spodestato, in tutta Europa, i numeri romani. A tal proposito, una curiosità: tra i primi a recepire l’importanza del Liber Abaci furono i banchieri, che prestavano denaro e avevano bisogno di calcolare gli interessi. Tuttavia, questo repentino cambio di scrittura, dai familiari numeri romani alle cifre di origine indiana, fu giudicato sospetto dai governanti dell’epoca: i banchieri furono accusati di aver cifrato i loro libri allo scopo di renderli incomprensibili e quindi pagare meno tasse del dovuto; nel 1299 a Firenze fu addirittura emanata una legge (Statuto dell’Arte del Cambio) che proibiva l’uso delle cifre nelle scritture contabili. Da questi fatti deriva l’etimologia di cifrare, nel senso di codificare: in origine voleva solo indicare lo scrivere usando le cifre di origine indiana.

come uscire da un labirinto

L’algoritmo per moltiplicare due numeri, visto nella sezione precedente, è un esempio tipico di algoritmo di calcolo numerico. Vediamo adesso alcuni algoritmi di tipo diverso, iniziando con quelli in grado di guidarci fuori da un labirinto.

Nel famoso romanzo di Umberto Eco Il nome della rosa, da cui è stato anche tratto un film interpretato da Sean Connery, il protagonista Gugliemo da Baskerville racconta al suo discepolo Adso un metodo (un algoritmo!) per uscire da un labirinto, metodo appreso da un antico testo:

“Per trovare la via di uscita da un labirinto,” recitò infatti Guglielmo, “non vi è che un mezzo. A ogni nodo nuovo, ossia mai visitato prima, il percorso di arrivo sarà contraddistinto con tre segni. Se, a causa di segn...

Indice dei contenuti

• Breve e universale storia degli algoritmi
• Indice
• Introduzione
• Conclusione
• Elenco delle figure
• Bibliografia