Corrigé Centrale 2026 Option informatique MP — Partie B, I.3-I.4 (Q16 à Q27) : File à deux piles et bicoloration par parcours

Q16. Une pile n'a besoin que de trois opérations : tester si elle est vide, empiler au sommet, dépiler le sommet. Avec une liste dont la tête est le sommet, empiler est x :: p, dépiler est le filtrage x :: r, tester le vide est p = [] : les trois opérations coûtent $O(1)$, car elles n'agissent que sur la première cellule. De plus la liste est persistante : empiler ou dépiler ne détruit pas l'ancienne pile, qui reste utilisable (c'est ce qui permet aux fonctions de Q17 de renvoyer une nouvelle file). La discipline « dernier entré, premier sorti » est exactement celle de l'accès par la tête.

Q17. La fonction auxiliaire transvase dépile un à un les éléments de e et les empile sur s.

let initFile () : 'a file = { entree = [] ; sortie = [] }

let estVideFile (f : 'a file) : bool = f.entree = [] && f.sortie = []

let enfile ((x, f) : 'a * 'a file) : 'a file = { f with entree = x :: f.entree }

let rec transvase (e : 'a pile) (s : 'a pile) : 'a pile =
  match e with
  | [] -> s
  | x :: r -> transvase r (x :: s)

let rec defile (f : 'a file) : 'a * 'a file =
  match f.sortie, f.entree with
  | x :: r, _ -> (x, { f with sortie = r })
  | [], [] -> failwith "defile : file vide"
  | [], e -> defile { entree = [] ; sortie = transvase e [] }

transvase termine car la longueur de e décroît ; elle renvoie List.rev e @ s (récurrence sur la longueur de e). Dans defile, l'appel récursif se fait avec une sortie non vide, donc il se termine au cas suivant. Défiler une file vide lève une exception (cas non spécifié par le sujet).

Q18. Pour une file $f$, notons $\mathrm{cont}(f)$ la liste $\text{f.sortie}@\mathrm{rev}(\text{f.entree})$. Montrons l'invariant : $\mathrm{cont}(f)$ est la liste des éléments présents, rangés du plus ancien entré au plus récent. Il est vrai pour initFile () (liste vide) et il est conservé :

• enfile (x, f) donne $\text{f.sortie}@\mathrm{rev}(x::\text{f.entree})=\mathrm{cont}(f)@[x]$ : $x$, le plus récent, est ajouté à la fin ;
• le transvasement de $\{\text{entree}=e;\text{sortie}=[]\}$ en $\{\text{entree}=[];\text{sortie}=\mathrm{rev}(e)\}$ ne change pas $\mathrm{cont}$ (les deux valent $\mathrm{rev}(e)$) ;
• si sortie vaut $x::r$, defile renvoie $x$, qui est la tête de $\mathrm{cont}(f)$, c'est-à-dire l'élément le plus ancien, et la nouvelle file a pour contenu $r@\mathrm{rev}(\text{f.entree})$, la queue de $\mathrm{cont}(f)$.

Chaque defile renvoie donc le plus ancien des éléments présents : les éléments sortent dans l'ordre où ils sont entrés. (Test : $10000$ opérations aléatoires, puis vidage : la suite des sorties est égale à la suite des entrées.)

Q19. Si sortie est vide et entree contient $k$ éléments, defile fait $k$ dépilements et $k$ empilements (transvasement), plus un dépilement : $2k+1$ opérations, soit $\Theta (k)$. Pour une file de $k$ éléments, le pire cas est donc linéaire, $\Theta (k)$ (par exemple après $k$ enfile consécutifs sur une file vide). Dans les autres cas, defile coûte $O(1)$.