6 x 9 = 42

“Ho sempre detto che c’era qualcosa di fondamentalmente sbagliato nell’universo…” (Arthur Dent)

A Ciascuno I Propri Sogni

Posted by scardax su dicembre 1, 2008

Ogni materia scientifica ha il suo “Santo Graal“, o meglio, i suoi Santi Graal: chimere che sembrano irraggiungibili, risultati ambiti da tutti, e come nelle migliori saghe medievali dedicate alla leggendaria coppa che avrebbe raccolto il sangue di Cristo, intere generazioni di cavalieri che hanno dedicato gli studi e le battaglie di una vita alla loro causa, il più delle volte per fallire miseramente.

Qualunque matematico darebbe un braccio, forse di più, per poter provare che ogni numero pari é la somma di due numeri primi (ed alcuni propongono anche un premio di un milione di dollari!); innumerevoli fisici sono disposti a spendere miliardi e miliardi per cercare il fantomatico Bosone di Higgs, per non dover continuare ad esclamare che “la massa ci sarà pure, ma io non ho idea di dove tirarla fuori dalle mie equazioni“; i paleontologi scavano da decenni sperando di incappare nel fossile del fatidico “anello mancante“, mentre i geologi probabilmente piangerebbero se riuscissero a capire finalmente con precisione cosa provoca il campo magnetico della Terra.

Ma, a differenza di Artù e dei suoi cavalieri della Tavola Rotonda, molti dei Graal vengono costantemente raggiunti da ricercatori, o team di ricercatori, ed appena la soddisfazione si conclude la ricerca si rivela appena iniziata: se negli anni ’70 si era finalmente riusciti a comprendere il meccanismo di codifica fra i geni del DNA e gli amminoacidi (ne parleremo nel prossimo post), solo quattro anni fa si é riusciti a mappare l’intero genoma umano, e di certo la strada per la sua comprensione é ancora lunga!

Tutto questo é più o meno conosciuto dal grande pubblico, ma qualunque ricercatore ha il suo cruccio personale: anche gli informatici! Per capire il sogno di ogni “smanettone“, pero’, un po’ di teoria non guasta mai. Fra i tanti obiettivi dei moderni calcolatori, c’é quello di risolvere problemi di ogni genere: un utente vuole poter cercare dei contatti nella sua rubrica elettronica, i meteorologi vorrebbero delle previsioni sempre più accurate, i virologi desiderano capire come diffondere efficacemente un vaccino in una popolazione, un amministratore di rete esige che i computer gesticano al meglio il traffico di pacchetti… Un gran casino!

Compito di alcuni informatici é riuscire a risolvere questi problemi implementando degli algoritmi nei calcolatori: delle sequenze di passi che, dato un certo input, producano un output in un tempo finito che risolva il problema dato. Ad esempio, un algoritmo di ricerca di un nome in una rubrica telefonica puo’ essere estremamente semplice, del tipo:

1) Comincia dal primo nome

2) Se il nome corrisponde a quello cercato, fine della ricerca, altrimenti:
– Avanza di un nome e ricomincia il punto 2 finché la lista non é terminata.

Già da questo esempio si puo’ capire il vero problema dietro la creazione di algoritmi: maggiore é la dimensione della rubrica, più lunga sarà, in media, la ricerca! Le prestazioni temporali dipendono dalla grandezza dell’input, per dirla in maniera più tecnica. Al che sorge la domanda successiva: dipendono in che misura? In questo caso, linearmente: raddoppiando la grandezza dell’elenco, raddoppiero’ in media il tempo di ricerca. In altri casi potrebbe essere una dipendenza quadratica: raddoppiando la grandezza dell’input, in media quadruplico la durata di esecuzione!

La maggior parte dei problemi che si affrontano, in genere, ha una dipendenza di tipo polinomiale: n, n², n3 (dove n é una qualche misura dell’input)… L’insieme di tutti questi problemi viene chiamato P (originale, eh?), ed in pratica identifica i problemi “fattibili“: anche eseguendoli con grandi input, in media avro’ una risposta in un tempo accettabile. Al contrario, esistono problemi per i quali non si conoscono algoritmi di complessità polinomiale, ma solo di complessità esponenziale: 2n, 4n e cosi via. Questi problemi (che vengono detti NP) sono molto fastidiosi: per grandi input, abbiamo dei tempi di attesa di giorni, mesi, anni (addirittura secoli!) prima di poter avere una risposta: nella maggior parte dei casi, questo é inaccettabile – anzi, inutile.

Per ricollegarci all’inizio del discorso, manca ancora un piccolo dettaglio: all’interno dei problemi NP vi é un sottoinsieme di problemi detto NP-COMPLETO, con una proprietà molto interessante: qualunque problema NP puo’ essere ricondotto ad un problema NP-COMPLETO in tempo polinomiale! (rileggete la frase tre volte per essere sicuri di capirla prima di andare avanti). Se ho un problema A che é Np-Completo, posso ricondurre qualunque problema NP (ed anche P) ad un’istanza di A in un tempo accettabile, ovvero polinomiale.

E da qui nasce un’interessante corollario: se riuscissi a trovare un algoritmo che risolva un problema Np-Completo in tempo polinomiale, potrei risolvere… qualunque problema Np in tempo polinomiale! (sarebbe sufficiente ricondurre il problema in tempo polinomiale al problema np per cui conosco un algoritmo polinomiale, e poi risolverlo). Molti dubitano che sia possibile ricavare un simile algoritmo per i problemi Np-Completi, ma (e questo é il punto chiave) nessuno l’ha mai dimostrato!

Ero convinto di voler dire qualcos altro, ma non ricordo cos’era ed inoltre ci siamo allungati un po’ troppo, mi sa.

Spoiler: nel prossimo post parlero’ delle basi della genetica e dell’evoluzione, ed in quello successivo uniro’ il tutto per far vedere come affrontare uno dei più famosi problemi Np-Completi ispirandoci alla natura, quindi… Namasté!

Annunci

4 Risposte to “A Ciascuno I Propri Sogni”

  1. AkiRoss said

    eh, ma ora voglio sentire se risolvere il dilemma della np-completezza e’ per caso il TUO graal 😀 o ne hai altri?

    Il mio sarebbe la macchina (pseudo)pensante o l’UI perfetta… Credo che, piu’ del RTS perfetto, questi siano i due problemi che piu’ mi assillano.
    Specialmente l’IA forte.

  2. Scardax said

    Intendi su cosa mi piacerebbe lavorare tutta la vita?
    Mi metti in crisi, sul serio!

    Sinceramente mi piacerebbe vedere funzionante un vero computer quantistico, ma per poter arrivare anche solo a capire le porte logiche quantistiche dovro’ studiare ancora molto mi sa! 😀

  3. AkiRoss said

    Ehh meglio che ti dai da fare allora, e’ un campo che fiorisce in questi anni, la concorrenza si fa sempre piu’ forte.

    Se fossi stato un dio dell’elettronica e delle nanotecnologie mi sarei buttato nella produzione di una macchina in grado di computare in velocita NP 😀

  4. […] settimana fa, in A Ciascuno I Propri Sogni, avevamo visto molto rapidamente la distinzione fra problemi P, ovvero problemi che si sanno […]

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

 
%d blogger hanno fatto clic su Mi Piace per questo: