\section{Questions diverses}

\textbf{ Question 1.} 
Donner un codage de compression optimal pour l'ensemble
des fr\'equences suivantes, correspondant aux $8$ premiers nombres de Fibonacci :
\begin{center}
	\texttt{a:1 \quad b:1 \quad c:2 \quad d:3 \quad e:5 \quad f:8 \quad g:13 \quad g:21}.
\end{center}
Justifier que ce codage est optimal.\\
G\'en\'eraliser la r\'eponse pour proposer un codage optimal lorsque les fr\'equences sont les
$n$ premiers nombres de Fibonacci v\'erifiant $F_n = F_{n-1} + F_{n-2}$.\\


\textbf{ Question 2.} 
Soit $T$ un texte contenant $256$ caract\`eres, 
et tel que la fr\'equence d'apparition est a peu pr\`es la m\^eme pour chaque caract\`ere.
Plus formellement, la fr\'equence maximale vaut moins de deux fois la fr\'equence minimale.
Montrer que dans ce cas, le codage de Huffman
n'est pas plus efficace qu'un codage de longueur fixe sur $8$ bits.


\section{Compression LZW}

On travaille sur un alphabet de 2 symboles, \texttt{x} et \texttt{y}.
On initialise le codage LZW avec \texttt{x} $\rightarrow 1$
(le symbole \texttt{x} est rang\'e \`a l'adresse $1$ dans la table)
et \texttt{y} $\rightarrow 2$.
On travaille avec une table de hachage de taille $7$,
et pour simplifier, on suppose que chaque nouvelle valeur de hachage n\'ecessaire,
correspond \`a la prochaine case libre dans la table. 
On se propose d'encoder le texte suivant avec l'algorithme LZW :
\begin{center}
	\texttt{xxxyyyyxyxyyyyxxy}.
\end{center}


\textbf{ Question 1.} 
Appliquer, en donnant toutes les \'etapes interm\'ediaires,
l'algorithme LZW sur l'exemple pr\'ec\'edent,
en pr\'ecisant l'endroit du texte o\`u l'on passe de la phase adaptative
(jusqu'\`a ce que la table soit remplie) \`a la phase stationnaire.
Donner le codage obtenu.\\

\textbf{ Question 2.} 
Dessiner l'arbre digital obtenu par ce codage. 
Quelle est l'utilit\'e de l'arbre en compl\'ement de la table de hachage ?\\


\textbf{ Question 3.} 
Avec les m\^emes hypoth\`eses sur la taille de la table de hachage et la taille de l'alphabet,
d\'ecoder 
\begin{center}
	\texttt{2 3 1 4 5 7 3 6}
\end{center}
et expliciter int\'egralement le d\'ecodage.\\

