96
3 Arbres, algorithmes et données
Fig. 3.23 L’arbre ET-OU
représentant l’expression
booléenne x ∨ (y ∧ (z ∨ t))
Une loi de probabilité sur l’ensemble des fonctions booléennes sur un nombre
fixé k de variables, i.e., sur l’ensemble des fonctions de {0, 1} k dans {0, 1}, peut
être définie comme suit. Choisissons pour taille d’une expression (ou de l’arbre la
représentant) le nombre de ses littéraux (ou de ses feuilles). 19 Dans un premier
temps est définie une distribution de probabilité uniforme sur l’ensemble des
expressions de même taille : les formes d’arbres sont tirées uniformément, puis
chaque nœud est étiqueté indépendamment des autres, les nœuds internes par ∧
ou ∨ avec une probabilité uniforme et les feuilles par les littéraux, là encore tirés
uniformément parmi les 2k littéraux possibles.
Passons maintenant des expressions aux fonctions booléennes. Chaque expression booléenne correspond à une unique fonction booléenne, mais chaque fonction
booléenne peut être représentée par une multitude d’expressions. Ainsi, les arbres
des figures 3.22 et 3.23 sont associés à deux expressions booléennes différentes,
mais ils correspondent à la même fonction booléenne x ∨ (y ∧ (z ∨ t)).
La distribution de probabilité définie plus haut sur les arbres ET-OU de même
taille n définit une distribution de probabilité induite P n sur l’ensemble des 2 2 k
fonctions booléennes. En notant par A n l’ensemble de toutes les expressions de
taille n et par A n (f ) le sous-ensemble de ces expressions qui calcule une fonction
booléenne f , la probabilité qu’une expression de taille n calcule f est
P n (f ) =
|A n (f )|
|A n |
.
Ce calcul conduit ainsi au dénombrement de A n , ensemble de tous les arbres ET-OU
de taille n sur k variables booléennes, ce qui ne pose aucune difficulté, et à celui de
A n (f ), sous-ensemble de ces arbres qui calculent la fonction f . Le point délicat
est souvent de trouver une spécification formelle de l’ensemble A(f ) des arbres
qui calculent f ; une fois cette spécification obtenue, les méthodes symboliques
de l’annexe B.2 fournissent en général facilement la fonction génératrice de
dénombrement de A(f ), dont le coefficient d’ordre n, |A n (f )| s’obtient alors soit
directement, soit par les techniques asymptotiques présentées en annexe B.3 lorsque
la taille n de l’expression booléenne tend vers l’infini.
19 Les formes des arbres ET-OU étant des arbres binaires complets, le nombre de leurs feuilles et le
nombre de leurs nœuds internes diffèrent toujours de 1.
3 Arbres, algorithmes et données
Fig. 3.23 L’arbre ET-OU
représentant l’expression
booléenne x ∨ (y ∧ (z ∨ t))
Une loi de probabilité sur l’ensemble des fonctions booléennes sur un nombre
fixé k de variables, i.e., sur l’ensemble des fonctions de {0, 1} k dans {0, 1}, peut
être définie comme suit. Choisissons pour taille d’une expression (ou de l’arbre la
représentant) le nombre de ses littéraux (ou de ses feuilles). 19 Dans un premier
temps est définie une distribution de probabilité uniforme sur l’ensemble des
expressions de même taille : les formes d’arbres sont tirées uniformément, puis
chaque nœud est étiqueté indépendamment des autres, les nœuds internes par ∧
ou ∨ avec une probabilité uniforme et les feuilles par les littéraux, là encore tirés
uniformément parmi les 2k littéraux possibles.
Passons maintenant des expressions aux fonctions booléennes. Chaque expression booléenne correspond à une unique fonction booléenne, mais chaque fonction
booléenne peut être représentée par une multitude d’expressions. Ainsi, les arbres
des figures 3.22 et 3.23 sont associés à deux expressions booléennes différentes,
mais ils correspondent à la même fonction booléenne x ∨ (y ∧ (z ∨ t)).
La distribution de probabilité définie plus haut sur les arbres ET-OU de même
taille n définit une distribution de probabilité induite P n sur l’ensemble des 2 2 k
fonctions booléennes. En notant par A n l’ensemble de toutes les expressions de
taille n et par A n (f ) le sous-ensemble de ces expressions qui calcule une fonction
booléenne f , la probabilité qu’une expression de taille n calcule f est
P n (f ) =
|A n (f )|
|A n |
.
Ce calcul conduit ainsi au dénombrement de A n , ensemble de tous les arbres ET-OU
de taille n sur k variables booléennes, ce qui ne pose aucune difficulté, et à celui de
A n (f ), sous-ensemble de ces arbres qui calculent la fonction f . Le point délicat
est souvent de trouver une spécification formelle de l’ensemble A(f ) des arbres
qui calculent f ; une fois cette spécification obtenue, les méthodes symboliques
de l’annexe B.2 fournissent en général facilement la fonction génératrice de
dénombrement de A(f ), dont le coefficient d’ordre n, |A n (f )| s’obtient alors soit
directement, soit par les techniques asymptotiques présentées en annexe B.3 lorsque
la taille n de l’expression booléenne tend vers l’infini.
19 Les formes des arbres ET-OU étant des arbres binaires complets, le nombre de leurs feuilles et le
nombre de leurs nœuds internes diffèrent toujours de 1.