Corrigé Centrale 2025 Option informatique MP — Partie I (Q1 à Q8) : Tas d'appariement et tri par tas

Sujet officiel du concours Centrale, session 2025, épreuve Option informatique MP. Corrigé rédigé par Ibrahim Alame.

Énoncé

Un arbre est vide ou formé d'une étiquette et d'une liste (éventuellement vide) d'enfants non vides ; un tas d'appariement est un tel arbre où l'étiquette de chaque nœud est inférieure ou égale à celles de ses enfants (ordre polymorphe d'OCaml, lexicographique sur les tuples). Les tas sont persistants.


type 'a arbre =
  | Vide
  | Noeud of 'a * 'a arbre list

Figure 1 (un tas à 12 nœuds) :

Fusion de deux tas non vides : celui dont la racine est la plus grande devient le premier enfant (en tête de liste) de l'autre. Insertion : fusion avec un tas à un nœud. Suppression du minimum : on retire la racine et on fusionne ses $k$ enfants par paires : (a) on fusionne de gauche à droite les arbres deux par deux ; (b) on fusionne les $⌈ k /2 ⌉$ arbres obtenus un par un, de droite à gauche, en partant de celui de droite. Figure 2 (suppression de la racine du tas de la figure 1) :

Q1. Écrire min_valeur : 'a arbre -> 'a (tas non vide) ; complexité dans le pire cas.
Q2. Écrire fusion : 'a arbre -> 'a arbre -> 'a arbre, en gérant les tas vides.
Q3. Écrire insere : 'a -> 'a arbre -> 'a arbre ; complexité dans le pire cas.
Q4. Insérer $0, 1, \dots, 6$ dans cet ordre dans un tas vide, puis supprimer deux fois le minimum : dessiner le tas obtenu.
Q5. Écrire fusion_par_paires : 'a arbre list -> 'a arbre (Vide pour la liste vide).
Q6. En déduire suppression_min : 'a arbre -> 'a arbre ; complexité dans le pire cas.
On admet que $n$ opérations quelconques parmi min_valeur, insere, suppression_min, à partir du tas vide, coûtent $O (n lo g n)$ au total.
Q7. Écrire tri : 'a list -> 'a list, tri croissant par tas d'appariement.
Q8. Complexité de tri dans le meilleur cas ; forme de liste qui la réalise, avec justification.

Corrigé

Q1. La propriété de tas minimum, appliquée de proche en proche le long de chaque branche (récurrence sur la profondeur), montre que l'étiquette de la racine est inférieure ou égale à toutes les étiquettes de l'arbre : le minimum est la racine.


let min_valeur (t : 'a arbre) : 'a =
  match t with
  | Vide -> failwith "min_valeur : tas vide"
  | Noeud (x, _) -> x

Un seul filtrage : complexité $O (1)$ dans le pire cas (le cas Vide, exclu par l'énoncé, lève une exception).

Q2.


let fusion (t1 : 'a arbre) (t2 : 'a arbre) : 'a arbre =
  match t1, t2 with
  | Vide, t | t, Vide -> t
  | Noeud (x1, l1), Noeud (x2, l2) ->
    if x1 <= x2 then Noeud (x1, t2 :: l1)
    else Noeud (x2, t1 :: l2)

Si l'un des tas est vide, l'autre est le résultat. Sinon, la plus petite racine, disons $x_{1} \leq x_{2}$ , reste racine et l'autre tas devient son premier enfant : la propriété de tas est conservée, car le seul nouveau lien parent-enfant est $x_{1} \to x_{2}$ avec $x_{1} \leq x_{2}$ , et l'ensemble des étiquettes est la réunion (avec multiplicités) des deux ensembles. Aucune récursion, un filtrage et une comparaison : $O (1)$ . Les arbres d'origine ne sont pas modifiés (structure persistante).

Q3.


let insere (x : 'a) (t : 'a arbre) : 'a arbre = fusion (Noeud (x, [])) t

Noeud (x, []) est un tas à un élément ; d'après Q2, le résultat est un tas contenant $x$ et les éléments de t. Complexité $O (1)$ dans le pire cas (une construction et une fusion).

Q4. Insertions : insere 0 Vide donne le tas réduit à $0$ ; ensuite chaque nouvel élément $i \geq 1$ est plus grand que la racine $0$ et devient son premier enfant. Après les sept insertions, la racine $0$ a les feuilles $6, 5, 4, 3, 2, 1$ pour enfants, dans cet ordre.

Première suppression. On fusionne $[6; 5; 4; 3; 2; 1]$ par paires : étape (a), $6$ et $5$ donnent $5 [6]$ , $4$ et $3$ donnent $3 [4]$ , $2$ et $1$ donnent $1 [2]$ (la notation $r [\dots]$ liste les enfants de la racine $r$ ) ; étape (b), en partant de la droite, $3 [4]$ fusionné avec $1 [2]$ donne $1 [3 [4]; 2]$ , puis $5 [6]$ fusionné avec ce tas donne $1 [5 [6]; 3 [4]; 2]$ .

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →