Teoria della complessità algoritmica: differenze tra le versioni

Versione delle 06:10, 10 giu 2011

Versione attuale delle 15:47, 14 feb 2022

(8 versioni intermedie di 7 utenti non mostrate)

Riga 1:

La '''Teoriateoria della Complessitàcomplessità algoritmica''' o '''Teoriateoria algoritmica della complessità''' si occupa dello studio della [[complessità descrittiva|complessità ''descrittiva'']] degli [[algoritmi]] e non delle risorse computazionali ([[memoria (informatica)|memoria]] occupata e tempo di calcolo) necessarie ad eseguirli.

Non va, quindi, confusa con la [[Teoriateoria della complessità computazionale]].

La '''Teoriateoria 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"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==

Riga 22:

==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]]