En la teoría de la computación, la complejidad de Kolmogórov es el tamaño o cantidad de información del programa de computadora más corto que produce cierto resultado. 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.
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, un pequeño programa informático 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.
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 salidas secuencias 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.
Comparación de códigos generadores del conjunto Mandelbrot en RosettaCode.
Datos:Q1456811
Multimedia:Kolmogorov complexity
Noviembre 05, 2021
complejidad, kolmogórov, teoría, computación, complejidad, kolmogórov, tamaño, cantidad, información, programa, computadora, más, corto, produce, cierto, resultado, debe, nombre, andréi, kolmogórov, complejidad, kolmogórov, también, denomina, complejidad, desc. En la teoria de la computacion la complejidad de Kolmogorov es el tamano o cantidad de informacion del programa de computadora mas corto que produce cierto resultado Debe su nombre a Andrei Kolmogorov La complejidad de Kolmogorov tambien se denomina complejidad descriptiva o complejidad de Kolmogorov Chaitin complejidad estocastica o entropia algoritmica Detalle de una parte del conjunto de Mandelbrot Almacenar esta imagen sin mas en color de calidad 24 bit requeriria 1 62 millones de bits sin embargo un pequeno programa informatico puede reproducir estos 1 62 millones de bits usando la definicion del conjunto de Mandelbrot Por esa razon la complejidad de Kolmogorov es de hecho mucho menor que 1 62 millones de bits Para definir la complejidad de Kolmogorov primero debe especificarse un lenguaje descriptivo para las secuencias o cadenas Tal lenguaje puede basarse en cualquier lenguaje de programacion como Lisp o Pascal Si P es un programa que genera como salidas secuencias de tipo x entonces P es una descripcion del conjunto de x La longitud de la descripcion 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 numero entero n que aparezca en el programa P es la cantidad de bits requeridos para representar n esto es log2n Vease tambien EditarTeoria algoritmica de la informacion Teoria de la complejidad computacionalEnlaces externos EditarComparacion de codigos generadores del conjunto Mandelbrot en RosettaCode Datos Q1456811 Multimedia Kolmogorov complexity Obtenido de https es wikipedia org w index php title Complejidad de Kolmogorov amp oldid 130391473, wikipedia, wiki, leyendo, leer, libro, biblioteca,
