Discussione:Teoria della complessità computazionale
| Teoria della complessità computazionale | |
|---|---|
| Argomento di scuola secondaria di II grado | |
| Materia | informatica |
| Dettagli | |
| Dimensione della voce | 15 743 byte |
| Progetto Wikipedia e scuola italiana | |
Io toglierei, o per lo meno cambierei la frase:
- "ai fini del calcolo, infatti, un problema risolubile in operazioni non è molto più trattabile al crescere di n di un problema risolubile in operazioni."
Infatti, per n > 58, 2^n aumenta molto più di n^10. È vero che si parla di numeri dell'ordine di 10^17, che per i calcolatori di oggi sono enormi, tuttavia chi sa per il futuro? E comunque è il concetto ad essere errato: asintoticamente un esponenziale è peggiore di qualunque potenza. -- BW Insultami 12:40, Gen 14, 2005 (UTC)
D'accordo con BW. Frieda (dillo a Ubi) 14:34, Gen 14, 2005 (UTC)
Visto che la frase incriminata l'ho scritta io, posso farvi notare che un problema che richiede 58^10 (o 2^58 ...) operazioni non lo potremmo comunque risolvere mai? So perfettamente che (1+epsilon)^x cresce asintoticamente più di x^100000, ma all'atto pratico preferirei un algoritmo del primo tipo. Capisco comunque le ragioni teoriche: vi va bene aggiungere alla frase di cui sopra
È vero che asintoticamente la complessità del secondo problema crescerà infinitamente più di quella del primo, ma nessun calcolatore costruibile in questo universo potrà arrivare al punto in cui avverrà il "sorpasso".
?? --.mau. (ca m' disa...) 15:05, Gen 14, 2005 (UTC)
Sono anche io d'accordo con BW, inoltre non capisco se la proposta fatta dall'autore sia una presa in giro, cosa intende per 'sorpasso'? Se un pentium 4 fa 3 miliardi di operazioni al secondo in quattro anni e mezzo ne fa 58^10. Quindi in un tempo finito. E poi come si fa a supporre che in un prossimo futuro i computer non possano diventare molto piu' potenti (calcolo parallelo? cluster machine? grid computing? vedi www.top500.org )? questa parte di articolo:
Non è detto comunque che un'eventuale dimostrazione del fatto che P = NP possa portare ricadute pratiche immediate: in effetti, per lo meno per quel che riguarda piccoli calcolatori, un algoritmo che opera in tempo O(n10) non è molto migliore di uno che opera in tempo O(2n). Va però detto che nell'ambito dei supercomputer un miglioramento simile sarebbe già molto utile, inoltre l'esperienza maturata finora ha mostrato come una volta che un problema viene portato in P, in tempi abbastanza brevi si trovano algoritmi via via più efficienti per la sua soluzione, vedi ad esempio l'algoritmo per la verifica di primalità AKS, migliorato di di 2 milioni di volte dal 2002 al 2005.
mi sembra sia un opinione personale
- viene mischiata tecnica con teoria
- il discorso che '(1+epsilon)^x cresce asintoticamente più di x^100000' vale solo se si considera l'input limitato, se per esempio fossi sicuro che l'input sia lungo meno di 100 allora e' preferibile la prima complessita', ma il fatto e' che non si conosce a priori la lunghezza di un input!
--nicolaennio 17:49, 14 set 2006 (CEST)
spiegazione rollback[modifica wikitesto]
ho effettuato il rollback in quanto il link inserito da Cmazzucc corrisponde alla descrizione di spam. grazie da --DoppiaQ 17:16, 9 giu 2006 (CEST)
Aggiunto link a problema del commesso viaggiatore[modifica wikitesto]
Ciao, ho aggiunto il link alla pagina del "Problema del commesso viaggiatore" che si trovava già su wikipedia ma non era linkato.