\documentclass[12pt]{article}
\usepackage{fullpage,amsmath,amssymb,graphicx}
\usepackage[utf8]{inputenc}
% \usepackage[boxed,french]{algorithm2e}
\usepackage[usenames]{xcolor}
\usepackage{hyperref}
\usepackage{listings}

\newcommand{\tower}[2]{$#1~\|~#2$}

\newenvironment{proof}
      {\noindent\textbf{Proof\ }}
      {\hspace*{\fill}$\Box$\medskip}

\newtheorem{lemma}{Lemma}
\newtheorem{question}{Question}
% \renewcommand{\thesubsection}{\Alph{section}.subsection}

\lstset{
        extendedchars=true,
        showstringspaces=false,
        keywordstyle=\bfseries,
        commentstyle=\itshape,
        frame=single,
        rulecolor=\color{gray},
        language=Python,
        framesep=1mm,
        xleftmargin=1mm,
        xrightmargin=1mm,
        tabsize=2,
        basicstyle=\ttfamily\footnotesize,
        numbers=none,
 literate=
  {á}{{\'a}}1 {é}{{\'e}}1 {í}{{\'i}}1 {ó}{{\'o}}1 {ú}{{\'u}}1
  {Á}{{\'A}}1 {É}{{\'E}}1 {Í}{{\'I}}1 {Ó}{{\'O}}1 {Ú}{{\'U}}1
  {à}{{\`a}}1 {è}{{\`e}}1 {ì}{{\`i}}1 {ò}{{\`o}}1 {ù}{{\`u}}1
  {À}{{\`A}}1 {È}{{\'E}}1 {Ì}{{\`I}}1 {Ò}{{\`O}}1 {Ù}{{\`U}}1
  {ä}{{\"a}}1 {ë}{{\"e}}1 {ï}{{\"i}}1 {ö}{{\"o}}1 {ü}{{\"u}}1
  {Ä}{{\"A}}1 {Ë}{{\"E}}1 {Ï}{{\"I}}1 {Ö}{{\"O}}1 {Ü}{{\"U}}1
  {â}{{\^a}}1 {ê}{{\^e}}1 {î}{{\^i}}1 {ô}{{\^o}}1 {û}{{\^u}}1
  {Â}{{\^A}}1 {Ê}{{\^E}}1 {Î}{{\^I}}1 {Ô}{{\^O}}1 {Û}{{\^U}}1
  {œ}{{\oe}}1 {Œ}{{\OE}}1 {æ}{{\ae}}1 {Æ}{{\AE}}1 {ß}{{\ss}}1
  {ç}{{\c c}}1 {Ç}{{\c C}}1 {ø}{{\o}}1 {å}{{\r a}}1 {Å}{{\r A}}1
  {€}{{\EUR}}1 {£}{{\pounds}}1
}

\begin{document}

\begin{center}
Master 1 STL 4I505 CPA -- Examen Mai 2017
\end{center}

Répondez aux parties A et B sur des copies séparées, pour que nous puissions les corriger en parallèle (A=Christoph Dürr, B=Antoine Genitrini).
Les documents distribués dans le cadre du cours et les notes personnelles sont autorisés.

\appendix


\section{Programmation dynamique et structures de données}

% \subsection{Question exemple (0 points)}

% Cette question sert d'illustration de ce qui est attendu de vous dans la partie A.  N'écrivez rien pour cette question exemple, une réponse type étant donnée.

% Jean-Claude vient d'apprendre à jouer au piano.  Pour l'instant il ne sait  jouer qu'une seule note particulière. Il active un métronome et à chaque tic  il joue ou ne joue pas la note.  Pour que la musique produite soit plus intéressante il ne joue jamais la note pendant deux tics consécutifs.  Maintenant son côté informaticien reprend le dessus, et il se demande, étant donnée $n$ tics, combien de différentes manières existent il de jouer ces notes.   Donnez un programme dynamique de complexité $O(n)$ pour ce problème.

% \subsubsection*{Réponse type}

% \paragraph{Notation}
% Appelons $F_n$ le nombre à calculer.  Formellement $F_n$ est le nombre de chaînes $x\in\{0,1\}^n$, tel qu'il n'existe pas de $1\leq i<n$ avec $x_i=1$ et $x_{i+1}=1$.  Notons ${\cal F}_n$ l'ensemble de ces chaînes.
% Par exemple $F_1=2, F_2=3, F_4=5$.

% \paragraph{Récursion}
% Le cas de base est $F_0=0, F_1=2$.
% L'induction pour $F_n$ avec $n\geq 2$ est $F_n = F_{n-1}+F_{n-2}$.

% \paragraph{Explication} une chaîne $x\in{\cal F}_n$ avec les conditions demandées, termine soit avec $x_n=0$ soit avec $x_n=1$. Dans le cas $x_n=0$, la partie $x_1,\ldots,x_{n-1}$ peut être n'importe quelle chaîne de ${\cal F}_{n-1}$.  Dans le case $x_n=1$, on a forcément $x_{n-1}=0$ et la partie  $x_1,\ldots,x_{n-2}$ peut être n'importe quelle chaîne de ${\cal F}_{n-2}$.

% \paragraph{Complexité}  Il y a $O(n)$ variables à calculer, chacune est déterminée en temps $O(1)$. Ce qui donne au total une complexité en temps de $O(n)$.


\subsection{Cailloux (4 points)}
% http://www.spoj.com/problems/BYTESM2/

Dans une chambre secrète de l'UPMC se trouvent les cailloux philosophaux.  Le sol de la chambre est pavé avec $h\times w$ carrelages carrés, organisés en $h$ lignes de l'entrée (première ligne) au fond de la chambre (dernière ligne) et en $w$ colonnes de gauche à droite.  Sur chacun des carrelages sont posés entre 1 et 100 cailloux.  Vous allez traverser cette chambre de la manière suivante. D'abord vous vous posez sur un des carrelage de votre choix de la première ligne.  Puis vous allez sur un carrelage de la ligne suivante, soit en allant tout droit, soit en allant en diagonale vers la gauche ou vers la droite.  Quand vous avez atteint la dernière ligne, votre traversé de la chambre est terminée.  Sachant que vous allez ramasser tous les cailloux des carrelages que vous traversez, déterminez le nombre maximum de cailloux que vous pourriez ramasser.

Donnez un programme dynamique qui résout ce problème en temps $O(h\cdot w)$, étant donné une matrice $M\in\{1,\ldots,100\}^{h\times w}$.
Prouvez qu'il est correct et qu'il a la complexité attendue.


\begin{figure}[hb]
  \centerline{\includegraphics[width=4cm]{cailloux}}
  \caption{La réponse sur cette grille est 32, ce qui représente $7+1+8+5+4+7$.}
  \label{fig:cailloux}
\end{figure}

% \subsection{Décomposition d'une chaîne (3 points)}
% % http://www.spoj.com/problems/ROCK/

% Un fabriquant de bonbons dispose d'un bâton comestible composé de segments d'un centimètre chacun. Un segment peut être sucré ou acide.  Les segments sont numérotés de 0 à $n-1$. Le bâton est décrit par un tableau $x\in\{0,1\}^n$, où $x[j]=1$ ssi le j-ème segment est sucré.  Le fabriquant peut découper le bâton en plusieurs morceaux, chacun étant constitué d'un nombre entier de segments.  Les enfants achètent un morceau seulement s'il contient strictement plus de segments sucrés que de segments acides.
% Quelle est la longueur totale des morceaux vendables que le fabriquant peut produire à partir d'un bâton décrit par $x$~? Donnez un programme dynamique qui résout ce problème en temps $O(n^2)$.

% Donnez le cas de base, la récursion et expliquez votre solution.

% \begin{tabular}{lll}
%   entrée & sortie & explication\\ \hline
%   10011 0 0 0 101 000 1 & 9 &  \underline{10011} {000} \underline{101} 000 \underline{1}
%   \\ \hline
%   0010111101100000 & 13 & \underline{0010111101100} 000
%   \\ \hline
% \end{tabular}

% \section{Pavage par des dominos (4 points)}
% % http://www.spoj.com/problems/GNY07H/

% On vous donne une grille de composée de 4 lignes et de $n$ colonnes avec $n\geq 2$.
% On veut \emph{paver} cette grille avec des \emph{dominos}, chaque domino couvre exactement 2 cases adjacentes verticalement ou horizontalement.  Paver veut dire que chaque case de la grille est couverte par exactement un domino.

% Étant donné $n$, calculez par programmation dynamique le nombre de pavages possibles, modulo 1000007.  Votre algorithme devrait avoir une complexité $O(n)$.   Notez: une solution en temps $O(\log n)$ est possible, mais c'est hors sujet.  Notez: le résultat est attendu modulo 1000007 juste pour s'assurer qu'il tient dans un entier 32 bits.

% Donnez le cas de base, la récursion et expliquez votre solution.

% \begin{figure}[bht]
%   \centerline{\includegraphics[width=10cm]{tiling}}
%   \caption{Les 5 pavages pour $n=2$ et les 11 pavages pour $n=3$.}
%   \label{fig:tiling}
% \end{figure}



% \section{Tétris avec des rectangles (8 points)}

% On considère un problème similaire à celui étudié en TME6.  Considérons une grille verticale sous forme d'une bande de largeur $W$ et de hauteur infini.  Des rectangles alignés sur la grille tombent du haut jusqu'à ce que leur bord bas touche un autre rectangle déjà en place ou touche le bord bas de la grille.  Et alors il ne bougeront plus.  Notez que dans l'exemple de la figure~\ref{fig:tetris} quand le deuxième rectangle est tombé --- il s'agit du rectangle bleu de dimensions $(x_2,w_2,h_2)=(4,5,1)$ --- il est resté figé en ligne 3, bien que dans la vie réelle la gravitation lui aurait ensuite fait subir une rotation pour faire tomber d'avantage la partie droite du rectangle.

% À tout moment, l'empilement des rectangles forme une sorte de histogramme --- illustré par une ligne rouge --- indiquant pour chaque colonne la hauteur de l'empilement.  Notons $T[j]$ la hauteur de l'empilement en colonne $j$, avec $0\leq j < W$.

% Écrivez une structure de données qui permet de maintenir $T$ en proposant les opérations suivantes, toutes de complexité en temps $O(\log W)$:
% \begin{itemize}
%   \item \textsl{T.set(j, k, v)} pose les entrées $T[j],T[j+1],\ldots,T[k-1]$ à $v$.
%   \item \textsl{T.max{j, k}} retourne la valeur de $\max\{T[j],T[j+1],\ldots,T[k-1]\}$.
% \end{itemize}


% \begin{figure}
%   \centerline{\includegraphics[width=8cm]{tetris}}
%   \caption{Le jeu de Tétris avec des rectangles sans intervention: le joueur ne peut pas décaler les rectangles qui tombent, ni appliquer des rotations. Il ne peut que regarder les rectangles s’empiler.}
%   \label{fig:tetris}
% \end{figure}

\newpage
\subsection{Peindre des dalles (6 points)}

Dans une petite ville existe une promenade qui la traverse d'est en ouest d'une longueur de $2^m$ mètres pour un entier positif $m$. Elle est composée de dalles carrées d'un mètre de côté mis bout à bout. Ces dalles sont numérotées successivement de 0 à $2^m-1$, la dalle $0$ étant la plus à l'ouest et la dalle $2^m-1$ étant la plus à l'est.  Les habitants de la ville n'arrivent pas à se mettre d'accord sur la couleur que la promenade devrait avoir. Le jour de son inauguration toutes les dalles sont grises.  Puis toutes les nuits un groupe d'habitants se met à repeindre un tronçon de la promenade, avec des couleurs alternants de nuit en nuit.
% Le jour $0$ est le jour de l'inauguration. Pendant le jour $j$ avec $1\leq j\leq n$, les dalles numérotées de $a_j$ à $b_j$ (inclus) sont repeints en noir si $j$ est pair et en blanc si $j$ est impair.
 L'administration de la ville vous a chargé de maintenir des données sur les couleurs des dalles, de telle sorte qu'à tout moment ils peuvent vous questionner rapidement sur la couleur d'une dalle particulière. Chaque matin ils vous informent d'un intervalle $[a,b]$ de dalles qui ont été peintes dans la couleur $c$ durant la nuit avec $0\leq a \leq b<2^m$ et $c\in\{1,2\}$.  Les couleurs sont codées par des entiers, 0=gris, 1=blanc, 2=noir.


\begin{figure}[hb]
  \centerline{\includegraphics[width=8cm]{peindre.pdf}}
  \caption{L'évolution des couleurs des dalles de la promenade.}
  \label{fig:peindre}
\end{figure}


Pour cela concevez une structure de données $T$ qui implémente les opérations suivantes.
\begin{description}
  \item[T(m)] le constructeur initialise la structure de données représentant un tableau d'entiers $t$ indicée de $0$ à $2^m-1$. Initialement $t$ ne contient que les valeurs $0$.
  \item[paint(a, b, c)] a pour effet de mettre la valeur $c$ dans toutes les entrées $t[a],t[a+1],\ldots,t[b]$.  Les paramètres satisfont $0\leq a \leq b < 2^m$ et $c\in\{1,2\}$.
  \item[color(a)] retourne la valeur de $t[a]$.
\end{description}
Le constructeur doit avoir une complexité en temps de $O(2^m)$, et les méthodes \textbf{paint} et \textbf{color} une complexité $O(m)$.  Adaptez les arbres de segments pour résoudre ce problème. Donnez votre solution en peudo-code, analysez la complexité des méthodes, et expliquez pourquoi votre solution est correcte.


\newpage
\section{Codage de Huffman Généralisé (10 points)}

On se propose de généraliser le codage de Huffman binaire au cas non
binaire, c'est-à-dire lorsqu'on dispose pour coder
non pas de bits, mais $m$ \textit{caractères} avec $m>2$.

On appelle \emph{symboles} les lettres de l'alphabet du texte à compresser.
On note $n$ la taille de cet alphabet (nombre de symboles distincts
du texte, $n\ge m$), et pour $i=1,\ldots,n$, on note $f_i$ la fréquence du symbole~$a_i$.

\bigskip
On rappelle l'algorithme $\mathcal{H}_2$
de construction d'un arbre binaire de Huffman\\
ENTR\'EE~: fréquences $f_1,\ldots,f_n$ des symboles  $a_1,\ldots,a_n$  d'un texte $T$.\\
SORTIE~: arbre digital donnant un code préfixe minimal pour $T$.
\begin{itemize}
\item[1.] Créer, pour chaque symbole $a_i$, $i=1,\ldots,n$, un arbre $A_i$
  (réduit à une feuille) de poids $f_i$
\item[2.] Itérer le processus suivant~:
  remplacer $2$ arbres $G$ et $D$ de poids minimum par un nouvel arbre
  $R$ ayant pour sous-arbre gauche $G$ et pour sous-arbre droit $D$,
  et affecter comme poids à $R$ la somme des poids de $G$ et $D$.\\
  Arrêter lorsqu'il ne reste qu'un seul arbre et renvoyer cet arbre.
\end{itemize}

\bigskip
L'algorithme de Huffman $\mathcal{H}_2$ satisfait les propriétés suivantes~:
\begin{itemize}
  \item[$(\alpha)$] si un symbole $a_i$ apparaît plus souvent dans le texte qu'un symbole $a_j$
    alors $a_i$ possède un codage plus court (au sens large) que $a_j$,
  \item[$(\beta)$] deux symboles $a_i$ et $a_j$, de fréquences d'apparition minimales strictement,
    c'est-à-dire, $f_i\le f_j$ et $\forall k\not\in \{i,j\}, f_k > f_j$,
    ont un codage de même longueur et ces $2$ codages diffèrent seulement par leur dernier caractère.
\end{itemize}


\begin{question}
  Montrer que si un code préfixe binaire est minimal alors
  la propriété \textbf{$(\alpha)$} est bien vérifiée.
\end{question}

\begin{question}
  Montrer que si un code préfixe binaire est minimal et s'il existe
  deux symboles $a_i$ et $a_j$, de fréquences d'apparition minimales strictement, alors
  la propriété \textbf{$(\beta)$} est bien vérifiée.
\end{question}


\bigskip
On peut obtenir un code de Huffman non binaire de la même manière
qu'avec l'algorithme de Huffman binaire. Nous allons cependant
constater que la propriété \textbf{$(\beta)$} pose un problème si on essaie de
la remplacer respectivement par
\textbf{$(\beta')$}~: ``les $m$ symboles qui ont les fréquences d'apparition minimales strictement
ont un codage de même longueur et les codages de ces $m$ symboles diffèrent seulement par
leur dernier caractère''.



\begin{question}
Quel problème rencontre-t-on si, dans l'étape 2 de cet algorithme, on remplace
simplement  ``$2$ arbres'' par ``$m$ arbres'' ? Pourquoi n'a-t-on pas de problème
dans le cas binaire ?
\end{question}



\bigskip
On considère ci-dessous l'algorithme $\mathcal{H}_m$
de construction d'un arbre $m$-aire.
\begin{itemize}
  \item[1.] Créer, pour chaque symbole $a_i$, $i=1,\ldots,n$, un arbre (réduit à une
    feuille) de poids $f_i$
  \item[2.] Tant qu'on dispose d'au moins $m$ arbres,
    itérer le processus suivant~:
      remplacer $m$ arbres de poids minimum, notés $A_1,\ldots,A_m$, par un nouvel arbre, noté $A$, ayant pour fils $A_1,\ldots, A_m$,
      et affecter comme poids à $A$, la somme des poids des $A_i$.
  \item[3.] Renvoyer l'arbre qui a pour fils tous les arbres restants.
\end{itemize}

\bigskip
On veut générer un arbre de Huffman ternaire ($m=3$) pour
un texte source formé à partir de $6$ symboles distincts (A,B,C,D,E,F)
avec les fréquences d'apparition suivantes~:
$f(B)=f(C)=f(E)=5, f(D)=4, f(A)=2$ et $f(F)=1$.
On utilise l'alphabet ternaire $0, 1, 2$ pour le codage.


\begin{question}
Dérouler l'algorithme $\mathcal{H}_3$ sur l'exemple précédent en donnant
les arbres ternaires obtenus à chaque étape avec leur poids.
\end{question}


\begin{question}
Calculer la taille du texte compressé (nombre de caractères $0,1$ ou $2$)
en utilisant l'arbre de Huffman ternaire ainsi construit.
\end{question}


\begin{question}
Prouver, pour tout $m>2$, que les propriétés \textbf{$(\alpha)$}, \textbf{$(\beta')$} sont
satisfaites par le code l'algorithme $\mathcal{H}_m$, lorsqu'il y a
$m$ symboles (parmi les $n$) dont les fréquences d'apparition sont minimales strictement.
\end{question}


\begin{question}
Montrer qu'un arbre contenant $p$ nœuds internes, tous exactement de degré $m$,
contient exactement $p\times(m-1)+1$ feuilles.
\end{question}


\begin{question}
S'il existe $p\in \mathbb{N}$ tel que $n = p\times(m-1)+1$, que peut-on dire de l'arbre construit
par l'algorithme $\mathcal{H}_m$ ?
\end{question}


\begin{question}
Supposons qu'il n'existe pas $p\in \mathbb{N}$ tel que $n = p\times(m-1)+1$.
Soit $q\in \mathbb{N}$ tel que $q \times(m-1)+1 < n < (q+1)\times(m-1)+1$.
Comment calculer $q$ en fonction de $n$ et de $m$ ? Que représente $q$ dans l'arbre
construit par $\mathcal{H}_m$ ?\\
Soit $m'$ le degré de la racine de l'arbre construit par $\mathcal{H}_m$. Calculer $m'$
en fonction de $m$, $n$ et $q$. On admet que $2 \leq m' < m$.
\end{question}


\bigskip
On propose un autre algorithme de construction de l'arbre. Lorsque tous les nœuds internes ne peuvent pas être de degré $m$,
on admet que plutôt que ce soit la racine dont le nombre de fils est $m'$, on peut construire un arbre dont le nœud
interne le plus profond est de degré~$m'$ et tous les autres de degré $m$.\\
On considère ci-dessous l'algorithme $\mathcal{H}'_m$
de construction d'un arbre $m$-aire.
\begin{itemize}
  \item[1.] Créer, pour chaque symbole $a_i$, $i=1,\ldots,n$, un arbre
    (réduit à une feuille) de poids $f_i$

  \item[2.] S'il n'existe pas $p\in \mathbb{N}$ tel que $n = p\times(m-1)+1$,
    calculer $m'$. Remplacer $m'$ arbres de poids minimum, notés $A_1,\ldots,A_{m'}$, par un nouvel arbre, noté $A$, ayant pour fils $A_1,\ldots, A_{m'}$,
    et affecter comme poids à $A$, la somme des poids des $A_i$.

  \item[3.] Itérer le processus suivant~:
    Remplacer $m$ arbres, notés $A_1,\ldots,A_m$, de poids minimum par un nouvel arbre
    $A$ ayant pour fils $A_1,\ldots, A_m$, et affecter comme poids à $A$
    la somme des poids des $A_i$.\\
    Arrêter lorsqu'il ne reste qu'un seul arbre et renvoyer cet arbre.
\end{itemize}





\begin{question}
Dans l'exemple précédent, où $n=6$ et $m=3$,
vérifier qu'il n'existe pas $p\in \mathbb{N}$ tel que $n = p\times(m-1)+1$
et vérifier que $m'$ vaut $2$.
\end{question}


\begin{question}
Dérouler chaque étape de l'algorithme $\mathcal{H'}_3$ sur l'exemple ci-dessus en donnant
les arbres obtenus à chaque étape avec leur poids.
Les arêtes des arbres sont étiquetées de gauche à droite respectivement
par $0, 1$ et $2$.
\end{question}


\begin{question}
Calculer la taille du texte compressé (nombre de caractères $0,1$ ou $2$)
en utilisant l'arbre de Huffman ternaire $H$ ainsi construit.
\end{question}


\begin{question}
Quel est le résultat de la compression à l'aide
de l'arbre $H$ du texte suivant : \texttt{BCADFFEA}
\end{question}


\begin{question}
Examiner si les propriétés \textbf{$(\alpha)$} et \textbf{$(\beta')$} sont
satisfaites par le code obtenu avec l'algorithme~$\mathcal{H'}_m$.
\end{question}



\begin{question}
Montrer qu'un code préfixe $m$-aire vérifiant les propriétés
\textbf{$(\alpha)$} et \textbf{$(\beta')$} n'est pas forcément minimal.
\end{question}

\newpage
\section{Éléments de correction}

\subsection{Cailloux}

Un programme dynamique était demandé, pas un algorithme glouton. D'ailleurs partir de la case maximale de la première ligne ne mène pas vers la solution optimale comme vous pouvez le voir en figure~\ref{fig:cailloux-glouton}.

\begin{figure}
  \centerline{\includegraphics[width=5cm]{cailloux-glouton.pdf}}
  \caption{La solution optimale ne débute pas par la case maximale en première ligne.}
  \label{fig:cailloux-glouton}
\end{figure}

Notons par $A[i,j]$ le points maximum atteignable en marchant de la ligne $1$ à la case en ligne $i$ et colonne $j$. Le cas de base est $A[1,j]=M[1,j]$, car il y a un seul chemin possible pour atteindre un case de la première ligne.  Le cas d'induction est pour $2\leq i\leq h$ et $2\leq j\leq w-1$
\[
  A[i,j] = M[i,j] + \max\{A[i-1,j-1], A[i-1,j], A[i-1,j+1]\}.
\]
En effet il n'y a que ces trois cases à partir des quelles on peut atteindre la case $(i,j)$ en un seul pas.
Les formules d'induction pour $A[i,1]$ et $A[i,w]$ sont similaires mais avec une valeur de moins afin de ne pas dépasser le bord de la grille.
L'optimum est simplement $\max_j A[1,j]$.
Il y a $O(w\cdot h)$ variables et le calcul de chacune se fait en temps constant.

\subsection{Peindre un mur}

Voir le billet correspondant de notre blog \href{tryalgo http://tryalgo.org/en/data\%20structures/2017/05/02/lazy-segment-tree/}{tryalgo}.

Idée:
On construit un arbre binaire avec $2^m$ feuilles, voir Figure~\ref{fig:peindre-arbre}. Chaque nœud de l'arbre est responsable d'une plage d'indices dans $t$, appelons $\textrm{range(i)}$ cette plage.  Le nœud $i$ est étiquetté par une valeur $s[i]$. Si celle-ci est $0$ la plage d'indices n'a pas été repeinte. Sinon celle-ci est de couleur $s[i]$ pour le sous-arbre.  Pour la méthode \textbf{paint(a,b,c)} il suffit de décomposer l'intervalle $[a,b]$ en intervalles correspondant à des nœuds de l'arbre et de leur donner l'étiquette $c$.  Seulement $O(m)$ nœuds sont concernés par cette mise à jour.  Pour la méthode \textbf{color(a)} il suffit de suivre le chemin de la racine au nœud correspondant à $t[a]$. Si les étiquettes sont tous $0$ la réponse sera $0$. Sinon elle sera la valeur de la première étiquette positive rencontrée.

Détail: Au début du traitement d'un nœud $i$ par la méthode \textbf{paint(a,b,c)} il faut propager la couleur de $i$ aux descendants.

\lstinputlisting[firstline=1,lastline=37]{peindre.py}

Ce code utilise les fonctions utiles suivantes sur les intervalles.

\lstinputlisting[firstline=41,lastline=53]{peindre.py}

\begin{figure}
  \includegraphics{peindre-arbre.pdf}
  \caption{Exemples de manipulation de l'arbre T.}
  \label{fig:peindre-arbre}
\end{figure}

\subsection{Arbres de Huffman}

  \begin{enumerate}
    \item cf cours, slide 17

    \item $a_i$ et $a_j$ sont jumelés au 1er coup (donc dernier caractère distinct) et
      après ils appartiennent toujours au même arbre : donc les caractères suivants sont identiques

    \item A la dernière étape il ne reste pas forcément $m$ arbres. Pour 2, à chaque fois le nb d'arbres est décrémenté de 1.

    \item D-A-F (pds 7) puis B-C-E (pds 15), il reste 2 arbres (D-A-F)-(B-C-E)

    \item 44

    \item même preuve que question 2

    \item récurrence par exemple

    \item Tous les nœuds internes sont de degré exactement $m$

    \item $q = \text{quotient}(n-1, m-1)$ car $q \times(m-1) < n-1 < (q+1)\times(m-1)$.\\
      $q$ est le nombre de nœuds interne de degré exactement $m$.\\
      $m' = n - q\times (m-1)$.

    \item $n=6$ n'est pas un nombre impair.\\
      $m' = 2$

    \item A-F (pds 3), E-D-(A-F) (pds 12) et B-C-(E-D-(A-F))

    \item 37

    \item tout dépend de l'arbre

    \item non pas 2'

    \item $37 < 44$, $\mathcal{H}_m$ vérifie 1 et 2', mais n'est pas minimal.
  \end{enumerate}

\end{document}