Sujets sur les arbres

vendredi 30 octobre 2020
par  Alain BUSSER , Franck JEAN-ALBERT , Sébastien HOARAU

Sujets

On propose ici

  • un sujet sur les PPAC, inspiré de celui de l’X 2010
  • un sujet sur le transport d’informations dans un arbre, inspiré de celui de l’X 2011
  • un sujet sur la représentation des entiers sous forme d’arbres, inspiré de celui de l’ENS 2002
  • un sujet sur les arbres de décision, inspiré de celui de Centrale 2013

Parents

Un arbre est un graphe, une façon naturelle de le modéliser est celle des listes d’adjacence :

  • Un dictionnaire qui, à chaque nœud de l’arbre, associe la liste de ses enfants,
  • ou une liste de listes (d’adjacence) si les clés du dictionnaire sont des entiers successifs.

Par exemple l’arbre du sujet X 2010 :

peut être modélisé en Python par un dictionnaire (voir l’onglet suivant) ou cette liste de listes :

  1. [ [1,4],
  2.   [2,3],
  3.   [],
  4.   [],
  5.   [5,6,7],
  6.   [],
  7.   [],
  8.   [8,9],
  9.   [],
  10.   []]

Télécharger

Le sujet Centrale 2000 introduit une nouvelle façon de représenter les arbres :

Ce sujet évoque une fonction père qui, à tout nœud (sauf la racine), associe son unique parent (ou « père »). Il s’agit d’une fonction partielle puisque la racine n’a pas de père. Mais comme l’ensemble des nœuds de l’arbre est fini, cette fonction père est entièrement déterminée par son tableau de valeurs. Par exemple pour l’arbre du sujet X 2010, le tableau des pères est :

nœud 0 1 2 3 4 5 6 7 8 9
père aucun 0 1 1 0 4 4 4 7 7

En Python on le code par

parent = [None,0,1,1,0,4,4,4,7,7]

Cette représentation est plus concise que la représentation traditionnelle par liste d’enfants, parce que, si chaque nœud (sauf les feuilles) peut avoir plusieurs enfants, il n’a qu’un seul parent. Par contre certains algorithmes sont plus faciles à mettre en œuvre sur la représentation traditionnelle.

L’arbre de Papa

Pour construire la liste de listes d’adjacences (l’arbre) à partir d’une liste P de parents, il suffit, pour chaque nœud k, de chercher de qui il est l’enfant :

  1. def p2g(P):
  2.     return [[j for j in range(len(P)) if P[j]==k] for k in range(len(P))]

Télécharger

Papa grimpe dans l’arbre

Pour créer la version raccourcie à partir des listes d’adjacence, on cherche, pour chaque nœud n, dans quelle liste d’adjacence il se trouve :

  1. def enfants(n,P):
  2.     return [k for k in range(len(P)) if P[k]==n]
  3.  
  4. def arbre(P):
  5.     return [enfants(n,P) for n in range(len(P))]

Télécharger

Ici P est la liste des parents des nœuds, et la fonction enfants associe à chaque nœud de P, la liste de ses enfants. La liste de telles listes est l’arbre représenté par listes d’adjacence.

Avec cette représentation par liste de parents, il est aisé de la racine de l’arbre.

back to the roots

La racine est le seul nœud n’ayant pas de parent [1] :

  1. def est_racine(a,P):
  2.     return P[a] is None

Télécharger

Ah, mes aïeux !

Par contre, il est plus simple d’utiliser la représentation traditionnelle par liste d’enfants, pour calculer les ancêtres d’un nœud [2]. En effet, a est un ancêtre de b si, et seulement si, b est un descendant de a :

  1. def descendants(a,G):
  2.     if est_une_feuille(a,G):
  3.         return [a]
  4.     else:
  5.         return [a]+[j for k in G[a] for j in descendants(k,G)]
  6.  
  7. def est_ancetre(a,b,G):
  8.     return b in descendants(a,G)

Télécharger

La notion d’ancêtres mène assez naturellement à celle d’ancêtres communs, à laquelle l’onglet suivant est consacré.

PPAC

