
\documentclass[10pt]{article}
%\usepackage{fullpage}
\usepackage{amsmath, amsfonts}
\usepackage[utf8]{inputenc}
%\usepackage[T1]{fontenc}
\usepackage[francais]{babel}

\usepackage{algorithm}
\usepackage{algorithmic}

\usepackage{color}


%\usepackage{pstricks, pst-node, pst-tree}
%\addtolength{\textheight}{1cm}
%\addtolength{\hoffset}{-1cm}
%\addtolength{\textwidth}{1.5cm}
\usepackage{graphicx}
%\usepackage[]{fullpage}
%\usepackage[francais]{babel}
%\addtolength{\topmargin}{-2.8cm}
\textheight=22cm
\addtolength{\oddsidemargin}{-2.5cm}
\textwidth=17cm
\parindent=0cm
%\addtolength{\topmargin}{-0,5cm}

\newtheorem{exercice}{ \textbf{ Exercice}}
\newcommand{\EXO}[1]{\begin{exercice} \ \em}
	\newcommand{\EXOF}{\end{exercice}}
\newcommand{\e}{\mbox{ \ \ }}
\renewcommand{\qquad}{\mbox{ \ \ \ \ }}
\newcommand{\Sn}{\mbox{${\cal S}_n$}}
\newcommand{\EQL}{\begin{eqnarray*}}
	\newcommand{\ENL}{\end{eqnarray*}}
\newcommand{\Card}{{\rm Card}\,}
\newcommand{\et}{\mbox{ \ \ et \ \ }}
\newcommand{\pere}{{\tt pere}\,}
\newcommand{\fils}{{\tt fils}\,}
\newcommand{\pred}{{\tt pred}\,}
\renewcommand{\succ}{{\tt succ}\,}
\renewcommand{\min}{{\tt min}\,}

\newcommand{\marque}{{\tt marque}\,}
\newcommand{\ora}{\overrightarrow}

%\renewcommand{\degre}{{\tt degre}\,}
\parindent=0cm


\begin{document}
	
\section{Questions diverses {\small [4 points]}}

\textbf{ Question 1.} 
Donner un codage de compression optimal pour l’ensemble
des fréquences 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énéraliser la réponse pour proposer un codage optimal lorsque les fréquences sont les
$n$ premiers nombres de Fibonacci vérifiant $F_n = F_{n-1} + F_{n-2}$.\\


\textbf{ Question 2.} 
Soit $T$ un texte contenant $256$ caractères, 
et tel que la fréquence d’apparition est a peu près la même pour chaque caractère.
Plus formellement, la fréquence maximale vaut moins de deux fois la fréquence 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 {\small [4 points]}}

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é à 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écessaire,
correspond à 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 étapes intermédiaires,
l’algorithme LZW sur l'exemple précédent,
en précisant l'endroit du texte où l'on passe de la phase adaptative
(jusqu'à ce que la table soit remplie) à la phase stationnaire.
Donner le codage obtenu.\\

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


\textbf{ Question 3.} 
Avec les mêmes hypothèses sur la taille de la table de hachage et la taille de l'alphabet,
décoder 
\begin{center}
	\texttt{2 3 1 4 5 7 3 6}
\end{center}
et expliciter intégralement le décodage.\\





\end{document}
