Questions en théorie de l'information
Quels sont vos exemples préférés dans lesquels la théorie de l’information est utilisée pour prouver de façon simple une déclaration combinatoire nette? Certains exemples auxquels je peux penser sont liés aux limites inférieures pour les codes localement décodables, par exemple, dans cet article:...
De manière informelle, la complexité de Kolmogorov d'une chaîne est la longueur d'un programme le plus court qui génère x . Nous pouvons définir une notion de 'chaîne aléatoire' en l'utilisant ( x est aléatoire si K ( x ) ≥ 0,99 | x | ) Il est facile de voir que la plupart des chaînes sont...
Cette question a été posée à Jeannette Wing après sa présentation de PCAST sur la science informatique. «Du point de vue de la physique, y a-t-il un volume maximal d'informations que nous pouvons avoir?» (Une question intéressante pour la communauté informatique théorique, car je pense que cela...
La complexité du préfixe de Kolmogorov (c'est-à-dire que est la taille du programme d'auto-délimitation minimal qui génère ) a plusieurs fonctionnalités intéressantes:xK( x )K(x)K(x)Xxx Cela correspond à une intuition de donner aux chaînes avec des motifs ou une structure une complexité inférieure...
Je recherche des codes correcteurs d'erreurs du type suivant: codes binaires à débit constant, décodable à partir d'une fraction constante d'erreurs, par un décodeur réalisable en tant que circuit booléen de taille , où est la longueur de codage.O(N)O(N)O(N)NNN Quelques antécédents: Spielman, dans...
Le code de Huffman pour une distribution de probabilité est le code de préfixe avec la longueur moyenne pondérée minimale du mot de code , où est la longueur du ème mot de code. C'est un théorème bien connu que la longueur moyenne par symbole du code Huffman est comprise entre et , où est...
Dans la théorie de l'information quantique, la distance entre deux canaux quantiques est souvent mesurée en utilisant la norme du diamant. Il existe également un certain nombre de façons de mesurer la distance entre deux états quantiques, comme la distance de trace, la fidélité, etc. L'...
La complexité de l'information a été un outil très utile dans la complexité de la communication, principalement utilisée pour réduire la complexité de la communication des problèmes distribués. Existe-t-il un analogue de la complexité des informations pour la complexité des requêtes? Il existe de...
Dans l'implémentation d'un filtre Bloom, l'approche traditionnelle nécessite plusieurs fonctions de hachage indépendantes. Kirsch et Mitzenmacher ont montré que vous n'en avez besoin que de deux et que vous pouvez générer le reste sous forme de combinaisons linéaires. Ma question est: quelle est...
Dernièrement, j'ai eu affaire à des algorithmes liés à la compression, et je me demandais quel était le meilleur taux de compression pouvant être atteint par la compression de données sans perte. Jusqu'à présent, la seule source que j'ai pu trouver sur ce sujet était Wikipedia: La compression sans...
La plupart d'entre nous connaissent - ou du moins ont entendu parler - l'entropie de Shannon d'une variable aléatoire, H(X)=−E[logp(X)]H(X)=−E[logp(X)]H(X) = -\mathbb{E} \bigl[ \log p(X)\bigr] , et toutes les mesures théoriques de l'information connexes telles que l'entropie relative, informations...
Lemme: En supposant une équivalence éta, nous avons cela (\x -> ⊥) = ⊥ :: A -> B. Preuve: ⊥ = (\x -> ⊥ x)par eta-équivalence, et (\x -> ⊥ x) = (\x -> ⊥)par réduction sous lambda. Le rapport Haskell 2010, section 6.2 spécifie la seqfonction par deux équations: seq :: a -> b -> b...
L'algorithme DEFLATE populaire utilise le codage Huffman au-dessus de Lempel-Ziv. En général, si nous avons une source aléatoire de données (= entropie 1 bit / bit), aucun encodage, y compris Huffman, n'est susceptible de le compresser en moyenne. Si Lempel-Ziv était "parfait" (ce qu'il approche...
L'entropie de Shannon est généralement utilisée pour prouver les résultats du codage de canal. Même pour les résultats de séparation source-canal, l'entropie shannon est utilisée. Étant donné l'équivalence entre les notions d'information de Shannon (global) et de Kolmogorov (local), y a-t-il eu une...
Il y a un chercheur montrant que l'effacement d'un bit doit consommer de l'énergie, maintenant y a-t-il des recherches sur la consommation moyenne d'énergie d'un algorithme avec une complexité de calcul ? Je suppose que la complexité de calcul F ( n ) est corrélée à la consommation moyenne...
Je cherche une borne sur l'entropie de la somme de deux variables aléatoires discrètes indépendantes X et Y . Naturellement, H ( X + Y ) ≤ H ( X ) + H ( Y ) ( ∗ ) Cependant, appliqué à la somme de n variables aléatoires Bernoulli indépendantes Z 1 , … , Z n , cela donne H ( Z 1 +H( X+...
Supposons que nous ayons une fonction f:Zn2→Rf:Z2n→Rf:\mathbb{Z}_2^n \to \mathbb{R} , telle que ∑x∈Zn2f(x)2=1∑x∈Z2nf(x)2=1\sum _{x\in \mathbb{Z}_2^n} f(x)^2 = 1 (nous pouvons donc penser à {f(x)2}x∈Zn2{f(x)2}x∈Z2n\{ f(x)^2\} _{x\in \mathbb{Z}_2^n} comme une distribution) . Il est naturel de définir...
Je travaille dans un laboratoire de neurosciences computationnelles qui quantifie les informations mutuelles entre paires ou groupes de neurones. Récemment, le patron s'est concentré sur la mesure de la "complexité de la dynamique neuronale". En poursuivant cette ligne de recherche, certaines...
Etant donné un état quantique choisi uniformément au hasard parmi un ensemble de N états mixtes ρ 1 . . . ρ N , quelle est la probabilité moyenne maximale d'identifier correctement A ?ρAρA\rho_ANNNρ1...ρNρ1...ρN\rho_1 ... \rho_NAAA Ce problème peut être transformé en un problème de distinction à...
Fixons et un entier .t > 00<E<10<E<10 E \} mais aussi, peut-être, en utilisant quelques coordonnées de l'ensemble { i | c je≤ E}{i | ci≤E}\{ i ~|~ c_i \leq E \} nous pourrions créer un autre bon ensemble! Alors, prouvez-le ou trouvez le bug! en espérant que cela pourrait être un jeu...