Techetechetè -- I Problemi del Millennio
rubrica:
Autore:
... se potessimo concentrare la nostra attenzione sui cicli di calcolo del computer, allora ci potremmo domandare quale realmente siano i limiti di fattibilità, cioè se possano essere stabilite a priori le regole generali...
Mi è capitato di andare indietro con la memoria e di fare un salto tra i ricordi del passato, alla fine degli anni cinquanta, dentro all’aula tetra e fredda della mia scuola elementare. Grembiuli neri, colletti bianchi ben stirati e il simbolo IV ricamato sul petto, rigorosamente a destra, per indicare coi numeri romani che anch’io facevo parte della quarta: facile, perché l’anno dopo sarebbe bastato scucire la barra alla sinistra della V per passare in quinta, l’ultimo anno della scuola dell’obbligo, o forse no, perché l’obbligo era già stato esteso alle tre medie.
I maschi scrupolosamente divisi dalle femmine al punto che l’edificio stesso era stato costruito in blocchi separati, guai mai che il diavolo si fosse potuto infiltrare tra gli allievi di sesso diverso per poi distrarli da quella rigida e severa istruzione che là in quelle aule lo Stato dispensava gratuitamente.
Non sempre però l’attenzione di noi alunni era al massimo livello e ogni tanto si calava un po’ di tono tanto che il silenzio diventava brusio per poi dirompere in uno schiamazzo insopportabile, mal tollerato da un maestro inflessibile e tormentato dall’ansia che il suo rigido programma formativo non venisse rispettato.
E quando scattava la punizione, non si conoscevano mezze misure: si ricorreva a una terapia d’urto molto efficace, ciò che in quegli anni si chiamava impropriamente ‘numerazione’.
Fare una numerazione significava, per esempio, calcolare il risultato della somma dei primi 300 numeri naturali, un compito assolutamente inutile e snervante.
Pare che anche a Gauss, in ben altri tempi, fosse stata inflitta una punizione simile e si dice che anch’egli avesse inizialmente provato la stanchezza e la noia di questo stupido esercizio ripetitivo.
Ma Gauss era Gauss e poiché i numeri li conosceva molto bene, risolse la somma 1 + 2 + 3 + ... + 300 = 45.150 solo in qualche secondo dando prova di inusuale destrezza e costringendo il dannato maestro a ricorrere ad altro genere di punizione.
Lo scolaro prodigio aveva scoperto lipperlì la formula della progressione per cui, semplificando la questione ai soli primi quattro numeri: 1 + 2 + 3 + 4 = 10, possiamo notare che il risultato 10 si può ottenere facilmente moltiplicando l’ultimo (il 4) per il successivo (5) e dividendo tutto per 2.
Ecco come: 1 + 2 + 3 + 4 = 4 x 5 : 2 = 10.
Nel caso specifico del problema di Gauss, la somma dei primi 300 numeri naturali diventa questa: 300 x 301 : 2 = 45.150.
Messa da parte la straordinarie capacità del bambinoprodigio, l’esempio di questa regola di calcolo “furba e veloce” apre una serie di considerazioni interessanti in merito al calcolo complesso, specialmente quando questo viene utilizzato all’interno del gradino superiore del software del computer, cioè il firmware.
Ma il problema si allarga al punto tale che ancora oggi non si è arrivati a una conclusione definitiva e soddisfacente.
Ancor prima di entrare nei dettagli, va detto che la formula “furba” di Gauss - in quanto “scorciatoia” per abbreviare i tempi di esecuzione - fa parte di una delle 3 classi fondamentali del calcolo numerico, più precisamente di quella logaritmica.
Giusto per semplificare: i calcoli di classe logaritmica, sono quelli per cui i tempi di elaborazione si accorciano in virtù di trucchi - algoritmi – che per così dire abbassano il livello di difficoltà e, specialmente, ne riducono i tempi.
E così anche noi, tutte le volte che riusciremo a trovare delle regole in grado di semplificare un calcolo, potremo vantarci di aver costruito un algoritmo di classe logaritmica (questi due termini bisticciano un po’ tra loro, quindi è bene fare attenzione a non confonderli).
Fin qui niente di strano, ma non sempre si riesce a trovare qualche scorciatoia per ridurre il calcolo e allora bisogna accontentarsi di eseguire tutte le operazioni “a tappeto”, una dopo l’altra, in perfetta sequenza, ciò che in gergo si chiama “operazione di forza bruta”.
Come esempio di questa seconda classe di problemi, si deve pensare a ciò che succede tutte le volte che ci viene proposto, per esempio, di riordinare un semplice mazzo di carte da gioco. In realtà, in modo praticamente automatico, la nostra mente esegue un ciclo logico elementare che inizia con il confronto tra le prime due carte che ci capitano tra le mani lasciandole così come sono se la prima vale meno della seconda oppure scambiandole in caso contrario. Questo ciclo logico elementare procede fino alla fine secondo un criterio di sequenzialità.
Questo sistema di Forza Bruta viene ripetuto fino a quando non sarà più necessario alcun cambio su tutta la fila delle carte ma ciò che si deve notare è che il tempo necessario per riordinare il mazzo dipende dal numero delle carte stesse: più sono le carte e più tempo occorre proporzionalmente per riordinarle.
Molto dipende poi dalle condizioni di disordine iniziale (e casuale) del mazzo, cioè dagli scambi (permutazioni) che ci troveremo a fare o non fare.
Questa seconda classe di calcolo è detta polinomiale.
Riassumendo fin qui:
1) Le classi di calcolo “con scorciatoia” si chiamano logaritmiche
2) Le classi di calcolo in cui il tempo di processo è proporzionale al numero degli elementi si chiamano polinomiali.
Ma la storia non finisce certo qui perché esiste anche una terza classe di calcolo per la quale vale, come esempio, un problema niente affatto banale, conosciuto come il Problema del commesso viaggiatore.
Vediamo esattamente di che cosa si tratta.
Supponiamo che un Commesso Viaggiatore debba visitare un certo numero di città e che abbia a disposizione la carta stradale di tutte le possibili connessioni tra una città e l’altra e un certo tempo a disposizione.
Dato per scontato che, per esempio, il tempo a disposizione sia di 8 ore, ci si chiede se esista un percorso che tocchi ogni città una volta soltanto in modo da visitarle tutte entro il tempo stabilito.
Bene: ecco il terzo tipo di problema di calcolo: dopo la classe logaritmica e quella polinomiale entra in scena la classe di routing che si identifica attraverso la sigla TSP, dall’inglese Travelling Salesman Problem.
Per la soluzione del TSP occorre costruire un grafo fatto da tanti nodi in cui ciascun nodo rappresenta i clienti da visitare e la casa del commesso, e da tanti archi quanti sono i percorsi fra i nodi. Il risultato finale sarà quel ciclo ottimale che tocca tutti i nodi e che avrà la durata complessiva minore.
Questo problema è molto semplice da descrivere ma non altrettanto facile da risolvere perché il numero delle soluzioni cresce molto rapidamente all’aumentare del numero dei nodi ma è anche un problema di importanza pratica fondamentale se si pensa alle applicazioni nelle aziende di distribuzione e, in generale, ai trasporti.
Il TSP è anche un problema di classe decisionale poiché alla domanda se il viaggiatore sia in grado o no di rispettare i tempi prestabiliti, le uniche due risposte possibili sono Vero oppure Falso, cioè Sì oppure No, ovvero 1 oppure 0.
Ma torniamo al nostro viaggiatore facendo subito un esempio.
Il grafo che vedete rappresenta la zona assegnata.
Il viaggiatore deve visitare quattro clienti, rappresentati dai nodi 2, 3, 4 e 5 partendo dalla propria abitazione, che corrisponde al nodo 1, per poi tornarsene a casa.
I numeri sugli archi rappresentano i tempi necessari a percorrerli.
Ecco le domande:
• In quanti modi diversi può il commesso visitare i suoi clienti?
• Qual è il percorso migliore?
Con un po’ di pazienza possiamo esaminare tutte le possibilità.
Le soluzioni possibili sono date dalla moltiplicazione:
• del numero dei nodi meno quello della città di partenza
• per tutti i numeri inferiori fino a 1 (il cosiddetto fattoriale).
Così: 4 x 3 x 2 x 1 = 24.
Vediamo i singoli casi:
1-2-3-4-5-1 (di durata 36)
1-2-3-5-4-1 (di durata 38)
1-2-4-3-5-1 (di durata 42)
1-2-4-5-3-1 (di durata 40)
1-2-5-3-4-1 (di durata 40)
1-2-5-4-3-1 (di durata 44)
1-3-2-4-5-1 (di durata 48)
1-3-2-5-4-1 (di durata 46)
1-3-4-2-5-1 (di durata 48)
1-3-4-5-2-1 (di durata 44)
1-3-5-2-4-1 (di durata 44)
1-3-5-4-2-1 (di durata 40)
1-4-3-2-5-1 (di durata 38)
1-4-3-5-2-1 (di durata 40)
1-4-2-3-5-1 (di durata 44)
1-4-2-5-3-1 (di durata 44)
1-4-5-3-2-1 (di durata 38)
1-4-5-2-3-1 (di durata 46)
1-5-3-4-2-1 (di durata 42)
1-5-3-2-4-1 (di durata 44)
1-5-4-3-2-1 (di durata 36)
1-5-4-2-3-1 (di durata 48)
1-5-2-3-4-1 (di durata 38)
1-5-2-4-3-1 (di durata 48).
Le soluzioni migliori quindi sono due: 1-2-3-4-5-1 e 1-5-4-3-2-1, entrambe di durata 36.
Come possiamo vedere, il numero delle soluzioni cresce molto più rapidamente rispetto al numero dei nodi.
E ancora una volta chiediamo aiuto ad Excel per capire come funziona la faccenda aumentando considerevolmente il numero delle città.
E’ veramente il caos: guardate un po’ cosa succede con 14 città!
La colonna in rosso mostra il numero dei percorsi calcolato con la formula del fattoriale dei nodi, mentre la colonna in verde è il risultato del numero delle città elevato alla potenza.
Dunque è come un po’ ci aspettavamo: le soluzioni possibili crescono molto più della potenza dei dati di partenza. Il problema in questione è di tipo esponenziale.
In modo analogo, possiamo spostare l’attenzione all’interno del cicli di calcolo di un Computer per capire facilmente che mentre le classi di calcolo logaritmico (1) e polinomiale (2) non destano problemi particolari, per la classe di tipo esponenziale (3) ci si domanda quali realmente siano i limiti di fattibilità delle memorie e se comunque esista o meno una regola, un tetto, un limite di contenimento più o meno raggiungibile.
Ormai l’abbiamo capito bene: quando i problemi aumentano di difficoltà, diventa impossibile risolverli in un tempo ragionevole e così ci troviamo di fronte a una nuova classificazione:
• Problemi decisionali di classe P (polinomiali)
• Problemi decisionali di classe NP (non polinomiali)
In definitiva, mentre i problemi P sono considerati accessibili alle risorse di calcolo, quelli NP risultano inaccessibili.
Stiamo parlando della cosiddetta Congettura P = NP che rappresenta uno dei problemi matematici ancora non risolti: chi troverà la soluzione si potrà aggiudicare un premio di un milione di dollari. Lo offre il CMI (Clay Mathematics Institute) del Massachusetts la cui missione è quella di incrementare e popolarizzare le conoscenze matematiche. L’Istituto è dedicato ai fondatori Landon e Lavinia Clay, prominenti personalità d’affari di Boston, che hanno deciso di valorizzare e incrementare la ricerca matematica del Terzo Millennio.
In pratica, chiunque di noi riuscirà a trovare un algoritmo che risolva “in fretta" - cioè sulla base di tempi polinomiali – tutte le domande di un problema NP potrà aggiudicarsi l’ambito premio e finire come un nababbo la propria esistenza.
Coraggio, forza, rimbocchiamoci le maniche … ma facciamo alla svelta perché uno dei 7 problemi del Millennio - la congettura di Poincaré - è stato risolto recentemente dal russo Grigori Perelman che, tra l’altro, ha rinunciato al ritiro del premio milionario.
Buon per lui, vorrà dire che è già ricco abbastanza.
Francesco Caranti