X Informatique MP 2010

Thème de l'épreuve Plus proche ancêtre commun
Principaux outils utilisés arbres, récursivité, opérations logiques bit à bit
Mots clefs plus proche ancêtre commun, arbre, logique binaire

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                       

Rapport du jury

(télécharger le PDF)
           

Énoncé obtenu par reconnaissance optique des caractères


MP ÉCOLE POLYTECHNIQUE FILIÈRE OPTION INFORMATIQUE CONCOURS D'ADMISSION 2010 COMPOSITION D'INFORMATIQUE (Durée : 4 heures) 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 noeuds dans cet arbre, quel est le plus proche ancêtre commun de ces deux noeuds ? Une solution efficace à ce problème a de nombreuses applications, notamment en bio-informatique. Ainsi, dans l'arbre 0 1 2 4 3 5 (1) 6 7 8 9 le plus proche ancêtre commun des noeuds 5 et 8 est le noeud 4, et celui des noeuds 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 noeuds dans cet arbre. Les arbres que l'on considère ici ont des noeuds étiquetés par des entiers distincts. Chaque noeud a un nombre fini de descendants immédiats, appelés ses fils. Un noeud 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 2, 3, 5, 6, 8 et 9. Le sous-arbre du noeud i est défini récursivement de la manière suivante : c'est l'ensemble de noeuds contenant i et l'union de tous les sous-arbres des fils de i. On écrira simplement « sous-arbre i » pour désigner le sous-arbre du noeud i. Si un noeud j appartient au sous-arbre i, on dit que i est un ancêtre de j. En particulier, chaque noeud est son propre ancêtre. Le plus proche ancêtre commun de deux noeuds i et j, noté PPAC(i, j), est défini formellement de la manière suivante : ­ 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 noeud a possédant au moins deux fils distincts f1 et f2 tels que i appartient au sous-arbre f1 et j au sous-arbre f2 . 1 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 n 1, et un arbre A contenant n noeuds numérotés de 0 à n - 1. On suppose en outre que cette numérotation vérifie la propriété suivante : Pour tout i, les noeuds du sous-arbre i portent des numéros consécutifs à partir de i. (P) On note que la racine de A est donc nécessairement le noeud 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 O(n log n) 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[i] est utilisée dans les questions pour désigner l'élément d'indice i du tableau t, indépendamment du langage de programmation choisi. On appelle segment et on note t[i..j] le sous-tableau du tableau t défini en considérant les indices compris entre i et j 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 O(n). Question 1 On suppose avoir déclaré un tableau global taille de taille n. Écrire une procédure remplir_taille qui stocke dans taille[i] le nombre de noeuds du sous-arbre i, pour tout i entre 0 et n - 1. On garantira une complexité O(n). (* 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 noeuds i et j et détermine, en temps constant, si i appartient au sous-arbre j. (* Caml *) appartient : int -> int -> bool { Pascal } function appartient(i : integer ; j : integer) : boolean ; 2 Question 3 Écrire une fonction ppac1 qui prend en arguments deux noeuds i et j et détermine PPAC(i, j) en temps O(n). (* 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 noeuds. On commence par construire une séquence de noeuds 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 noeud i est défini comme agissant sur une séquence résultat, construite de la manière suivante : 1. ajouter le noeud 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 noeud i à la fin de la séquence résultat. Ainsi, sur l'exemple de l'arbre (1), on obtient la séquence suivante : 0, 1, 2, 1, 3, 1, 0, 4, 5, 4, 6, 4, 7, 8, 7, 9, 7, 4, 0 Question 4 Montrer que le tour Eulérien de A contient exactement 2 × n - 1 éléments. Par la suite, on appelle m cette valeur et on suppose avoir déclaré un tableau global euler de taille m 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[i]] = i pour tout i entre 0 et n - 1 (s'il existe plusieurs valeurs possibles pour index[i], 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 i et j dans A est égal au plus petit élément du tableau euler compris entre les indices index[i] et index[j]. Question 7 Écrire une fonction log2 qui prend en argument un entier n, avec n 1, et calcule le plus grand entier k tel que 2k n. (* Caml *) log2 : int -> int { Pascal } function log2(n : integer) : integer ; 3 Question 8 On pose k = log2(m). On suppose avoir déclaré une matrice globale M de taille m × (k + 1). Écrire une procédure remplir_M qui remplit la matrice M de telle sorte que, pour tout 0 j k et tout 0 i m - 2j , on ait M[i][j] = min euler[l] il 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 i et j, avec 0 i j < m, et qui détermine le plus petit élément du segment euler[i..j] 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 noeuds i et j et qui détermine PPAC(i, j) 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 N dont la valeur est non précisée et non connue (mais inférieure ou égale à 30). Un entier x s'écrivant en binaire sur N bits est noté (xN -1 . . . x1 x0 )2 où chaque bit xi vaut 0 ou 1. Les chiffres les moins significatifs sont écrits à droite, de sorte que la valeur P -1 i de x est donc N i=0 xi 2 . 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 x = (xN -1 . . . x1 x0 )2 et y = (yN -1 . . . y1 y0 )2 , alors et_bits(x, y) est l'entier z = (zN -1 . . . z1 z0 )2 défini par zi = ET(xi , yi ) pour tout i ; 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 OU OU-exclusif 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 1 0 1 1 1 1 1 1 0 4 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 x = (xN -1 . . . x1 x0 )2 et si 0 k N alors decalage_gauche(x, k) = (xN -1-k . . . x1 x0 0| .{z . . 0})2 k decalage_droite(x, k) = (0 . . 0} xN -1 . . . xk+1 xk )2 | .{z k Question 11 Écrire une fonction bit_fort qui prend en argument un entier x = (xN -1 . . . x1 x0 )2 , supposé non nul, et détermine le plus grand indice i tel que xi = 1, c'est-à-dire la position du bit le plus significatif de x. On garantira une complexité O(N ). (* 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é N 30.) 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 noeud 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 : 0 1 2 4 3 5 6 D'une manière générale, si on note d la hauteur de A, alors A possède 2d feuilles et n = 2d+1 - 1 noeuds au total. La hauteur d'un noeud 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 noeuds 1 et 4 ont pour hauteur 1 et la racine 0 a pour hauteur 2. L'idée consiste alors à associer à chaque noeud i un entier B(i) dont la représentation en binaire sur d + 1 bits encode sa position dans l'arbre. On procède ainsi : le chemin qui mène de la racine au noeud 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 noeud de hauteur h, on obtient donc un chemin de longueur d - h, soit xd . . . xh+1 . À ce chemin, on concatène alors à droite la représentation binaire de 2h , c'est-à-dire un bit 1 suivi de h bits 0. Au final, on a donc pour tout noeud i de hauteur h dans A : B(i) = ( xd . . . xh+1 1 0| .{z . . 0} )2 | {z } chemin de 0 à i h 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 : 5 (100)2 (010)2 (001)2 (110)2 (011)2 (101)2 (111)2 On note que les B(i) prennent toutes les valeurs entre 1 et n, et qu'il y a donc bijection entre les noeuds et les valeurs que leur associe la fonction B. Question 13 On suppose avoir déclaré deux tableaux globaux, B de taille n et Binv de taille n + 1. Écrire une procédure remplir_B qui remplit le tableau B avec les valeurs de B et le tableau Binv avec les valeurs de B -1 (l'élément d'indice 0 de Binv étant inutilisé). On garantira une complexité O(n). (* Caml *) remplir_B : unit -> unit { Pascal } procedure remplir_B ; Par la suite, on suppose avoir appelé cette procédure. Question 14 Soient i et j deux noeuds de A tels que i n'est pas un ancêtre de j et j n'est pas un ancêtre de i. Soit x le résultat de ou_excl_bits(B(i), B(j)), puis k le résultat de bit_fort(x). Que représente k ? Comment en déduire la valeur de B(a), où a est le plus proche ancêtre commun de i et j dans A ? Question 15 Déduire de la question précédente une fonction ppac3 qui prend en arguments deux noeuds i et j et qui détermine PPAC(i, j) en temps constant. On prendra soin de traiter différemment le cas où i est un ancêtre de j ou j un ancêtre de i ; 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 i et j tels que 0 i j < n, l'élément minimum du segment T[i..j]. 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 n éléments de T 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 T[i..j] en procédant récursivement de la manière suivante : 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 : 6 (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 noeuds de A ont directement pour valeurs les éléments de T, i.e. on ne se soucie pas ici de numéroter les noeuds de A de 0 à n - 1 afin de vérifier la propriété (P). On admet le résultat suivant : le plus proche ancêtre commun des noeuds correspondant à i et j dans A est égal à l'élément minimum du segment T[i..j]. Question 16 Donner la complexité dans le pire des cas de l'algorithme récursif ci-dessus construisant A à partir de T, en fonction de n (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 T[0..i], pour i allant de 0 à n - 1. Initialement, l'arbre est réduit à l'unique noeud 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 v 1 v2 t1 (2) vk-1 t2 vk tk-1 tk avec une « branche droite » formée de k noeuds tels que v1 v2 . . . vk-1 vk . Chaque arbre ti est éventuellement vide et ne contient que des éléments strictement plus grands que vi . Pour insérer l'élément suivant, soit v = T[i], on cherche la position de v dans la liste v1 , v2 , . . . , vk , c'est-à-dire le plus grand j tel que vj v < vj+1 (si v < v1 on pose j = 0 et si vk v on pose j = k). On crée alors un nouveau noeud v que l'on insère à la place de vj+1 et le sous-arbre vj+1 est accroché sous le noeud v. On obtient le nouvel arbre v1 vj t1 tj v vj+1 vk tj+1 tk dont la nouvelle branche droite est donc v1 , . . . , vj , v. Si j = k, alors on ajoute v comme fils droit de vk , 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. 7 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 vk , . . . , v1 . Chacun de ces arbres a une racine vi et au plus un fils ti . Question 18 Montrer que la complexité de cet algorithme est O(n). 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. 8

Extrait du corrigé obtenu par reconnaissance optique des caractères


 X Informatique MP 2010 -- Corrigé Ce corrigé est proposé par Vincent Danjean (Enseignant-chercheur en école d'ingénieur) ; il a été relu par Olivier Levillain (École Polytechnique) et Benjamin Monmege (ENS Cachan). Ce problème s'intéresse au problème de la recherche du plus petit ancêtre commun (PPAC en abrégé) dans un arbre. Ce thème possède de nombreuses applications, notamment en bio-informatique. Le sujet s'articule en cinq parties relativement indépendantes. · La première propose une implémentation simple de la recherche du PPAC. · La deuxième élabore une solution plus complexe mais plus efficace, à l'aide d'un parcours eulérien de l'arbre. · La troisième partie, qui ne comprend que deux questions, introduit des manipulations de bits ; il s'agit d'un préliminaire pour la partie suivante. · La partie 4 reprend le problème initial, mais suppose cette fois que l'arbre est binaire complet. Cela permet d'utiliser une méthode originale et efficace basée sur des manipulations de bits. · Enfin, la cinquième partie est une application de la recherche du PPAC dans un arbre pour trouver des minimums sur les segments d'un tableau. Ce sujet aborde bien évidemment les notions d'arbre, et donc la récursivité pour leur parcours. La structure d'arbre imposée permet de manipuler des arbres d'arité quelconque. Les parties 3 et 4 font également beaucoup intervenir les opérations logiques bit à bit. L'introduction du sujet est assez longue. Il faut cependant bien la lire puisqu'elle présente des propriétés, en particulier sur la numérotation des arbres, qui seront beaucoup utilisées dans tout le sujet. L'énoncé introduit également de nombreuses variables globales, généralement des entiers ou des tableaux d'entiers. Il est demandé, la plupart du temps, d'écrire le code nécessaire à leur utilisation. Indications 1 Écrire une fonction récursive taille_liste_arbres qui calcule la somme des tailles des arbres de la liste (en stockant au passage la taille du premier élément de la liste dans le tableau taille). 2 Penser à utiliser la propriété P du sujet (et le tableau taille). 3 Traiter d'abord le cas où l'un des noeuds est ancêtre de l'autre ; sinon, descendre dans l'arbre jusqu'à trouver le PPAC. On peut s'aider d'une fonction auxiliaire pour chercher dans une liste d'arbres celui qui contient un noeud particulier. 4 Démontrer la propriété par récurrence sur la taille de l'arbre. 5 Utiliser une fonction récursive tour_eulerien qui prend en paramètre le noeud pour lequel elle calcule le tour Eulérien ainsi que la position dans le tableau euler à laquelle elle doit commencer à écrire et qui renvoie la prochaine position dans le tableau euler où il faudra écrire. 6 Traiter d'abord le cas où un noeud est ancêtre de l'autre et utiliser la propriété P de l'énoncé pour trouver le minimum. Si aucun noeud n'est ancêtre de l'autre, écrire le tour Eulérien du PPAC, trouver le minimum de ce tour et montrer que le segment délimité par index[i] et index[j] contient ce minimum. 7 Écrire une fonction auxiliaire récursive qui recherche la propriété inverse (premier entier k tel que 2k > n). 8 Remplir M colonne par colonne en utilisant à chaque fois la colonne précédente. 9 Montrer que [ i ; j ] = i ; i + 2log2 (j-i+1) - 1 j - 2log2 (j-i+1) + 1 ; j . Précalculer les éléments nécessaires et utiliser M pour répondre en temps constant. 10 Utiliser la propriété de la question 6 et la fonction de la question précédente. 11 Écrire la fonction récursivement, le cas terminal étant la valeur 1 pour x. 12 Couper les 30 bits du nombre en deux et regarder si le premier groupe est entièrement nul ou pas. Rechercher le bit de poids fort uniquement dans le bon groupe. Refaire la même chose une seconde fois. Conclure grâce au tableau pré-calculé. 13 Utiliser une fonction auxiliaire qui parcourt récursivement tout l'arbre en ayant également en paramètre le chemin parcouru jusqu'au noeud courant. La hauteur peut être pré-calculée ou elle peut être renvoyée par la fonction récursive. 14 B(i) et B(j) commencent par le chemin commun jusqu'à leur PPAC a, puis diffèrent juste à ce moment-là (par définition du PPAC). Pour obtenir B(a), extraire le chemin jusqu'à a de B(i), puis compléter la valeur comme indiquée dans l'énoncé pour tous les noeuds. 15 Traiter rapidement les cas triviaux, puis coder les résultats de la question précédente et utiliser Binv pour obtenir le résultat final. 16 Le pire cas est obtenu, par exemple, pour un tableau initial trié. 17 Écrire deux fonctions récursives cree_liste_vi et liste_vi_en_arbre. La fonction cree_liste_vi prend en paramètre une valeur v à insérer, une liste de noeuds vi classée comme dans l'énoncé et une liste de noeuds qui représente les fils de v après insertion. Elle renvoie la nouvelle liste de noeuds vi . La fonction liste_vi_en_arbre prend en paramètre une liste de noeuds vi classée comme dans l'énoncé et une liste d'arbres vide ou avec juste l'arbre final partiellement reconstruit. Elle renvoie l'arbre final. Appeler ensuite cree_liste_vi pour chacune des valeurs et liste_vi_en_arbre à la fin. 18 Compter les insertions et suppressions de valeurs dans la liste des noeuds vi . I. Une solution simple 1 Le calcul des tailles de tous les sous-arbres va être réalisé au cours d'un parcours récursifs de tous les noeuds. Pour cela, on va utiliser une fonction auxiliaire récursive. La fonction taille_liste_arbres prend en paramètre une liste d'arbres et calcule, récursivement par rapport à la liste, la taille totale cumulée de ces arbres. Elle stocke dans le tableau taille la taille de l'arbre sous le premier noeud. La taille d'un arbre est obtenue en s'appelant récursivement sur ses fils (ce qui stocke au passage les tailles des fils dans le tableau taille). Il suffit donc à la fonction principale d'appeler cette fonction en passant une liste, dont l'unique élément est l'arbre complet. let taille = make_vect n 0;; let remplir_taille () = let rec taille_liste_arbres liste_arbres = match liste_arbres with [] -> 0 | Noeud(i, fils)::suite -> taille.(i) <- 1 + (taille_liste_arbres fils); taille.(i) + (taille_liste_arbres suite) in let taille_totale = taille_liste_arbres [A] in () ;; Ce code parcourt l'arbre récursivement en passant une fois par chacun des noeuds. Le traitement de chaque noeud se fait en temps constant (somme et affectation dans le tableau). La complexité du code est donc proportionnelle à la taille de l'arbre. remplir_taille a une complexité en O(n). 2 Comme les noeuds d'un sous-arbre sont numérotés consécutivement à partir du numéro de sa racine, il est facile de connaître l'appartenance d'un noeud à un sousarbre. En effet, le sous-arbre i contient les noeuds j à j + taille[j] - 1 (propriété P de l'énoncé). let appartient i j = (j <= i) && (i <= j+taille.(j)-1) ;; appartient a une complexité en temps constante. 3 Pour trouver le PPAC de deux noeuds, on utilise sa définition. Tout d'abord, si l'un des deux noeuds est un ancêtre de l'autre, alors on peut conclure immédiatement (en temps constant) en appelant la fonction appartient de la question 2. Sinon, le PPAC sera un noeud possédant deux fils distincts dont les sous-arbres respectifs abritent les deux noeuds. Pour trouver le PPAC, on part de la racine. Si les noeuds sont dans deux branches distinctes, cela signifie que le PPAC est trouvé. Dans le cas contraire, la recherche est relancée dans le sous-arbre commun. Pour trouver la branche à laquelle appartient un noeud, on fait une recherche récursive dans les fils grâce à la fonction auxiliaire chercher_fils : int -> arbre list -> arbre. Cette fonction prend en premier paramètre le noeud que l'on recherche dans la liste des sous-arbres passée en second paramètre. Elle retourne le sous-arbre trouvé. let rec chercher_fils i fils = match fils with [] -> failwith "noeud cherché absent !" | (Noeud(v, _) as noeud)::suite -> if appartient i v then noeud else chercher_fils i suite ;; let ppac1 i j = if appartient j i then i else if appartient i j then j else let rec ppac1_rec arbre = match arbre with | Noeud(v, fils) -> let a1 = chercher_fils i fils and a2 = chercher_fils j fils in if a1 == a2 then ppac1_rec a1 else v in ppac1_rec A ;; Lorsqu'on regarde si les deux noeuds trouvés sont les mêmes ou pas, on utilise l'opérateur == et pas l'opérateur =. En effet, on veut savoir si les deux noeuds sont physiquement les mêmes (ce qui se fait en temps constant). On ne veut pas comparer récursivement la structure des deux sous-arbres de ces deux noeuds (ça serait correct pour le résultat, puisque deux sous-arbres distincts ne peuvent pas avoir la même numérotation, mais ça ne serait pas en temps constant). La fonction ppac1_rec effectue au pire un parcours de l'une des branches de l'arbre. Son coût (en excluant celui des appels à chercher_fils pour l'instant) est donc majoré par la hauteur de l'arbre. La recherche dans un fils (fonction appartient) étant en temps constant, la fonction chercher_fils a un coût proportionnel au nombre de fils du noeud de recherche. Par conséquent, le coût global de toutes ces recherches est proportionnel à deux fois la somme du nombre de fils des noeuds explorés (chercher_fils est appelé deux fois pour chaque noeud exploré dans ppac1_rec). Il est majoré par deux fois le nombre de noeuds total. La fonction ppac1 a une complexité dans le pire des cas en O(n).