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 :

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

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 :

def enfants(n,P):
    return [k for k in range(len(P)) if P[k]==n]

def arbre(P):
    return [enfants(n,P) for n in range(len(P))]

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.

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

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

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 :

def descendants(a,G):
    if est_une_feuille(a,G):
        return [a]
    else:
        return [a]+[j for k in G[a] for j in descendants(k,G)]

def est_ancetre(a,b,G):
    return b in descendants(a,G)

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.

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

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

Voici le fichier Newick :

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 :

                                       _________________ f2
                    __________________|
                   |                  |_________________ f3
___________________|
                   |                   _________________ f5
                   |                  |
                   |__________________|_________________ f6
                                      |
                                      |                  __________________ f8
                                      |_________________|
                                                        |__________________ f9

Et

tree.rooted=True
Phylo.draw(tree)

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

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 :

{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}

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.

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.

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.

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 :

À 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 u_n le nombre de nœuds disposant de l’information au temps n, on sait que

• u₀=1 (seule la racine est au courant au temps t=0
• u_n+1≤2×u_n

On en déduit (par récurrence) que le nombre de nœuds informés au temps n est majoré par 2ⁿ et donc que le temps nécessaire pour diffuser l’information à tout l’arbre est minoré par log₂(T) où T désigne la taille de l’arbre (nombre de nœuds) et log₂ 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 log₂(T).

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 A₁.A₂ où A₁ et A₂ sont eux-mêmes des arbres binaires.

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

class Arbre():
    def __init__(self,G=None,D=None):
        self.G = G
        self.D = D

La décomposition complète du nombre 2^a+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 2^a+b. C’est un excellent exemple de fonction récursive :

def log2(n):
    assert n==int(n) and n>0
    if n==1:
        return 0
    else:
        return 1+log2(n//2)

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

def her2(n):
    if n==0:
        return Arbre()
    else:
        a = log2(n)
        b = n-2**a
        return Arbre(her2(a),her2(b))

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.

from graphviz import Graph
AB = Graph()

def tree2dot(T):
    global AB
    if not T.G and not T.D:
        AB.node(str(hash(T)),'',shape='circle',fixedsize='true',width='0.2',style='filled',fillcolor='green')
    else:
        AB.node(str(hash(T)),'',shape='circle',fixedsize='true',width='0.1',style='filled',fillcolor='brown')
    if T.G:
        tree2dot(T.G)
        AB.edge(str(hash(T)),str(hash(T.G)),color='brown')
    if T.D:
        tree2dot(T.D)
        AB.edge(str(hash(T)),str(hash(T.D)),color='brown')

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.

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

def admis:
    if e:
        return True
    else:
        if a:
            if r:
                return True
            else:
                return False
        else:
            return False

On peut d’ailleurs simplifier ce code :

def admis:
    if e:
        return True
    else:
        if a:
            return r
        else:
            return False

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

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 :

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.

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

print(ITE(t,e1,e2))

on obtient

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 :

Avec Sympy, en entrant

print(ITE(x,False,True))
print(ITE(x,True,y))
print(ITE(x,y,False))

on obtient

Not(x)
Or(And(Not(x), y), x)
And(x, y)

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

ou = ITE(x,True,y)
print(simplify_logic(ou))

on obtient

Or(x,y)

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

En posant la question à Sympy :

a,b,c,d,e = symbols('a,b,c,d,e')
print(simplify_logic(ITE(ITE(a,b,c),d,e)))
print(simplify_logic(ITE(a,ITE(b,d,e),ITE(c,d,e))))

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

Or(And(Not(a), Not(c), e), And(Not(a), c, d), And(Not(b), a, e), And(a, b, d))
Or(And(Not(a), Not(c), e), And(Not(a), c, d), And(Not(b), a, e), And(a, b, d))

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.

La seconde partie du devoir, hors sujet dans cet article sur les arbres, portait sur les tables de routage. Elle avait été préparée par une activité basée sur celle-ci.

Construire les tables de routage à partir du graphe qui en en bas de la page 6 de ce document a été donné en devoir maison. Mais auparavant, les tables de routages des pages 3 et 4 du même document ont été données, et les élèves ont dû reconstituer le réseau à partir de ces données disponibles.

Bien que disposant de 📜, de ✏️ et d’une gomme, un élève a préféré utiliser l’🖥️ avec le logiciel GIMP :

Cela lui a donné un « brouillon de graphes » :

ensuite reproduit sur papier :

Un autre a préféré (merci à lui) dessiner les étapes de sa recherche sur la feuille :

Certains rendus sont justes mais complexes :

Un élève a choisi arts plastiques en plus de NSI :

Un graphe plus typique :

une variante :

Et voici les rendus de deux élèves rapides, avec optimisation de la forme du graphe :