Écrire un contrat avant toute réalisation

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 6 — Types et structures de données abstraites

Énoncé

Un sac (ou multiensemble) est un ensemble où chaque élément a une multiplicité. Écrire son contrat — opérations, rôles, invariant —, puis écrire, en n'utilisant que ce contrat, un algorithme qui dit si deux listes sont des permutations l'une de l'autre.

Corrigé

Le contrat.

Opération	Rôle	Effet
`creer()`	constructeur	un sac vide
`ajouter(s, x)`	transformateur	incrémente la multiplicité de $x$
`retirer(s, x)`	transformateur	décrémente ; précondition : $m (x) \geq 1$
`multiplicite(s, x)`	accesseur	le nombre d'exemplaires de $x$
`cardinal(s)`	accesseur	le nombre total d'exemplaires

Invariant : toutes les multiplicités sont positives, et cardinal est leur somme. C'est cet invariant qui justifie la précondition de retirer — sans elle, une multiplicité pourrait devenir négative, et cardinal cesserait d'être un cardinal.

L'algorithme, écrit contre le contrat seul.


(* permutation a b dit si les listes a et b ont les memes elements avec
   les memes multiplicites. Ne suppose RIEN de la realisation du sac. *)
let permutation a b =
  let s = Sac.creer () in
  List.iter (fun x -> Sac.ajouter s x) a;
  let rec retire = function
    | [] -> true
    | x :: r -> if Sac.multiplicite s x = 0 then false
                else (Sac.retirer s x; retire r)
  in
  retire b && Sac.cardinal s = 0

Terminaison : le variant est la longueur de la liste restante. Correction : après la première boucle, $s$ porte exactement les multiplicités de $a$ ; la seconde retire celles de $b$ en refusant tout élément en excès ; on conclut que $a$ et $b$ ont les mêmes multiplicités si et seulement si aucun refus n'a eu lieu et qu'il ne reste rien.

Le test final Sac.cardinal s = 0 n'est pas décoratif : sans lui, la liste [1;2] serait déclarée permutation de [1], puisque tout élément de $b$ se retire. Il faut les deux inclusions.

Ce que l'exercice démontre. On vient d'écrire, de prouver et de raisonner sur un algorithme sans avoir choisi la réalisation du sac — c'est très exactement ce que le programme appelle « utiliser des structures de données avant d'avoir programmé leur réalisation concrète ». Et la complexité se lit dans le contrat, pas dans le code : si les trois opérations sont en $O (1)$ , l'algorithme est en $Θ (n)$ ; si elles sont en $O (n)$ , il est en $Θ (n^{2})$ . Changer de réalisation change la complexité sans changer une ligne.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.