Il computer, il genio e la forza bruta

Un problema banale, che nemmeno i calcolatori più potenti riescono a risolvere in un tempo ragionevole. La matematica combinatoria, severa, fissa i limiti della tecnologia attuale e futura. E ci insegna ad usare il cervello al posto della forza bruta.



[ZEUS News - www.zeusnews.it - 22-07-2003]

Karim lavora per un corriere espresso: con il suo furgone consegna pacchi e buste per conto di un'organizzazione avanzatissima dal punto di vista telematico ed informatico. Ogni giorno deve consegnare un certo numero, facciamo 20 oggetti in 20 indirizzi diversi, per cui avrà da percorrere un circuito, con partenza ed arrivo nel magazzino, formato da 20+1 tappe. Karim è un tipo pignolo: gli è saltato il ticchio di chiedere la sequenza ottimale, quella che può fargli risparmiare tempo, benzina, gomme, etc. Ma quell'antipatico del ragioniere gli ha risposto picche. Perchè?

Quello di Karim è un esempio del Traveller Salesman Problem, o TSP, un problema che è considerato difficile, perchè ad oggi non si conosce un algoritmo polinomiale (collegato polinomialmente alla dimensione n del problema, e quindi veloce) che possa risolverlo. Se volesse risolvere il problema, la ditta dovrebbe per prima cosa, e già qui non sarebbe facile, munirsi di una tabella enorme riportante le distanze tra ogni via della città e tutte le altre. Se rappresentiamo ogni tappa di Karim con una lettera dell'alfabeto, un esempio di percorso, detto ciclo hamiltoniano, può essere il seguente:

abcdefghijklmnopqrstua,

che sarà diverso, per esempio, da

abcdefghijklmnopqrsuta,

se associamo ad ogni passaggio di lettera la distanza tra gli indirizzi estratta dal tabellone di cui sopra, e le sommiamo, possiamo associare ad ogni percorso possibile la distanza totale da percorrere, e quindi indirettamente il suo costo. Il metodo di soluzione cosiddetto della "forza bruta" consiste nell'analisi di ciascun percorso possibile, nel calcolo del suo costo, e nel confronto tra queste soluzioni possibili, alla ricerca di quella minore, e quindi ottima.

Quanti percorsi dovranno essere analizzati? Il loro numero è 20! (venti fattoriale), cioè 20x19x18x17... x ...3x2x1. il risultato è 243290200817640000. Detto così non sembra un granchè. Per chi mastica di crittografia e sicurezza, corrisponde circa a trovare una password composta da 8 caratteri da 8 bit, cioè password del tipo µ2«K<+;E.

Dunque, un calcolatore, con un processore di ultima generazione, col clock ad almeno un paio di gigahertz, equipaggiato con un software velocissimo, come AZPR, può analizzare fino a 30 milioni di combinazioni al secondo.

Per trovare la soluzione ottima, questa combinazione hardware-software impiegherà:

81.096.733.606 secondi,

cioè 1.351.612.227 minuti,

cioè 22.526.870 ore,

quindi 938.619 giorni,

perciò 2.571 anni e mezzo.

Questi sono i limiti della forza bruta: di fronte ad un problema così banale la best available technology dell'umanità va in crisi.

Naturalmente esistono algoritmi più efficienti, esiste la possibilità di collegare più elaboratori e farli lavorare contemporaneamente, e grazie a questo si può ampliare la dimensione del problema risolvibile in tempi decenti. Ma la sostanza non cambia: alcuni tipi di problemi, anche con dimensioni attorno al 50, non solo non sono praticamente risolvibili attraverso gli attuali computer, ma si può ragionevolmente supporre che non lo saranno mai, qualunque sia il progresso futuro della velocità dei calcolatori.

