giovedì, marzo 17, 2005

Approfondimenti

Il cifrario di Cesare

Wikipedia in Italiano

1 commento:

Alessandro ha detto...

Il gioco di Einstein... presupposto sul significato di soluzione.
Trovare una soluzione di un problema, anche quando questa è unica, non significa aver risolto il problema... Al contrario, costruire un algoritmo risolutore di un gioco sognifica aver risolto il problema, anche quando cambiano i parametri di riferimento. A volte è persino possibile costruire un algoritmo risolutore senza poi riuscire a trovare una effettiva soluzione, in quanto l'algoritmo impiega troppo tempo (a volte persino milioni di anni) per poter individuare il set di soluzioni. Esistono 2 grandi famiglie di problemi; i problemi a soluzione polinomiale (p) ed i problemi a soluzione non polinomiale (np). Questi ultimi, generalmente, sono considerati difficili perchè l'algoritmo prevede un numero di calcoli che cresce in maniera esponenziale con il numero di variabili del problema. Tra i problemi np, un sottoinsieme è purtroppo considerato np-completo, ossia è dimostrato che non esiste una soluzione polinomiale, altri invece per i quali semplicemente non è stata ancora trovata. Tra le ultime scoperte degne di nota, il problema della fattorizzazione dei numeri è stato risolto in p, e nei prossimi anni questo potrebbe richiedere una decisa ridefinizione delle chiavi pubbliche e private delle firme elettroniche oggi utilizzate e legalizzate.