DS 1 — Typage, listes et récursivité

MPSI option informatique, année scolaire 2021-2022 — devoir surveillé du 12 mars 2022 — durée totale 2h.

Corrigés

La source ne comporte pas de corrigé. Les corrigés des questions de programmation ci-dessous sont des propositions (testées), à relire.

I. Typage

Question 1. Dans une expression conditionnelle if expr1 then expr2 else expr3, quelles sont les contraintes de types sur expr1, expr2 et expr3 ? Quel est alors le type de cette expression et sa valeur ?

Question 2. Quelles sont les contraintes de types sur expr1 et expr2 pour que l'expression (expr1 expr2) soit une expression bien typée en CAML et quel est alors son type et sa valeur ?

Question 3. Déterminer le type des fonctions suivantes. Certaines définitions sont équivalentes et ne diffèrent que par la syntaxe utilisée. Préciser quelles sont les définitions équivalentes.

let f01 x y = x
let f02 x = fun y -> y
let f03 x y = x y
let f04 x y = y x
let f05 x y = x y y
let f06 x y = x (x y)
let f07 = fun x -> fun y -> y (x y)
let f08 x y = (x y) y
let f09 x y = x (y x)
let f10 x y = y (x y)

Question 4. Prévoir et donner la réponse de CAML pour chacune des phrases dans la séquence suivante :

let a = fun b -> (b 4) / 5
let b a = fun c -> a (fun d -> c + d) + c
let c = b a
let d = c 11

II. Type somme

On considère le type entier suivant :

type entier =
  | Zero
  | Successeur of entier

Question 5. Écrire une fonction add : entier -> entier -> entier réalisant l'addition de deux entiers avec ce type.

Corrigé

let rec add a b =
  match a with
  | Zero -> b
  | Successeur a' -> Successeur (add a' b)

Question 6. Écrire une fonction mult : entier -> entier -> entier réalisant la multiplication de deux entiers avec ce type.

Corrigé

let rec mult a b =
  match a with
  | Zero -> Zero
  | Successeur a' -> add b (mult a' b)

III. Listes

Question 7. Écrire une fonction produit : int list -> int qui renvoie le produit des éléments d'une liste d'entiers.

Corrigé

let rec produit l =
  match l with
  | [] -> 1
  | x :: q -> x * produit q

Question 8. Écrire une fonction supprime : 'a -> 'a list -> 'a list qui renvoie une liste identique à celle passée en argument à ceci près que toutes les occurrences éventuelles de l'élément passé en argument ont été supprimées.

Corrigé

let rec supprime x l =
  match l with
  | [] -> []
  | y :: q -> if x = y then supprime x q else y :: supprime x q

Question 9. Écrire une fonction avant_dernier : 'a list -> 'a qui renvoie l'avant-dernier élément d'une liste de taille au moins deux. Le filtrage devra être exhaustif et on lèvera une exception (avec failwith) si la liste est trop courte.

Corrigé

let rec avant_dernier l =
  match l with
  | [] | [_] -> failwith "liste trop courte"
  | [x; _] -> x
  | _ :: q -> avant_dernier q

IV. Tri fusion

Question 10. Implémenter une fonction division : 'a list -> 'a list * 'a list qui divise une liste passée en argument en deux sous-listes de même taille, à un près. La première sous-liste doit contenir les éléments d'indices pairs et la deuxième ceux d'indices impairs, dans le même ordre relatif que dans la liste initiale. Par exemple :

division [1; 4; 2; 6; 7; 1; 2; 4; 2]
- : int list * int list = ([1; 2; 7; 2; 2], [4; 6; 1; 4])

Corrigé

let rec division l =
  match l with
  | [] -> [], []
  | [x] -> [x], []
  | x :: y :: q ->
    let l1, l2 = division q in
    x :: l1, y :: l2

Question 11. Implémenter une fonction fusion : 'a list -> 'a list -> 'a list qui prend en argument deux listes, supposées triées, et qui renvoie la liste triée formée des éléments des deux listes (avec doublons). Par exemple :

fusion [1; 2; 2; 2; 7] [1; 4; 4; 6]
- : int list = [1; 1; 2; 2; 2; 4; 4; 6; 7]

Corrigé

