Los programas escritos en cualquier lenguaje de programación son secuencias finitas de caracteres (conocidos como string), algunos, gracias a su sintaxis, nos permiten crear programas más compactos y flexibles, en otros casos, tendremos que añadir muchos más caracteres para llegar a una misma solución (no lo diré, bueno si, como en Java). ¿Cómo se mide la complejidad de la información en un
nov 21, 2022·editado nov 21, 2022Gustado por Camilo Chacón Sartori
En un eventual lenguaje en el que cualquier número en base decimal puede convertirse a binario de forma "natural"
1047552.toB <-- 11 caracteres
1864135.toB <-- 11 caracteres
341725.toB <-- 10 caracteres
Y en un lenguaje en el que lo normal fuese expresar los números en hexadecimal
FFC00.toB <- 9 caracteres
1C71C7.toB <-9 caracteres
536DD.toB <- 9 caracteres
Casualmente, el más aleatorio resulta ser el más corto :-/
En realidad, empaquetar como número decimal o hexadecimales es una forma de expresar con menos caracteres la misma información incrementando el número de símbolos y aunque el cambio de base no es la forma más eficiente de elegir símbolos, supone una mejora (a primera vista)
Encontrar un conjunto de símbolos S eficiente con el que representar una secuencia de "1" y "0" mediante el algoritmo de Huffman, supongo, que tiene una relación directa con la complejidad de Kolmogórov (cuanto menos aleatorio, menos símbolos son necesarios).
Como siempre, Camilo, complicándo la vida un ratito a tus lectores
Curioso tema. Cuando estuve estudiando la historia de FORTRAN me llamó la atención que la mayoría de matemáticos hechos programadores, no confiaban en programación automática porque decían que no optimizaban el código generado. Eso fue cierto para la mayoría de compiladores hasta la llegada de FORTRAN.
Quizás la complejidad no debería medir el código escrito en el lenguaje a alto nivel, sino el código a ejecutar por la máquina. En ese caso, dependería no solo de la habilidad del programador para expresar un código de forma escueta sino también del compilador por optimizar ese código a su forma más breve.
Sobre el último código, no me pude resistir a ver que era una secuencia octal representando 1, 2, 3, 3, 3, 4 y 5. Así que escribí este código:
>>> '{0:021b}'.format(0o1233345)
'001010011011011100101'
No obstante, es un código peor que escribir tan solo la cadena de caracteres.
Por otro lado, no debemos perder el foco de que el código escrito no se hace para la máquina, sino para las personas. Cuando medimos la complejidad computacional no se tiene en cuenta la extensión del código sino solo el procesamiento que de ese código deberá hacer la máquina, mientras que esta complejidad mide de forma específica la cantidad de código a leer. Sin tener en cuenta de que hay lenguajes como C, donde se puede escribir:
for (i=0; s[i]!=\0; i++);
Siendo "s" una cadena de texto, la variable "i" un entero que se inicia al valor 0 y se incrementa en cada vuelta de "for" hasta encontrar el valor nulo o fin de cadena y obtenemos en "i" el tamaño de la cadena. Es breve, pero no claro. ¿Es útil? Sin duda, pero sigue siendo tan ofuscado como mucho código escrito en C++ y Perl.
Por eso hay que poner el foco en escribir para las personas, por eso el énfasis en poner comentarios y por eso lenguajes como Java, Ada o COBOL son tan "verbose" y burocráticos.
En un eventual lenguaje en el que cualquier número en base decimal puede convertirse a binario de forma "natural"
1047552.toB <-- 11 caracteres
1864135.toB <-- 11 caracteres
341725.toB <-- 10 caracteres
Y en un lenguaje en el que lo normal fuese expresar los números en hexadecimal
FFC00.toB <- 9 caracteres
1C71C7.toB <-9 caracteres
536DD.toB <- 9 caracteres
Casualmente, el más aleatorio resulta ser el más corto :-/
En realidad, empaquetar como número decimal o hexadecimales es una forma de expresar con menos caracteres la misma información incrementando el número de símbolos y aunque el cambio de base no es la forma más eficiente de elegir símbolos, supone una mejora (a primera vista)
Encontrar un conjunto de símbolos S eficiente con el que representar una secuencia de "1" y "0" mediante el algoritmo de Huffman, supongo, que tiene una relación directa con la complejidad de Kolmogórov (cuanto menos aleatorio, menos símbolos son necesarios).
Como siempre, Camilo, complicándo la vida un ratito a tus lectores
Curioso tema. Cuando estuve estudiando la historia de FORTRAN me llamó la atención que la mayoría de matemáticos hechos programadores, no confiaban en programación automática porque decían que no optimizaban el código generado. Eso fue cierto para la mayoría de compiladores hasta la llegada de FORTRAN.
Quizás la complejidad no debería medir el código escrito en el lenguaje a alto nivel, sino el código a ejecutar por la máquina. En ese caso, dependería no solo de la habilidad del programador para expresar un código de forma escueta sino también del compilador por optimizar ese código a su forma más breve.
Sobre el último código, no me pude resistir a ver que era una secuencia octal representando 1, 2, 3, 3, 3, 4 y 5. Así que escribí este código:
>>> '{0:021b}'.format(0o1233345)
'001010011011011100101'
No obstante, es un código peor que escribir tan solo la cadena de caracteres.
Por otro lado, no debemos perder el foco de que el código escrito no se hace para la máquina, sino para las personas. Cuando medimos la complejidad computacional no se tiene en cuenta la extensión del código sino solo el procesamiento que de ese código deberá hacer la máquina, mientras que esta complejidad mide de forma específica la cantidad de código a leer. Sin tener en cuenta de que hay lenguajes como C, donde se puede escribir:
for (i=0; s[i]!=\0; i++);
Siendo "s" una cadena de texto, la variable "i" un entero que se inicia al valor 0 y se incrementa en cada vuelta de "for" hasta encontrar el valor nulo o fin de cadena y obtenemos en "i" el tamaño de la cadena. Es breve, pero no claro. ¿Es útil? Sin duda, pero sigue siendo tan ofuscado como mucho código escrito en C++ y Perl.
Por eso hay que poner el foco en escribir para las personas, por eso el énfasis en poner comentarios y por eso lenguajes como Java, Ada o COBOL son tan "verbose" y burocráticos.