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
Qual il momento tra questi in cui avverti il maggior bisogno di privacy?
Leggo gli annunci di lavoro in ufficio
Spio un/una mio/a ex sui social network
Utilizzo i social network in ufficio
Consulto l'online banking
Guardo foto o filmati a luci rosse
Invio o guardo foto private
Faccio shopping online

Mostra i risultati (1851 voti)
Luglio 2022
Alexa fa parlare i morti
Giugno 2022
Tesla e la batteria che dura 100 anni
Cosa succede alle password se cambio o perdo il mio dispositivo?
Il sistema operativo open source che ridà vita ai vecchi smartphone
Adobe, prove di Photoshop gratuito per tutti
15 giugno, finisce l'era di Internet Explorer
Grave falla in Windows, occhio ai documenti di Word
Toyota: cartucce di idrogeno per alimentare auto, case, droni
Maggio 2022
La Rete esce da TIM: nasce la Open Access italiana
DuckDuckGo consente a Microsoft di tracciare gli utenti
Russi saccheggiano trattori ucraini, che vengono brickati da remoto
Necrofinanza e criptovalute: lo scoppio di Terra/Luna
Pwn2Own 2022, Windows 11 e Ubuntu cadono il primo giorno
Migliaia di siti sono keylogger nascosti
Radio a onde corte: davvero?
Tutti gli Arretrati
Accadde oggi - 2 luglio


web metrics