Proponiamo a tutti voi Lettori, questa  intervista/recensione del libro “Algoritmi” editoalgoritmi_Toffalori_matematica dalla casa editrice Il Mulino e scritto dal prof. Carlo Toffalori docente di Logica matematica all’Università di Camerino e presidente dell’Associazione Italiana di Logica e sue Applicazioni.

In questa prima parte dell’intervista l’autore risponde alle nostre domande sul suo libro introducendo il lettore al mondo degli algoritmi.

Vi lasciamo alla lettura di questa interessante intervista che spazia dal Teorema di Zermelo al problema “P versus NP” passando per Fibonacci, Eulero e molto altro (comprese le suocere!).

 


D- Come è nata l’idea di scrivere un libro dedicato agli Algoritmi?

R- La proposta mi giunse dall’editore Il Mulino, che stava progettando una collana dedicata a vari aspetti della  matematica moderna. Non che l’argomento mi sembrasse semplice, ma con l’editore mi trovai subito benissimo, e così un po’ alla volta il libro è venuto alla luce.Toffalori_0

D- Nel suo libro scrive che gli algoritmi “provvedono al nostro quieto vivere”. Può anticipare ai nostri lettori il perché di questa frase?

R- Algoritmo è sinonimo di procedimento, procedura. Come parola, richiama un po’ la matematica, e in effetti deriva dal nome di un matematico arabo di molti secoli fa. Però oggi partecipa della nostra vita di tutti i giorni, anche se non ce ne rendiamo conto. Per esempio, è di largo impiego anche in informatica. Ci sono allora operazioni che ripetiamo abitualmente, come l’uso di computer, telefonini e congegni vari, compresi gli elettrodomestici e molto altro, e di cui gli algoritmi garantiscono funzionamento e sicurezza.

D- Nell’ultimo periodo nei media italiani si parla spesso d’algoritmi (da quelli dei motori di ricerca a quelli dei social network). Ritiene che siano trattati in modo adeguato e che questi articoli contribuiscano a migliorare la consapevolezza dei lettori su questo tema?

R- Il tema “algoritmo” è molto vasto. Come dicevo, non riguarda la sola matematica, maalgoritmo_img investe la storia della scienza, l’informatica e, tramite le sue varie applicazioni, moltissimi altri campi. Allora non stupisce che venga trattato con frequenza, quasi con familiarità. Per lo stesso motivo c’è il rischio che sia talora accostato con una qualche superficialità. Comunque un articolo che parla di scienza, e di algoritmo in particolare, non è per me un fattore negativo. L’importante è che sappia stimolare nel lettore l’interesse e il desiderio di approfondire.

D- Nel primo capitolo del suo testo, parla del Teorema di Zermelo, di Fibonacci e dei ponti di Königsberg. Dopo averli brevemente introdotti, ci può spiegare cosa accomuna cose così apparentemente diverse fra loro?

R- Si tratta di tre storie diverse, tutte legate in qualche modo al discorso degli algoritmi. Parto di fondo, e cioè dal problema dei ponti di Königsberg. La questione risale al Settecento e può sembrare banale. Si trattava infatti di individuare il percorso di una passeggiata domenicale sui sette ponti della città di Königsberg, che consentisse di attraversarne ognuno esattamente una volta e ritornare alla fine al punto di partenza. Eulero, che fu un grande matematico di quell’epoca, risolse il problema dimostrando che quell’itinerario era impossibile. Per farlo inaugurò concetti e strumenti – la così detta teoria dei grafi – che oggi hanno una gran varietà di applicazioni concrete, dall’organizzazione della rete e dei suoi nodi al commercio e alla distribuzione delle merci.

Anche la successione di Fibonacci nacque da un sorta di gioco, anzi di quiz. L’epoca stavolta è il Medio Evo. Il problema riguarda la riproduzione dei conigli. Si assume che ogni loro coppia, maschio e femmina, diventi fertile dopo due mesi di vita e prenda a generare nuove coppie, sempre maschio e femmina, al ritmo di una al mese. Ci si chiede allora come evolve nei mesi la popolazione di conigli, escludendo casi di mortalità. La sequenza di numeri che così si stabilisce, a indicare in funzione del mese il numero complessivo delle coppie di conigli presenti, manifesta un’incredibile ubiquità nella natura, dove regola, per esempio, la distribuzione delle foglie sui rami delle piante o le spirali delle conchiglie. Trova applicazioni sorprendenti anche nell’arte, in architettura o pittura o musica.

