Initiation à CAMLlight avec TP de Caml

Formation CAML, tutoriel & guide de travaux pratiques en pdf.

Itération

L’itération consiste à eﬀectuer plusieurs fois une même opération.
Itération inconditionnelle : On prend un ensemble fini E ordonné et pour x ∈ E (pris dans l’ordre), on eﬀectue truc(x).
Itération conditionnelle :
– Tant qu’une certaine condition n’est pas vérifiée, faire truc.
– Faire truc jusqu’à ce qu’une certaine condition soit réalisée. ( L’opération est eﬀectuée, au moins une fois)
En CAML on dispose de l’itération inconditionelle («for» avec E = Ja, bK), et de l’itération inconditionnelle avec test au début («while »).
Code CAML : Exemples
>>let carré n =
for i = 1 to n do
print_int(i*i);
print_newline();
done;;

Les références

Si l’itération est destinée à faire évoluer des valeurs, on utilise des variables dont le contenu est destiné à bouger : des références. Une référence de type ’a est une feuille de papier sur laquelle est écrit un élément de type ’a.
Deux opérations sur les référence : écrire quelquechose dessus et en lire la valeur.
Code CAML : Déclaration d’une référence
>>let a = ref 3;;
>>!a;;
int,3
>>a:=5;;
>>!a;;
int,5
>>a:=!a+1;;
>>!a;;
int,6
Code CAML : Si n = 1, la boucle est eﬀectuée pour
>>let facto n =
let a = ref 1 in tout i ∈ ∅ et n’est donc pas eﬀectuée.
for i = 2 to n do
a:=!a+1;
done;
!a;;
Code CAML : Test de primalité
>>let estpremier n = let onatrouvé = ref false and k = ref 2 in
while (!onatrouvé=false)&&(!k*!k<=n) do
if (n mod !k) = 0 then
onatrouvé := true;
incr(k);
done;
not(!onatrouvé);;

Structure de tableau

Un tableau est un groupe de références, une feuille sur laquelle on a n valeurs de type ’a. ( tableau = nombre d’éléments, adresse mémoire de la première valeur, les autres suivent)
Code CAML : Déclaration d’un tableau
>>let t = make_vect 18 2.3;;
Où 18 est le nombre de cases et 2,3 la valeur d’utilisation mise dans toutes les cases : CAML cherche un espace mémoire disponible long de 18 flottants, initialise toutes les cases et renvoie l’adresse du premier élément.
Code CAML : Aﬀectation d’une valeur :
>>t.(4)<-3.2;;
Code CAML : Lecture d’une case : ♥ Attention : la numérotation commence à
>>t.(4);; 0. La première est 0 et la dernière n-1.
Code CAML : Nombres d’éléments d’un tableau
>>vect_length t;;
Code CAML : Autre manière de définir un tableau :
>>let t = [|3;4;3;8|];;
Code CAML :
>>let carrés n =
let t = make_vect n 0 in
for i = 1 to n do
t.(i-1)<-i*i;
done;
t;;

Exercices

Exercice 2.3.1: Somme & produit Cette fonction est de type «int->int->int-
>>let sum f a b =
let s = ref 0 in >int->int»
for i = a to b do
s:=!s +f(i);
done;
!s;;
>>let prod f a b =
let s = ref 1 in
for i = a to b do
s:=!s *f(i);
done;
!s;;
Exercice 2.3.2: Suites récurrentes >>let iter f u0 n = let suite = ref u0 in
for i = 1 to n do
suite := f(!suite);
done;
!suite;;
Exercice 2.3.3: Test de primalité
cf : Cours
Exercice 2.3.4: Somme de chiﬀres >>let somchiffres n = let somme = ref 0 in
let quotient = ref abs(n) in while !quotient <> 0 do
somme :=!somme + (!quotient mod 10); quotient:=!quotient/10; done;
!somme;;
>>let somcubes() =
let cube x = x*x*x in
let i = ref 1 and cubmax = ref 0 and result:=1 in
while (cube !i <=10000) do
let a = somchiffres(cube !i) in if (a >!cubmax) then
(cubmax:=a result:=i); incr i;
done;
result;;
Cette fonction est du type «int->int->int->int->int» Preuve du programme : un in-variant de boucle : après la ième itération, c contient Un.
Cette fonction est du type «int->int».( Le abs permet de traiter aussi les nombres né-gatifs.)
Exercice 2.3.5: Suite de syracuse
>>let syracuse n =
let k = ref 0 in
let suite = ref n in
while !suite <>1 do
if (!suite mod 2)=0 then
suite:=!suite/2
else
suite:=3*!suite+1;
incr(k);
done;
!k;;
Exercice 2.3.6: Map
>>let map f t =
let a = vect_length (t) in
let u = make_vect a f(t.(0)) in
for i = 1 to pred(a) do
u.(i)<-f(t.(i));
done;
u;;
Exercice 2.3.7: égalité de tableaux >>let test t u =
let b = ref true in
let n = vect_length t in
let m = vect_length u in
let k = ref 0 in
if n<>m then
b:=false
else
while (!b)&&(!k<n) do
if t.(!k)=u.(!k) then
incr(k)
else
b:=false;
done;
!b;;
La complexité en temps de l’algorithme est le temps d’exécution. Ici si n est la taille du tableau, la complexité vaut O(n) dans le pire des cas.
Exercice 2.3.8: Minimum d’un tableau
>>let mint t =
let a = vect_length t in
let k = ref t.(0) in
for i = 1 to pred (a) do
if t.(i)<(!k) then
k:=t.(i);
done;
!k;;
Exercice 2.3.9: Maximum d’un tableau et nombre d’occurrences en lecture unique
>>let maks t = Cette fonction est d’une complexité li-
let k = ref 1 in néaire.(ie : du type O(1), appliqué n fois.)
let n = vect_length t in
let m = ref t.(0) in
for i = 1 to pred(n) do
if t.(i)=(!m) then
incr(k)
else if t.(i)>(!m) then
(m:=t.(i); k:=1);
done;
(!m,!k);;

