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
La prossima auto che acquisterai sarà
a benzina
a gasolio (diesel)
elettrica
ibrida
a metano
a idrogeno
a biada

Mostra i risultati (8687 voti)
Giugno 2025
Hai cancellato inetpub? Lo script di Microsoft la ricrea e salva il PC
Il DNS europeo che promette di tutelare i dati personali
Guarda film pirata? Rischi fino a 5.000 euro di multa
Il Q-day è vicino
OneDrive: app e siti possono accedere a tutto il cloud
Windows 11, ennesimo aggiornamento che blocca l'avvio del PC
Maggio 2025
Il cripto-ladro è nella stampante e ruba un milione di dollari
Amazon, la IA ha trasformato la programmazione in una catena di montaggio
Lidar nelle auto: utile per la guida, letale per le fotocamere
Azienda IA in tribunale per il suicidio di un adolescente
Non è proprio legale... ma le sanzioni sono irrisorie
Pirateria, multati in Italia anche gli utenti finali
Bancomat da attivare e complessità digitale
Un ''diritto a riparare'' piccolo, virtuoso e originale
Siti per adulti, la verifica dell'età non avverrà tramite SPID
Tutti gli Arretrati
Accadde oggi - 11 giugno


web metrics