zermelo_02

Ernst Zermelo

Il teorema di Zermelo si riferisce invece al gioco degli scacchi. Dimostra la possibilità di partite perfette, cioè esenti da errori. Il risultato non è forse sorprendente, perché gli scacchi costituiscono un gioco così detto finito. In altre parole, e per dirla in modo un po’ grossolano, il numero dei casi che si possono presentare è sostanzialmente finito. Anche il numero complessivo delle partite immaginabili, al netto di qualche ovvia semplificazione, è finito e viene stimato in circa 10 alla 120 – un uno con centoventi zero dietro. Dunque è lecito, in linea di principio, ammettere le partite perfette assicurate da Zermelo. A proposito: quest’ultimo fu un matematico tedesco di inizio Novecento, e in effetti questo suo teorema risale al 1912. Stabilita l’esistenza di partite senza errori, ci si può ovviamente domandare quali esse siano. Un algoritmo per trovarle è semplice: esplorare tutti i casi possibili, confrontarli e decidere quali sono i migliori. Il problema, però, è che un’indagine di questo tipo richiede tempi imprevedibili. Infatti l’età del mondo espressa in secondi non arriva a 10 alla 18. Come dire che, se Adamo ed Eva avessero preso a sfidarsi a scacchi all’inizio dell’universo al ritmo di una partita al secondo, quelle che avrebbero disputato a tutt’oggi sarebbero solo una goccia rispetto all’oceano delle altre ancora da giocare. L’algoritmo in teoria funziona, ma nella pratica è sostanzialmente inattuabile.

D- Il secondo capitolo si intitola “La misteriosa incalcolabilità del mondo”. Ci può spiegare il senso di questo titolo?

R- Il caso di Zermelo e degli scacchi, ovvero di problemi risolubili in teoria, ma difficili da risolvere nella pratica, non è il peggiore che può capitare. Ci sono anche problemi per i quali non si possono trovare algoritmi di risposta. Per dimostrarne l’esistenza, bisogna stabilire una definizione precisa e astratta di algoritmo, o meglio di problema dotato di algoritmo, dedurne poi, per negazione, quella, sempre astratta, di problema sprovvisto di algoritmo e finalmente provare, sempre in via teorica, che certi problemi corrispondono a quest’ultima descrizione. Il concetto più convincente di problema dotato, o sprovvisto, di algoritmo fu proposto da Alan Turing nel 1936. Su quel fondamento, si trova una gran varietà di questioni irrisolvibili, non solo in matematica, ma anche in informatica. Diceva Edgar Allan Poe che non c’è quesito che la mente umana sappia formulare e a cui poi non sappia rispondere. Aveva torto. Come Gödel, Turing e altri ci insegnano, ci sono interrogativi che il nostro cervello sa porre ma non risolvere. A questo, appunto, alludevo parlando della “misteriosa incalcolabilità del mondo”.

D- Nel capitolo “Aspettando Godot” pone l’accento sulla differenza fra “problemi teoricamente risolubili” e problemi che sono “praticamente risolubili con risorse accessibili”. Può spiegare ai lettori questa differenza?

R- E’ la situazione del gioco degli scacchi. Esistono in generale problemi che dispongono in teoria di algoritmi anche brillanti ed eleganti, i quali però, se applicati nella pratica, riproducono gli imbarazzi della ricerca della partita perfetta. In certi casi l’esistenza di algoritmi rapidi ed efficienti è esclusa categoricamente. In altri, è ancora un problema aperto.

pvsnp

D- Sempre nel capito citato in precedenza, parla delle “fortune di Gastone”. Che cosa c’entrano con il problema P versus NP?

