	\documentclass{tp-caml}

\tp{
  title=Un Tp dont vous êtes le héros,
  number=Second,
  date=Vendredi 10 juin 2011,
  class=HX4 \& HX1
}

\usepackage{pstricks,pstricks-add,pst-node,pst-tree}

\begin{document}

\begin{corpus}

\section{huffman}
\textit{Temps estimé : 1h42, difficulté : 2 }

\subsection{Principes}
Dans cette section nous allons compresser de façon simple. En effet, à
chaque symbole de l'alphabet nous allons associer une suite de 0 et de
1 qui la représente en mémoire. On ne peut pas choisir n'importe
quoi. Si je prends, par exemple, 0 pour $a$ et $b$ alors je ne saurais
pas distinguer les a et les b. De même, plus subtil, si je prends 010
pour $a$, 0100 pour $b$ et 10 pour $c$, comment distinguer les $aa$ et
les $bc$ ?

Pour éviter cela, les codes que nous utiliserons seront
préfixes. C'est à dire, aucun mot ne sera le préfixe d'un autre. Comme
ça, si mon texte commence par 101010 et que je sais que $a$ est 101,
je suis sûr que mon texte commence par un $a$ et qu'il se continue par
la traduction de 010.

Les codes que l'on va utiliser seront manipulés à l'aide d'arbres. Les
feuilles seront des caractères et pour savoir le code d'un caractère
$c$, on suivra le chemin depuis la racine jusqu'à $c$. À chaque fois
que l'on prendra une branche droite, on écrira un 0 et une branche
gauche un 1.

Par exemple pour 

\pstree[nodesep=2pt,levelsep=5ex]{\TR{} }{
        
        
                     \TR{a}
        			\pstree{\TR{}}{
       						 \TR{c} 
		                     \TR{b}
                              }
                              }\\
                              
                              
$a$ est codé par 0, $b$ par 11, $c$ par 10.                              

\begin{exo}
Traduire abbcbaded.

\pstree[nodesep=2pt,levelsep=5ex]{\TR{} }{
        
        \pstree{ \TR{} }{
                     \TR{a}
                     \TR{b}
                              }
        \pstree{\TR{}}{
        \TR{c} 
        \pstree{\TR{}}{
        	\TR{e} 
        	\TR{d} 
        
        }
                    }}\\
\end{exo}
\begin{sol}
00 01 01 10 01 00 111 110 111 
\end{sol}
\subsection{Programmation de fonctions préliminaires}

On utilisera le type 
\begin{caml}
type arbre = Noeud of (arbre*arbre) | Feuille of char ;;
\end{caml}

 
\begin{exo}
Écrire une fonction qui prend en argument un (arbre*bool list) et renvoie le caractère décodé et la liste restant à décoder.

\end{exo}
\begin{solc}
let rec trad = function
  | Feuille c,x -> c,x
  | Noeud(a,b),t::q -> if t then trad (a,q) else trad (b,q) ;;
\end{solc}

\begin{exo}
Écrire une fonction qui prend un caractère et un arbre et qui renvoie la liste des caractères codant le caractère.
\end{exo}

\begin{solc}
exception gagne of bool list ;;

let reverse =
  let rec foo l = function
    | [] -> l
    | a::q -> foo (a::l) q
  in
foo []
;;

let inv c dico = 
  let rec foo chemin = function
    | Feuille f -> if f = c then raise (gagne (reverse chemin))
    | Noeud(a,b) -> foo (true::chemin) a ; foo (false::chemin) b
  in
  try
    foo [] dico ; []
  with 
      gagne l -> l
;;
\end{solc}


\subsection{Compression}
\begin{exo}
Écrire une fonction qui prend en paramètre un arbre et une liste de caractères et renvoie une bool list correspondant à la liste des caractères compressée.
\end{exo}


\begin{solc}
let compresse txt dico =
  let rec foo i = 
    if i = string_length txt 
    then []
    else (inv txt.[i] dico)@(foo (i+1))
  in
foo 0;;
\end{solc}

\subsection{Décompression}

\begin{exo}
Écrire une fonction qui prend un arbre et une bool list et renvoie la liste des caractères dont cette liste est le compressé.
\end{exo}

\begin{solc}
let rec decompresse dico = function
  | [] -> []
  | l -> let (c,r) = trad (dico,l) in c::(decompresse dico r)
;;
\end{solc}

\subsection{Huffman}

La question qui se pose est maintenant de choisir de manière optimale l'arbre pour arriver à un texte le plus compressé possible. Huffman a proposé une méthode pour construire l'arbre optimal par rapport à la fréquence d'apparition de chaque lettre : 

Tant qu'il reste plus d'une lettre à coder.
  On extrait les deux lettres qui apparaissent le moins souvent.
  On remplace ces deux caractères $a$ et $b$ par un nouveau caractère n'apparaissant pas dans l'alphabet originel, $c=$Nœud$(a,b)$, le codage de $a$ sera celui de $c$ suivi d'un 1 et $b$ suivi d'un 0.
  
