Qual é a definição de ciência da computação da entropia?
https://stackoverflow.com/questions/510412
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu recentemente comecei um curso de compressão de dados na minha universidade. No entanto, acho que o uso do termo "entropia" como se aplica a ciência da computação bastante ambígua. Tanto quanto eu posso dizer, que traduz aproximadamente a "aleatoriedade" de um sistema ou estrutura.
O que é a definição adequada da ciência da computação "entropia"?
Solução
A entropia pode significar coisas diferentes:
Em computação, a entropia é a aleatoriedade recolhido por um operacional ou sistema de aplicação para uso em criptografia ou outros usos que exigem dados aleatórios. esta aleatoriedade é muitas vezes coletado de hardware fontes, queridos, quer pré-existentes, tais como os movimentos do rato ou especialmente geradores fornecidos aleatoriedade.
Em teoria da informação, a entropia é uma medir a incerteza associada com uma variável aleatória. O termo por -se, neste contexto, refere-se geralmente para a entropia de Shannon, que quantifica, no sentido de um valor esperado, as informações contido em uma mensagem, geralmente em unidades tais como bits. Equivalentemente, o Shannon entropia é uma medida da uma média de conteúdo de informação é falta quando não se sabe o valor da variável aleatória
Entropia em compressão de dados pode denotar a aleatoriedade dos dados que você está entrando para o algoritmo de compressão. Quanto mais a entropia, menor será a taxa de compressão. Isso significa que quanto mais aleatório o texto é, menor você pode comprimi-lo.
entropia de Shannon representa um limite absoluto sobre o melhor possível compressão sem perdas de qualquer comunicação: o tratamento de mensagens para ser codificada como uma sequência de independente e identicamente distribuídos aleatória variáveis, fonte de Shannon codificação teorema mostra que, no limite, o comprimento médio da menor possível representação para codificar o mensagens em um determinado alfabeto é sua entropia dividido pelo logaritmo o número de símbolos no alvo alfabeto.
Outras dicas
A minha definição favorita, com um enfoque mais prático, é encontrado no capítulo 1 do livro excelente A Pragmatic Programmer: From Journeyman para Mestre por Andrew Hunt e David Thomas:
Software Entropy
Enquanto o desenvolvimento de software é imune de quase todas as leis da física, a entropia nos bate forte. A entropia é um termo de física que se refere à quantidade de "Desordem" em um sistema. Infelizmente, as leis da termodinâmica garantia que a entropia no universo tende para um máximo. quando desordem aumentos de software, programadores chamá-lo de "podridão software."
Existem muitos fatores que podem contribuir para rot software. A maioria um importante parece ser a psicologia, ou cultura, no trabalho em um projeto. Mesmo se você é uma equipe de um, a psicologia de seu projeto pode ser uma coisa muito delicada. apesar da melhores planos e as melhores pessoas, um projeto ainda pode experimentar ruína e decaem durante o seu tempo de vida. No entanto, há são outros projectos que, apesar enormes dificuldades e constante contratempos, natureza combater com êxito do tendência para a desordem e conseguem sair muito bem.
...
...
Uma janela quebrada.
Uma janela quebrada, esquerda não reparados para qualquer comprimento substancial de tempo, instila nos habitantes da a construção de um sentimento de abandono-a sentido de que os poderes que não fazer se preocupam com o edifício. Assim, uma outra janela é quebrada. As pessoas começam jogar lixo. aparece graffiti. Grave dano estrutural começa. Em um espaço relativamente curto de tempo, o edifício for danificado além do do proprietário deseja corrigi-lo, eo sensação de abandono se torna realidade.
A "Teoria Indicador quebrado" tem departamentos de polícia inspirados em Nova York e outras grandes cidades de crack para baixo nas coisas pequenas, a fim de manter fora as coisas grandes. Funciona: manter no topo das janelas quebradas, grafite, e outras pequenas infrações reduziu o nível de crime grave.
Dica 4
Não viva com Windows quebrado
Não deixe "janelas quebradas" (bad projetos, decisões erradas, ou pobre código) não reparados. Corrigir cada um o mais rapidamente uma vez que é descoberto. Se não houver tempo suficiente para corrigi-lo corretamente, em seguida, embarcar-lo. Talvez você pode comente o código incorreto, ou exibir uma mensagem "não implementado", ou dados substituto fictícios vez. Leva algumas medidas para evitar mais danos e para mostrar que você está no topo da situação.
Texto retirado de: http://pragprog.com/the-pragmatic- programador / extratos / software entropia
(fonte: mit.edu )
As informações noção teórica de A entropia é uma generalização do noção física. Existem muitos caminhos para descrever a entropia. É uma medida da aleatoriedade de um aleatória variável. É também uma medida da quantidade de informação que um aleatório variável ou processo estocástico contém. É também um limite inferior sobre a mensagem quantidade um pode ser comprimido. E, finalmente, é o número médio de perguntas sim / não que precisam ser perguntado sobre um aleatório entidade para determinar o seu valor.
Equação de entropia em uma aplicação de exemplo para o cálculo da probabilidade:
é a soma de todos os valores de um rv da probabilidade de que os tempos de valor o log de que prov (i. p (x) logP (x)). Esta equação pode ser derivado de primeiros princípios do Propriedades de informação.
Eu sempre encontrou entropia no sentido de Shannon Entropia.
A partir http://en.wikipedia.org/wiki/Information_entropy :
Em teoria da informação, a entropia é uma medida da incerteza associada com uma variável aleatória. O termo, por si só, neste contexto, refere-se normalmente para a entropia de Shannon, que quantifica, no sentido de um valor esperado, a informação contida numa mensagem, normalmente em unidades tais como bits. Equivalentemente, a entropia de Shannon é uma medida do conteúdo da informação média, um está faltando quando não se sabe o valor da variável aleatória.
Em termos de compressão e a teoria da informação, a entropia de uma fonte é o valor médio de informação (em bits) que os símbolos a partir da fonte pode transmitir. Informalmente falando, o símbolo a mais improvável é, mais surpreender sua aparência traz.
Se a sua fonte tem dois símbolos, A digamos e B, e eles são igualmente prováveis, então cada símbolo transmite a mesma quantidade de informações (um pouco). Uma fonte com quatro igualmente prováveis ??símbolos transmite dois bits por símbolo.
Para um exemplo mais interessante, se sua fonte tem três símbolos, A, B e C, onde os dois primeiros são duas vezes mais provável como o terceiro, em seguida, o terceiro é mais surpreendente, mas também é menos provável. Há uma entropia líquida de 1,52 para esta fonte, conforme calculado abaixo.
Você calcular a entropia como a "surpresa média", onde a "surpresa" para cada símbolo é a sua probabilidade vezes o log binário negativo da probabilidade:
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
A negativa do log binário é usado (é claro), porque os logs de valores entre 0 e 1 (exclusive) são negativos.
Aqui está uma grande explicação alternativa para entropia na teoria da informação.
A entropia é uma medida de incerteza envolvida na tomada de uma previsão .
Nós também pode descrever a entropia como a forma como surpreendeu que seria se conseguirmos um resultado depois que fizemos a nossa previsão inicial.
Vamos dizer que temos uma moeda dobrada que nos dá uma cabeça de 99% do tempo e uma cauda 1% do tempo. Uma vez que existe apenas uma chance de um por cento de conseguir uma cauda, ??que ficaria muito surpreso se nós realmente obter uma cauda. Por outro lado, ele não vai ser muito surpreendente se tem uma cabeça como já temos uma chance de 99 por cento de obter uma cabeça.
vamos supor que temos uma função chamada Surprise(x) que nos daria a quantidade de surpresa para cada resultado; então podemos calcular a média da quantidade de surpresa em uma distribuição de probabilidade. Esta quantidade média de surpresa também poderia ser usado como uma medida de como incerto somos. Esta incerteza é chamado entropia .
definição simples Super
A palavra entropia pode ser definido em uma frase:
"A quantidade de informações necessárias para descrever um sistema."
Imagine por exemplo a expansão do universo: Desde o início, toda a matéria foi coletado em um pequeno ponto antes do big bang, portanto, poderíamos ter descrito o sistema com "toda a matéria é apenas um ponto." Enquanto hoje significativamente mais informação é necessária para descrever o sistema (o Universo, que é), seria necessário descrever todas as posições planetárias, seu movimento, o que está sobre eles etc ..
Em termos de teoria da informação, a definição também funciona: por exemplo: Quanto mais letras você adicionar a uma senha (o sistema), mais informações são necessárias para descrever a senha. Depois, você pode medi-lo em unidades diferentes, por exemplo, bits ou caracteres, como
"Olá" = 5 caracteres entropia = 40 bits de entropia (se charsize é de 8 bits).
Deste vem também que quanto mais informações você tiver, mais maneiras que você pode organizar essa informação. Se você tem 40 bits, existem 2 ^ 40 maneiras diferentes que podem ser organizadas. Se estamos falando de senhas aqui em seguida, os mais possíveis arranjos de informação (bits), mais tempo vai levar craqueamento (com a força bruta ou ataques de dicionário).
Em palavras mais simples, Entropia define aleatoriedade. É mais como quão imprevisível algo está. Em palavras mais técnicas, “Em computação, a entropia é a aleatoriedade coletados por um sistema operacional ou aplicativo para uso em criptografia ou outros usos que requerem dados aleatórios. Esta aleatoriedade é frequentemente recolhida a partir de fontes de hardware, os quer pré-existentes, tais como os movimentos do rato ou geradores de aleatoriedade especialmente previstas.” como definido pela Wikipedia.
Agora pode-se facilmente concluir o significado da entropia em relação a um arquivo como a medida do quanto desordenada os bytes estão em um arquivo. Existem várias unidades utilizadas para a definição de entropia como nat, Shannon ou Hartley. Bem, a maioria unidade comum utilizado é Shannon. O intervalo de valores de entropia de um arquivo deve entrar como por algoritmo de Shannon é 0 a 8. Assim, quando o valor da entropia é zero, pode-se dizer que o resultado é certo. No contrário, quando o valor da entropia é 8, o resultado é mais imprevisível que poderia ser. A fórmula dada por Shannon para medir aleatoriedade em resultado de eventos é:
Entropy = ∑ pi log(1/pi)
que i é o evento com probabilidade pi .
Esta equação sempre resultará em entre 0 a 8.
Para obter mais informações, acesse através do link: https: //www.talentcookie.com/2016/02/file-entropy-in-malware-analysis/
entropia refere-se à extensão em que um software é remodelada, ocasionalmente, baseando-se as necessidades dos clientes, por conseguinte, o custo para adaptação para reqrments atender clientes torna-se máximo.
A entropia é como um código de hash para pesquisadores de vírus também. Menos entropia que você começa, isso significaria que ele é provavelmente criptografados ou código que poderia ser potencialmente ser um vírus comprimido.
Um binário padrão teria uma entropia mais elevada do que um compactados ou criptografados.
Entropia tem muitos significados normalmente em Ciência da Computação. Depende do contexto. Em meio entropia de segurança quanto randomality você colocar, por exemplo, quando você gera uma chave privada muitas aplicações pedir-lhe para mover o mouse para gerar entropia. Isso gera entropia, tendo o elemento "humano" de randomality e adiciona-lo para o processo de hashing de gerar a chave.
Agora, há também uma defnição para a engenharia da entropia software. Essa definição representa fora do código de data ou código que tem tido muitos desenvolvedores escrevê-lo. Normalmente usado em referência a quando se está perto tempo para refatorar seu projeto de software. "O código para este projeto tem uma quantidade enorme de entropia, porque muitos dos indivíduos que mantinham não estão no projeto atualmente".
Aqui está um terceiro exemplo de uso que me lembrei também. No tópico de recozimento simulado (tanto quanto a ciência da computação está em causa), a entropia é descrito como a quantidade de decadência que aconteceu durante a avaliação do algoritmo.
Eu acho que para responder a sua pergunta, porém, não há uma definição concreta da palavra 'entropia', exceto para os que você pode encontrar em um dicionário. Como ciência da computação tende a aplicar esse prazo depende do contexto do termo que está sendo usado e que ele está sendo aplicado.
É fácil fazer um grande negócio fora de entropia. Para minha mente é uma simples href="https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it/630142#630142"> muito .
Basicamente, quantifica o que, em média, você vai aprender a partir de um evento, como jogar uma moeda, tomando uma instrução de desvio, ou indexar um array.
Como uma operação de comparação no meio de um algoritmo de busca tem uma certa probabilidade P de tomar um ramo, e 1-P de tomar o outro.
P Suponha que é 1/2, como é em uma busca binária. Então, se você tomar esse ramo, sabe 1 pouco mais do que você fez antes, porque log (2/1), base 2, é 1. Por outro lado, se você tomar o outro ramo você também aprender um pouco.
Para obter a quantidade média de informação que você vai aprender, multiplique o que aprender sobre os primeiros tempos do ramo a probabilidade de tomar esse ramo, mais o que aprender no segundo tempo do ramo a probabilidade de que se ramificam.
1/2 vezes um bit, além de 1/2 vezes um pouco, é pouco mais 1/2 1/2 bits, ou total de um pouco de entropia. Isso é o que você pode esperar para saber, em média, a partir dessa decisão.
Por outro lado, suponha que você está fazendo pesquisa linear em uma tabela de 1024 entradas.
No primeiro teste ==, a probabilidade de SIM é 1/1024, de modo a entropia do SIM em que a decisão é
1/1024 times log(1024/1)
ou 1/1024 * 10 = cerca de 1/100 bit.
Então, se a resposta for sim, você aprende 10 bits, mas a chance de que é cerca de 1 em cada mil.
Por outro lado, o NO é muito mais provável. É entropia é
1023/1024 * log(1024/1023)
ou cerca de 1 vezes cerca de zero = cerca de zero.
Adicione os dois juntos, e, em média, você vai aprender sobre 1/100 de um pouco sobre essa decisão.
É por isso que busca linear é lento. A entropia (o quanto você pode esperar para aprender) em cada decisão é muito pequeno, desde que você está indo ter que aprender 10 bits para encontrar a entrada na tabela.
Entropy em ciência da computação comumente se refere a como aleatória uma seqüência de bits é. A pergunta seguinte é sobre como fazer essa preciso:
Como faço para calcular a entropia aproximada de uma cadeia de bits?
Em palavras simples se você sabe as probabilidades de símbolos no langauge, pode-se calcular o teor médio de informações de símbolo na língua.
ou
A entropia de uma língua é uma medida do conteúdo de informação de um símbolo média no idioma
Considere uma moeda honesta;
Existem dois símbolos, cada um com probabilidade 1/2 assim entropia é calculada como
h = - (1/2 * log1 / 2 + 1/2 * log1 / 2) = 1
eu ouvi abusar as definições termodinâmicas de entropia w.r.t CS.
por exemplo. Entropia é definitivamente aumentando neste sistema.
Quando o que eles querem dizer é este código está ficando cada vez pior!
