informatique (MP2I/MPI) · Chapitre 5 · Exercice de TD

Problème — Le tri par partition-fusion, et la troisième récurrence

Récursivité · niveau 3 (difficile)

Énoncé

Écrire en OCaml le tri par partition-fusion sur les listes : une fonction coupe qui sépare, une fonction fusion qui recolle, et le tri lui-même.
Prouver la terminaison, puis la correction de fusion par récurrence.
Résoudre $T (n) = 2 T (n /2) + c n$ à la main, sans théorème général.
Comparer le nombre mesuré de comparaisons à $lo g_{2} (n!)$ , qui minore le coût de tout tri par comparaisons.

Corrigé de la question 1

1. Le tri.


(* coupe l renvoie deux listes dont la reunion est l, de longueurs
   egales a une unite pres. Complexite : Theta(|l|). *)
let rec coupe = function
  | [] -> ([], [])
  | [x] -> ([x], [])
  | x :: y :: r -> let (a, b) = coupe r in (x :: a, y :: b)

(* fusion a b : si a et b sont triees, renvoie la liste triee de leurs
   elements reunis (avec repetitions). Complexite : Theta(|a| + |b|). *)
let rec fusion a b = match a, b with
  | [], l | l, [] -> l
  | x :: r, y :: s -> if x <= y then x :: fusion r b else y :: fusion a s

(* tri l renvoie la liste des elements de l, triee par ordre croissant. *)
let rec tri = function
  | ([] | [_]) as l -> l
  | l -> let (a, b) = coupe l in fusion (tri a) (tri b)

Vérification : coupe [3;1;4;1;5;9;2;6] rend ([3;4;5;2], [1;1;9;6]) — un élément sur deux — et tri [3;1;4;1;5;9;2;6] rend [1;1;2;3;4;5;6;9] en $16$ comparaisons.

Question 2 : comment l'IA t'aide

2. Prouver la terminaison, puis la correction de fusion par récurrence.

Élève

Pour la terminaison de tri, je prends la longueur comme variant : coupe rend deux moitiés, donc deux listes strictement plus courtes. Pour fusion, je ne vois pas sur quoi faire la récurrence, puisque les deux listes ne raccourcissent pas en même temps.

Pour tri, teste ton affirmation sur une liste à un élément : que rend coupe, et qu'est-ce qui, dans le code, évite le problème ? Pour fusion, quelle quantité diminue à chaque appel récursif, quelle que soit la branche prise ?

Élève

Pour un élément, coupe rend la liste elle-même et une liste vide, mais le premier motif de tri traite ce cas sans appel récursif. Pour fusion, la somme des deux longueurs baisse de un à chaque appel.

Dans le cas $a = x :: r$ et $b = y :: s$ avec $x \leq y$ , pourquoi est-il légitime de placer $x$ en tête du résultat, et à quel couple de listes appliques-tu l'hypothèse de récurrence pour la suite ?

L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.

Continue cet exercice avec l'IA

Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.

Continuer avec l'IA — gratuit, sans inscription

Gratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.

Le cours du chapitre · Tous les exercices du chapitre

Continuer avec l'IA, gratuit →