Session de Septembre 1996
Exercice 1:
Pour chacune des équations suivantes, justifier si elle est vraie ou fausse:
1- []::["abc"]=[["abc"]]
2- (8::[])@[5;7]=[8;5;7]
3- []::[["ab"]]=[["ab"]]
4- []::([[1]]@[[2]])=[[];[1];[2]]
Exercice 2:
Le scipt ci-dessous définit la fonction G.
G n = 1 si n=0
= 1 si n=1
= G(n-1) + G(n-2), sinon
IIa: Donner le type de la fonction G.
IIb: Donner le détail de l'évaluation de G 5.
IIc: Définir ce script en CAML
Exercice 3:
La fonction alloc est définie de la manière suivante:
assoc xys x = tete[y|(x',y) <- xys;x'=x].
IIIa: Quel est le résultat de l'évaluation de assoc [(1,2);(3,4);(5,6);(3,11)]3?
IIIb: Préciser clairement la spécification de assoc dans le cas général.
IIIc: Proposer alors une définition récursive de assoc en CAML.
Exercice 4:
On définit en CAML la fonction iterer de la manière suivante:
# let iterer = function f ->
# let rec itere_f = function n -> function x ->
# if n = 0 then x else itere_f (n-1)(f x)
# in itere_f;;
IVa: Pour une fonction f donnée, que renvoie iterer f n x ?
IVb: Justifier la session:
# iterer pred 2 7;;
-: int 5
IVc: Donner une traduction algorithmique du script définissant iterer.
Exercice 5:
On donne le script suivant, pour n lié:
Va: Sachant que n=5, évaluer f_rec (2,1)
Vb: Définir (a,?) donnant f_rec (a,1)=n!
Vc: En utilisant f_rec comme définition locale, définir la fonction fact telle que fact n=n!
Vd: Traduire ce script obtenu en CAML.
Exercice 6:
VIa: Rappeler les définitions par filtrage de renverser et de @.
VIb: Montrer par induction que, pour toutes les listes finies xs et ys:
renverser (xs@ys)= renverser ys@renverser xs.
NB: On rappelle que les notations et les définitions utilisées dans l'énoncé sont celles du cours d'Algorithmique Fonctionnelle. En particulier, x, y et z désignent des éléments de listes, et xs, ys, et zs des listes d'éléments.