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:

X X X V × X I I = ??

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.

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 ad 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 edizio ne 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.  Ne Il nome della rosa, il famoso romanzo di Umberto Eco 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 segni precedenti su qualcuno dei cammini del nodo, si vedrà che quel nodo è già stato visitato, si porrà un solo segno sul percorso di arrivo. Se tutti i varchi sono già stati segnati allora bisognerà rifare la strada, tornando indietro. Ma se uno o due varchi del nodo sono ancora senza segni, se ne sceglierà uno qualsiasi, apponendovi due segni. Incamminandosi per un varco che porta un solo segno, ve ne apporremo altri due, in modo che ora quel varco ne porti tre. Tutte le parti del labirinto dovrebbero essere state percorse se, arrivando a un nodo, non si prenderà mai il varco con tre segni, a meno che nessuno degli altri varchi sia ormai privo di segni.”
Se il metodo vi sembra complicato, sappiate che anche Guglielmo era dubbioso sull’efficacia: quando il suo discepolo gli chiede “E secondo questa regola si esce?”, lui risponde “Quasi mai, che io sappia.”
In realtà l’algoritmo descritto non proviene da un antico testo ma è stato inventato da Trémaux nel 1892: l’idea è quella di marcare con un singolo segno il corridoio che stiamo percorrendo, mettendo il segno sia all’inizio che alla fine del corridoio. Se poi siamo costretti, perché non ci sono altre possibilità, a ripercorrere all’indietro il corridoio, aggiungiamo altri due segni, sempre ad entrambe le estremità del corridoio. In questa maniera sapremo che, relativamente alle entrate marcate con tre segni, non portano da nessuna parte. Se il labirinto ha una entrata e una uscita allora il percorso tra le due sarà quello che passa attraverso i corridoi con un solo segno. Se invece il labirinto ha solo una entrata (che quindi coincide con l’uscita), questo algoritmo fa percorrere tutti i corridoi del labirinto due volte, in entrambe le direzioni.
Se pensate che l’algoritmo di Trémaux sia complicato, nel caso dobbiate affrontare un labirinto potete usare quello che è stato usato nella versione cinematografica de Il nome della rosa: qui, a differenza del romanzo, Gugliemo consiglia a Adso di girare sempre a sinistra. L’algoritmo, noto anche con il nome di regola della sinistra (o regola della destra), consiste semplicemente nel
poggiare una mano (la sinistra o la destra, indifferentemente) su un muro e camminare in modo da tenere la mano sempre poggiata sul muro. In questo
modo, ogni volta che si arriva a un vicolo cieco, se ne uscirà continuando a percorrerlo
(costeggiando tutto il muro).  Se il labirinto ha un solo ingresso, che è anche il punto di uscita, l’algoritmo visita tutto il labirinto. Questo algoritmo garantisce di poter uscire da qualsiasi labirinto, ed è noto anche ad Harris, uno dei protagonisti del romanzo Tre uomini in barca (per non parlar del cane) di Jerome K. Jerome. Harris, parlando del labirinto di Hampton Court, dice infatti: “Basta sempre prendere la prima a destra”, anche se poi il gruppetto di persone da lui guidato si perderà e dovrà ricorrere all’aiuto del custode del labirinto per riuscire a uscirne.