Ciência da Computação information-theory
Perguntas com a marcação «information-theory»
Perguntas sobre a teoria da informação, entropia e conteúdo de informação de várias fontes
O código Morse sem espaços é exclusivamente decifrável?
Todas as seqüências de código Morse são decifráveis ​​de maneira única? Sem os espaços, ......-...-..---.-----.-..-..-.. poderia ser, Hello Worldmas talvez a primeira letra seja uma 5- na verdade, parece muito improvável que uma sequência arbitrária de pontos e traços deva ter uma tradução única. Pode-se usar a desigualdade de Kraft, …
54 information-theory coding-theory
Os PRNGs podem ser usados ​​para compactar magicamente coisas?
Esta ideia me ocorreu quando criança aprendendo a programar e encontrando PRNG pela primeira vez. Ainda não sei o quão realista é, mas agora há troca de pilhas. Aqui está o esquema de uma criança de 14 anos para um incrível algoritmo de compactação: Pegue um PRNG e faça o …
Os algoritmos de compactação sem perdas reduzem a entropia?
De acordo com a Wikipedia : A entropia de Shannon mede as informações contidas em uma mensagem em oposição à parte da mensagem que é determinada (ou previsível). Exemplos deste último incluem redundância na estrutura da linguagem ou propriedades estatísticas relacionadas às frequências de ocorrência de pares de letras ou …
35 information-theory data-compression entropy
Simulando uma probabilidade de 1 de 2 ^ N com menos de N bits aleatórios
Digamos que preciso simular a seguinte distribuição discreta: P(X=k)={12N,1−12N,if k=1if k=0P(X=k)={12N,if k=11−12N,if k=0 P(X = k) = \begin{cases} \frac{1}{2^N}, & \text{if $k = 1$} \\ 1 - \frac{1}{2^N}, & \text{if $k = 0$} \end{cases} A maneira mais óbvia é desenhar NNN bits aleatórios e verificar se todos são iguais a …
Compactação eficiente de dados binários simples
Eu tenho um arquivo que contém números binários ordenados de a :2 n - 10 0002n- 12n−12^n - 1 0000000000 0000000001 0000000010 0000000011 0000000100 ... 1111111111 7z não compactou esse arquivo com muita eficiência (para n = 20, 22 MB foram compactados para 300 kB). Existem algoritmos que podem reconhecer …
27 information-theory data-compression
O Código Morse é binário, ternário ou quinário?
Estou lendo o livro: " Código: a linguagem oculta do hardware e software dos computadores " e no capítulo 2 o autor diz: Diz-se que o código Morse é um código binário (literalmente significa dois por dois) porque os componentes do código consistem em apenas duas coisas - um ponto …
27 information-theory coding-theory encoding-scheme
Compactação de dados usando números primos
Recentemente, deparei com o seguinte artigo interessante, que afirma compactar com eficiência conjuntos de dados aleatórios sempre em mais de 50%, independentemente do tipo e formato dos dados. Basicamente, ele usa números primos para construir exclusivamente uma representação de blocos de dados de 4 bytes que são fáceis de descompactar, …
22 information-theory data-compression primes
Comprimindo dois números inteiros sem considerar a ordem
Comparando um par ordenado (x, y) a um par não ordenado {x, y} (conjunto) e, em seguida, informações teoricamente, a diferença é de apenas um bit, pois se x vem primeiro ou y requer exatamente um único bit para representar. Portanto, se recebermos um conjunto {x, y} em que x, …
20 information-theory data-compression
Por que a criptografia com o mesmo teclado único não é boa?
Para criptografar uma mensagem com uma tecla de teclado único faça .m1m1m_1kkkEn c ( m1, k ) = m1⊕ kEnc(m1,k)=m1⊕kEnc(m_1,k) = m_1 \oplus k Se você usar o mesmo para criptografar uma mensagem diferente obtém , e se você executa Xor dos dois textos cifrados, obtém kkkm2m2m_2En c ( m2, …
O que é mais difícil: embaralhar um baralho classificado ou ordenar um baralhado?
Você tem uma matriz de elementos distintos. Você tem acesso a um comparador (a função de caixa preta tomando dois elementos e e retornando verdadeira sse ) e uma fonte verdadeiramente aleatório de bits (a função de caixa preta que não recebe argumentos e retornar um pouco independentemente uniformemente aleatório). …
18 algorithms algorithm-analysis information-theory permutations entropy
Os dados podem ser compactados para um tamanho menor que o limite de compactação de dados de Shannon?
Eu estava lendo sobre algoritmos de compactação de dados e o limite teórico para compactação de dados. Recentemente, encontrei um método de compressão chamado "Combinatorial Entropy Encoding", a idéia principal desse método é codificar o arquivo como os caracteres apresentados no arquivo, suas frequências e o índice de permutação de …
17 information-theory data-compression
Diferença entre "informação" e "informação útil" na teoria algorítmica da informação
De acordo com a Wikipedia : Informalmente, do ponto de vista da teoria algorítmica da informação, o conteúdo da informação de uma string é equivalente ao comprimento da menor representação possível possível dessa string. Qual é a definição rigorosa informal análoga de "informação útil"? Por que a "informação útil" não …
16 information-theory terminology kolmogorov-complexity
Codificação eficiente de quebra-cabeças sudoku
A especificação de qualquer grade 9x9 arbitrária requer a posição e o valor de cada quadrado. Uma codificação ingênua para isso pode fornecer 81 (x, y, valor) trigêmeos, exigindo 4 bits para cada x, y e valor (1-9 = 9 valores = 4 bits) para um total de 81x4x3 = …
16 combinatorics modelling information-theory sudoku
Entropia de Shannon de 0,922, 3 valores distintos
Dada uma sequência de valores , a Entropia de Shannon na base de log chega a . Pelo que entendi, na base a Entropia de Shannon arredondada é o número mínimo de bits em binário para representar um único dos valores.AAAAAAAABCAAAAAAAABCAAAAAAAABC2220.9220.9220.922222 Retirado da introdução nesta página da Wikipedia: https://en.wikipedia.org/wiki/Entropy_%28information_theory%29 Então, …
14 information-theory mathematical-foundations entropy binary
PRNG para gerar números com n bits definidos exatamente
Atualmente, estou escrevendo algum código para gerar dados binários. Eu preciso especificamente gerar números de 64 bits com um determinado número de bits definidos; mais precisamente, o procedimento deve levar cerca de e retornar um número pseudo-aleatório de 64 bits com exatamente n bits definido como 1 e o restante …