Newsgroup: it.comp.programmare
Titolo: Non è vero che un PC può calcolare tutto

Ciao a tutti devo scrivere una funzione matematica ma non ho mai programmato
nulla in vita mia.
Mia figlia piů grande, durante uno dei suoi eccessi di ottimismo, se ne č
uscita con la affermazione, che un computer puň calcolare qualunque cosa in
pochi secondi se programmato bene.
Chi mi aiuta a dimostrarle che sbaglia ?
Io avrei bisogno di questo :
Vorrei far trovare al mio PC i numeri perfetti e farle vedere come sia poco
esatta la sua affermazione.
I numeri perfetti sono quelli uguali alla somma di tutti i suoi divisori
interi ( eccezion fatta per il numero stesso )
il primo č 6 = 1+2+3
il secondo č 28 = 1+2+4+7+14
Il terzo 496
Il quarto 8128 .....e sapete certo meglio di me che il trentesimo numero
perfetto č di 130100 cifre.
Chiedo :
qualcuno mi scrive il codice di una funzione che controlli se i numeri sono
perfetti partendo da 1...2...3...io non so nulla di programmazione ma mi
hanno detto che con il visual basic posso incollare il codice scritto qui
sul newsgroup e incollarlo in access....poi lo voglio proprio vedere il mio
PC friggere arrancando....il massimo sarebbe che i numeri venissero
visualizzati mentre il computer controlla se sono perfetti cosi dopo la
partenza iniziale baldanzosa si potranno udire gli sfrigolii....
Grazie
Marco

esatta la sua affermazione.
Provato con google?
http://www.google.it/search?q=numeri+perfetti+algoritmo&hl=it&lr=
Il primo risultato ottenuto riporta anche un esempio in Javascript
(che a dire il vero non trova 6).
-- 
Marco Barisione (ICQ 84277092)

 Chi mi aiuta a dimostrarle che sbaglia ?
Be', l'affermazione e' talmente generica che, a mio avviso non le si
puo' dare torto.  Voglio dire: con il termine "computer" puo' intendersi
qualsiasi computer, anche il SuperCray della NASA.
L'uomo ha delle facolta' di calcolo limitate, che difficilmente 
evolveranno nel tempo sino a riuscire a calcolare qualsiasi cosa in
pochi secondi.  Il computer, viceversa, subisce trasformazioni e 
ottimizzazioni continue.
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 tempo, che implicano una grande quantità di calcoli).
Scusa, ma non capisco :)
Stai dicendo: non e' vero che un computer calcoli qualunque cosa,
altrimenti non ci sarebbero computer che lo fanno.
Non mi sembra abbia molto senso :)


 Chi mi aiuta a dimostrarle che sbaglia ? Io avrei bisogno di questo : Vorrei
Ciao, non ti so aiutare con la soluzione dell'algoritmo, ma ti assicuro che
c'e` una intera branca della scienza informatica che sta studiandi una classe
di problemi non calcolabili, quindi ci sono problemi (o calcoli, come vuoi
chiamarli) che non sono risolvibili da un computer.
Adesso potrei sbagliarmi, ma quelli risolvibili mi pare siano gli NP-completi.
Dovresti trovare informazioni su un testo di Ricerca Operativa a livello
universitario.
Ah, non sono risolvibili nemmeno in tempo lungo, sono proprio con computazione
infinita, quindi non serve avere computer piu` potenti.
Bye.

altrimenti non ci sarebbero computer che lo fanno.
Mi riferivo ai pochi secondi :-)


 computazione infinita, quindi non serve avere computer piu` potenti.
