Teoria della complessità algoritmica: differenze tra le versioni

Versione delle 16:42, 1 ago 2013

Versione delle 04:13, 30 ago 2013

Riga 1:

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

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

Riga 7:

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

Riga 15:

In italiano:

* Chaitin Gregory J., Alla ricerca di Omega, Adelphi, 2007

* Chaitin Gregory J., Teoria algoritmica della complessità, Giappichelli, 2006