Teoria della complessità algoritmica: differenze tra le versioni

Naviga nella cronologia in modo interattivo

Contenuto cancellato Contenuto aggiunto

VisualeWikitesto

Versione delle 23:17, 27 lug 2006 modifica Robmontagna (discussione \| contributi) 400 modifiche ha spostato Teoria della complessità algoritmica a Teoria della complessità computazionale: ci si riferisce di solito alla complessità computazionale, mi pare che questo nome sia più corretto		Versione attuale delle 15:47, 14 feb 2022 modifica annulla Mat4free (discussione \| contributi) Utenti autoverificati 8 005 modifiche m grammatica
(17 versioni intermedie di 14 utenti non mostrate)
Riga 1: La '''teoria della complessità algoritmica''' o '''teoria algoritmica della complessità''' si occupa dello studio della [[complessità descrittiva]] degli [[algoritmi]] e non delle risorse computazionali ([[memoria (informatica)\|memoria]] occupata e tempo di calcolo) necessarie ad eseguirli. #REDIRECT [[Teoria della complessità computazionale]]▼ ▲~~#REDIRECT~~Non va, quindi, confusa con la [[~~Teoria~~teoria della complessità computazionale]]. La teoria algoritmica della complessità è stata sviluppata principalmente da [[Andrej Nikolaevič Kolmogorov\|Kolmogorov]], [[Gregory Chaitin\|Chaitin]] e [[Ray Solomonoff\|Solomonoff]], per questo motivo è nota anche come "teoria K-C-S" dalle iniziali dei tre scienziati. ==Bibliografia== Gli articoli storici dei tre autori sono: * R.J.Solomonoff, A formal theory of inductive inference. Information and Control, 7:1-22 e 224-254, 1964. * A.N.Kolmogorov. Three approaches to the quantitative definition of information. Problems of Information Transmission, 1:1-17, 1965. * G.J.Chaitin. On the length of programs for computing finite binary sequences. Journal of the Association for Computer Machinery, 13:547-569, 1966. Un testo moderno è il seguente: * Ming Li and Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer, 1997. ISBN 0-387-94868-6 In italiano: * Chaitin Gregory J., Alla ricerca di Omega, Adelphi, 2007, ISBN 9788845922053 * Chaitin Gregory J., Teoria algoritmica della complessità, Giappichelli, 2006, ISBN 9788834863985 ==Voci correlate== * [[Juergen Schmidhuber]] ==Collegamenti esterni== * {{cita web \|1=http://www.kolmogorov.com/ \|2=Sito dedicato a Kolmogorov \|accesso=25 ottobre 2007 \|urlarchivio=https://web.archive.org/web/20050115091525/http://kolmogorov.com/# \|dataarchivio=15 gennaio 2005 \|urlmorto=sì }} * {{cita web \|1=http://www.cs.umaine.edu/~chaitin/ \|2=Sito di Chaitin \|accesso=25 ottobre 2007 \|urlarchivio=https://web.archive.org/web/20150215210504/http://www.cs.umaine.edu/~chaitin/# \|dataarchivio=15 febbraio 2015 \|urlmorto=sì }} * {{cita web\|http://www.idsia.ch/~juergen/ray.html\|Sito di Solomonoff}} * {{cita web\|http://www.idsia.ch/~juergen/\|Sito di Schmidhuber}} [[Categoria:Teorie dell'informatica]]