Newsgroup: it.comp.lang.c
Titolo: Ancora sulla tabella di verita'.... forse ci siamo

L'idea è sempre quella: realizzare un programma che MEMORIZZI in una matrice
[n][2^n] (vedasi i #define) una tabella di verità come quella sotto (dove
n=3)...
Il codice che ho scritto crea una matrice avente le dimensioni richieste ma
con gli 0 e gli 1 disposti secondo una logica che non capisco. Un'altra cosa
importante che ho notato è che i valori presenti nella matrice variano al
variare del valore di " #define due_max " (addirittura, se il valore di "
#define due_max " è ESATTAMENTE uguale a 2^50, il programma non viene
proprio compilato). C'è ancora una volta qualche anima buona che sappia
spiegarmi cosa sto combinando? Grazie comunque per l'attenzione...
2^0     2^1       2^2
------------------------
 0          0           0
 1          0           0
 0          1           0
 1          1           0
 0          0           1
 1          0           1
 0          1           1
 1          1           1
=========================================================
#define max 50
#define due_max 1125899906842625   /* questo è 2^50 + 1 */
main()
{
double n;
int i,k,p,l,cont,lung_max;
int matrix[max][due_max];
do
{
  printf("\n\nnumero => ");
  scanf("%lf",&n);
}
while (n>max);
lung_max=pow(2.0,n);
for (i=0;i<n;i++)
{
       p=pow(2.0,i);
         for (k=0;k<lung_max;k++)
         {
           matrix[i][k]=(k/p)%2;
         }
}
============================================

 int matrix[max][due_max];
Non penso proprio che tu possa allocare una matrice di queste dimensioni...
ossia 50*(2^50+1)*sizeof(int), e' davvero impensabile, su _qualsiasi_
sistema, anche per un film di fantascienza ;-)
-- 
 Ciao, Bianco.
 Reply to luca.bianco (at) 
tiscalinet.it

Ti ho gia' postato la soluzione qualche giorno fa. Il tuo apporto
doveva essere solo quello di sostituire le stampe a video con
istruzioni di assegnamento, se proprio vuoi memorizzarle stabilmente
nella tua matrice.
Ti invito ad andare a controllare e studiare quanto scritto il
4/1/2001.
La tua soluzione non ha nulla di sbagliato (mancata corrispondenza
di tipi e parentesi graffe a parte) se non il fatto che 2^50 e' circa
la quantita' di molecole di cui e' composto il pianeta terra!!!
Figurarsi se esiste un computer che ha tanta memoria.
Se qualcuno ti ha suggerito che con il computer si puo' fare tutto
allora ha profondamente sbagliato: i limiti, in termini di capacita'
di calcolo, tempo e spazio sono tali che quasi non riusciamo a fare
nulla.
Il problema che ti sta assillando e' detto facente parte della classe
"intrattabile" per questo motivo.
Nella ricerca di avvicinarti ai limiti di spazio certo non aiuta
"sprecare" un "int" per immagazzinare solo uno "0" o un "1" ... !!
Se vuoi saperne di piu' di computabilita' e complessita', e se hai
forti base logico/matematiche, ti suggerisco la lettura di "Algoritmi
e Strutture di dati" di Alan Bertossi - UTET.
Il mio suggerimento e' quello di  vivere prospero, felice e in pace
anche senza queste nozioni. :-)

la quantita' di molecole di cui e' composto il pianeta terra!!!
Molto circa immagino. 2^32 sono 4G. 2^32 ci sta 262144 volte
in 2^50. Mi stai dicendo che un byte occupa molto meno di una
molecola oppure che non esistono e non esisteranno mai
duecentomila hard disk da 4Gb sul pianeta terra ?
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

 duecentomila hard disk da 4Gb sul pianeta terra ?
Ultimo mio messaggio in questa conversazione.
Ho espressamente parlato di problema _intrattabile_, non incomputabile
o incalcolabile, tanto e' vero che la mia proposta di algoritmo di
soluzione (4/1/2001) ben si presta a queste capacita' se compilata in
un opportuno linguaggio di programmazione.
Quando avrai costruito un sistema di calcolo atto a memorizzare 2^50 o
piu' byte (ovviamente, come certo saprai, per risparmiare fatica
inutile e tempo prezioso ci sono gia' modelli computazionali teorici e
reali - distribuiti) prova a far girare il programma in questione, e
fammi un fischio non prima di 35 anni ovvero il tempo minimo
necessario alla fine della computazione, ipotizzando un _RISULTATO_
(non istruzione eseguita) ottenuto ogni microsecondo - ovvero 1
milione di risultati memorizzati al secondo.
Questo caratterizza un problema "intrattabile".
La tua replica in merito alla possibile capacita' di memorizzazione in
diverse centinaia di migliaia di hard disk, mi trova bonariamente
disilluso: parlare in termini di spazio come grandezza di riferimento
per la complessita' o computabilita' di un problema e' assai
rischioso, perche' sono sicuro che converrai con me sul fatto che
PSPACE contiene la classe NP (vedi: Bovet, Crescenzi, Bertossi, ...)
Passo e chiudo.

Passo e chiudo.
nano-nano vostra obesita'
