Je recherche une référence pour le résultat suivant: Ajouter deux entiers dans la représentation factorisée est aussi difficile que factoriser deux entiers dans la représentation binaire habituelle. (Je suis presque sûr que c'est là-bas parce que c'est quelque chose que je me demandais à un moment...
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...
Il est facile de voir que pour tout nnn il existe un mappage 1-1 FFF de {0,1} n à {0,1} n + O ( log n ) de telle sorte que pour tout x le vecteur F ( x ) est " équilibré ", c'est-à-dire qu'il a un nombre égal de 1 et de 0. Est-il possible de définir un tel F pour que, étant donné x, nous pouvons...
Soit un alphabet, c'est-à-dire un ensemble fini non vide. Une chaîne est une séquence finie d'éléments (caractères) de Σ . Par exemple, { 0 , 1 } est l'alphabet binaire et 0110 est une chaîne pour cet alphabet.ΣΣ\SigmaΣΣ\Sigma{0,1}{0,1} \{0, 1\}011001100110 Habituellement, tant que contient plus...