Les ancêtres communs (AC) de deux nœuds a et b d’un arbre G forment une liste :

  1. def AC(a,b,G):
  2.     return [s for s in G if est_ancetre(s,a,G) and est_ancetre(s,b,G)]

Télécharger

Parmi tous ces ancêtres communs, le plus petit est par définition celui qui est le plus éloigné de la racine. La notion de plus petit ancêtre commun est assez régulièrement abordée en CPGE, comme un outil servant à résoudre d’autres problèmes, ou en liaison avec la bio-informatique (notion d’arbre phylogénétique). Mais au concours Polytechnique de 2010, c’était le thème majeur du sujet :

Voici le sujet qui a été donné en devoir maison aux élèves de terminale NSI du lycée Roland-Garros :

Et voici le devoir rendu par un des élèves au format html (choix spontané) :


BioPython

BioPython et NSI

Plusieurs fonctionnalités de BioPython sont en phase avec le programme de NSI. Tout d’abord, c’est un excellent exemple du paradigme de programmation objet. Ensuite, certains objets mettent en œuvre des algorithmes ou des exemples qui sont au programme :

  • L’objet Sequence se comporte en bien des points comme une chaîne de caractères. En particulier on peut y chercher des motifs [3] [4].
  • L’objet MultipleSeqAlignment comporte plusieurs chaînes de caractères (des séquences d’ADN ou de protéines) et peut calculer la distance de Lehvenstein (qui est au programme) entre elles, afin de les aligner.
  • L’objet PairwiseAligner donne à un alignement entre deux séquences, un « score » qui permet de fabriquer un arbre phylogénétique commun aux deux génomes analysés.
  • L’objet Phylo permet d’étudier et représenter les arbres phylogénétiques.

Le format Newick

L’arbre ci-dessus peut être décrit par une expression parenthésée de ce genre :

((f2,f3),(f5,f6,(f8,f9)));

On constate que seules les feuilles sont nommées, on verra plus bas pourquoi.

En sauvegardant le résultat sous le nom ppac.dnd on peut créer l’arbre dans BioPython en faisant

  1. from Bio import Phylo
  2. tree = Phylo.read("ppac.dnd","newick")

Télécharger

Voici le fichier Newick :

Affichage

Dans BioPython, un arbre est un objet (puisque tout est objet en BioPython), et il possède des méthodes d’affichage. Tout d’abord, en faisant

print(tree)

on obtient

Tree(rooted=False, weight=1.0)
   Clade(branch_length=1.0)
       Clade(branch_length=1.0)
           Clade(branch_length=1.0, name='f2')
           Clade(branch_length=1.0, name='f3')
       Clade(branch_length=1.0)
           Clade(branch_length=1.0, name='f5')
           Clade(branch_length=1.0, name='f6')
           Clade(branch_length=1.0)
               Clade(branch_length=1.0, name='f8')
               Clade(branch_length=1.0, name='f9')

On y apprend que les arbres phyologénétiques sont des nœuds, ici appelés clades. Mais on peut également obtenir le dessin de l’arbre dans la console, avec

Phylo.draw_ascii(tree)

qui donne :

  1.                                        _________________ f2
  2.                     __________________|
  3.                    |                  |_________________ f3
  4. ___________________|
  5.                    |                   _________________ f5
  6.                    |                  |
  7.                    |__________________|_________________ f6
  8.                                       |
  9.                                       |                  __________________ f8
  10.                                       |_________________|
  11.                                                         |__________________ f9

Télécharger

Et

  1. tree.rooted=True
  2. Phylo.draw(tree)

Télécharger

permet d’avoir un dessin (à l’aide de matplotlib.pyplot) de l’arbre :

Accesseurs

