Teoria della complessità algoritmica
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 occupata e tempo di calcolo) necessarie ad eseguirli.
Non va, quindi, confusa con la teoria della complessità computazionale.
La teoria algoritmica della complessità è stata sviluppata principalmente da Kolmogorov, Chaitin e Solomonoff, per questo motivo è nota anche come "teoria K-C-S" dalle iniziali dei tre scienziati.
Bibliografia
[modifica | modifica wikitesto]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
[modifica | modifica wikitesto]Collegamenti esterni
[modifica | modifica wikitesto]- Sito dedicato a Kolmogorov, su kolmogorov.com. URL consultato il 25 ottobre 2007 (archiviato dall'url originale il 15 gennaio 2005).
- Sito di Chaitin, su cs.umaine.edu. URL consultato il 25 ottobre 2007 (archiviato dall'url originale il 15 febbraio 2015).
- Sito di Solomonoff, su idsia.ch.
- Sito di Schmidhuber, su idsia.ch.