Complejidad de Kolmogórov
- Complejidad de Kolmogórov
-
Detalle de una parte del
conjunto de Mandelbrot. Almacenar esta imagen sin más en color de calidad 24-bit requeriría 1,62 millones de bits; sin embargo, una pequeño programa informática puede reproducir estos 1,62 millones de bits, usando la definición del conjunto de Mandelbrot. Por esa razón, la complejidad de Kolmogórov, es de hecho mucho menor que 1,62 millones de bits.
En la teoría de la computación, la complejidad de Kolmogórov es una medida de la cantidad de recursos computacionales necesarios para describir una cierta cantidad de información, debe su nombre a Andréi Kolmogórov. La complejidad de Kolmogórov también se denomina complejidad descriptiva o complejidad de Kolmogoróv-Chaitin, complejidad estocástica, o entropía algorítmica.
Para definir la complejidad de Kolmogórov, primero debe especificarse un lenguaje descriptivo para las secuencias o cadenas. Tal lenguaje puede basarse en cualquier lenguaje de programación como Lisp o Pascal. Si P es un programa que genera como outputs secuenciaas de tipo x, entonces P es una descripción del conjunto de x. La longitud de la descripción es la longitud de P como secuencia de caracteres. Para determinar la longitud de P, debe darse cuenta de las longitudes de todas las subrutinas empleadas en P. La longitud de cualquier número entero n que aparezca en el programa P es la cantidad de bits requeridos para representar n, esto es, log2n.
Wikimedia foundation.
2010.
Mira otros diccionarios:
Andréi Kolmogórov — Andréi Kolmogórov. Andréi Nikoláyevich Kolmogórov (Андрей Николаевич Колмогоров) (Tambov, 25 de abril de 1903 Moscú, 20 de octubre de 1987) fue un matemático ruso que hizo progresos importantes en los campos de la teoría de la probabilidad y de… … Wikipedia Español
Andrei Kolmogorov — Andrey Nikolaevich Kolmogorov (Андрей Николаевич Колмогоров) (25 de abril de 1903 20 de octubre de 1987) fue un matemático ruso que hizo progresos importantes en los campos de la teoría de probabilidad y de la topología. Trabajó al principio de… … Enciclopedia Universal
Teoría algorítmica de la información — La teoría algorítmica de la información, es una teoría científica de las ciencias de la computación teórica, que en contraste con la clásica teoría de la información, se basa en la complejidad de Kolmogorov para la determinación del contenido de… … Wikipedia Español
Navaja de Ockham — La navaja de Ockham (a veces escrito Occam u Ockam), principio de economía o principio de parsimonia (lex parsimonia), es un principio metodológico y filosófico atribuido a Guillermo de Ockham (1280 1349), según el cual cuando dos teorías en… … Wikipedia Español
Constante de Chaitin — La constante de Chaitin es la probabilidad de que un programa elegido al azar detenga correctamente una máquina de Turing determinada. Al ser una probabilidad ha de ser un número entre 0 y 1. Sea P el conjunto de todos los programas que se… … Wikipedia Español
Algoritmo de Karatsuba — El algoritmo de Karatsuba es un procedimiento para multiplicar números grandes eficientemente, que fue descubierto por Anatolii Alexeevitch Karatsuba en 1960 y publicado en 1962.[1] [2] El algoritmo consigue reducir la múltiplicación de dos… … Wikipedia Español
Anexo:Matemáticos importantes — En esta lista de matemáticos importantes se presenta una selección de matemáticos desde la antigüedad hasta el presente. La selección se orienta por los aportes científicos, utilizando como criterio para definir el grado de notoriedad la atención … Wikipedia Español
Algoritmo divide y vencerás — En la cultura popular, divide y vencerás hace referencia a un refrán que implica resolver un problema difícil, dividiéndolo en partes más simples tantas veces como sea necesario, hasta que la resolución de las partes se torna obvia. La solución… … Wikipedia Español
Aleatoriedad — Puntos esparcidos aleatoriamente sobre un plano bidimensional. Sus puntos más cercanos están resaltados en rojo. La aleatoriedad es un c … Wikipedia Español
Yuri Petrovich Ofman — (Ю. П. Офман) es un matemático ruso que trabaja en teoria de complejidad. Yuri obtuvo su Doctorado en la Universidad Estatal de Moscú, supervisado por Andréi Kolmogórov. Publicaciones «О приближенной реализации непрерывных функций на автоматах»… … Wikipedia Español