Quelques algorithmes usuels sur les tableaux

Recherche d’un élément dans un tableau

On dispose d’un tableau t et d’un élément e. On parcourt le tableau jusqu’à ce que l’on trouve e, ou bien que l’on arrive à la fin du tableau. On retourne à la fin un booléen résultat du test e ∈ t, et éventuellement l’indice, dans un couple.
Code CAML :
>>let recherche e t =
let j = ref 0 in
let resultat = ref false in while (!resultat=false)
&& (!j<vect_length t) do if t.(j)=e then
result:=true;
incr(j);
done;
!resultat;;
La complexité O(n) où n est la longueur du tableau dans le cas le pire (si e n’y est pas).

Recherche des éléments dans un tableau trié

On dispose d’un talbeau trié (t.(0) ≤ t.(1) ≤ ≤ t.(n − 1)) et d’un élément e.Si le tableau n’est pas vide, on considère l’élément médian du tableau, t.(m) où m = ⌊n −2 1 ⌋.
– Si e = t.(m) on a trouvé et on s’arrête.
– Si e > t.(m) on se ramène à chercher dans le tableau de droite.
– Si e < t.(m) On se ramène à chercher dans le tableau de gauche
En CAML On fait évoluer deux références «début» et «fin» correspondant aux indices de début et de fin du tableau extrait :

Tri d’un tableau : Tri par sélection

Code CAML : Preuve de terminaison : Lors de l’exécution
>>let recherche e t = de la boucle, la valeur de fin-début déroit
let début = ref 0 strictement et devient donc forcément né-and fin = ref (vect_length t -1) in gative à un moment ce qui garantit la ter-let trouvé = ref false in minaison de l’algorithme.
while (!trouvé=false) Soit T (n) le temsp d’exécution del’algo-
&&(!début<=!fin) do rithme sur un tableau de taille n. On a
let m=(!debut+!fin)/2 in n n
if e=t.(m) then T (n) = O(1) + T ( ) = O(1)+O(1)+T ( )
2 4
trouvé:=true n
else if e>t.(m) then
= kO(1) + T ( ) = O(log2(n)) = O(ln n)
début:=m+1 2k
else fin:=m-1
done;
!trouvé;;
On dispose en entrée d’un tebleau t, on veut réorodonner les éléments de t en un tableau t′.

I Initiation à CAMLlight
1 Premiers pas en CAML light
2 Itération
3 Quelques algorithmes usuels sur les tableaux
4 Récursivité
5 Listes
6 Deux tris efficaces
7 Diviser pour mieux règner
8 Tris
9 Programmation dynamique
10 Logique propositionnelle
II TP de Caml
11 TP1 : Premiers pas en Caml Light
12 TP2 : Références, boucles, tableaux
13 TP3 : Listes, récursion, types somme
14 TP4 : Ensembles, chaînes, types produit
15 TP5 : graphics, dessin, géométrie plane.
16 TP6 : diviser pour règner, programmation dynamique
17 TP7 : Logique propositionnelle
III Contrôles
18 Contrôle no 1