Consignes
TDTP donné en devoir maison noté
28 octobre 2020
Avertissement : ce TDTP est à faire de manière individuelle. Tout plagiat et toute triche seront sanctionnés : nous appliquerons des algorithmes de détection de “similitudes” entre les copies d’étudiants pour cela.Tous les documents du cours sont autorisés cependant, ainsi bien sûr que la documentation OCaml.
Vous devez produire une archive de la forme prenom_nom_GX.zip où prenom et nom seront orthographiés exactement comme dans votre adresse email prenom.nom@u-psud.fr, et où X est le numéro de votre groupe de TD. Cette archive contiendra 5 fichiers nommés exoN.ml où N correspond au numéro de l’exercice.
prenom_nom_GX.zip
exo1.ml exo2.ml exo3.ml exo4.ml exo5.ml
Chaque fichier .ml doit impérativement compiler. Si vous voulez rajouter du code qui ne compile pas mettez-le en commentaire. Si les réponses sont à rédiger en français, mettez- les également en commentaires dans le fichiers correspondant, en omettez les accents, afin d’éviter les problèmes de codage de fichiers.
Le TDTP est à rendre sur eCampus dans la rubrique TD/TP > TP Noté, avant la date indiquée. Les exercices sont indépendants et peuvent être faits dans n’importe quel ordre. Ne restez pas bloqué sur une question.
1 Syntaxe
Question 1.1 Trouver deux manières de parenthèser la fonction ajout_deux pour qu’elle fasse bien ce que l’on souhaite : ajouter deux à un nombre entier g.
let f a b = a + b
let ajout_deux g = if g = 0 then f 2 0 else f 2 + 1 g – 1
Question 1.2 Trouver les erreurs de syntaxe dans la fonction suivante, qui parcourt deux listes d’entiers jusqu’à leurs derniers éléments, pour sommer ces deux derniers éléments et renvoyer cette somme. Il y a quatre erreurs à corriger.
1
let somme_derniers l1 l2 = match l1 with
| [] -> | | | | x1 ::
match l2 with
[] -> 0
x2 :: [] -> x2
hd2 :: tl2 -> somme_derniers [] tl2 [] -> match l2 with
| [] -> 0
| x2 :: [] -> x1 + x2
| hd2 @ tl2 -> somme_derniers [x1] tl2
| hd1 :: tl1 -> somme_derniers tl1 l2
Question 1.3 Trouver les erreurs de syntaxe dans le code suivant. Il y a trois erreurs. let x a b = a +. b
let f x y z = let v = y + 5
if z > y then Printf.printf “%d” z ; z else x v 0
Question 1.4 Pour chaque occurence des variables u z et y, indiquer où se trouve leur lieur, c’est-à-dire la déclaration qui correspond à cette occurence. Pour cela indiquer, en commentaire de ligne où apparaît la variable, le numéro de la ligne de son lieur.
1 lety=5.3;;
2 letuz=
3 z-.y;;
4 let y =
5 let y =
6 y+.2.5
7 inletz=uy
8 iny*.z
9 inletu=2.0in
10 y+.y+.u;; 2 Typage
Question 2.1 Donner le type de chacune des variables de la fonction et de l’objet renvoyé. Justifier votre réponse.
let f1 (x,y) z =
let g a b = a < b in
if z then g x else g y ;;
Question 2.2 Dans le code suivant, que font les fonctions list_sum et list_or ? Quels sont leur types ?
Le code des lignes 4-6 est-il bien typé ? Quel est le type de a à chaque étape ?
Mêmes questions pour les lignes 8-10.
2
1 let list_sum = List.fold_left (fun x y -> x + y) 0;;
2 let list_or = List.fold_left (fun x y -> x || y) false;;
3
4 leta=[];;
5 list_sum a;;
6 list_or a;;
7
8 leta=ref[];;
9 list_sum !a;;
10 list_or !a;;
Question 2.3 On définit le type suivant :
type ‘a arbre_binaire = Feuille
| Noeud of ‘a * ‘a arbre_binaire * ‘a arbre_binaire;;
Écrire une fonction map_arbre qui prend en entrée un arbre binaire représenté par ce type et une fonction f, et qui renvoie l’arbre obtenu en transformant chacune des valeurs portées en chaque noeud, par f.
Écrire une fonction forall_arbre qui prend en entrée un arbre binaire et un prédicat (fonc- tion de type ’a -> bool), et renvoie true ssi toutes les étiquettes vérifient le prédicat. Quels sont les types de ces deux fonctions ?
3 Exécution
Soit le code suivant :
type valeur = {debut : int; fin : int}
type arbre = V | Noeud of valeur * arbre * arbre
let rec mystere t =
match t with
|V -> 0
|Noeud (v, V, V) -> mystere V + v.debut |Noeud (v1, V, Noeud (v2,V,V)) ->
let v1′ = {debut = v1.debut; fin = v1.debut} in
mystere (Noeud (v2, Noeud (v1′,V,V),V)) |Noeud (v, Noeud (v’,V,V), V) ->
let v1 = {debut = v.fin; fin = v’.debut} in let v2 = {debut = v’.debut; fin = v’.fin} in let v3 = {debut = v1.fin; fin = v2.fin} in let v4 = {debut = v2.debut; fin = v3.fin} in v.debut + mystere (Noeud (v4, V,V))
|Noeud (v, a, b) -> v.debut + mystere a + mystere b |Noeud (v, Noeud (v2,V,V), Noeud (v3,V,V)) -> 0
let arb = Noeud ({debut = 1; fin = -2000}, V, Noeud ({debut = 400; fin = 30000}, V, V))
3
Pour chacune des questions, répondez en commentaire.
Question 3.1 Etant donnée la fonction mystere et la variable arb, expliquer, en détaillant étape par étape, le résultat renvoyé par mystere arb.
Question 3.2 Expliquer le fonctionnement de la fonction mystere. Vous devez détailler votre raisonnement.
4 Recherche linéaire d’un chemin optimal
Dans cette section on se propose d’implémenter un algorithme de recherche d’un chemin de plus grande somme dans une grille d’entiers, de complexité linéaire en le nombre de cases de cette grille. La grille suivante à 4 lignes et 3 colonnes est la grille-exemple.
Plus de détails sur les chemins seront donnés dans la suite. Intéressons-nous pour le moment aux grilles d’entiers, celles-ci sont représentées en OCaml par le type suivant :
type grid = int list list Question 4.1 Sachant que la grille
est représentée par [[0; 1]; [2; 3]] de type grid, définir un élémént g_example : grid re- présentant la grille-exemple.
Question 4.2 Définir la fonction is_empty qui prend une liste et qui renvoie un booléen qui indique si la liste est vide. Cette fonction devra s’exécuter en temps constant.
Question 4.3 Définir la fonction height : grid -> int qui, pour une liste g non-vide donnée en argument, renvoie la longueur de la première liste de g. Par exemple on doit avoir height g_example = 4.
Un élément g du type grid sera dit bien formé s’il représente bien une grille et que cette grille a au moins une case. Autrement dit, g est bien formé si g n’est pas la liste vide et si chaque liste qui compose g a une même taille non-nulle.
Question 4.4 En utilisant l’itérateur List.exists, définir la fonction wf_grid_exn : grid -> unit qui renvoie une erreur si l’argument n’est pas une grille bien formée.
On suppose dorénavant que nous ne travaillons qu’avec des grilles bien formées.
Question 4.5 En utilisant List.map, définir grid_map :(int -> int)-> grid -> grid telle que grid_map f g renvoie la grille g où f a été appliquée à chaque case.
4
−2
7
6
0
2
−1
1
−3
3
4
−4
5
0
2
1
3
Un chemin dans une grille commence par une case dans la première colonne puis continue avec une case dans la deuxième colonne, et ainsi de suite pour arriver à une case dans la dernière colonne. Un chemin est valide si, étant donnée une case dans la colonne j, le chemin continue avec une case dans la colonne j+1 qui sur la même ligne, une ligne au-dessus ou une ligne en-dessous (en considérant en plus que la première ligne est en-dessous de la dernière ligne et que la dernière ligne est au-dessus de la première ligne).
Question 4.6 Écrire en commentaire le nombre maximal que l’on peut obtenir en faisant la somme des cases d’un chemin valide dans la grille-exemple.
Donner les chiffres qui composent un tel chemin et expliquer pourquoi ce dernier est valide (il pourra commencer par n’importe quelle case dans la première colonne).
Question 4.7 Écrire une fonction rotate_up : int list -> int list qui, appliquée à une liste non-vide [i0; i1; …; in] donne la liste [i1; …; in; i0].
Question 4.8 Écrire une fonction firsts_last : ‘a list -> ‘a list * ‘a qui, appli- quée à une liste non-vide [a0; a1; …; an] donne la paire constituée de la liste [a0; …; an−1] et de an.
Question 4.9 Écrire une fonction rotate_down : int list -> int list qui, appliquée à une liste non-vide [i0; i1; …; in] donne la liste [in; i0; i1; …; in−1].
Question 4.10 Écrire une fonction sums_2 : int list -> int list -> int list qui, appliquée à deux listes de même taille non-nulle l1 et l2, donne une liste de même taille. En considérant la grille [l1;l2] (où l1 est la première colonne et l2 est la seconde colonne), cette fonction doit renvoyer les sommes maximales des chemins valides qui partent de chacune des cases de la première colonne.
Indication : on pourra utiliser rotate_up, rotate_down ainsi que les itérateurs List.map et List.combine.
Question 4.11 Définir une fonction sums : grid -> int list qui, étant donnée une grille, renvoie la liste des sommes maximales des chemins valides qui partent de chacune des cases de la première colonne de la grille.
Indication : on poura utiliser List.fold_right en itérant sur les premières colonnes, l’accumulateur étant initialisé à la dernière colonne.
Question 4.12 Écrire une fonction solve : grid -> path qui, étant donnée une grille, renvoie un chemin valide de somme maximale, le type path étant à définir.
Indication : adapter les deux dernières questions pour retenir les chemins qui mènent à une somme maximale. Vous pourrez définir un chemin comme la liste des coordonnées des cases qui le constitue (en prenant par exemple la case en haut à gauche comme origine).
5 Fibonacci et mémoïsation
Cet exercice portera votre attention sur un problème d’efficacité lié au fait de devoir combiner plusieurs appels récursifs. Il proposera une solution dite de mémoïsation.
Question 5.1 Programmer fibo : int -> int de manière récursive et naïve, c’est-à-dire en retranscrivant directement la définition mathématique suivante : rappelons que F0 = 0, F1 = 1, et Fn = Fn−1 + Fn−2. On utilisera failwith en cas d’argument négatif.
5
Question 5.2 Copier et renommer fibo en fibocount : int -> int, ainsi que les appels récursifs bien sûr, et ajouter une ligne en début de fonction pour incrémenter un compteur global count (que vous aurez pris soin de déclarer au préalable en tant que ref). Ce comp- teur vous permet de traquer le nombre d’appel à fibocount. Ayant initialisé count à 0, puis exécuté fibocount n pour différentes valeurs de n, et répété l’expérience quelques fois, commenter sur la loi de croissance de count en fonction de n.
Question 5.3 Déclarer un tableau F de taille 1024, initialisé à −1 partout. Copier et re- nommer fibocount en memofibocount en remplaçant tous les appels récursifs à fibocount i, par un appel à une fonction fibocheck i.
Votre fibocheck i vérifie dans le tableau pour voir si F.(i) y a déjà été calculé. Si F.(i)=-1 ce n’est pas le cas, et donc fibocheck appelle memofibocount i pour remplir F.(i). Dans tous les cas, fibocheck i finit par renvoyer le F.(i).
Question 5.4 Ayant initialisé count à 0, puis exécuté memofibocount n pour différentes valeurs de n<1024, et répété l’expérience quelques fois, commenter sur la loi de croissance de count en fonction de n. Donner une courte explication de la différence de comportement par rapport à 5.1.
6