Ma l'inventiva umana, il genio, ci viene in soccorso. Come? Primo, accontentandosi: può essere agevole trovare soluzioni sub-ottimali, e queste sono spesso soddisfacenti. Secondo, cercando algoritmi più efficienti, tipo gli euristici, magari basati su interessanti interazioni col mondo della biologia, come quelli genetici o l'affascinante Ant Colony Optimization, che ricava un algoritmo dal comportamento apparentemente caotico delle formiche. Terzo, provando a rovesciare gli attuali paradigmi tecnologici: il calcolatore digitale ci intristisce? Proviamo con quello quantistico: per esso esistono già algoritmi efficienti a risolvere problemi ex-difficili (ottima documentazione disponibile anche su ZEUSNews).

Ma non è tutto: talvolta la matematica, quando ci mostra percorsi logici che possono essere utilizzati al di fuori di essa, ci insegna a vivere. Quando le variabili in gioco sono molte, un problema puramente combinatoriale come quello di Karim, assomiglia molto ai piccoli e grandi crucci della vita reale, come la droga, il terrorismo, la tutela dei diritti d'autore, gli insetti che infestano la mia albizia. In questi casi, può essere utile trarre insegnamento dalla teoria: la forza bruta difficilmente porta alla soluzione.

Se questo articolo ti è piaciuto e vuoi rimanere sempre informato con Zeus News ti consigliamo di iscriverti alla Newsletter gratuita. Inoltre puoi consigliare l'articolo utilizzando uno dei pulsanti qui sotto, inserire un commento (anche anonimo) o segnalare un refuso.
© RIPRODUZIONE RISERVATA

Commenti all'articolo (ultimi 5 di 8)

kensan
Bell'articolo! Leggi tutto
23-7-2003 17:18

Vanni
Elementi finiti Leggi tutto
23-7-2003 13:24

Pinatubo
Human kind Leggi tutto
23-7-2003 12:50

Guerino Giancola
Segnalazione Leggi tutto
23-7-2003 10:01

Lele2k
Troppi ragionamenti inutili... Leggi tutto
23-7-2003 09:16

La liberta' di parola e' un diritto inviolabile, ma nei forum di Zeus News vige un regolamento che impone delle restrizioni e che l'utente e' tenuto a rispettare. I moderatori si riservano il diritto di cancellare o modificare i commenti inseriti dagli utenti, senza dover fornire giustificazione alcuna. Gli utenti non registrati al forum inoltre sono sottoposti a moderazione preventiva. La responsabilita' dei commenti ricade esclusivamente sui rispettivi autori. I principali consigli: rimani sempre in argomento; evita commenti offensivi, volgari, violenti o che inneggiano all'illegalita'; non inserire dati personali, link inutili o spam in generale.
E' VIETATA la riproduzione dei testi e delle immagini senza l'espressa autorizzazione scritta di Zeus News. Tutti i marchi e i marchi registrati citati sono di proprietà delle rispettive società. Informativa sulla privacy. I tuoi suggerimenti sono di vitale importanza per Zeus News. Contatta la redazione e contribuisci anche tu a migliorare il sito: pubblicheremo sui forum le lettere piu' interessanti.
Sondaggio
Cosa ne pensi del ritocco digitale dei film classici (non solo di fantascienza)?
E' un falso storico; i film vanno visti come furono girati.
E' necessario, per evitare che certi film vengano dimenticati.
Va bene, basta che sia indicato chiaramente.
Non me ne pu fregar di meno.

Mostra i risultati (3080 voti)
Febbraio 2020
Il browser per navigare sempre in incognito
Equo compenso, raffica di aumenti per Pc, smartphone e schede Sd
Come provare Windows 10X in anteprima, gratis
Windows 10, la patch causa più problemi di quelli che risolve
Gennaio 2020
Mummia di 3.000 anni torna a parlare
Microsoft per pietà aggiorna Windows 7
Agcom, due milioni di multa per Tim, Vodafone e Wind Tre
Windows 10: e adesso la pubblicità
Batterie al grafene, ormai ci siamo
Edge è morto, viva Edge (Chromium)
Il giorno della morte di Windows 7
The New Facebook, il social network cambia pelle
Samsung fa un balzo in avanti con il Galaxy S20
Dicembre 2019
Le peggiori password del 2019
Il chip che realizza la crittografia perfetta a prova di hacker
Tutti gli Arretrati


web metrics