let rec fusion l1 l2 =
  match l1, l2 with
  | [], _ -> l2
  | _, [] -> l1
  | x :: q1, y :: q2 ->
    if x <= y
    then x :: fusion q1 l2
    else y :: fusion l1 q2

Question 12. Implémenter une fonction tri_fusion : 'a list -> 'a list qui trie la liste reçue en argument. Par exemple :

tri_fusion [1; 4; 2; 6; 7; 1; 2; 4; 2]
- : int list = [1; 1; 2; 2; 2; 4; 4; 6; 7]

Corrigé

let rec tri_fusion l =
  match l with
  | [] | [_] -> l
  | _ ->
    let l1, l2 = division l in
    fusion (tri_fusion l1) (tri_fusion l2)

V. Dénombrement de \(\N^2\)

On se propose dans cette partie d'étudier une fonction permettant de numéroter les éléments de \(\N^2\).

On considère la fonction \(carre\) définie par :

\[ \forall (x, y) \in \N^2, \quad carre(x, y) = (\max(x, y))^2 + \max(x, y) + y - x \]

Question 13. Définir en CAML la fonction carre : int -> int -> int.

Corrigé

let carre x y =
  let m = max x y in
  m * m + m + y - x

La fonction \(carre\) permet d'effectuer une numérotation dite en carré des éléments de \(\N^2\).

Question 14. Représenter dans le plan les points numérotés entre 0 et 30 et justifier le nom de la fonction.

La fonction \(carre\_rec\) est définie sur \(\N \times \N\) par \(\forall (m,n) \in \N^2\),

\[ carre\_rec(m,n) = \begin{cases} m^2 & \text{lorsque } n = 0 \\ carre\_rec(m,n-1) + 1 & \text{lorsque } 1 \le n \le m \\ carre\_rec(m+1,n) + 1 & \text{lorsque } n > m \end{cases} \]

Question 15. Définir en CAML la fonction carre_rec : int -> int -> int.

Corrigé

let rec carre_rec m n =
  if n = 0 then m * m
  else if n <= m then carre_rec m (n-1) + 1
  else carre_rec (m+1) n + 1

Question 16. Montrer que la fonction \(carre\_rec\) est égale à la fonction \(carre\).

Question 17. Prouver la terminaison de la fonction \(carre\_rec\).

VI. Ackermann

La fonction d'Ackermann \(A\) est définie sur \(\N \times \N\) par :

\[ \begin{cases} A(0,p) = p+1 \\ A(n,0) = A(n-1,1) & \text{si } n > 0 \\ A(n,p) = A(n-1,A(n,p-1)) & \text{si } n > 0 \text{ et } p > 0 \end{cases} \]

Question 18. Calculer \(A(0,0)\) puis \(A(2,2)\).

Question 19. Implémenter une fonction calculant \(A\) en CAML, elle sera du type int -> int -> int.

Corrigé

let rec ackermann n p =
  if n = 0 then p + 1
  else if p = 0 then ackermann (n-1) 1
  else ackermann (n-1) (ackermann n (p-1))

VII. Exponentiation rapide

Question 20. Définir une fonction exp : int -> int -> int qui étant donné deux entiers \(x\) et \(n\) calcule \(x^n\) de manière naïve, en faisant des multiplications successives par \(x\).

Corrigé

let rec exp x n =
  if n = 0 then 1
  else x * exp x (n-1)

Il est possible d'améliorer ce calcul en remarquant que :

\[ x^{2n} = (x^n)^2 \qquad x^{2n+1} = x \times (x^n)^2 \]

On peut donc calculer récursivement \(x^n\) pour en déduire \(x^{2n}\) avec une multiplication de plus et \(x^{2n+1}\) avec deux multiplications de plus.

Question 21. Définir une fonction exp_rap : int -> int -> int qui réalise cette méthode de calcul.

Corrigé

let rec exp_rap x n =
  if n = 0 then 1
  else begin
    let y = exp_rap x (n / 2) in
    if n mod 2 = 0 then y * y
    else x * y * y
  end

Question 22. Justifier, avec précision et rigueur, la terminaison et la correction de cette fonction.

Question 23. Déterminer, en fonction \(n\), le nombre total d'appels à la fonction pour calculer \(x^n\). On pourra noter \(C_n\) le nombre d'appels pour calculer exp_rap n et chercher une relation de récurrence vérifiée par la suite \((C_n)_{n \in \N}\).