Complexitat de Kolmogórov

De Viquipèdia
Salta a la navegació Salta a la cerca
Detall d'una part del conjunt de Mandelbrot. Emmagatzemar aquesta imatge sense més en color de qualitat 24-bit requeriria 1,62 milions de bits; no obstant això, un petit programa informàtic pot reproduir aquests 1,62 milions de bits usant la definició del conjunt de Mandelbrot. Per aquesta raó, la complexitat de Kolmogórov és de fet molt menor que 1,62 milions de bits.

En la teoria de la computació, la complexitat de Kolmogórov és una mesura de la quantitat de recursos computacionals necessaris per poder descriure una certa quantitat d'informació, deu el seu nom a Andréi Kolmogórov. La complexitat de Kolmogórov també es denomina complexitat descriptiva o complexitat de Kolmogoróv-Chaitin, complexitat estocàstica, o entropia algorítmica.[1]

Per poder definir la complexitat de Kolmogórov, primer s'ha d'especificar un llenguatge descriptiu per a les seqüències o cadenes. Aquest llenguatge pot basar-se en qualsevol llenguatge de programació com ara Lisp o Pascal. Si P és un programa que genera com sortides seqüències de tipus x, llavors P és una descripció del conjunt de x. La longitud de la descripció és la longitud de P com a seqüència de caràcters. Per determinar la longitud de P, ha d'adonar-se de les longituds de totes les subrutines emprades en P. La longitud de qualsevol nombre enter n que aparegui en el programa P és la quantitat de bits requerits per representar n, això és, log2n..[2]

Referències[modifica]

  1. Kolmogorov, Andrey «On Tables of Random Numbers». Sankhyā Ser. A., 25, 1963, pàg. 369–375.
  2. Kolmogorov, Andrey «On Tables of Random Numbers». Theoretical Computer Science, 207, 2, 1998, pàg. 387–395. DOI: 10.1016/S0304-3975(98)00075-9.

Bibliografia[modifica]

  • Blum, M. «On the size of machines». Information and Control, 11, 3, 1967, pàg. 257. DOI: 10.1016/S0019-9958(67)90546-3.
  • Brudno, A. Entropy and the complexity of the trajectories of a dynamical system., Transactions of the Moscow Mathematical Society, 2:127{151, 1983.
  • Cover, Thomas M. and Thomas, Joy A., Elements of information theory, 1st Edition. New York: Wiley-Interscience, 1991. ISBN 0-471-06259-6. 2nd Edition. New York: Wiley-Interscience, 2006. ISBN 0-471-24195-4.
  • Lajos, Rónyai and Gábor, Ivanyos and Réka, Szabó, Algoritmusok. TypoTeX, 1999. ISBN 963-279-014-6
  • Li, Ming; Vitányi, Paul An Introduction to Kolmogorov Complexity and Its Applications. Springer, 1997. ISBN 978-0387339986. 
  • Yu Manin, A Course in Mathematical Logic, Springer-Verlag, 1977. ISBN 978-0-7204-2844-5
  • Sipser, Michael, Introduction to the Theory of Computation, PWS Publishing Company, 1997. ISBN 0-534-95097-3.

Vegeu també[modifica]

Enllaços externs[modifica]