1) Le calcul de l'entropie de AAAAAAHH donne (en utilisant l'approximation log2(3) ≈ 1.56) :
Tandis que l'entropie de AHAHAHAH vaut
et est donc plus grande que la précédente. En général, plus la distribution des lettres est uniforme
(i.e., proche de (1/2; 1/2) pour 2 lettres), plus l'entropie est grande.
2) Avec le même calcul que ci-dessus, on obtient H(ABBA) = H(BEBE) = 1.
3) H(CALC) = 1/2 log2(2) + 1/2 log2(4) = 1.5, tandis que
4) Sans faire de calcul, on peut dire que H(MEDITERRANNEE) > H(MEDETERRENNEE), vu que
dans la seconde expression, toutes les voyelles ont été remplacées par une seule et même lettre. Il y a
donc moins de diversité dans cette seconde expression.
5) H(EPFL) = H(EEPPFFLL) = log2(4) = 2.
1) Non, ce code n'est pas optimal: il utilise 2 bits pour distinguer les symboles 3 et 4, alors qu'un seul
aurait suffi.
2) Les longueurs des mots de code sont les suivantes: l (1) = 1; l (2) = 2; l (3) = 4; l (4) = 4, et donc
L'inegalité de Kraft est donc bien verifiée par ce code.
3) Oui, c'est un code sans préfixe (en accord avec le point 2).
4) Non, l'algorithme de Shannon-Fano générerait le code
c(1) = 0; c(2) = 10; c(3) = 110; c(4) = 111;
et la séquence S correspondante serait (par exemple): S = 11112234.
1) Ce code est singulier, car pour une même séquence codée 01 (par exemple), on ne sait pas si le
message d'origine est "YE" ou "N".
2) Etant singulier, ce code ne peut pas être sans préfixe.
3) Le décodeur reçoit la séquence 0110 et trouve donc les phrases possibles suivantes:
YEEY, YEO, NEY, NO
Il ne peut pas décoder le message d'origine (on pourrait objecter ici que le seul mot du dictionnaire
(anglais) parmi les quatre ci-dessus est bien "NO" et donc que le message est décodable, mais pour cela, on doit faire appel à un autre type d'information que le code en lui-même, ce qu'on voudrait justement
éviter).
1) On sait que la longueur moyenne par lettre du code est toujours plus grande ou égale à l'entropie
du message, qui vaut:
2) Le code qu'on obtient par l'algorithme de Shannon-Fano est (par exemple):
3) Sa longueur moyenne par lettre vaut
4) Si on utilisait un code avec le même nombre de bits pour chaque lettre, on aurait alors besoin de 3 bits par lettre, car il y a 5 lettres différentes et log2(5) ≈ 2.32 > 2. On aurait donc besoin de 3 x 12 = 36 bits au total pour représenter la séquence.
5) H(S') = 1.
6) Vu que C et D sont chacun représentés par 4 bits dans le code de Shannon-Fano établi à partir de la séquence ABRACADABRAA, la longueur moyenne par lettre de ce code vaudrait 4, ce qui est clairement plus grand que H(S') + 1 = 2. Il n'est donc pas vrai ici que L(C) < H(S') + 1, mais c'est normal, car C ne correspond pas au code de Shannon-Fano établi pour la sequence S' (pour la séquence S ci-dessus, par contre, le code de Shannon-Fano satisfait bien la relation L(C) <= H(S)+1; on a même L(C) ≈ H(S) + 0.05, donc un code avec une longueur moyenne très proche de l'entropie de la séquence, comme c'est souvent le cas en pratique).
Pour partager en deux parties égales le nombre de possibilités, la meilleure première question à poser
est: "est-ce une case vide?" (32 possibilités sur 64) Si ma reponse est oui, vous aurez trouvé la réponse en une seule question. Si ma reponse est non, vous devrez encore poser d'autres questions. La deuxième question peut être par exemple (vu qu'il y a le même nombre de pions et de pièces sur l'échiquier): "la case est-elle occupée par un pion?" Si ma réponse est oui, il faut encore poser une troisième question qui est: "le pion est-il noir?" et vous obtiendrez forcément la réponse à la devinette posée. Si ma réponse à votre deuxieme question est non, alors vous devrez également poser une troisième question: "la pièce est-elle noire?", et vous obtiendrez à nouveau la réponse à la devinette posée après cette troisième question.
Au total, vous aurez posé en moyenne
