62
3 Arbres, algorithmes et données
Fig. 3.1 Arbres d’expressions pour deux expressions booléennes : la première expression (x →
y) → (x → ((z → y) → t)) est une expression de la logique construite sur le connecteur ‘→’
(IMPLICATION) ; la seconde, (x ∨ y) ∧ (z ∨ (x ∨ t)), est dans la logique construite sur les deux
connecteurs ∧ (ET) et ∨ (OU)
informatiques, qui sont des arbres non planaires et d’arité non bornée (en oubliant
les liens symboliques vers des fichiers d’autres répertoires, qui transforment ces
arbres en graphes orientés). Ils apparaissent aussi dès que nous utilisons des expressions formelles (arithmétiques, booléennes. . . ) : celles-ci peuvent être représentées
par des arbres marqués, 1 comme suit :
– les opérateurs sont les marques des nœuds internes ;
– si un opérateur est d’arité p, le nœud interne associé possède p sous-arbres ;
– les symboles terminaux sont les marques des feuilles.
Le type d’arbre diffère suivant la manière dont nous choisissons de définir
l’expression. La figure 3.1 représente deux expressions booléennes, le premier arbre
est un arbre binaire planaire (l’opérateur d’implication n’est pas commutatif), tandis
que le second peut être vu, au choix, comme un arbre non planaire (les opérateurs
logiques ∨ et ∧ sont a priori commutatifs) ou planaire (dans le cas où nous décidons
de considérer ∨ et ∧ comme des opérateurs non commutatifs). Nous reviendrons
sur les expressions booléennes dans la section 3.4.1, et montrerons comment le
dénombrement de diverses familles d’arbres permet par exemple d’obtenir une loi
de probabilité sur l’ensemble des fonctions booléennes définies sur un nombre fixé
de variables.
En ce qui concerne les deux arbres de la figure 3.2, le premier est binaire
et représente une expression sur les opérateurs binaires +, ∗ et −, le second
est unaire-binaire et représente une expression sur ces mêmes opérateurs et sur
l’opérateur EXP, d’arité 1. De plus, les opérateurs + et ∗ peuvent être vus
comme non commutatifs, et dans ce cas les deux arbres sont planaires, ou comme
commutatifs et le second arbre devient alors non planaire ; quant au premier, il
est alors d’un type particulier, ni planaire ni non planaire, 2 puisque l’opérateur de
soustraction n’est pas commutatif !
1 De fait, nous identifions la plupart du temps une expression et l’arbre marqué la représentant.
2 De tels arbres, dont nous ne parlons pas dans ce livre, peuvent cependant faire l’objet d’analyses ;
cf. par exemple un article de Genitrini et al. [119].
3 Arbres, algorithmes et données
Fig. 3.1 Arbres d’expressions pour deux expressions booléennes : la première expression (x →
y) → (x → ((z → y) → t)) est une expression de la logique construite sur le connecteur ‘→’
(IMPLICATION) ; la seconde, (x ∨ y) ∧ (z ∨ (x ∨ t)), est dans la logique construite sur les deux
connecteurs ∧ (ET) et ∨ (OU)
informatiques, qui sont des arbres non planaires et d’arité non bornée (en oubliant
les liens symboliques vers des fichiers d’autres répertoires, qui transforment ces
arbres en graphes orientés). Ils apparaissent aussi dès que nous utilisons des expressions formelles (arithmétiques, booléennes. . . ) : celles-ci peuvent être représentées
par des arbres marqués, 1 comme suit :
– les opérateurs sont les marques des nœuds internes ;
– si un opérateur est d’arité p, le nœud interne associé possède p sous-arbres ;
– les symboles terminaux sont les marques des feuilles.
Le type d’arbre diffère suivant la manière dont nous choisissons de définir
l’expression. La figure 3.1 représente deux expressions booléennes, le premier arbre
est un arbre binaire planaire (l’opérateur d’implication n’est pas commutatif), tandis
que le second peut être vu, au choix, comme un arbre non planaire (les opérateurs
logiques ∨ et ∧ sont a priori commutatifs) ou planaire (dans le cas où nous décidons
de considérer ∨ et ∧ comme des opérateurs non commutatifs). Nous reviendrons
sur les expressions booléennes dans la section 3.4.1, et montrerons comment le
dénombrement de diverses familles d’arbres permet par exemple d’obtenir une loi
de probabilité sur l’ensemble des fonctions booléennes définies sur un nombre fixé
de variables.
En ce qui concerne les deux arbres de la figure 3.2, le premier est binaire
et représente une expression sur les opérateurs binaires +, ∗ et −, le second
est unaire-binaire et représente une expression sur ces mêmes opérateurs et sur
l’opérateur EXP, d’arité 1. De plus, les opérateurs + et ∗ peuvent être vus
comme non commutatifs, et dans ce cas les deux arbres sont planaires, ou comme
commutatifs et le second arbre devient alors non planaire ; quant au premier, il
est alors d’un type particulier, ni planaire ni non planaire, 2 puisque l’opérateur de
soustraction n’est pas commutatif !
1 De fait, nous identifions la plupart du temps une expression et l’arbre marqué la représentant.
2 De tels arbres, dont nous ne parlons pas dans ce livre, peuvent cependant faire l’objet d’analyses ;
cf. par exemple un article de Genitrini et al. [119].