computer-science - propiedades - que significa entropia en informatica
¿Cuál es la definición de entropía de informática? (16)
Escuché que las personas hacen un uso incorrecto de las definiciones termodinámicas de entropy wrt CS.
Por ejemplo, Entropy definitivamente está aumentando en este sistema.
¡Cuando lo que quieren decir es que este código está empeorando cada vez más!
Recientemente comencé un curso de compresión de datos en mi universidad. Sin embargo, encuentro que el uso del término "entropía" tal como se aplica a la ciencia de la computación es bastante ambiguo. Por lo que puedo decir, se traduce aproximadamente a la "aleatoriedad" de un sistema o estructura.
¿Cuál es la definición correcta de "entropía" de la informática?
La entropía es como un código hash para los investigadores de virus también. Al obtener menos entropía, significaría que probablemente sea un código cifrado o comprimido que podría ser potencialmente un virus.
Un binario estándar tendría una entropía más alta que uno comprimido o encriptado.
La entropía puede significar cosas diferentes:
En informática, la entropía es la aleatoriedad recogida por un sistema operativo o aplicación para su uso en criptografía u otros usos que requieren datos aleatorios. Esta aleatoriedad a menudo se recolecta de fuentes de hardware, ya sean preexistentes como los movimientos del mouse o generadores de aleatoriedad especialmente provistos.
En la teoría de la información, la entropía es una medida de la incertidumbre asociada a una variable aleatoria. El término en sí mismo en este contexto generalmente se refiere a la entropía de Shannon, que cuantifica, en el sentido de un valor esperado, la información contenida en un mensaje, generalmente en unidades tales como bits. De manera equivalente, la entropía de Shannon es una medida del contenido de información promedio que falta cuando no se conoce el valor de la variable aleatoria
Entropía en la compresión de datos
La entropía en la compresión de datos puede denotar la aleatoriedad de los datos que está ingresando al algoritmo de compresión. Cuanto más entropía, menor es la relación de compresión. Eso significa que cuanto más aleatorio sea el texto, menor podrá comprimirlo.
La entropía de Shannon representa un límite absoluto para la mejor compresión sin pérdidas posible de cualquier comunicación: el tratamiento de mensajes codificados como una secuencia de variables aleatorias independientes y distribuidas de forma idéntica, el teorema de la codificación de fuentes de Shannon muestra que, en el límite, la longitud promedio del más corto La posible representación para codificar los mensajes en un alfabeto dado es su entropía dividida por el logaritmo de la cantidad de símbolos en el alfabeto objetivo.
Siempre encontré entropía en el sentido de Shannon Entropy.
De http://en.wikipedia.org/wiki/Information_entropy :
En la teoría de la información, la entropía es una medida de la incertidumbre asociada con una variable aleatoria. El término en sí mismo en este contexto generalmente se refiere a la entropía de Shannon, que cuantifica, en el sentido de un valor esperado, la información contenida en un mensaje, generalmente en unidades tales como bits. Equivalentemente, la entropía de Shannon es una medida del contenido de información promedio que falta cuando uno no conoce el valor de la variable aleatoria.
de la Universidad de México
La noción teórica de información de entropía es una generalización de la noción física. Hay muchas formas de describir Entropy. Es una medida de la aleatoriedad de una variable aleatoria. También es una medida de la cantidad de información que contiene una variable aleatoria o proceso estocástico. También es un límite inferior en la cantidad que se puede comprimir un mensaje. Y, finalmente, es la cantidad promedio de preguntas sí / no que deben formularse sobre una entidad aleatoria para determinar su valor.
Ecuación para entropía en una aplicación de muestra para el cálculo de probabilidad:
es la suma de todos los valores de un rv de la probabilidad de que ese valor sea multiplicado por el log de ese problema (es decir, p (x) logp (x)). Esta ecuación puede derivarse de los primeros principios de las propiedades de la información.
En términos de compresión y teoría de la información, la entropía de una fuente es la cantidad promedio de información (en bits) que pueden transmitir los símbolos de la fuente. Hablando informalmente, cuanto más improbable es un símbolo, más sorprendente es su apariencia.
Si su fuente tiene dos símbolos, digamos A y B , y son igualmente probables, entonces cada símbolo transmite la misma cantidad de información (un bit). Una fuente con cuatro símbolos igualmente probables transmite dos bits por símbolo.
Para un ejemplo más interesante, si su fuente tiene tres símbolos, A , B y C , donde los dos primeros son dos veces más probables que el tercero, entonces el tercero es más sorprendente, pero también es menos probable. Hay una entropía neta de 1.52 para esta fuente, como se calcula a continuación.
Calcula la entropía como la "sorpresa media", donde la "sorpresa" para cada símbolo es su probabilidad multiplicada por el registro binario negativo de la probabilidad:
binary
symbol weight probability log surprise
A 2 0.4 -1.32 0.53
B 2 0.4 -1.32 0.53
C 1 0.2 -2.32 0.46
total 5 1.0 1.52
El negativo del registro binario se usa (por supuesto) porque los registros de valores entre 0 y 1 (exclusivo) son negativos.
La entropía tiene muchos significados típicamente en informática. Depende del contexto. En la entropía de seguridad significa la cantidad de aleatoria que coloca, por ejemplo, cuando genera una clave privada, muchas aplicaciones le piden que mueva el mouse para generar entropía. Esto genera entropía al tomar el elemento "humano" de la aleatoriedad y lo agrega al proceso de generación de la clave.
Ahora también hay una definición para la ingeniería de software de entropía. Esta definición representa un código obsoleto o un código que ha tenido muchos desarrolladores que lo escriben. Normalmente se usa en referencia a cuando es hora de refactorizar su proyecto de software. "El código para este proyecto tiene una enorme cantidad de entropía porque muchas de las personas que lo mantuvieron no están actualmente en el proyecto".
Aquí hay un tercer ejemplo de uso que también recordé. En el tema del recocido simulado (en lo que respecta a la ciencia de la computación), la entropía se describe como la cantidad de descomposición que ha ocurrido durante la evaluación del algoritmo.
Sin embargo, para responder a su pregunta, no existe una definición concreta de la palabra "entropía", excepto las que puede encontrar en un diccionario. La forma en que la ciencia de la computación tiende a aplicar ese término depende del contexto del término que se usa y de lo que se está aplicando.
Mi definición favorita, con un enfoque más práctico, se encuentra en el Capítulo 1 del excelente libro The Pragmatic Programmer: From Journeyman to Master, de Andrew Hunt y David Thomas:
Entropía de software
Si bien el desarrollo de software es inmune a casi todas las leyes físicas, la entropía nos golpea con fuerza. La entropía es un término de la física que se refiere a la cantidad de "desorden" en un sistema. Desafortunadamente, las leyes de la termodinámica garantizan que la entropía en el universo tiende a un máximo. Cuando el desorden aumenta en el software, los programadores lo llaman "podredumbre del software".
Hay muchos factores que pueden contribuir a la putrefacción del software. El más importante parece ser la psicología, o la cultura, trabajando en un proyecto. Incluso si eres un equipo de uno, la psicología de tu proyecto puede ser algo muy delicado. A pesar de los mejores planes y las mejores personas, un proyecto puede experimentar la ruina y la decadencia durante su vida. Sin embargo, hay otros proyectos que, a pesar de las enormes dificultades y los reveses constantes, logran combatir con éxito la tendencia de la naturaleza hacia el desorden y logran salir bastante bien.
...
...
Una ventana rota.
Una ventana rota, dejada sin reparar durante un período considerable de tiempo, inculca en los habitantes del edificio una sensación de abandono, una sensación de que los poderes fácticos no se preocupan por la construcción. Entonces otra ventana se rompe. La gente comienza a tirar basura. Graffiti aparece. El daño estructural serio comienza. En un espacio de tiempo relativamente corto, el edificio se daña más allá del deseo del propietario de arreglarlo, y la sensación de abandono se convierte en realidad.
La "Teoría de la ventana rota" ha inspirado a los departamentos de policía de Nueva York y otras ciudades importantes a tomar medidas enérgicas contra las cosas pequeñas con el fin de evitar las cosas importantes. Funciona: mantenerse encima de ventanas rotas, graffiti y otras pequeñas infracciones ha reducido el nivel de delincuencia grave.
Consejo 4
No vivas con ventanas rotas
No deje reparadas las "ventanas rotas" (diseños defectuosos, decisiones incorrectas o código incorrecto). Arregle cada uno tan pronto como se descubra. Si no hay tiempo suficiente para arreglarlo correctamente, entonces obsérvelo. Tal vez pueda comentar el código ofensivo, o mostrar un mensaje "No implementado", o sustituir los datos ficticios en su lugar. Tome medidas para evitar más daños y para demostrar que está al tanto de la situación.
Texto tomado de: http://pragprog.com/the-pragmatic-programmer/extracts/software-entropy
Definición Súper SIMPLE
La palabra entropía se puede definir en una oración:
"La cantidad de información necesaria para describir un sistema".
Imagínese, por ejemplo, la expansión del universo: desde el principio, toda la materia se recopiló en un pequeño punto antes del Big Bang, por lo que podríamos haber descrito el sistema con "toda la materia está dentro de un punto". Si bien hoy en día se requiere mucha más información para describir el sistema (el Universo), uno necesitaría describir todas las posiciones planetarias, sus movimientos, lo que hay sobre ellas, etc. En términos de teoría de la información, la definición también funciona: Por ejemplo: Cuantas más letras agregue a una contraseña (el sistema), más información se necesita para describir la contraseña. Luego puede medirlo en diferentes unidades, por ejemplo, bits o caracteres, como "hello" = 5 caracteres de entropía = 40 bits de entropía (si el charsize es de 8 bits).
De esto también se deduce que cuanta más información tenga, más formas tendrá de organizar esa información. Si tiene 40 bits, hay 2 ^ 40 formas diferentes de organizarlos. Si estamos hablando de contraseñas aquí, entonces, cuanto más arreglos posibles de la información (bits), más tiempo tomará agrietarse (con fuerza bruta o ataques de diccionario).
En palabras más simples, Entropy define la aleatoriedad. Es más como lo impredecible que es algo. En palabras más técnicas, "En computación, la entropía es la aleatoriedad recogida por un sistema operativo o aplicación para su uso en criptografía u otros usos que requieren datos aleatorios. Esta aleatoriedad a menudo se obtiene de fuentes de hardware, ya sean preexistentes como los movimientos del mouse o generadores de aleatoriedad especialmente provistos ", como se define en la wikipedia.
Ahora se puede concluir fácilmente el significado de entropía con respecto a un archivo como la medida de cuánto desordenan los bytes en un archivo. Hay varias unidades usadas para definir la entropía como nat, shannon o hartley. Bueno, la unidad más común utilizada es Shannon. El rango de valores de la entropía de un archivo debe venir de acuerdo con el algoritmo de Shannon de 0 a 8. Entonces, cuando el valor de entropía es cero, uno puede decir que el resultado es cierto. Por el contrario, cuando el valor de entropía es 8, el resultado es más impredecible que podría ser. La fórmula dada por Shannon para medir la aleatoriedad en el resultado de los eventos es:
Entropy = ∑ pi log(1/pi)
donde i es el evento con probabilidad pi .
Esta ecuación siempre dará como resultado entre 0 y 8.
Para obtener más información, vaya a través del enlace: https://www.talentcookie.com/2016/02/file-entropy-in-malware-analysis/
En palabras simples, si conoce las probabilidades de los símbolos en el idioma, puede calcular el contenido de información promedio del símbolo en el idioma.
O
La entropía de un idioma es una medida del contenido de información de un símbolo promedio en el idioma
Considera una moneda justa;
Hay dos símbolos, cada uno con probabilidad 1/2, por lo que la entropía se calcula como
h = - (1/2 * log1 / 2 + 1/2 * log1 / 2) = 1
Es fácil sacar provecho de la entropía. En mi opinión, es un concepto bastante simple y útil .
Básicamente, cuantifica qué, en promedio, aprenderá de un evento, como lanzar una moneda, tomar una instrucción de bifurcación o indexar una matriz.
Al igual que una operación de comparación en el medio de un algoritmo de búsqueda tiene una cierta probabilidad P de tomar una rama, y 1-P de tomar la otra.
Supongamos que P es 1/2, ya que está en una búsqueda binaria. Entonces, si tomas esa rama, sabes 1 bit más que antes, porque log (2/1), base 2, es 1. Por otro lado, si tomas la otra rama también aprendes 1 bit.
Para obtener la cantidad promedio de información que aprenderá, multiplique lo que aprenda en la primera rama por la probabilidad de que tome esa rama, más lo que aprenda en la segunda rama multiplicada por la probabilidad de esa rama.
1/2 veces 1 bit, más 1/2 veces 1 bit, es 1/2 bit más 1/2 bit, o total 1 bit de entropía. Eso es lo que puede esperar aprender en promedio de esa decisión.
Por otro lado, supongamos que está haciendo una búsqueda lineal en una tabla de 1024 entradas.
En la primera prueba ==, la probabilidad de SÍ es 1/1024, por lo que la entropía de SÍ en esa decisión es
1/1024 times log(1024/1)
o 1/1024 * 10 = aproximadamente 1/100 bit.
Entonces, si la respuesta es SÍ, aprendes 10 bits, pero la probabilidad de eso es aproximadamente 1 en mil.
Por otro lado, NO es mucho más probable. Es entropía es
1023/1024 * log(1024/1023)
o aproximadamente 1 veces más o menos = aproximadamente cero.
Suma los dos y, en promedio, aprenderás aproximadamente 1/100 de una decisión.
Es por eso que la búsqueda lineal es lenta. La entropía (cuánto puede esperar aprender) en cada decisión es demasiado pequeña, ya que tendrá que aprender 10 bits para encontrar la entrada en la tabla.
La entropía en ciencias de la computación comúnmente se refiere a qué tan aleatoria es una cadena de bits. La siguiente pregunta es sobre hacer eso preciso:
Aquí hay una gran explicación alternativa para la entropía en la teoría de la información.
La entropía es una medida de incertidumbre involucrada en hacer una predicción .
También podemos describir la entropía como lo sorprendidos que estaríamos si obtenemos un resultado después de hacer nuestra predicción inicial.
Digamos que tenemos una moneda doblada que nos da una cabeza el 99% del tiempo y una cola el 1% del tiempo. Dado que solo hay un uno por ciento de posibilidades de obtener una cola, nos sorprendería mucho si realmente obtuviéramos una cola. Por otro lado, no será demasiado sorprendente si tenemos una cabeza, ya que tenemos un 99 por ciento de probabilidades de obtener una cabeza.
supongamos que tenemos una función llamada Surprise(x) que nos daría la sorpresa de cada resultado; entonces podemos promediar la cantidad de sorpresa en una distribución de probabilidad. Esta cantidad promedio de sorpresa también podría usarse como una medida de cuán inciertos estamos. Esta incertidumbre se llama entropía .
la entropía se refiere al grado en que un software se reconfigura de vez en cuando en función de los requisitos del cliente, por lo que el costo de remodelarlo para cumplir con los requisitos del cliente se vuelve máximo.