▶ HX4 & HX1 – Option Informatique

Second TP Caml Vendredi 10 juin 2011

Un Tp dont vous êtes le héros

1 huffman

Temps estimé : 1h42, difficulté : 2

1.1 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 a {c \atop b}

a est codé par 0, b par 11, c par 10.

▶ Question 1 Traduire abbcbaded.

{a \atop b}  c {e \atop d}

1.2 Programmation de fonctions préliminaires

On utilisera le type

type arbre = Noeud of (arbre∗arbre) | Feuille of char ;;

▶ Question 2 Écrire une fonction qui prend en argument un (arbre*bool list) et renvoie le caractère décodé et la liste restant à décoder.

▶ Question 3 Écrire une fonction qui prend un caractère et un arbre et qui renvoie la liste des caractères codant le caractère.

1.3 Compression

▶ Question 4 É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.

1.4 Décompression

▶ Question 5 Écrire une fonction qui prend un arbre et une bool list et renvoie la liste des caractères dont cette liste est le compressé.

1.5 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.

▶ Question 6 É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.

▶ Question 7 Écrire une fonction qui prend en argument une (int*char) list et qui renvoie l’arbre de huffman correspondant.

▶ Question 8 É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.

▶ Question 9 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.

▶ Question 10 Que penser de ce codage? Combien gagnet-on en moyenne?

2 Mastermind

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.

2.1 Comparer deux combinaisons

▶ Question 11 É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.

▶ Question 12 É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.

2.2 Générer des cas de base

▶ Question 13 Écrire une fonction alea qui génère, au hasard, une combinaison.

▶ Question 14 É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.

▶ Question 15 Écrire une fonction qui génère toutes les combinaisons à n et k fixés, et les met dans un liste.

2.3 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.

▶ Question 16 É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.

▶ Question 17 Écrire l’IA

3 Chameau

Temps estimé : 3m42s Difficulté : e^{i∗π}

▶ Question 18 Dessiner un chameau

4 Joseph le marchand

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} ∈ 1..n, i ∈ 1..m grammes.

▶ Question 19 Écrire le programme pour joseph.

5 Daniel le fourbe

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.

▶ Question 20 Écrire le programme pour daniel.

▶ HX4 & HX1 – Option Informatique

Second TP Caml Vendredi 10 juin 2011

Un Tp dont vous êtes le héros

Un corrigé

▶ Question 1 00 01 01 10 01 00 111 110 111

▶ Question 2

let rec trad= function
| Feuille c,x −> c,x
| Noeud(a,b),t::q −> if tthen trad(a,q) else trad(b,q) ;;

▶ Question 3

exception gagne of bool list;;
let reverse =
let rec foo l = function
| []−> l
| a::q −> foo (a::l) q

in

foo []

;;

let invc 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

;;

▶ Question 4

let compresse txtdico =
let rec foo i =
if i = string_length txt
then []
else (invtxt.[i]dico)@ (foo (i+1))

in

foo 0;;

▶ Question 5

let rec decompresse dico = function
| []−> []
| l−> let (c,r) = trad(dico,l) in c::(decompresse dico r)

;;

▶ Question 6

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

▶ Question 7

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)

;;

▶ Question 9

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

;;

▶ Question 10 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.

▶ Question 12

let compare a b =
let c = copy_vect b in
let rec point_noiri =
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_noir0, point_blanc_noir 0 0 )

;;

▶ Question 13

let alea ()=
let res = make_vect n 0 in
for i = 0 to n−1 do
res.(i) <− random__int k
done ;
res;;

▶ Question 14

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

;;

▶ Question 15

let rec genere_tous courant =
if courant <> make_vect n (k−1)
then (courant)::(genere_tous (suivant courant))
else [courant]

;;

▶ Question 16

let rec filtreessai v = function
| []−> []
| a::q −>
if compare a essai = v
then (a::filtreessai v q)
else (filtreessai v q)

;;

▶ Question 17

let IAsecret =
let rec trouve = function
| []−> failwith"no␣solution␣?␣"
| [a]−> a
| l−>
let essai = alea ()in
let reste = (filtreessai (secret essai ) l) in
trouve reste

in

trouve (genere_tous (make_vect n 0)),secret

;;

▶ Question 19

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− ilpossible de faire javec les fruitsd’id > i ? ∗)
let rec possible ji =
print_inti;print_string"␣"; print_intj;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

;;

▶ Question 20

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 (tril,tril’)

;;

let daniel l =
let rec filtremax_dif = function
| []−> []
| (a,b)::q −>
if b > max_dif
then (a,b)::(filtreb q)
else (filtremax_dif q)

in

filtre(−1) (tril)

;;