\begin{exo}
Écrire une fonction qui prend en argument une (int*arbre) list, liste de (nombre d'occurrences d'un caractère de l'arbre, arbre), et renvoie l'arbre qui a le plus petit nombre d'occurrences. 
\end{exo}
\begin{solc}
 let rec sort_plus_petit = function
    | [a] -> (a,[])
    | a::q -> let (p,l) = sort_plus_petit q in
              if p < a then (p,a::l) else (a,p::l) 
  in
\end{solc}

\begin{exo}
Écrire une fonction qui prend en argument une (int*char) list et qui renvoie l'arbre de huffman correspondant. 
\end{exo}
\begin{solc}
let dico_huffman l = 
 
  let rec arborifie = function
    | [a,b] -> b
    | l -> let ((p1,v1),l2) = sort_plus_petit l in
           let ((p2,v2),l3) = sort_plus_petit l2 in
           arborifie ((p1+p2,Noeud (v1,v2))::l3)

  in
  arborifie (map (fun (x,y) -> x,Feuille y) l)   
;;
\end{solc}

\begin{exo}
Écrire une fonction qui prend un texte et qui renvoie une (int*char) list comptant le nombre d'occurrences de chaque caractère, on veillera à éliminer les caractères ayant 0 occurrences.
\end{exo}

\begin{exo}
En déduire une fonction qui compresse un texte à l'aide de l'algorithme de huffman. Cette fonction renverra aussi le dictionnaire construit pour vérifier que compresse est bien l'inverse de décompresse.
\end{exo}

\begin{solc}
let huffman s = 
  let freq = make_vect 256 0 in 
  let rec parcours i = 
    if i < string_length s 
    then (freq.(int_of_char s.[i])<-freq.(int_of_char s.[i])+1 ; parcours (i+1))
  in
  let rec make_list i = 
    if i = 256             
    then []
    else 
      if freq.(i) > 0 
      then  (freq.(i),char_of_int i)::make_list (i+1)
      else  make_list(i+1)
  in
  let dico = dico_huffman (parcours 0 ; make_list 0) in
  compresse s dico,dico
;;
\end{solc}

\begin{exo}
Que penser de ce codage ? Combien gagne-t-on en moyenne ?
\end{exo}

\begin{sol}
Ce code est bien appliqué aux fichiers dont la répartition des différents symboles est très mauvaise, comme un fichier texte. Cependant, en moyenne sur toutes les entrées il ne sert à rien, d'après le paradoxe du compresseur.
\end{sol}

\section{Mastermind}
\textit{Temps estimé : 1h05, difficulté : 1,8 }

Si vous ne connaissez pas le Mastermind, rejouer !


On fixe $k$ et $n$ qui sont le nombre de couleurs et la taille des combinaisons.

\subsection{Comparer deux combinaisons}

\begin{exo}
Étant donné deux combinaisons, compter le nombre de noirs qu'elles génèrent, i.e le nombre de points sur lesquelles elles sont identiques.
\end{exo}

\begin{exo}
Étant donné deux combinaisons, compter le nombre de rouges qu'elles génèrent, i.e le nombre de noirs qu'elles génèreraient, au maximum, si on permutait l'ordre des pions de l'une d'elle.
\end{exo}

\begin{solc}
let compare a b =
  let c = copy_vect b in
  let rec point_noir i = 
    if i = vect_length a 
    then 0
    else (if a.(i) = b.(i) then 1 else 0)+point_noir (i+1)
  in
  let rec point_blanc_noir ia ib=
      if ia = vect_length a 
      then 0
      else
        if ib = vect_length b 
        then point_blanc_noir (ia+1) 0 
        else
          (if a.(ia) = c.(ib)
           then (c.(ib)<-(-1);1+point_blanc_noir (ia+1) 0) 
           else point_blanc_noir (ia) (ib+1))
    in
    (point_noir 0, point_blanc_noir 0 0 )
;;
\end{solc}

\subsection{Générer des cas de base}

\begin{exo}
Écrire une fonction alea qui génère, au hasard, une combinaison.
\end{exo}

\begin{solc}
let alea () = 
  let res = make_vect n 0 in
  for i = 0 to n-1 do
    res.(i) <- random__int k
  done;
res;;
\end{solc}

\begin{exo}
Écrire une fonction qui passe d'une combinaison à la suivante, i.e on voit les combinaisons comme des nombres de tailles au plus $n$ dans une base $n$ et on veut ajouter un. 
\end{exo}
\begin{solc}
let suivant s =
  let f = copy_vect s in
  let rec foo i = 
    if f.(i) < k-1
    then (f.(i)<- f.(i)+1)
    else (f.(i)<- 0 ; foo (i+1))
  in
    foo 0 ; f
;;
\end{solc}

\begin{exo}
Écrire une fonction qui génère toutes les combinaisons à $n$ et $k$ fixés, et les met dans un liste.
\end{exo}
\begin{solc}
let rec genere_tous courant = 
  if courant <> make_vect n (k-1)
  then (courant)::(genere_tous (suivant courant))
  else [courant]
;;
\end{solc}

\subsection{IA}
On veut écrire une IA qui joue toute seule au mastermind. Pour cela, on va lui faire choisir des combinaisons au hasard et éliminer au fur et à mesure les combinaisons incompatibles avec le test que l'on vient de faire quand il ne reste plus qu'une seule combinaison qui n'est pas incompatible on l'élimine.

\begin{exo}
Écrire une fonction filtre qui prend la combinaison que l'IA vient de jouer, le résultat donné par le joueur opposé (nombre de noir, nombre de rouge) et la liste des combinaisons qui sont compatibles avec les résultats précédents et renvoie la liste des résultats compatibles en tenant compte de l'essai venant d'être fait.
\end{exo}
\begin{solc}
let rec filtre essai v = function 
    | [] -> []
    | a::q -> 
      if compare a essai = v
      then (a::filtre essai v q)
      else (filtre essai v q)
;;
\end{solc}

\begin{exo}
Écrire l'IA
\end{exo}
\begin{solc}
let IA secret = 
  
  let rec trouve = function 
    | [] -> failwith "no solution ? "
    | [a] -> a
    | l -> 
      let essai = alea () in
      let reste =  (filtre essai (secret essai) l) in
      trouve reste
  in
trouve (genere_tous (make_vect n 0)),secret
;;
\end{solc}

\section{Chameau}
\textit{Temps estimé : 3m42s Difficulté : $e^{i*\pi}$}

\begin{exo}
Dessiner un chameau
\end{exo}

\section{Joseph le marchand}
\textit{Temps estimé : 12m30s Difficulté : 3}

Joseph à régulièrement des demandes de la part de ses clients sous la forme : pourrais-je avoir 2kg de fraises ? Je voudrais 750g de poires. Comme Joseph est un bon vendeur, il aime satisfaire ses clients. Pour cela, à chaque fois que quelqu'un lui demande $n$ grammes d'un quelconque fruit, il pèse chacun de ses fruits et quand c'est possible il donne au client la somme exacte. Comme ses capacités de calculs diminuent avec son grand age, il voudrait que vous lui fassiez un programme qui détermine si, oui ou non, c'est possible d'obtenir $n$ grammes avec des fruits qui pèsent $p_i \in 1..n$, $i \in 1..m$ grammes.

\begin{exo}
Écrire le programme pour joseph.
\end{exo}

\begin{solc}
let joseph k poids =
  let n = vect_length poids in
  let vus = make_matrix (k+1) n false in
  let peut = make_matrix (k+1) n false in
  (* est-il possible de faire j avec les fruits d'id > i ? *)
  let rec possible j i =
    print_int i;print_string " " ; print_int j;print_newline ();
    (i<n||j=0) && (j=0|| (j>0 && 
      (
        if not vus.(j).(i)
        then peut.(j).(i) <- possible j (i+1) || possible (j-poids.(i)) (i+1) ;
        vus.(j).(i)<-true ;
        peut.(j).(i)
      )))
  in
  possible k 0
;;
\end{solc}

\section{Daniel le fourbe}
\textit{Temps estimé : 21m30s Difficulté : 2,5}

Daniel sait que, pour paraître brillant, il faut faire des exercices
difficiles rapidement. Or, son TDman a - dans sa grande magnanimité -
annoté chacun des exercices avec le temps estimé et la difficulté de
chaque sujet. Daniel décide donc de ne lire que les énoncés - pourtant
tous extrêmement intéressants - des sujets pour lesquels il n'existe
pas un autre sujet qui soit à la fois plus rapide à faire et considéré
plus difficile. Daniel, flemmard mais astucieux, demande à son voisin
de lui faire un programme qui ferait le tri à sa place. Ce programme
doit cependant être rapide pour qu'il ne perde surtout pas de temps
avant de commencer son tp.

\begin{exo}
Écrire le programme pour daniel.
\end{exo}

\begin{solc}
let rec coupe = function 
  | [] -> ([],[])
  | a::q -> 
    let (l,l') = coupe q in 
    (a::l',l)
;;

let rec merge = function
  | [],l -> l 
  | l,[] -> l
  | a::q,x::t -> if a < x then a::(merge (q,x::t)) else x::(merge (a::q,t))
;;

let rec tri = function 
  | [] -> []
  | [a] -> [a]
  | l -> let l,l' = coupe l in
         merge (tri l,tri l')

;;

let daniel l =
  let rec filtre max_dif = function
    | [] -> []
    | (a,b)::q -> 
      if b > max_dif 
      then (a,b)::(filtre b q)
      else (filtre max_dif q) 
  in
  filtre (-1) (tri l)
;;
\end{solc}

\end{corpus}


\end{document}



%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
	