L’arbre de Phylo possède, entre autres, ces méthodes permettant d’obtenir des renseignements sur lui :

  • find_clades permet de parcourir l’arbre (en profondeur par défaut mais cela peut être modifié)
  • rooted permet de savoir si l’arbre est enraciné
  • root permet de connaître la racine de l’arbre
  • name pemet de connaître le nom (étiquette) éventuel d’un clade
  • is_terminal permet de savoir si un nœud (ou clade) est une feuille
  • is_preterminal permet de savoir si un des enfants du nœud est une feuille
  • get_terminals donne la liste des feuilles de l’arbre
  • get_nonterminals donne la liste des nœuds internes de l’arbre
  • is_parent_of donne la fameuse relation de paternité dans l’arbre
  • common_ancestor est ce qui nous intéresse ici : le fameux plus proche ancêtre commun
  • count_terminals donne le nombre de feuilles de l’arbre
  • get_path donne lechemin entre deux nœuds de l’arbre
  • distance donne la distance entre deux nœuds de l’arbre
  • total_branch_length donne la longueur totale de l’arbre
  • depths renvoie les profondeurs des nœuds, sous forme d’un dictionnaire Pytthon :
  1. {Clade(branch_length=1.0, name='f5'): 3.0, Clade(branch_length=1.0, name='f3'): 3.0, Clade(branch_length=1.0): 2.0, Clade(branch_length=1.0, name='f8'): 4.0, Clade(branch_length=1.0, name='f6'): 3.0, Clade(branch_length=1.0): 3.0, Clade(branch_length=1.0): 1.0, Clade(branch_length=1.0, name='f9'): 4.0, Clade(branch_length=1.0): 2.0, Clade(branch_length=1.0, name='f2'): 3.0}

Pour chercher le plus proche ancêtre commun aux taxons numéros 5 et 8, on peut tenter un

  1. ppac = tree.common_ancestor({"name":'f5'}, {"name":'f8'})
  2. print(ppac)

Télécharger

Mais dans ce cas on obtient

  1. Clade

ce qui n’est pas très explicite : cela revient à dire que le plus proche ancêtre commun est un nœud de l’arbre (ne possédant pas de nom), ce dont se doutait un peu. Pour le dessiner, on propose de le colorier en rouge dans l’arbre tree et de dessiner la nouvelle version de cet arbre :

  1. ppac.color='red'
  2. Phylo.draw(tree)

Télécharger

ce qui donne l’affichage suivant :

Comme on le voit, BioPython ne fait pas la distinction entre un arbre et un nœud de l’arbre.

Clades anonymes

Pourquoi les nœuds internes de BioPython n’ont-ils pas de nom ?

La réponse est assez simple à deviner : ils sont trop nombreux pour les nommer. Voici un exemple tiré du monde réel :

Question d’un élève : alors l’Homme descend du Bonobo ? Réponse : non, en fait il y a un ancêtre commun à l’Homme et au Bonobo, ou plus précisément, un ancêtre commu à l’Homme et à l’ancêtre commun au Bonobo et au Chimpanzé.

C’est l’existence de ces ancêtres communs qui est importante, pas leur nom.

Diffusion

Le sujet X 2011 portait sur la diffusion d’un message dans un arbre, à partir de la racine :

Arbres binomiaux

La diffusion est optimale lorsque l’arbre est dit binomial, c’est-à-dire lorsqu’il a une des formes suivantes :

Cette structure est définie récursivement, ce qui lui donne son intérêt pour l’exercice. On remarque que la taille d’un arbre binomial est une puissance de 2.

Origine de l’exercice

En fait il s’agit de l’exercice 49 du chapitre 3 du livre de Jeff Erickson. Voici le chapitre 3 :

L’exercice 49, comme le suggère le titre du chapitre, se résout par la programmation dynamique. On y demande non pas comment diffuser le message, mais seulement le temps minimum que ça prendra.

La programmation dynamique est au programme de terminale.

On a un arbre (pas nécessairement binaire) sur lequel on doit diffuser une information à tous les nœuds. Au début seule la racine dispose de l’information :

Mais à un instant donné, un nœud ne peut diffuser l’information qu’à un seul de ses enfants. Au bout du temps t=1, seuls deux nœuds disposent alors de l’information, la racine et un de ses enfants :

La situation s’améliore ensuite puisque chacun des deux nœuds peut diffuser l’information à un (autre) de ses enfants :

Au temps t=3, la racine diffuse l’information au seul de ses enfants qui n’était pas encore au courant, et lui passe en quelque sorte le relais :

Au temps t=4, seule la partie droite de l’arbre est encore à traiter :

