Polytechnique Option Informatique MP 2010Sujet, corrigé et rapport du jury

COMPOSITION D'INFORMATIQUE

Plus proche ancêtre commun

Ce problème s'intéresse à la question suivante : étant donné un arbre et deux nœuds dans cet arbre, quel est le plus proche ancêtre commun de ces deux nœuds ? Une solution efficace à ce problème a de nombreuses applications, notamment en bio-informatique. Ainsi, dans l'arbre

le plus proche ancêtre commun des nœuds 5 et 8 est le nœud 4 , et celui des nœuds 3 et 7 est la racine 0 . De manière générale, on se donne un arbre quelconque, sur lequel on s'autorise un prétraitement, puis on souhaite calculer le plus efficacement possible le plus proche ancêtre commun pour des couples de nœuds dans cet arbre.

• si i est un ancêtre de j, alors PPAC(i, j) = i;
• symétriquement, si j est un ancêtre de i, alors PPAC(i, j) = j;
• sinon, PPAC(i, j) est l'unique nœud a possédant au moins deux fils distincts f_1 et f_2 tels que i appartient au sous-arbre f_1 et j au sous-arbre f_2.

        (* Caml *)
type arbre =
| Noeud of
    int * arbre list;;

    { Pascal }
type arbre = `noeud;
liste_arbre = `element;
noeud = record n :integer; l :liste_arbre; end;
element = record a :arbre; r :liste_arbre; end;

I. Une solution simple

(* Caml *) remplir_taille : unit -> unit
{ Pascal } procedure remplir_taille;

(* Caml *) appartient : int -> int -> bool
{ Pascal } function appartient(i : integer ; j : integer) : boolean;

II. Une solution plus efficace

1. ajouter le nœud i à la fin de la séquence résultat;
2. pour chaque fils j de i,
   (a) effectuer un tour Eulérien à partir de j,
   (b) ajouter le nœud i à la fin de la séquence résultat.

(* Caml *) remplir_M : unit -> unit
{ Pascal } procedure remplir_M;

(* Caml *) minimum : int -> int -> int
{ Pascal } function minimum(i : integer ; j : integer) : integer;

(* Caml *) ppac2 : int -> int -> int
{ Pascal } function ppac2(i : integer ; j : integer) : integer;

III. Opérations sur les bits des entiers primitifs

(* Caml *) bit_fort : int -> int
{ Pascal } function bit_fort(n : integer) : integer;

IV. Cas particulier d'un arbre binaire complet

Dans cette partie, on considère le problème du plus proche ancêtre commun dans le cas particulier où l'arbre A est un arbre binaire complet, c'est-à-dire que tout nœud de A a exactement zéro ou deux fils et toutes les feuilles de A sont à la même distance de la racine. (On continue cependant d'utiliser le même type arbre.) Voici un exemple d'arbre binaire complet de hauteur 2 :

On note que le chemin est vide pour la racine et que le suffixe de zéros est vide pour les feuilles. Pour l'arbre ci-dessus, on obtient les valeurs suivantes de B(i), données en binaire :

(* Caml *) remplir_B : unit -> unit
{ Pascal } procedure remplir_B;

(* Caml *) ppac3 : int -> int -> int
{ Pascal } function ppac3(i : integer ; j : integer) : integer;

V. Application

1. si i = j, l'arbre est réduit à la feuille T[i];
2. sinon, sa racine est le plus petit élément de T[i..j]; soit T[m] cet élément, avec i ≤ m ≤ j (s'il y a plusieurs valeurs possibles de m, on choisit arbitrairement). On distingue alors trois cas :
   (a) si m = i, on construit un unique sous-arbre à partir de T[m + 1..j],
   (b) si m = j, on construit un unique sous-arbre à partir de T[i..m − 1],
   (c) sinon, on construit deux sous-arbres, respectivement à partir de T[i..m − 1] et de T[m + 1..j].
   L'arbre A est alors défini en partant du segment complet T[0..n − 1]. On note que les nœuds de A ont directement pour valeurs les éléments de T, i.e. on ne se soucie pas ici de numéroter les nœuds de A de 0 à n − 1 afin de vérifier la propriété ( P ).

On propose un algorithme plus efficace pour construire l'arbre A. Cet algorithme construit incrémentalement l'arbre correspondant aux éléments de T[0..i], pour i allant de 0 à n − 1. Initialement, l'arbre est réduit à l'unique nœud T[0]. Supposons avoir déjà construit l'arbre correspondant aux i premiers éléments de T , c'est-à-dire au segment T[0..i − 1]. Cet arbre a la forme suivante

avec une «branche droite» formée de k nœuds tels que v_1 ≤ v_2 ≤ … ≤ v_(k − 1) ≤ v_k. Chaque arbre t_i est éventuellement vide et ne contient que des éléments strictement plus grands que v_i. Pour insérer l'élément suivant, soit v = T[i], on cherche la position de v dans la liste v_1, v_2, …, v_k, c'est-à-dire le plus grand j tel que v_j ≤ v < v_(j + 1) (si v < v_1 on pose j = 0 et si v_k ≤ v on pose j = k ). On crée alors un nouveau noeud v que l'on insère à la place de v_(j + 1) et le sous-arbre v_(j + 1) est accroché sous le nœud v. On obtient le nouvel arbre

dont la nouvelle branche droite est donc v_1, …, v_j, v. Si j = k, alors on ajoute v comme fils droit de v_k, et la nouvelle branche droite est simplement l'ancienne étendue par v (à la fin). On ne demande pas de montrer la correction de cet algorithme.

(* Caml *) construire_A : int array -> arbre
{ Pascal } function construire_A(t : array[0..n-1] of integer) : arbre;

Note : En 1984, Harel et Tarjan ont montré qu'il existe un pré-traitement de complexité linéaire sur un arbre qui permet d'obtenir ensuite le plus proche ancêtre commun en temps constant. On a donc le même résultat pour le problème du minimum du segment.