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

Problème — L'aller-retour de la sérialisation d'un arbre

Tableaux associatifs, hachage et sérialisation · niveau 3 (difficile)

Énoncé

Écrire la désérialisation, et détecter les entrées mal formées.
Démontrer que la sérialisation du chapitre est injective, donc que l'aller-retour est l'identité.
Le # est-il toujours nécessaire ? Étudier le cas d'un arbre binaire de recherche.

Corrigé de la question 1

1. La désérialisation. Elle suit la structure de l'écriture : un jeton # rend $Vide$ , un nombre lit son fils gauche puis son fils droit.


exception Format_invalide

(* Reconstruit l'arbre écrit par serialise. Lève Format_invalide si la chaîne
   ne code aucun arbre, ou en code un suivi de jetons superflus.
   Complexité : Theta(nombre de jetons) = Theta(2n+1). *)
let deserialise s =
  let reste = ref (List.filter (fun j -> j <> "")
                     (String.split_on_char ' ' s)) in
  let suivant () = match !reste with
    | [] -> raise Format_invalide          (* la chaîne s'arrête trop tôt *)
    | j :: r -> reste := r; j in
  let rec lire () =
    let j = suivant () in
    if j = "#" then Vide
    else
      let e = int_of_string j in
      let g = lire () in                   (* l'ORDRE compte : gauche AVANT droit *)
      let d = lire () in
      Noeud (g, e, d) in
  let a = lire () in
  if !reste <> [] then raise Format_invalide   (* des jetons en trop *)
  else a

Les deux contrôles ne sont pas décoratifs. Sans le premier, une chaîne tronquée provoquerait une exception obscure ; sans le second, "# 5 # #" serait acceptée en ne lisant que son premier jeton, et l'on perdrait silencieusement le reste. Un désérialiseur lit des données venues de l'extérieur : il doit refuser, pas deviner.

Mesuré : sur l'arbre du chapitre chap:arbres, deserialise (serialise a) = a rend true, et la chaîne compte $15$ jetons pour $7$ nœuds.

Question 2 : comment l'IA t'aide

2. Démontrer que la sérialisation du chapitre est injective, donc que l'aller-retour est l'identité.

Élève

Je fais une induction : si deux arbres non vides ont la même sérialisation, leurs étiquettes de racine sont égales, et la suite des jetons de $g_{1}$ puis $d_{1}$ égale celle de $g_{2}$ puis $d_{2}$ . Mais je ne vois pas comment en déduire $g_{1} = g_{2}$ .

C'est bien le point dur : en général, $uv = u^{'} v^{'}$ n'impose pas $u = u^{'}$ . Dans quel cas particulier cette égalité l'impose-t-elle, si $u$ et $u^{'}$ sont deux sérialisations d'arbres ?

Élève

Il ne faut pas que l'une soit un préfixe strict de l'autre. Je devrais donc montrer qu'aucune sérialisation n'est préfixe strict d'une autre, mais je ne vois pas comment m'y prendre.

Une sérialisation, lue jeton par jeton, « sait-elle » à quel moment elle se termine ? Que faudrait-il suivre au fil de la lecture pour le détecter, et comment cette quantité évolue-t-elle sur une étiquette et sur un # ?

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 →