Étant donné une application booléenne `f` d'arité `n`, et étant donnée `n` inconnus booléens `(x_1,x_2,...,x_n)`, le problème SAT (boolean SATisfiability problem) consiste à déterminer si `f(x_1,x_2,...,x_n)` est satisfaisable, c'est à dire s'il existe au moins une solution `(x_1,x_2,...,x_n)` telle que `f(x_1,x_2,...,x_n) = 1`.
La première méthode dite « full-attaque » consiste à passer en revue les `2^n` possibilitées, et à s'arrêter dès que l'on trouve une solution.
Une autre méthode dite « Shadock » consiste à essayer des combinaisons au hasard, et à s'arrêter dès que l'on trouve une solution.
Il existe une opération booléenne binaire qui permet de construire toutes les autres opérations booléennes d'arité fixe, c'est le NAND (et aussi le NOR). Cet opérateur est commutatif mais non associatif.
Afin de pouvoir facilement construire des arbres mutli-aires, on peut étendre l'opérateur NAND en un opérateur d'arité variable, qui est encore commutatif, c'est à dire dont le résultat ne dépend pas de l'ordre des arguments, mais qui n'est pas associatif. Et on note cet opérateur multi-aire comme un ensemble. Ainsi en nommant les inconnus `a,b,c,d` nous avons par exemples :
`{ } = 0`
`{a} = ¬a`
`{a,b} = ¬(a "et" b)`
`{a,b,c} = ¬(a "et" b "et" c)`
`{a,b,{c}} = ¬(a "et" b "et" ¬c)`
`{a,b,{c},{d}} = ¬(a "et" b "et" ¬c "et" ¬d)`
`{a,b,{c,d}} = ¬(a "et" b "et" ¬(c "et" d))`
La seconde méthode dite « full-remonté » consiste à partir de la racine de l'arbre représentant la fonction booléenne et à explorer toutes les possibilités. Par exemple considérons la fonction suivante :
`{{a,{a}}, {a,{a,b}}}`
Cette fonction booléenne des variables `(a,b)` s'écrit également comme suit :
` ¬(¬(a "et" ¬a) "et" ¬(a "et" ¬(a "et" b)))`
Pour que `{{a,{a}}, {a,{a,b}}}=1` il faut que `{a,{a}}=0` ou que `{a,{a,b}}=0`. On explore alors les deux alternatives et on s'arrête dès qu'une alternative produit une solution. Pour que `{a,{a}}=0` il faut que `a=1` et `{a}=1` et pour que `{a}=1` il faut que `a=0` ce qui est impossible puisque dans le contexte en cours `a=1`. On passe alors à l'autre alternative. Pour que `{a,{a,b}}=0` il faut que `a=1` et `{a,b}=1` et pour que `{a,b}=1` il faut que `a=0` ou que `b=0`. Le cas `a=0` étant écartée par le contexte, la solution est donc `a=1, b=0`.
La fonction booléenne est mémorisée sous forme d'un arbre. L'arbre est composé de noeuds et de feuilles. Les noeuds correspondent aux fonctions NAND multi-aires, les feuilles sont les inconnues numérotées de `1` à `n`. La liste des `n` inconnues est `(x_1,x_2,...,x_n)`. On se dote d'un ensemble d'outils pour opérer sur cet arbre.
Pour percevoir la forme du programme, on fait le calcul à la main sur un exemple. Et on s'aperçoit alors que l'on parcourt l'arbre de données en explorant tous les chemins croisés possibles tant que la solution n'est pas trouvée.
A chaque noeud de l'arbre, on définie un contexte qui contient toutes les nécessités logiques associées, c'est à dire ici toutes les variables booléennes connues à l'instant juste avant de résoudre le sous-arbre commençant à ce noeud. Cela correspond à l'exploration d'un « arbre et-ou » où l'information est localisée dans les feuilles. C'est un algorithme fondamentale en intelligence artificielle.
Puis nous sommes libre d'adapter le langage au problème. Rappellez-vous que la bonne formulation d'un problème résoud la moitier du problème, et que le bon choix du langage de programmation et du framework résoud la moitier de la conception du programme.
Nous allons programmer la résolution d'un arbre et-ou en profondeur d'abord.
On considére des éléments de langage suivant :
La variable `r` représente un noeud de l'arbre, et qui peut être aussi une feuille de l'arbre.
La variable `A` représente un contexte qui contient l'ensemble des variables booléennes connues avec leurs valeurs booléennes.
On utilise des pointeurs pour désigner les noeuds et les contextes. Un pointeur sur un noeud désigne l'arbre dont la racine est ce noeud. Un pointeur sur une feuille désigne un arbre rudimentaire ne contenant que cette feuille qui joue à la fois le rôle de racine et de feuille. On utilise le pointeur `nil` pour désigner l'arbre vide, et aussi pour désigner le contexte impossible.
Le symbole `nil` représente l'arbre vide.
Le symbole `nil` représente le contexte impossible.
Un noeud est caractérisé par un label "et" ou "ou" et par une liste de fils qui peut être vide.
On s'inspire du langage Lisp et des fonctions car et cdr qui décomposent par exemple une liste `(a,b,c)` en un premier terme `a` et un second terme qui est le reste `(b,c)`, et qui permettent ainsi d'implémenter des arbres multi-aire sous forme d'arbre binaire.
On se munie de la fonction `p` qui appliquée à un noeud retourne son premier fils, ou `nil` s'il n'en a pas.
On se munie de la fonction `q` qui appliquée à un noeud retourne un noeud possèdant le même label et la même liste de fils mais dans laquelle on a retiré le premier fil, ou qui retourne `nil` s'il n'y avait au plus qu'un seul fils.
Remarquez que la fonction composée `p_2=p@q` appliquée à un noeud retourne son second fils ou `nil` s'il n'en a pas, que la fonction composée `p_3=p@q@q` appliquée à un noeud retourne son troisième fils ou `nil` s'il n'en a pas, etc..
On constate que l'arbre multi-aire munie des fonctions `p,p@q,p@q@q,...` pour accéder aux n-ième fils de chaque noeud, est équivalent à l'arbre binaire munie des fonctions `p` et `q` pour accéder aux premiers et second fils de chaque noeud. On implémente ainsi un arbre et-ou multi-aire sous forme d'un arbre et-ou binaire.
On se munie d'une fonction `C` qui, appliquées à une feuille et un contexte, permet de produire un nouveau contexte intégrant ces deux éléments.
Noeud ou feuille Contexte
Retourne le premier fils de `r` Retourne un noeud similaire à `r` dans lequel on a enlevé le premier fils. Retourne un nouveau contexte comprenant le contexte `A` avec la feuille `r` ajoutée. Résoud l'arbre et-ou de racine `r` sous le contexte `A` et retourne le contexte en cours qui est soit une solution ou soit `nil`.
L'arbre et-ou est désigné par sa racine `r`. La résolution de cet arbre `r` sous un contexte `A` se note `R(A,r)`. Pour des raisons mémotechniques, on a placé en premier argument le contexte `A` puisque celui-ci est prédéfinie avant d'entrer dans l'arbre `r`. Puis on choisie de transmettre comme résultat de cette fonction non pas la valeur booléenne résultat mais un élément beaucoup plus riche qu'est le contexte en cours, c'est à dire soit le contexte impossible noté `nil` si l'arbre et-ou n'est pas satisafaisable ou bien le contexte en cours qui décrit une solution si l'arbre et-ou est satisafaisable (et qui est alors satisfait par ce contexte).
La résolution en profondeur d'abord consiste à explorer dans chaque noeud d'abords les fils dans l'ordre, c'est à dire à commencer par le premier fils puis le second fils. Les fils de `r` sont : `p(r), q(r)`.
Si le noeud `r` est un noeud "et" alors nous avons :
`R(A,r) = R(R(A,p(r)),q(r))`
Si le noeud `r` est un noeud "ou" alors nous avons :
`R(A,r) = "le premier contexte différent de "nil" parmis " R(A,p(r)), R(A,q(r)) " où "nil" s'il n'y en à pas "`
Si le noeud `r` est une feuille alors nous avons :
`R(A,r) = C(A,r)`
D'autre part, quelque soit `r`, si le contexte est impossible alors la résolution est impossible :
`R(nil,r) = nil`
Et quelque soit le contexte `A`, si l'arbre est vide alors il n'y a rien à résoudre et le contexte résultat est inchangé :
`R(A,nil) = A`
L'algorithme d'exploration de l'arbre et-ou en profondeur d'abord s'écrit sous la forme d'une fonction récurcive suivante :
Fonction `R(A,r)` : Si `r=nil` alors retourner `A`
Si `A=nil` alors retourner `nil`
Si `r` est une feuille alors retourner `C(A,r)`
Si `r` est un noeud "et" alors retourner `R(R(A,p(r)),q(r))`
Si `r` est un noeud "ou" alors
`B=R(A,p(r))`
Si `B != nil` alors retourner `B`
Retourner `R(A,q(r))`
On utilise le langage go, un langage C amélioré adapté aux systèmes d'exploitation et aux calculs parallèle libres.
On ajoute au type noeud, le champ "op" qui contient "et" lorsque le noeud est un noeud "et", et qui contient "ou" lorsque le noeud est un noeud "ou". Le noeud est une feuille s'il ne possède pas de premier fils.
Vrai si `r` est un noeud "et". Vrai si `r` est un noeud "ou". Vrai si `r` est une feuille.
Le programme se met sous la forme suivante :
package main
import ( "fmt" )
type Contexte struct{......} // nil représente un pointeur pointant sur le contexte impossible.
type Noeud struct {op string, ......} // nil représente un pointeur pointant sur un arbre vide.
func a(r *Noeud) *Noeud {......} // Retourne de premier fils de r.
func b(r *Noeud) *Noeud {......} // Retourne de second fils de r.
func C(A *Contexte, r *Noeud) *Contexte {......} // Retourne un contexte complétant A en ajoutant r.
func R(A *Contexte, r *Noeud) *Contexte { // Résoud l'arbre et-ou r avec le contexte prédéfini A.
if r==nil {return A}
if A==nil {return nil}
if p(r)==nil {return C(A,r)}
if r.op == "et" {return R(R(A,p(r)),q(r))}
if r.op == "ou" {
B:=R(A,p(r))
if B!=nil {return B}
return R(A,q(r))
}
return nil
}
On remarque que la fonction `C(A,r)` n'est que la restriction de la fonction `R(A,r)` aux seuls feuilles `r`.
Le contexte contient la connaissance atomique booléenne sur les `n` variables. Le contexte peut se caractérisé par deux ensembles disjoints d'entiers compris entre `1` et `n`, chaque entier `i` désignant l'inconnue `x_i`. Le premier ensemble `E_1` contient les variables connues pour être vrais, et le second ensemble `E_0` contient les variables connues pour être fausses. Le contexte peut aussi se caractériser par deux ensembles inclus l'un dans l'autre. Le premier ensemble `C` contient les variables connues. Et le second ensemble `V` contient les variables connues pour être vrai. On peut utiliser une troisième valeur logique pour désigner l'absence de connaissance sur une variable booléenne. Il peut être judicieux d'ordonner ces trois valeurs dans cet ordre `("false", "ne sait pas", "true")` et de les coder respectivement par les entiers `(-1,0,1)`. Ainsi on note `x=-1` si nous connaissons que `x` est faux. On note `x=0` si on ne connait pas la valeur logique de `x`. Et on note `x=1` si nous connaissons que `x` est vrai. Le contexte se caractérise alors par un tableau associant à chaque inconnue une valeur parmi `{-1,0,1}`.
Il ne faut pas confondre l'absence de connaisance sur `x` avec la contrainte de ne pas avoir de connaisance sur `x`, ou autrement dit, avec la connaissance de cette absence de connaissance sur cette variable. Cette dernière affirmation constitue une quatrième valeurs logique. C'est une extension naturelle des contextes logiques. Et d'autres extensions similaires sont encore possibles.
Une opimisation est possible sur la définition de la fonction `q`. Lorsque `q` s'applique à un singleton il retourne 'nil'. Lorsque `q` s'applique à un couple, il retourne le singleton composé du second élément du couple. L'optimisation consiste à modifier cette règle et à faire que lorsque `q` s'applique à un couple, il retourne directement le second élément du couple.
Un arbre est un graphe non orienté connexe et sans cycles. Dans un arbre on ne fait pas de distinction entre noeud et feuille, se sont tous des sommets d'un graphe qui constitue un objet plus générale que l'arbre. Une feuille est un noeud ne possédant pas de fils, et est appellée noeud terminal ou noeud externe en opposition aux noeuds internes qui eux possèdent au moins un fils.
Le nombre de sommets d'un arbre est toujours égal au nombre d'arêtes de l'arbre plus un.
L'arbre est nu si les noeuds ne sont pas étiquetés.
L'arbre, par défaut, est nu, il possède une racine et chaque noeud possède une liste de fils qui peut être vide. Ces 3 prédispositions que l'on considère implicites caractérisent ce que classiquement on appelle un arbre de Catalan.
L'ensemble des arbres forment une structure composée d'une opération multi-aire `f(...)` et d'un élément générateur `a` dont la définition programmative et linguistique est :
Arborescence monogène `"("f, a")" = "<"a,f"(...)"">"`
L'opérateur multi-aire `f` permet de construire un arbre à partir d'une suite non vide d'arbres. Il crée un noeud racine prenant pour fils ses arguments. Considérons trois arbres `r` et `s` et `t` qui appartiennent à l'arborescence. On construit un nouvel arbre `f(r,s,t)` qui appartient toujours à cette arborescence.
---- 2 avril 2016 ----
Dans un arbre commutatif les fils d'un même noeuds peuvent se permuter librement.
Dans un arbre sans racine, on ne parle plus de fils mais de voisins. Chaque noeud possède une liste de voisins qui est définie circulairement. C'est à dire qu'il n'y a pas de premier voisin, il n'y a qu'une succession circulaire de voisins telle que décrite par une représentation de l'arbre dans un plan. Les arbres sans racines sont classiquement appellés arbres planaires.
Le nombre d'arbres de Catalan possèdant `n` noeuds est `c_(n-1)`, le `(n-1)`ième nombre de Catalan. Ces nombres sont nommés ainsi en l'honneur du mathématicien belge Eugène Charles Catalan (1814-1894). Les premiers nombre de Catalan de `c_0` à `c_9` sont :
`1, 1, 2, 5, 14, 42, 132, 429, 1 430, 4 862,...`
Chaque noeud de l'arbre est caractérisé par son adresse qui est une suite finie d'entiers et qui représente le chemin permettant de passer de la racine au noeud en question. Dans cette suite chaque entier désigne le numéro du fils qu'il faux choisir pour parcourir le chemin.
Un arbre nu est similaire à un autre arbre nu ssi tous les chemins existant dans l'un existe dans l'autre. Un arbre nu est similaire à un autre arbre nu ssi chaque noeud caractérisé par son adresse relative possède le même nombre de fils que son homologue sur l'autre arbre.
On privilègie l'implémentation par pointeur et la conception qui en découle. Le pointeur `nil` désigne l'arbre vide. La fonction `p` qui permet d'accéder au premier fils d'un noeud, retourne `nil` s'il n'a pas de fils. Ainsi pour un noeud `r`, si `p(r) = nil` cela signifie que le noeud `r` est terminal, qu'il constitue une feuille, un noeud externe. Les autres noeuds sont dit internes. Les arêtes internes sont les arêtes reliants deux noeuds internes. Les arêtes externes sont les arêtes reliant un noeud interne à un noeud externe, autrement dit, reliant un noeud à une feuille.
L'arbre est désigné par sa racine `r`. Le nombre de sommets de l'arbre `r` se note `S(r)` est correspond au nombre de noeuds et de feuilles. Le nombre d'arêtes de l'arbre `r` se note `M(r)`. Et nous avons la relation : `S(r) = M(r)+1` car `r` est un arbre.
L'intérieur de `r` se note `I(r)` et est constitué des noeuds internes de `r` et des arêtes internes de `r`. Et nous avons la relation : `S(I(r)) = M(I(r))+1` car l'interieur de `r`, noté `I(r)`, est encore un arbre. Le procédé peut s'appliquer plusieurs fois de suite pour définir l'intérieur de l'interieur de l'arbre, `I(I(r))`, et ainsi de suite...
L'arbre commutatif possède une racine et chaque noeud possède un ensemble de fils (qui peut être vide). L'arbre commutatif se différencie de l'arbre non commutatif part le fait que chaque noeud possède un ensemble de fils et non une liste de fils.
Dans un arbre binaire chaque noeud interne a exactement 2 fils. L'ensemble des arbres binaires non vides forment la structure suivante dont la définition linguistique est :
Magma monogène `"("**, a")" = "<"a,**">"`
L'opérateur binaire `**` permet de construire un arbre à partir de deux autres arbres. Il crée un noeud racine prenant pour fils ses deux arguments. Considérons deux arbres `r` et `s` qui appartiennent au magma. On construit un nouvel arbre `r**s` qui appartient toujours à ce magma.
Le symbole `a` désigne l'arbre unité. C'est l'arbre générateur qui permet de construire tous les arbres binaires nus. Dans une expression telle que par exemple `(a**a)**(a**a)`, le nombre de noeuds internes est égal au nombre d'apparitions du symbole `**` dans l'expression, et le nombre de feuilles est égal au nombre d'apparitions du symbole `a` dans l'expression.
On ajoute quelque fois à cette structure, l'arbre vide qui constitue l'élément neutre pour l'opération `**` et que l'on note `nil`. L'ensemble des arbres binaires forment alors la structure suivante dont la définition linguistique est :
Magma unitaire monogène `"("**, nil,a")" = "<"nil, a,**"> / {"x**nil = x, nil**x = x}`
Il est possible de définir une relation d'ordre totale sur le magma monogène, et l'ordre correspond alors à une bijection entre `"<"a,**">"` et `NN`. On définie l'ordre par la taille d'abord puis par l'ordre lexicographique ensuite. L'ordre commence par `a`, `a**a`, puis pour des arbres de même taille, c'est à dire de même nombre de noeuds, on applique la règle lexicographique suivante :
`r_1**s_1 < r_2**s_2 <=> r_1<r_2" ou "(r_1=r_2" et "s1<s_2)`
Ainsi en notant |r| = S(r) la taille de l'arbre `r` c'est à dire son nombre de noeuds, on définie la relation d'ordre `<` récurcivement comme suit : `r_1**s_1 < r_2**s_2` si et seulement si :
`|r_1**s_1| < | r_2**s_2| " ou " ( |r_1**s_1| = | r_2**s_2| " et (" r_1<r_2" ou "(r_1=r_2" et "s1<s_2)))`
ou en développant :
`|r_1**s_1| < | r_2**s_2| " ou " (|r_1**s_1| = | r_2**s_2| " et " r_1<r_2) " ou "(|r_1**s_1| = | r_2**s_2|" et "r_1=r_2" et "s1<s_2)`
Si on ajoute l'arbre vide `nil`, celui-ci est alors le plus petit de tous les arbres.
Lorqu'il n'y a pas d'ambiguité on remplace le symbole `**` par l'absence de symbole, comme dans un produit. Mais l'opération n'étant pas associative, toute combinaison de plus de deux termes doit être scindée par des parenthèses. L'ordre des arbres binaires nus est celui-ci :
Gauche/Droite
Le dénombrement des arbres binaires se fait récurcivement et correspond aux nombres de Catalan. Le nombre d'arbres binaires de `n` noeuds internes se note `c_n` et s'appelle le `n`ième nombre de Catalan.
L'arbre vide `nil` n'est pas utilisé. Il y a exactement un arbre sans noeud interne qu'est l'arbre générateur `a`, donc `c_0 = 1`. Il y a exactement un arbre avec un seul noeud interne qu'est l'arbre `a**a`, donc `c_1=1`. Considérons `n` noeuds internes. Un noeud est utilisé par la racine. Il reste `n-1` noeuds qui se répartissent dans le sous-arbre gauche et le sous-arbre droits, selon les répartitions possibles suivantes `(0,n-1)`, `(1,n-2)`, `(2,n-3)`, ... , `(k,n-1-k)`, ... , `(n-1,0)`. Pour une répartition `(u,v)` des noeuds internes, il existe `c_u` arbres gauches distincts possibles et `c_v` arbres droits distincts possibles. On en déduit que le nombre d'arbres ayant `n` noeuds internes est :
`c_n = c_0c_(n-1) + c_1c_(n-2)+...+c_kc_(n-1-k)+... +c_(n-1)c_0`
Ce qui se note :
`c_n = sum_(k=0)^(n-1)c_kc_(n-1-k)`
Le nombre de parties de `k` éléments dans un ensemble de `n` éléments se note `((n),(k))` et s'appelle le nombre de combinaison de `k` parmi `n`, et s'appelle un coefficient binomial. Voici quelques égalités remarquables de base :
Les nombres de Catalan
`c_n = 1/(n+1)((2n)!)/((n!)^2)`
`c_n = prod_(i=2)^n (n+i)/i`
`c_n = 2(2n-1)/(n+1)c_(n-1)`
`c_n =1/(n+1) ((2n),(n))`
`c_n =((2n),(n))-((2n),(n+1))`
Les coefficients binomiaux
`((n),(k)) = (n!)/(k!(n-k)!)`
`((n),(k)) = ((n),(n-k))`
`((n),(k)) = n/k((n-1),(k-1))`
`((n),(k)) + ((n),(k+1)) = ((n+1),(k+1))`
La formule de Stirling permet de calculer un équivalent asymptotique de la suite des nombres de Catalan :
`n! ~~ sqrt(2pin)(n/e)^n c_n ~~ 4^n/(n^(3/2)sqrt(pi))`
`n! = sqrt(2pin)(n/e)^n(1+1/(12n) + 1/(288n^2) - 139/(51840n^3) - 571/(2488320n^4) + O(1/n^5)) `
`c_n = 4^n/(n^(3/2)sqrt(pi))(1-9/(8n)+14/(128n^2)-1155/(1024n^3)+36939/(32768n^4) + O(1/n^5))`
Dans notre étude présente sur la logique on s'intéresse plus particulièrement aux arbres binaires commutatifs non nuls, c'est à dire à permutation près des fils dans chaque noeud.
Les arbres binaires commutatifs non nuls forment la structure suivante dont la définition linguistique est :
Magma commutatif monogène`"("**, a")" = "<"a,**"> / {"x**y=y**x}`
On représente un arbre binaire commutatif par l'arbre binaire le plus petit de sa classe à commutation près. Voici les premiers arbres commutatifs dans l'ordre :
Gauche/Droite
Notons `a_n` le nombres d'arbres à commutation près ayant `n` noeuds intérieurs. Il y a exactement un arbre à commutation près sans noeud interne qu'est l'arbre générateur `a`, donc `a_0 = 1`. Il y a exactement un arbre à commutation près avec un noeud interne qu'est l'arbre `a**a`, donc `a_1=1`. Il faut séparer le cas pair et le cas impair. Considérons `2n` noeuds internes. Un noeud est utilisé par la racine. Il reste `2n-1` noeuds qui se répartissent dans le sous-arbre gauche et le sous-arbre droits, selon les répartitions possibles suivantes `(0,2n-1)`, `(1,2n-2)`, `(2,2n-3)`, ... , `(k,2n-1-k)`, ... , `(n-1,n)`. Comme cela est à commutation près, on ne tient pas compte des répartitions symétriques. Pour une répartition `(u,v)` des noeuds internes, avec `u<v` , il existe `a_u` arbres gauches distincts possibles à commutation près et `a_v` arbres droits distincts possibles à commutation près. On en déduit le nombre d'arbres ayant `2n` noeuds internes à commutation près :
`a_(2n) = a_0a_(2n-1) + a_1a_(2n-2)+...+a_ka_(2n-1-k)+... +a_(n-1)a_n`
Ce qui se note :
`a_(2n) = sum_(k=0)^(n-1)a_ka_(2n-1-k)`
De même considérons `2n+1` noeuds internes. Un noeud est utilisé par la racine. Il reste `2n` noeuds qui se répartissent dans le sous-arbre gauche et le sous-arbre droits, selon les répartitions possibles suivantes `(0,2n)`, `(1,2n-1)`, `(2,2n-2)`, ... , `(k,2n-k)`, ... , `(n,n)`. Comme cela est à commutation près, on ne tient pas compte des répartitions symétriques. Mais pour la répartition `(n,n)`, des solutions symétriques apparaissent. Il faut considérer le nombre de couples `(x,y)` appartenant à `{1,2,3...,a_n}×{1,2,3...,a_n}` tel que `x<=y`. Et il y en a exactement :
`(a_n(a_n+1))/2`
On en déduit le nombre d'arbres à commutation près ayant `2n+1` noeuds internes :
`a_(2n+1) = a_0a_(2n) + a_1a_(2n-1)+...+a_ka_(2n-k)+... +a_(n-1)a_(n+1) + (a_n(a_n+1))/2`
Ce qui se note :
`a_(2n+1) = (a_n(a_n+1))/2 + sum_(k=0)^(n-1)a_ka_(2n-k)`
Voici la liste des nombres de Catalan abeliens de `a_0` à `a_15` :
`1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905...`
L'arbre ternaire possède une racine et chaque noeud interne possède une liste d'exactement `3` fils. Le nombre de tels arbres possédant `n` nœuds internes est :
`1/(2n+1)((3n),(n))`
La formule se généralise au cas des arbres `b`-aire où chaque noeud interne possède `b` fils. Le nombre de tels arbres possédant `n` nœuds internes est :
`1/((b-1)n+1)((bn),(n))`
L'ensemble des arbres ternaire non vides forment une structure apellée trium dont la définition linguistique est :
Trium monogène `"("f"(.,.,.)", a")" = "<"a,f"(.,.,.)"">"`
L'opérateur ternaire `f` permet de construire un arbre à partir de trois autres arbres. Le suffixe de `"f(.,.,.)"` précise que `f` est un opérateur ternaire dans la structure. Il crée un noeud racine prenant pour fils ses trois arguments. Considérons trois arbres `r, s, t` qui appartiennent au trium. On construit un nouvel arbre `f(r,s,t)` qui appartient toujours à ce trium.
Le symbole `a` désigne l'arbre unité. Il ne contient qu'une feuille et aucun noeud interne. C'est l'arbre générateur qui permet de construire tous les arbres ternaires nus. Dans une expression telle que par exemple `f(f(a,a,a),f(a,a,a),f(a,a,a))`, le nombre de noeuds internes est égal au nombre d'apparitions du symbole `f` dans l'expression, et le nombre de feuilles est égal au nombre d'apparitions du symbole `a` dans l'expression.
Le dénombrement des arbres ternaires se fait selon le même principe. Notons `p_n` le nombre d'arbres ternaires ayant `n` noeuds internes. Il y a exactement un arbre sans noeud interne qu'est l'arbre générateur `a`, donc `p_0 = 1`. Il y a exactement un arbre avec un seul noeud interne qu'est l'arbre `f(a,a,a)`, donc `p_1=1`. Considérons `n` noeuds internes. Un noeud est utilisé par la racine. Il reste `n-1` noeuds qui se répartissent dans les trois sous-arbre. Ces répartitions sont décrites par l'ensemble des triplets d'entiers positifs `(x,y,z)` tels que `x+y+z = n-1`. Pour une répartition `(u,v,w)` des noeuds internes, il existe `p_u` arbres gauches distincts possibles, `p_v` arbres centrales distincts possibles et `p_w` arbres droits distincts possibles. On en déduit que le nombre d'arbres ayant `n` noeuds internes est :
`c_n = sum_((x,y,z) in NN^3 "/" x+y+z=n-1)c_xc_yc_z`
L'arbre représente un calcul. Chaque feuille correspond à une entrée de donnée. Chaque noeud interne correspond à un calcul opérant sur les données produites par ses fils et produisant un résultat qui est transmis à son père, ou si c'est le noeud racine, qui est le résultat global. Le partage permet de réutiliser un calcul intermédiaire sans avoir à le recalculer. Cela permet de réduire la complexité du calcul. C'est même le seul moyen semble-t-il, en dehors des équivalences logiques, de réduire la complexité du calcul.
L'arbre partagé se définie simplement en permettant d'affecter les feuilles à des sous-arbres déjà existant dans l'arbre, mais dont la racine ne doit pas être un descendant de la feuille en question afin d'éviter les références récursives.
---- 6 mars 2016 ----
Pour programmer élégamment la résolution d'arbres et-ou multi-aires, on remplace les deux fonctions `a` et `b` par la fonction premier fils `p` et la fonction frère `f`.
Puis on développe deux fonctions de compositions.