L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie.
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.
Les arbres que l'on considère ici ont des nœuds étiquetés par des entiers distincts. Chaque nœud a un nombre fini de descendants immédiats, appelés ses fils. Un nœud sans descendant est appelé une feuille. Dans l'exemple ci-dessus, le noeud 4 a trois fils, à savoir 5, 6 et 7, et les feuilles sont et 9 . Le sous-arbre du nœud est défini récursivement de la manière suivante : c'est l'ensemble de nœuds contenant et l'union de tous les sous-arbres des fils de . On écrira simplement «sous-arbre » pour désigner le sous-arbre du nœud . Si un nœud appartient au sous-arbre , on dit que est un ancêtre de . En particulier, chaque nœud est son propre ancêtre.
Le plus proche ancêtre commun de deux nœuds et , noté PPAC , est défini formellement de la manière suivante :
si est un ancêtre de , alors ;
symétriquement, si est un ancêtre de , alors
sinon, est l'unique nœud possédant au moins deux fils distincts et tels que appartient au sous-arbre et au sous-arbre .
Les arbres seront représentés en Caml et en Pascal de la manière suivante :
(* 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;
Dans l'ensemble de ce problème, on se fixe une constante entière n , avec , et un arbre A contenant nœuds numérotés de 0 à . On suppose en outre que cette numérotation vérifie la propriété suivante :
Pour tout , les nœuds du sous-arbre portent des numéros consécutifs à partir de . On note que la racine de A est donc nécessairement le nœud 0 .
La partie I propose une solution simple mais inefficace pour le problème du plus proche ancêtre commun. La partie II propose ensuite une solution plus efficace, avec un pré-traitement en et une réponse en temps constant. Les parties III et IV étudient le cas particulier des arbres binaires complets. Enfin, la partie V étudie une application du calcul du plus proche ancêtre commun.
Les parties peuvent être traitées indépendamment. Mais attention, chaque partie utilise des notations et des fonctions introduites dans les parties précédentes. Les tableaux sont indexés à partir de 0 et la notation t est utilisée dans les questions pour désigner l'élément d'indice du tableau t , indépendamment du langage de programmation choisi. On appelle segment et on note le sous-tableau du tableau t défini en considérant les indices compris entre et au sens large.
I. Une solution simple
Dans cette partie, on considère une solution simple qui calcule le plus proche ancêtre commun en temps .
Question 1 On suppose avoir déclaré un tableau global taille de taille n. Écrire une procédure remplir_taille qui stocke dans taille le nombre de nœuds du sous-arbre , pour tout entre 0 et . On garantira une complexité .
(* Caml *) remplir_taille : unit -> unit
{ Pascal } procedure remplir_taille;
Par la suite, on suppose avoir appelé cette procédure.
Question 2 Écrire une fonction appartient qui prend en arguments deux nœuds et et détermine, en temps constant, si appartient au sous-arbre .
(* Caml *) appartient : int -> int -> bool
{ Pascal } function appartient(i : integer ; j : integer) : boolean;
Question 3 Écrire une fonction ppac1 qui prend en arguments deux nœuds et et détermine en temps .
(* Caml *) ppac1 : int -> int -> int
{ Pascal } function ppac1 (i : integer ; j : integer) : integer;
II. Une solution plus efficace
Dans cette partie, on va effectuer un pré-traitement de l'arbre A qui permettra de déterminer ensuite en temps constant le plus proche ancêtre commun pour tout couple de nœuds.
On commence par construire une séquence de nœuds en effectuant un tour Eulérien de l'arbre A à partir de sa racine. D'une manière générale, le tour Eulérien à partir du nœud est défini comme agissant sur une séquence résultat, construite de la manière suivante :
ajouter le nœud à la fin de la séquence résultat;
pour chaque fils de ,
(a) effectuer un tour Eulérien à partir de ,
(b) ajouter le nœud à la fin de la séquence résultat.
Ainsi, sur l'exemple de l'arbre (1), on obtient la séquence suivante :
Question 4 Montrer que le tour Eulérien de A contient exactement éléments. Par la suite, on appelle cette valeur et on suppose avoir déclaré un tableau global euler de taille destiné à contenir le résultat du tour Eulérien.
Question 5 On suppose avoir déclaré un tableau global index de taille n. Écrire une procédure remplir_euler qui remplit le tableau euler avec le résultat du tour Eulérien de A et, dans le même temps, le tableau index de telle sorte que euler[index[ ]] pour tout entre 0 et (s'il existe plusieurs valeurs possibles pour index , on pourra choisir arbitrairement).
(* Caml *) remplir_euler : unit -> unit
{ Pascal } procedure remplir_euler;
Par la suite, on suppose avoir appelé cette procédure.
Question 6 Montrer que le plus proche ancêtre commun de et dans A est égal au plus petit élément du tableau euler compris entre les indices index et index .
Question 7 Écrire une fonction qui prend en argument un entier , avec , et calcule le plus grand entier tel que .
(* Caml *) : int -> int
{ Pascal } function
Question 8 On pose . On suppose avoir déclaré une matrice globale M de taille . Écrire une procédure remplir_M qui remplit la matrice M de telle sorte que, pour tout et tout , on ait
On garantira une complexité , c'est-à-dire au plus proportionnelle à la taille de la matrice M.
(* Caml *) remplir_M : unit -> unit
{ Pascal } procedure remplir_M;
Par la suite, on suppose avoir appelé cette procédure.
Question 9 Écrire une fonction minimum qui prend en arguments deux entiers et , avec , et qui détermine le plus petit élément du segment euler en temps constant.
(* Caml *) minimum : int -> int -> int
{ Pascal } function minimum(i : integer ; j : integer) : integer;
Question 10 Écrire une fonction ppac2 qui prend en arguments deux nœuds et et qui détermine en temps constant.
(* Caml *) ppac2 : int -> int -> int
{ Pascal } function ppac2(i : integer ; j : integer) : integer;
III. Opérations sur les bits des entiers primitifs
Dans cette partie, on introduit des notations et des fonctions qui seront utiles pour la partie IV. Il s'agit de fonctions opérant sur la représentation binaire des entiers primitifs (type int de Caml ou integer de Pascal). On ne considère ici que des entiers positifs ou nuls, s'écrivant en binaire sur un nombre de bits dont la valeur est non précisée et non connue (mais inférieure ou égale à 30 ). Un entier s'écrivant en binaire sur bits est noté où chaque bit vaut 0 ou 1 . Les chiffres les moins significatifs sont écrits à droite, de sorte que la valeur de est donc .
On suppose que le langage fournit les trois opérations et_bits, ou_bits et ou_excl_bits calculant respectivement les opérations ET, OU et OU-exclusif sur les représentations binaires de deux entiers, en temps constant. Plus précisément, si et , alors et_bits est l'entier défini par pour tout ; de même pour les opérations ou_bits et ou_excl_bits. On rappelle que les opérations ET, OU et OU-exclusif sont définies par les tables de vérité suivantes :
ET
0
1
0
0
0
1
0
1
OU
0
1
0
0
1
1
1
1
OU-exclusif
0
1
0
0
1
1
1
0
On suppose que le langage fournit également deux opérations decalage_gauche et decalage_droite décalant respectivement les bits d'un entier vers la gauche et vers la droite, en insérant des bits 0 respectivement à droite et à gauche. Plus précisément, si et si alors
Question 11 Écrire une fonction bit_fort qui prend en argument un entier , supposé non nul, et détermine le plus grand indice tel que , c'est-à-dire la position du bit le plus significatif de . On garantira une complexité .
(* Caml *) bit_fort : int -> int
{ Pascal } function bit_fort(n : integer) : integer;
Question 12 Pour plus d'efficacité, on peut pré-calculer et ranger dans un tableau les valeurs de bit_fort pour les 256 premiers entiers. Écrire une nouvelle version de bit_fort qui exploite cette idée pour n'effectuer pas plus de deux décalages. (On rappelle qu'on a supposé .)
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 :
D'une manière générale, si on note la hauteur de , alors possède feuilles et nœuds au total. La hauteur d'un nœud dans l'arbre A est définie comme sa distance aux feuilles. Dans l'exemple ci-dessus, les feuilles 2, 3, 5, 6 ont pour hauteur 0 , les nœuds 1 et 4 ont pour hauteur 1 et la racine 0 a pour hauteur 2 .
L'idée consiste alors à associer à chaque nœud un entier dont la représentation en binaire sur bits encode sa position dans l'arbre. On procède ainsi : le chemin qui mène de la racine au nœud est représenté par une suite de 0 et de 1 , avec la convention que 0 représente un déplacement vers le sous-arbre gauche et 1 un déplacement vers le sous-arbre droit. Pour un nœud de hauteur , on obtient donc un chemin de longueur , soit . À ce chemin, on concatène alors à droite la représentation binaire de , c'est-à-dire un bit 1 suivi de bits 0 . Au final, on a donc pour tout nœud de hauteur dans A :
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 , données en binaire :
On note que les prennent toutes les valeurs entre 1 et n , et qu'il y a donc bijection entre les nœuds et les valeurs que leur associe la fonction .
Question 13 On suppose avoir déclaré deux tableaux globaux, B de taille n et Binv de taille . Écrire une procédure remplir_B qui remplit le tableau avec les valeurs de et le tableau Binv avec les valeurs de (l'élément d'indice 0 de Binv étant inutilisé). On garantira une complexité .
(* Caml *) remplir_B : unit -> unit
{ Pascal } procedure remplir_B;
Par la suite, on suppose avoir appelé cette procédure.
Question 14 Soient et deux nœuds de A tels que n'est pas un ancêtre de et n'est pas un ancêtre de . Soit le résultat de ou_excl_bits , puis le résultat de bit_fort . Que représente ? Comment en déduire la valeur de , où est le plus proche ancêtre commun de et dans A ?
Question 15 Déduire de la question précédente une fonction ppac3 qui prend en arguments deux nœuds et et qui détermine en temps constant. On prendra soin de traiter différemment le cas où est un ancêtre de ou un ancêtre de ; on pourra réutiliser à cet effet la fonction appartient de la question .
(* Caml *) ppac3 : int -> int -> int
{ Pascal } function ppac3(i : integer ; j : integer) : integer;
V. Application
Dans cette partie, on considère une application du calcul du plus proche ancêtre commun au problème suivant : étant donné un tableau T de n entiers, on souhaite calculer, pour des paires d'indices et tels que , l'élément minimum du segment . Comme pour le calcul du plus proche ancêtre commun, on s'autorise un pré-traitement du tableau T permettant ensuite de répondre en temps constant pour tout segment. L'idée est de construire un arbre A contenant les éléments de et de se ramener au problème du plus proche ancêtre commun.
D'une manière générale, on définit un arbre binaire à partir d'un segment non vide en procédant récursivement de la manière suivante :
si , l'arbre est réduit à la feuille ;
sinon, sa racine est le plus petit élément de ; soit cet élément, avec (s'il y a plusieurs valeurs possibles de , on choisit arbitrairement). On distingue alors trois cas :
(a) si , on construit un unique sous-arbre à partir de ,
(b) si , on construit un unique sous-arbre à partir de ,
(c) sinon, on construit deux sous-arbres, respectivement à partir de et de .
L'arbre A est alors défini en partant du segment complet . 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 à afin de vérifier la propriété ( P ).
On admet le résultat suivant : le plus proche ancêtre commun des nœuds correspondant à et dans A est égal à l'élément minimum du segment .
Question 16 Donner la complexité dans le pire des cas de l'algorithme récursif ci-dessus construisant à partir de , en fonction de (en supposant le minimum calculé en temps linéaire).
On propose un algorithme plus efficace pour construire l'arbre A. Cet algorithme construit incrémentalement l'arbre correspondant aux éléments de , pour allant de 0 à . Initialement, l'arbre est réduit à l'unique nœud . Supposons avoir déjà construit l'arbre correspondant aux premiers éléments de T , c'est-à-dire au segment . Cet arbre a la forme suivante
avec une «branche droite» formée de nœuds tels que . Chaque arbre est éventuellement vide et ne contient que des éléments strictement plus grands que . Pour insérer l'élément suivant, soit , on cherche la position de dans la liste , c'est-à-dire le plus grand tel que (si on pose et si on pose ). On crée alors un nouveau noeud que l'on insère à la place de et le sous-arbre est accroché sous le nœud . On obtient le nouvel arbre
dont la nouvelle branche droite est donc . Si , alors on ajoute comme fils droit de , et la nouvelle branche droite est simplement l'ancienne étendue par (à la fin). On ne demande pas de montrer la correction de cet algorithme.
Question 17 Écrire une fonction construire_A qui construit l'arbre A à partir du tableau T en suivant ce nouvel algorithme.
(* Caml *) construire_A : int array -> arbre
{ Pascal } function construire_A(t : array[0..n-1] of integer) : arbre;
Indication : on pourra représenter la branche droite par une liste d'arbre (du type arbre list en Caml et liste_arbre en Pascal), dans l'ordre inverse, c'est-à-dire . Chacun de ces arbres a une racine et au plus un fils .
Question 18 Montrer que la complexité de cet algorithme est .
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.
Polytechnique Option Informatique MP 2010 - Version Web LaTeX | WikiPrépa | WikiPrépa
