Bonjour,
Dans la deuxième question de l'exercice 1 de l'examen 3 de 2018, on nous demande les meilleures bornes possibles pour l'entropie H(X) du mot. La réponse proposée pour la borne inférieure est L( Huffman(X) ) - 1.
Pourtant, vu l'inégalité L( Huffman (X)) < L(Shannon-Fano (X) ) < H(X) + 1, L(Shannon-Fano (X)) - 1 n'est elle pas une meilleure borne inférieure pour H(X) ? (Les inégalités ne sont pas strictes)
Si, si vous voulez, mais c'est en fait le but du b) :
les points pour b) sont pour savoir que L_Huffman <= L_Shannon-Fano et que L_Shannon-Fano < H(X) + 1
et les points pour a) sont pour savoir que L_Huffman < H(X) + 1 et que H(X) <= log(n)
Si vous me dites les 4, peu importe où (du moment que ça fait sens ! ;-) ), vous avez les points.
A noter que l'inégalité L_Shannon-Fano < H(X) + 1 est effectivement stricte.
Les autres sont larges.