% Document Type: LaTeX
% Master File: TP5.tex
% FILE. . . . . /users/formel2/dicosmo/ACADEMIC/CORSI-DIDATTICA/Algo199798/TP4.tex
% EDIT BY . . . Roberto Di Cosmo
% ON MACHINE. . Verveine.Ens.Fr
% STARTED ON. . Thu Nov 20 15:19:43 1997
\documentclass{article}
\usepackage{a4}
\usepackage{xypic}
\usepackage{francais}
% *****FULLNAME: /users/formel/dicosmo/Paperi/Miei/Definitions/tdenv.tex
% *****EXPORTBEGS: \input{tdenv}
%
% General \ignore{ . . . } macro.
%
\long\def\ignore#1{\relax}
%
% definition rules environment
%
\newenvironment{rules}{\begin{list}{}{\itemindent.3in\labelwidth0in\labelsep10pt\parskip0pt\partopsep0pt\itemsep0pt\topsep0pt\leftmargin0pt}}{\end{list}}
%
% definition of standard Article environment
%
\def\piripi{\par} % cambiare con \endgraf
\newenvironment{bodydouble}[1]{\endgraf\noindent {\bf #1}\em}{\endgraf}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{notation}[theorem]{Notation}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{rem}[theorem]{}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{exercise}{Exercice}[section]
\newtheorem{remark}[theorem]{Remark}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{exmpl}[theorem]{Example}
\newenvironment{example}{\begin{exmpl}\em}{$\qed$\end{exmpl}}
\newenvironment{tinyexample}{\begin{exmpl}\em\twocolscond{\footnotesize\endgraf\smallskip}{\endgraf}}{$\qed$\end{exmpl}}
\newtheorem{defn}[theorem]{Definition}
\newenvironment{definition}{\begin{dfntn}\em}{$\qed$\end{dfntn}}
\newtheorem{lgrthm}[theorem]{Algorithm}
\newenvironment{algorithm}{\begin{lgrthm}\em}{\end{lgrthm}}
\newtheorem{xms}[theorem]{Axioms}
\newenvironment{abstract2}[1]{\small\centerline{#1}\begin{list}{}{\rightmargin=\leftmargin} \item}{ \end{list} \normalsize }
\newenvironment{axioms}{\begin{xms}\em}{\end{xms}}
\newenvironment{proof}{\begin{trivlist}\item[]\hspace{\parindent}{\em Proof.}}{$\qed$\end{trivlist}}
%
%\newenvironment{remark}{\begin{trivlist}\item[]{\bf Remark\ \ }}{\end{trivlist}}
%
\def\qed{\proofbox}
\def\proofbox{\begin{picture}(7,7)%
  \put(0,0){\framebox(7,7){}}\end{picture}}
\def\iff{\mbox{$\leftrightarrow$}}
\def\Iff{\mbox{$\Longleftrightarrow$}}
\def\imp{\mbox{$\rightarrow$}}
\def\revimp{\mbox{$\leftarrow$}}
\def\Imp{\mbox{$\Rightarrow$}}
\def\RevImp{\mbox{$\Leftarrow$}}

\begin{document}
% tp1-enonce.tex
\parindent=0pt
MMFAI\par
Cours de programmation
\bigskip
\bigskip

\centerline {TP num\'ero 4}
\centerline {semaine du 5 janvier 1998}
\bigskip
\bigskip
\bigskip
\centerline{\bf Arbres: codage de Huffman.}
\bigskip
%\section{Le codage de Huffman.}

Le codage de Huffman peut \^etre utilis\'e pour compresser une suite d'\'el\'ements (par
exemple un texte, qui est une suite  de caract\`eres) en rempla\c{c}ant chaque \'el\'ement
par son code,  qui est une s\'equence de  valeurs bool\'eens (dans la r\'ealit\'e, cette
s\'equence sera bien stoqu\'ee dans des octets en m\'emoire, mais pour l'instant on se
contentera de  listes   d'entiers ayant valeur   0  ou  1, pour r\'eutiliser   les
fonctions programm\'ees dans les TP pr\'ec\'edants).  On s'int\'eressera  ici \`a coder et
d\'ecoder des suites de {\tt char}.

\subsection*{Pr\'eliminaires.}

Voyons d'abord le d\'ecodage, qui  est le plus simple \`a  r\'ealiser. Un ``codage  de
Huffman'' est constitu\'e  d'un ensemble de s\'equences  binaires  dont aucune n'est
pr\'efixe d'un autre.  Cela corresponde  tr\`es exactement  aux branches d'un  arbre
binaire, si l'on d\'ecide  de  coder ``gauche'' avec 0   et ``droite'' avec 1  par
exemple,  et il est  bien  raisonnable  que l'on  garde  sur chaque  feuille les
\'el\'ements dont le code correspond \`a la branche qui m\`ene \`a cette feuille.

Plus exactement,  \'etant donn\'e un {\tt chararbre} dont toutes les feuilles sont
diff\'erentes, on peut coder les \'el\'ements qu'il contient de la mani\`ere suivante~:

le chemin qui va de la racine de l'arbre \`a une feuille  peut \^etre repr\'esent\'e par
la  liste des choix  0 ({\it  sous-arbre de gauche})  ou  1 ({\it sous-arbre  de
droite}) effectu\'es a  chaque  n\oe ud interne.    Ceci d\'efinit une injection  de
l'ensemble  des  feuilles de l'arbre   dans  l'ensemble   des {\tt int   liste}.
Appelons {\it ensemble  des codes  valides} l'image de  cette injection.    

Par exemple, le dessin  suivant repr\'esente un arbre avec  des {\tt char} sur les
feuilles~:

\[
\spreaddiagramrows {-1pc}
\diagram
	&\bullet\dlto\drto		&	&	&	\\
a	&		&\bullet\dlto\drto	&	&	\\
	&	e	&	&\bullet\dlto\drto	&	\\
	&		&g	&	&h	\\
\enddiagram
\]

Pour cet  arbre, la liste {\tt  [1; 1; 0]} est  un code valide qui repr\'esente la
feuille {\tt g}.  Par contre, les listes {\tt [1; 1]} et {\tt [1; 0; 0]} ne sont
pas des codes valides.

\subsection*{Le d\'ecodage.} 

\begin{itemize}					
\item  \'Ecrivez une fonction {\tt decode} qui, \'etant donn\'es un {\tt chararbre} et
une {\tt intliste} $L$ qui commence par un code valide, retourne l'\'el\'ement cod\'e 
et le reste de la liste (le suffixe de $L$ qui
n'a pas \'et\'e utilis\'e pour trouver l'\'el\'ement.)  Par exemple,
 {\tt decode} appliqu\'ee \`a l'arbre ci-dessus et la liste {\tt [1; 1;
0; 0]} retourne  {\tt g} et {\tt [0]}.
\smallskip
\item  \'Ecrivez une fonction {\tt decode\_liste} qui, \'etant donn\'es un {\tt chararbre}
et une {\tt intliste} obtenue par concatenation de codes corrects,
retourne la {\tt charliste} des \'el\'ements qu'elle code.
Par exemple, \hbox{\tt decode\_liste} appliqu\'ee \`a l'arbre ci-dessus et la liste
{\tt [1; 1; 0; 0]} retourne la liste {\tt [g;~a]}.
\end{itemize}

\subsection*{L'arbre de Codage.} 

Le codage de Huffman est efficace si l'arbre de d\'epart est bien choisi~: il faut
placer les  \'el\'ements souvent rencontr\'es le  plus proches possible de  la racine.
D\'efinissez une structure  {\tt charintpaire} avec  un champ entier et un  champs
char.  Si  on  a  une {\tt  charintpaire  liste}  de  la  forme {\tt [(elem$_1$,
poids$_1$);  \dots;  (elem$_n$,  poids$_n$)]}, o\`u  les   {\tt elem$_i$} sont les
\'el\'ements qui doivent appara\^{\i}tre dans l'arbre  de Huffman, et les {\tt poids$_i$}
repr\'esentent leur fr\'equence probable dans les textes \`a compresser, il est facile
de construire un arbre de Huffman optimal contenant les {\tt elem$_i$}.
\begin{itemize}
\smallskip

\item D\'efinissez une structure {\tt arbrepoids} avec un champ {\tt int}
      et un champs  {\tt chararbre}.   \'Ecrivez une fonction {\tt coerce}
      qui prend une {\tt charintpaire  liste} en argument et retourne  la
      {\tt  arbrepoids   liste} o\`u  chaque   \'el\'ement  {\tt  elem$_i$} est
      remplac\'e par l'arbre qui \`a un seul n\oe ud contenant {\tt elem$_i$}
      et o\`u les couples sont tri\'ees par poids croissants.
\smallskip
      L'algorithme suivant permet de construire un arbre optimal~:

      On choisit dans la liste deux arbres $a_1$ et $a_2$ de poids $p_1$ et $p_2$
      minimaux.

      On construit l'arbre $A$ suivant~:

\[
\diagram
        &		&\bullet\dlto\drto		&	& \\
        &\stackrel{\displaystyle a_1}{\vdots}	&		&\stackrel{\displaystyle a_2}{\vdots}	&\\
\enddiagram
\]

On lui  donne le poids  $p_1 + p_2$,  et on consid\`ere  alors la liste de d\'epart,
moins les couples {\tt ($a_1$, $p_1$)} et {\tt ($a_2$,  $p_2$)}, plus {\tt ($A$,
$p_1  + p_2$)} ins\'er\'ee comme  il faut pour pr\'eserver   l'ordre des poids.  Cette
nouvelle liste  contient un \'el\'ement de moins  que la  pr\'ec\'edente.  On applique \`a
nouveau la  transformation jusqu'\`a obtenir  une liste r\'eduite  \`a un seul couple.
Elle contient l'arbre optimal.

\smallskip

\item  Programmez une fonction {\tt make\_huff} qui prend une {\tt charintpaire
       liste} en argument, et qui retourne un arbre de Huffman optimal
       pour cette liste.
\item  \'Ecrivez une fonction qui prend un arbre de Huffman en argument, 
       un argument de type {\tt char} et renvoie la {\tt intliste}
       qui m\`ene \`a cet \'el\'ement dans l'arbre donn\'e.
\item  \'Ecrivez une fonction qui prend un arbre de Huffman en argument, 
       un argument de type {\tt charliste } et renvoie la {\tt intliste}
       qui est le codage de Huffman de la suite de {\tt char}.
\item  Pensez-vous qu'on pourrait rendre vos fonctions ``polymorphes'',
       c'est \`a dire capable de manipuler des codages pour des \'el\'ements arbitraires
       et non pas seulement des {\tt char}? Si oui, est-ce que votre solution
       \`a des d\'esavantages? Lesquels?
\item  Comment \'ecririez vous le vrai programme de codage qui travaille sur
       des r\'eels fichiers?
\end{itemize}

\end{document}
En C il est possible pour l'utilisateur de d\'efinir des structures de donn\'ees
en utilisant la construction \verb|struct| qui corresponde aux declarations de
types enregistrement en CamlLight ou Pascal.\\

Par exemple, 
%
\begin{verbatim}
struc date {
            int annee;
            int mois;
            int jour;
};
\end{verbatim}
%
d\'efinit un   type   enregistrement \verb|date| avec  des   champs  \verb|annee|,
\verb|mois| et \verb|jour| de type \verb|int|.\\

Ensuite, on peut d\'eclarer des variables de ce nouveau type:
%
\begin{verbatim}
struct date d;
\end{verbatim}
%
et la d\'eclaration alloue directement la m\'emoire n\'ecessaire pour la structure.\\
On peut acceder aux champs par l'op\'erateur de s\'el\'ection \verb|.| comme en CamlLight:
%
\begin{verbatim}
d.annee=1997;
d.mois=11;
d.jour=24;
printf("La date est %d/%d/%d\n",d.jour,d.mois,d.annee);
\end{verbatim}
%
Enfin, on peut utiliser la construction \verb|typedef| pour assigner un nouveau
nom \`a tout type d\'ej\`a existant, avec la m\^eme syntaxe que pour une d\'eclaration \verb|extern|
ou \verb|static|, i.e.\\
\mbox{}\hfill \verb|typedef| $typepreexistant$ \verb|NOUVEAU(X)NOM(S)|\hfill\mbox{}\\
Par exemple:
%
\begin{verbatim}
typedef struct date DATE, *DATEPTR;
\end{verbatim}
%
permet ensuite de d\'eclarer
%
\begin{verbatim}
DATE d;      /* struct date d   */
DATEPTR pd;  /* struct date *pd */
\end{verbatim}
%
On peut aussi tout faire en un seul coup, comme dnas l'exemple du type list plus avant.\\
%
Notons enfin que quand on manipule des structures on le fait  le plus souvant en
passant aux fonctions des pointeurs sur des structures et non pas les structures
elles m\^emes (on n'a pas  envie de recopier des  structures \`a chaque coup!), donc
on   trouve    souvent  la   notation   syntaxique  \verb|pd->annee|    qui  est
\emph{exactement \'equivalente \`a} \verb|(*pd).annee|.

\section{Manipulation de listes}

Nous souhaitons    nous constituer ici  une librairie   de fonctions utiles pour
travailler   sur  des  listes.  Un  approche algebrique   aux  types  de donn\'ees
developp\'ee au  debut  des ann\'ees  80   sugg\`ere de  decomposer les  fonctions qui
manipulent une structure de  donn\'ees en differentes  classes: ``constructeurs'',
``destructeurs'' et ``testeurs'' (des noms qui expliquent d\'ej\`a tout).

\begin{exercise}[Le type de donn\'ee intlist]
Pour la structure de donn\'ees \verb|intintlist| d\'efinie  comme suit

\begin{verbatim}
typedef struct intlist{
        int data;
        struct intlist *suivant;
} intlist;
\end{verbatim}

d\'efinissez les fonctions suivantes:\\
Coonstructeurs:
\begin{itemize}
  \item \verb|intlist *nil()| construit une ``intliste vide''
  \item \verb|intlist *cons(int data, intlist *l)| construit la intliste {\tt cons(data,l)}
        (la concatenation de la donn\'ee data en t\^ete de la intliste l)
\end{itemize}
Testeurs:
\begin{itemize}
  \item \verb|int isnil(intlist *l)| renvoie 1 si la intliste est vide et 0 sinon
\end{itemize}
Destructeurs:
\begin{itemize}
  \item \verb|int hd(intlist *l)| renvoie le premier \'el\'ement de la intliste {\tt l}
  \item \verb|intlist *tl(intlist *l)| renvoie le reste de la intliste {\tt l} apr\`es avoir enlev\'e
                                 le premier \'el\'ement
\end{itemize}
\end{exercise}

\begin{exercise}[Append et reverse]
\'Ecrivez une fonction \verb|void printintlist(intlist *l)| qui imprime les \'el\'ements d'une intliste.
En utilisant \emph{uniquement} les fonctions definies ci-dessus, \'ecrire une fonction 
%
\verb|intlist *append(intlist *l1, intlist *l2)| qui concatene deux listes, et une fonction
\verb|intlist *rev(intlist *l)|
qui renverse une intliste.\\
Testez vos fonctions.
\end{exercise}

\section{Manipulation d'arbres}

\begin{exercise}[Le type de donn\'ee intarbre]
Pour la structure de donn\'ees \verb|intarbre| d\'efinie  comme suit

\begin{verbatim}
typedef struct intarbre {
                int data;
                struct intarbre *fg;
                struct intarbre *fd;
} intarbre, *iaptr;
\end{verbatim}

d\'efinissez les fonctions suivantes:\\
Constructeurs:
\begin{itemize}
  \item \verb|iaptr empty()| construit un ``intarbre vide''
  \item \verb|iaptr node(int data, iaptr g, iaptr d)| construit l'intarbre {\tt node(data,g,d)}
\end{itemize}
Testeurs:
\begin{itemize}
  \item \verb|int isempty(iaptr a)| renvoie 1 si l'intarbre est vide et 0 sinon
\end{itemize}
Destructeurs:
\begin{itemize}
  \item \verb|int data(iaptr a)| renvoie la donn\'ee dans la racine de {\tt a}
  \item \verb|iaptr filsg(iaptr a)| renvoie le sousarbre gauche de {\tt a}
  \item \verb|iaptr filsd(iaptr a)| renvoie le sousarbre droit de {\tt a}
\end{itemize}
\end{exercise}

\begin{exercise}[Parcours d'arbres]
\'Ecrivez une fonction \verb|intlist *infixintarbre(iaptr a)| qui renvoie la liste des noeuds d'un intarbre
dans l'ordre de la visite infixe.\\
\'Ecrivez ensuite une fonction \verb|void printintarbre(iaptr a)| qui imprime les \'el\'ements d'un intarbre
d'entiers dans cet ordre (utilisez \verb|printintlist|).\\
\end{exercise}

\begin{exercise}[Miroir d'un arbre]
\'Ecrivez une fonction \verb|iaptr miroir(iaptr a)| qui construit l'arbre miroir de {\tt a},
en utilisant \emph{uniquement} les fonctions definies ci-dessus.\\
Testez votre fonction.
\end{exercise}

\begin{exercise}[Modification en place]
\'Ecrivez  maintenant,  en accedant   directement  \`a la   structure, une  fonction
\verb|void echange(iaptr a, iaptr b)| qui \'echange les arbres point\'es par {\tt a}
et {\tt b}.\\ Re\'ecrivez  la fonction \verb|miroir|  \`a l'aide de cette  fonction.
Commentez sur la diff\'erence des deux approches.
\end{exercise}

{\bf N'oubliez pas de vous d\'econnecter avant d'abandonner le clavier (voir notes du stage Unix).}
\end{document}
