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

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 modifica

Collegamenti esterni modifica