R-Supponiamo di avere un numero naturale di un milione di cifre, e di volerlo scomporre nei suoi fattori primi. Insomma, lo stesso esercizio che conduce a esprimere 15 come 3 per 5, ma applicato a un suo fratello maggiore, cioè a un numero delle dimensioni che dicevo. Neppure in questo caso è difficile immaginare in teoria una strategia apparentemente adeguata per provvedere: basta prendere tutti i numeri minori di quello dato e controllare caso per caso se lo dividono; se nessuno ci riesce, il numero è primo e non c’è altro da aggiungere; in caso contrario, trovato il divisore e il relativo quoziente, si può iniziare la decomposizione e, iterando la procedura, completarla. Per intendersi: fissato 45, si scopre il divisore 3, si esprime 45 come 3 per 15, poi si analizza la condizione di 3 e 15, scoprendo che l’uno è primo e l’altro è 3 per 5 (entrambi primi). Dunque, in definitiva, 45 è 3 per 3 per 5. Il guaio è che questa procedura, e tutte quelle che fin qui si conoscono per decomporre un numero in fattori primi, condividono gli stessi imbarazzi degli scacchi: richiedono troppo tempo. E’ tuttavia vero che, se un qualche amico bendisposto ci confidasse un divisore appropriato, per esempio 3 nel caso di 15, oppure fossimo così fortunati da indovinarlo per conto nostro, allora ci basterebbe svolgere per scrupolo la relativa divisione, 15 per 3, per controllare la bontà del suggerimento e trovare il quoziente 5 completando la decomposizione. Ecco: parlando alla buona, P è la classe dei problemi che si risolvono velocemente, NP la classe di quelli che si risolvono velocemente con un po’ di aiuto o di fortuna. Chiaramente la prima è contenuta nella seconda, perché un problema cui si risponde rapidamente senza bisogno di aiuto si risolve rapidamente anche con un po’ di aiuto. Ma la questione se le due classi coincidano, dunque se P sia o no uguale a NP, è la più complicata dell’attuale informatica teorica.

D- Una domanda semiseria non possiamo non farla. Nel suo libro parla spesso della categoria “suocera”. Ha mai incontrato una suocera lettrice dei suoi libri? Come ha fatto a cavarsela?

R- Mia suocera è vissuta fino a 98 anni, e negli ultimi 5 ha monopolizzato un po’ – diciamo così – la vita di mia moglie e mia. Gli accenni che faccio a lei nel libro sono un tributo affettuoso e scherzoso alla sua memoria. Non credo abbia mai letto le mie pagine. Suppongo però che qualche suocera, non mia ma di altri, l’abbia fatto. Spero che abbia considerato quelle righe nel modo giusto, e cioè con spirito e ironia. Altrimenti dubito di riuscire a cavarmela.

D- Nel suo testo, citando S. Banach scrive che l’essenza ultima del genio matematico sta “nella capacità di cogliere dove gli altri non vedono e di cogliere analogie sempre più elevate, fra teoremi, teorie e fra le stesse analogie”. Ci può fare un esempio di un matematico che è riuscito in questo?

banach

Matematico Stefan Banach

R- Direi che tutti i grandi matematici hanno avuto questa virtù. Astrarre, capire il nocciolo delle questioni, cogliere analogie è il mestiere del matematico. Pensiamo al problema, che forse abbiamo incontrato nelle scuole superiori, di costruire con riga e compasso un poligono regolare di un certo numero di lati – un triangolo equilatero, un quadrato, un pentagono regolare e via dicendo. Si tratta evidentemente di una questione di geometria, che certe volte, incluse quelle che ho appena citato, si riesce a risolvere, certe altre, come per l’ettagono regolare, no: non c’è possibilità di costruire con riga e compasso un poligono regolare di 7 lati. Gauss, che visse a cavallo tra Settecento e Ottocento ed è considerato il più grande dei matematici mai esistiti, chiarì completamente la questione, distinguendo i numeri di lati per cui la costruzione è possibile, e quelli per cui è preclusa. L’interrogativo di partenza, dicevo, è di geometria. Ma per rispondergli si sconfina nell’algebra e poi addirittura nell’aritmetica, si parla di polinomi e addirittura di decomposizione in fattori primi. Analogie, appunto: ragionevolissime per chi adesso le impara dai libri e da Gauss, eppure difficilissime da concepire a priori, e in questo senso ancora sorprendenti.


Inseriamo qui di seguito il video di presentazione del libro disponibile su youtube

CC BY-NC-SA 4.0
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.