Cela permet au temps t=5 de diffuser l’information à deux nœuds en même temps (venant de leurs pères respectifs) :

Et au temps t=6, tous les nœuds de l’arbre disposent de l’information :

On peut faire mieux

Sur le même arbre, il y a un moyen de diffuser plus rapidement l’information, en commençant par l’enfant ayant le plus de descendants :

Au temps t=0 la situation est la même, avec un seul nœud (la racine) disposant de l’information :

Au temps t=1, là encore, seuls deux nœuds disposent de l’information :

Au temps t=2, là encore, 4 nœuds disposent de l’information :

Mais au temps t=3 il y a 8 nœuds qui disposent de l’information :

Ce qui permet de finir au temps t=4 :

Peut-on faire mieux ?

À chaque étape, les nœuds qui disposent déjà de l’information, ne peuvent la donner qu’à un de leurs enfants maximum. Alors si on note un le nombre de nœuds disposant de l’information au temps n, on sait que

  • u0=1 (seule la racine est au courant au temps t=0
  • un+1≤2×un

On en déduit (par récurrence) que le nombre de nœuds informés au temps n est majoré par 2n et donc que le temps nécessaire pour diffuser l’information à tout l’arbre est minoré par log2(T) où T désigne la taille de l’arbre (nombre de nœuds) et log2 la fonction qui, à un entier, associe le nombre de chiffres binaires de son écriture.

Ce minimum est atteint sur un arbre binomial, comme le montre cet exemple :

Temps arbre
0
1
2
3
4

Noter que pour un arbre binaire complet, le temps nécessaire est le double de la hauteur de l’arbre, soit le double du minimum log2(T).

Entiers

Le sujet ENS 2002 portait sur le théorème de Goodstein :

Ce qui est intéressant avec ce sujet, c’est qu’il propose entre autres une manière de représenter les entiers naturels par des arbres binaires. Et même plusieurs puisque l’arbre obtenu dépend de la base. Ici on va le faire en base 2 seulement. Voici les représentations obtenues :

Nombre Arbre binaire
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

Arbre binaire

La définition d’un arbre binaire donnée par le sujet est courte, parce qu’elle est récursive et qu’elle ne fait pas la distinction entre un arbre et un nœud :

Un arbre binaire est soit O, soit A1.A2 où A1 et A2 sont eux-mêmes des arbres binaires.

En Python cette définition peut se traduire par la classe suivante :

  1. class Arbre():
  2.     def __init__(self,G=None,D=None):
  3.         self.G = G
  4.         self.D = D

Télécharger

logarithme

La décomposition complète du nombre 2a+b en base 2 est un couple formé par les décompositions complètes de a et de b. On a donc besoin de calculer a qui n’est autre que le logarithme en base 2 du nombre 2a+b. C’est un excellent exemple de fonction récursive :

  1. def log2(n):
  2.     assert n==int(n) and n>0
  3.     if n==1:
  4.         return 0
  5.     else:
  6.         return 1+log2(n//2)

Télécharger

Décomposition complète

On peut alors directement créer l’arbre représentant la décomposition complète d’un entier n en base 2 :

  1. def her2(n):
  2.     if n==0:
  3.         return Arbre()
  4.     else:
  5.         a = log2(n)
  6.         b = n-2**a
  7.         return Arbre(her2(a),her2(b))

Télécharger

Dessin

Les dessins ci-dessus ont été faits avec le module graphviz, à l’aide d’une variable globale appelée AB (comme « arbre binaire »). Le graphe étant créé au format dot, la fonction de conversion s’appelle donc tree2dot (de l’arbre vers le dot).

Le problème est qu’il faut, pour tracer une arête entre deux sommets de l’arbre, connaître les noms de ces sommets. Il faut donc leur attribuer un identifiant unique. La fonction hash de Python le permet, mais elle envoie un entier, alors on applique à cet entier la fonction str qui le convertit en une chaîne de caractères.

  1. from graphviz import Graph
  2. AB = Graph()
  3.  
  4. def tree2dot(T):
  5.     global AB
  6.     if not T.G and not T.D:
  7.         AB.node(str(hash(T)),'',shape='circle',fixedsize='true',width='0.2',style='filled',fillcolor='green')
  8.     else:
  9.         AB.node(str(hash(T)),'',shape='circle',fixedsize='true',width='0.1',style='filled',fillcolor='brown')
  10.     if T.G:
  11.         tree2dot(T.G)
  12.         AB.edge(str(hash(T)),str(hash(T.G)),color='brown')
  13.     if T.D:
  14.         tree2dot(T.D)
  15.         AB.edge(str(hash(T)),str(hash(T.D)),color='brown')

Télécharger

Pour faire plus joli, on a donné un style différent selon que le nœud est une feuille, ou pas :

  • si T est une feuille (n’a pas ni de T.G ni de T.D) alors on le met en grand et en vert,
  • sinon on le met plus petit et en marron.

Ce sujet est en relation avec le jeu Hydra décrit ici :

Décision

Le sujet Centrale 2013 portait sur la notion d’arbre de décision. Un tel arbre est un arbres binaire. Le fils gauche représente la valeur vrai et le fils droit représente la valeur faux :

L’exemple introductif est intéressant :

  • on note e la proposition « le candidat a réussi l’examen »
  • on note a la proposition « le candidat a été assidu »
  • on note r la proposition « le candidat a réussi au rattrapage ».

Avec ça, le 1 désigne l’admission à l’examen, et s’obtient ainsi :

La partie basse de l’arbre signifie que seuls les étudiants assidus ont droit au rattrapage, ce qui en dit long sur la situation actuelle des études supérieures...

De l’arbre au script

Le même arbre peut s’obtenir avec les blocs de Blockly [5] ressemblant à des arbres binaires orientés de gauche à droite : « si ... alors ... sinon ... » :

En Python cela donne quelque chose comme

  1. def admis:
  2.     if e:
  3.         return True
  4.     else:
  5.         if a:
  6.             if r:
  7.                 return True
  8.             else:
  9.                 return False
  10.         else:
  11.             return False

Télécharger

On peut d’ailleurs simplifier ce code :

  1. def admis:
  2.     if e:
  3.         return True
  4.     else:
  5.         if a:
  6.             return r
  7.         else:
  8.             return False

Télécharger

La simplification d’expressions de ce genre est d’ailleurs centrale (!) dans ce sujet.

De l’arbre au graphe

L’exemple donné dans l’énoncé comprend de la redondance :

Par exemple, la proposition c intervient 4 fois, et chaque fois de la même manière. On décide alors de ne la faire intervenir qu’une seule fois, quitte à renoncer au caractère arborescent du graphe :

On remarque que même avec ce graphe simplifié, il subsiste encore de la redondance, cette fois avec la proposition b qui intervient deux fois, et chaque fois de la même manière. Cela permet encore une simplification :

L’énoncé s’arrête là mais il est possible de simplifier encore :

Simplification

Le sujet décrit deux modifications de graphe qui peuvent aboutir à une simplification du graphe de décision :

Élimination

L’élimination consiste à remplacer

par

Isomorphisme

L’isomorphisme consiste à remplacer

par

Montrer que l’algorithme converge, ou le programmer en Python, risque d’être plus de niveau post-bac que de niveau terminale. On va donc se concentrer ci-après sur les arbres de décision et leur construction.

On verra dans l’onglet suivant que les arbres syntaxiques sont intéressants parce que les opérations sont, en général, binaires (à deux opérandes). C’est le cas de and et or notamment. Ces opérations booléennes étant à deux opérandes, on s’attend assez logiquement à voir des arbres binaires en logique. Mais la surprise est que le seul opérateur booléen ternaire (à trois opérandes), est à l’origine de ces arbres binaires ! En fait si chaque nœud a deux enfants, il a également un parent [6].

L’opérateur ternaire

En fait, en logique booléenne, on n’utilise guère qu’un opérateur ternaire, et on l’appelle l’opérateur ternaire ou, en anglais, if then else, ci-dessous abrégé en IFT.

Définition de IFT

L’énoncé définit IFT(t,e1,e2) comme étant l’expression

(t and e1) or (not t and e2)

C’est la définition connue par Sympy. En entrant

  1. print(ITE(t,e1,e2))

on obtient

  1. Or(And(Not(t), e2), And(e1, t))

que Sympy dessine ainsi :

Remarque : L’expression suivante aussi donne l’opérateur ternaire, d’une manière qui permet peut-être de mieux voir l’arbre de décision :

« If t then e1 else e2 » peut se dessiner par cet arbre (qui est un arbre de décision) :

ou par l’expression Python

e1 if t else e2

La puissance de cet opérateur ternaire vient de ce qu’il est possible de s’en servir pour définir les autres opérateurs booléens.

Comment ?

Avec Sympy, en entrant

  1. print(ITE(x,False,True))
  2. print(ITE(x,True,y))
  3. print(ITE(x,y,False))

Télécharger

on obtient

  1. Not(x)
  2. Or(And(Not(x), y), x)
  3. And(x, y)

Télécharger

On sait donc comment implémenter la négation et la conjonction avec l’opérateur ternaire. Mais pour la disjonction il reste un travail à faire. On obtient à la place, cette expression :

Ceci dit, en entrant

  1. ou = ITE(x,True,y)
  2. print(simplify_logic(ou))

Télécharger

on obtient

Or(x,y)

ce qui montre que la solution proposée est bien la bonne.

Voici comment on peut représenter sous forme d’arbres de décision, les opérations booléennes élémentaires :

non x x ou y x et y

Il est donc possible de convertir n’importe quelle expression booléenne en arbre de décision (donc, avec les simplifications vues ci-dessus, en arbre de décision).

récursivité

En posant la question à Sympy :

  1. a,b,c,d,e = symbols('a,b,c,d,e')
  2. print(simplify_logic(ITE(ITE(a,b,c),d,e)))
  3. print(simplify_logic(ITE(a,ITE(b,d,e),ITE(c,d,e))))

Télécharger

on obtient deux fois la même réponse :

  1. Or(And(Not(a), Not(c), e), And(Not(a), c, d), And(Not(b), a, e), And(a, b, d))
  2. Or(And(Not(a), Not(c), e), And(Not(a), c, d), And(Not(b), a, e), And(a, b, d))

Télécharger

ce qui prouve que les deux graphes suivants sont équivalents :

Le passage de l’un à l’autre permet de construire récursivement l’arbre de décision, en partant d’une expression booléenne donnée.

Syntaxe

Si on invoque Sympy avec

  1. from sympy import *
  2. from sympy.printing.dot import *
  3. from sympy.abc import *

Télécharger

alors on peut représenter sous forme d’arbres (syntaxiques) les expressions (a+b)² et a²+2ab+b² :

dotprint((a+b)**2)

donne cet arbre

et

dotprint(expand((a+b)**2))

donne celui-là :

On voit que le premier arbre est celui d’un produit, et le second, celui d’une somme.

Pour aller plus loin, voir

Cet arbre a été dessiné par Alain Colmerauer lors de la conception du langage Prolog, basé sur la représentation de phrases en français, par des arbres :

Les arbres pondérés sont évoqués à la fin de cet article


[1ou plus précisément, dont le père est None. On constate que Python utilise le mot None pour désigner le père d’Adam, la Bible se sert d’un tout autre mot...

[2parce qu’on ne connaît pas d’avance combien de fois on doit composer la fonction père avec elle-même pour aboutir à la racine de l’arbre.

[3BioPython étant un logiciel libre, il peut être intéressant de consulter son code source pour voir si c’est l’algorithme de Boyer-Moore-Horspool qui est utilisé.

[4La recherche d’un motif d’ADN dans l’ADN d’un virus est une activité favorite des complotistes. C’est par exemple une de ces recherches qui alimente les discours de Luc Montagnier sur l’ADN du coronavirus SARS-CoV-2.

[5ici fait avec Sofus.

[6Page 5 de ce document, on voit ce qui peut se passer lorsqu’on applique une rotation de 120° à un arbre de décision, c’est impressionnant.


Documents joints

PDF - 229.6 ko
PDF - 160.4 ko

Commentaires

Navigation