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
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:
Voci correlate
Collegamenti esterni