no, sbagli. I problemi NP-completi sono quelli non risolvibili in tempo 
polinomiale; in genere esiste pero` una soluzione in tempo esponenziale 
o fattoriale (tipicamente una ricerca esaustiva).
ciao anto
-- 
Antonio Cuni, 19 anni, studente
Brainbench C++ Master: 4.73, higher than 99% of all previous test takers.
C Language: 3.79, higher than 92% of all previous test takers.
Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it

 perfetto è di 130100 cifre.
Quello che sono riuscito a produrre stasera in un momento di relax....
immaginate dove...
/*Numeri perfetti*/
#include <stdio.h>
#include <math.h>
int main(){
 int x, i, div;
 int MAX;
 int cifre;
 printf("\nDi quante cifre deve essere al massimo\nil numero perfetto che
vuoi trovare?\n\n>> ");
 scanf("%d", &cifre);
 MAX=pow(10, cifre);
 for (i=2; i < MAX; i=i+2){
  x=0;
  for(div=1; div <= (i/2); div++){
   if(i % div == 0) x=x+div;
  }
  if(x==i) printf("\n %d", x);
 }
 return 0;
}

 partenza iniziale baldanzosa si potranno udire gli sfrigolii....
Non mi sembra gran che come dimostrazione, tua figlia potrebbe sempre
obbiettare che la colpa e' del programma "non ottimale" e che ne potrebbe
esistere un altro che in tempo minore faccia la stessa cosa...

Ci sono limiti teorici a quello che un computer puo' fare, al di la del
tempo necessario.
Ad esempio un computer non puo' decidere se un _qualsiasi_ programma
termina.
Inoltre ci sono problemi _intrinsecamente_ risolvibili solamente in un tempo
esponenziale rispetto alle dimensioni dell'input. Ovvero in cui basta
aumentare di 1 unita' la lunghezza dell'input per raddoppiare il tempo
necessario a calcolarne l'output.
La crittografia offre un'ampia scelta di tali problemi, ad esempio la
fattorizzazione in numeri primi, etc. etc.

 per raddoppiare il tempo necessario a calcolarne l'output.
Be', ma se si considera un calcolo singolo, e' plausibile 
pensare che ci sia o che ci possa essere una macchina in
grado di risolverlo in breve tempo.


 grado di risolverlo in breve tempo.
No. Alcuni tipi di algoritmi sono intrinsecamente di complessita'
esponenziale; anche avendo a disposizione svariati GHz i tempi necessari
sarebbero non accettabili. Uno di questi problemi e':
Individuare l'insieme delle parti (cioe' l'insieme dei sottoinsiemi) di
un insieme.
Ad es:
se A={1,2,3}
l'output e': {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
Ora si provi ad applicare l'algoritmo all'insieme
A={1,2,3,...,500}
La complessita' e' O(2^n) quindi 2^500=.......


 fattoriale (tipicamente una ricerca esaustiva).
Hai ragione. Ho cannato sia nome che corso universitario... :)
Comunque, quello che ho detto e` vero, e si studia a Teoria della
Calcolabilita`, che e` un corso universitario completamente fondato sul fatto
che esistono tutta una classe di funzioni non calcolabili in modo algoritmico.
Ho trovato questo link (in italiano) che spiega un po' il discorso. Ah, se
avessi studiato di piu` all'Universita`, magari questo esame l'avrei potuto
dare :)
http://tosca.dmi.unict.it/~vs/Prog/books/LezCalc.pdf
Bye.

 La complessita' e' O(2^n) quindi 2^500=.......
Rischiamo di sforare nella filosofia.  Dire che un calcolo non
e' fattibile e' una cosa, dire che ci vuole molto tempo per 
portarlo a termine e' una cosa *molto* diversa.  Non si sta 
parlando della capacita' di risolvere un problema, con un 
input variabile, ma di risolvere un calcolo preciso.
Se un determinato calcolo e' fattibile in un tempo preciso,
per quanto grande esso sia, allora e' possibile pensare che
esista una macchina che riduca il tempo per *quel* calcolo
preciso a pochi secondi (basta che abbia una capacita' di
calcolo molto grande).  La deduzione mi sembra logica, o no?


calcolo molto grande).  La deduzione mi sembra
logica, o no?
Si, dire che "un problema non e' computabile" e "un
problema richiede moltissimo tempo" sono cose diverse. Cio' che voglio dire
e' che per problemi di complessita' esponenziale, anche incrementando di
1000 volte la potenza del processore, il guadagno che ottieni NON supera il
10%. Questo non lo dico io, lo dicono ricerche condotte con metodo
scientifico.
Parliamo ovviamente di macchine assimilabili, per potenza di
calcolo, alla Macchina di Turing (per macchina X assimilabile per potenza
di calcolo alla macchina Y intendo: Se X puo' risolvere il problema P,
allora anche Y puo' risolvere il problema P).
I computer con cui abbiamo a
che fare, dai VIC20 ai MACm ai PC con Pentium IV, Athlon XP, etc, sono
macchine assimiliabili alla MdT come potenza di calcolo, sono macchine
deterministiche.
--------------------------------
Inviato via 
http://usenet.iol.it
 

 calcolo molto grande).  La deduzione mi sembra logica, o no?
La deduzione e' logica pero' e' logico anche dedurre che data una qualsiasi
macchina esista un calcolo non risolvibile in tempi accettabili.
In ogni caso la teoria e' ben diversa dalla realta'; la realta' dimostra
che, pur avendo a disposizione budget illimitati, non si riesca a costruire
macchine che risolvono problemi per cui sono state costruite in tempi brevi.
Ciao, Davide.