Discussion :

[Djobird]

Bonjour,
je désire modéliser une formule booléenne, je ne vois pas tellement d'autre solution que celle-ci mais par acquis de conscience je préfères vérifier si vous n'en connaissez pas de meilleurs.
Donc, je pense modéliser ca sous forme d'arbre, j'ai l'entité réflexive noeud, l'entité opérateur, et l'entité feuille.

Chaque nœud a donc un opérateur (ou, et, non ...), et a soit des noeuds fils, soit des feuilles.

Est ce que cela convient, ou y'a il mieux ?

[JPhi33]

Peux-tu donner quelques exemples de formules booléennes pour nous raffraîchir la mémoire ? Et leur correspondance dans ton modèle.

[Djobird]

Et bien par exemple supposons que l'on ait la formule suivante :

(A & B & C ) || ( D & !E)

Cela donne un arbre du genre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12

                      ||
                     /  \
                   /      \
                 &          &
                / \         / \
               /   \       D   !
              &    C           |
             / \               E 
            /   \
           A     B

(bon moche mais en gros compréhensible).

J'aurais dans mon entité feuilles, A, B, C, D, et E
Puis une instance de noeud (N1) relié à à l'opérateur &, et les deux feuilles A et B qui symbolise le A & B.
Ensuite une instance de noeud (N2) relié à l'op &, la feuille C et le noeud N1
Et ainsi de suite.

[JPhi33]

Bonjour,

Les idées sont là mais il faut les formaliser.

Chaque nœud a donc un opérateur (ou, et, non ...), et a soit des noeuds fils, soit des feuilles.

... ou un mélange des deux. Par exemple, le "&" à gauche sous le "||" a comme fils un opérateur (&) et une feuille (C).

Je vois 4 manières de modéliser ce sujet. Dans chaque modèle on considère que :
- Les opérateurs et les feuilles sont tous des noeuds
- Un Noeud est identifié par un "numéro_noeud" ou un "id_noeud"
- Un Noeud a un et un seul Noeud père.
- Un Noeud a 0 à n Noeud fils : 0 si le Noeud est une feuille, 1 ou 2 si le Noeud est un opérateur.


1) Modèle immédiat
Un Noeud contient la propriété "valeur_noeud". Seule cette propriété renseigne sur le type de Noeud (opérateur ou feuille).

[ Noeud ]--1,1---père---( connecte )---fils---0,n->[ Noeud ]


2) Modèle simple
Le modèle immédiat est complété par l'ajout d'une entité Type_Noeud contenant "opérateur" ou "feuille" (ce qui peut être plus pratique que dans le modèle 1 pour identifier le type de noeud)

[ Noeud ]--1,1---père---( connecte )---fils---0,n->[ Noeud ]
[ Noeud ]--1,1------( a-un )------0,n->[ Type_Noeud ]


3) Modèle intermédiaire
- Le Noeud ne contient pas la propriété "valeur_noeud" car on distingue des types d'opérateurs et des feuilles
- Un Noeud est soit un opérateur, dans ce cas il a un Type_Opérateur, soit une Feuille.
- Une contrainte d'exclusion (le "soit ... soit" ci-dessus) doit être modélisée entre les deux "pattes" de cardinalités (0,1).
- Une Feuille est unique (mais une même valeur de feuille, par exemple "A", peut se retrouver dans plusieurs feuilles) ; elle est donc reliée à un seul Noeud qui la représente.

[ Noeud ]--1,1---père---( connecte )---fils---0,n->[ Noeud ]
[ Noeud ]--0,1------( a-un )------0,n->[ Type_Opérateur ]
[ Noeud ]<-0,1------( a-un )------1,1--[ Feuille ]


4) Modèle sémantique
Ce modèle porte une sémantique plus riche que les autres modèles.
On a déjà considéré dans le modèle 3 qu'un noeud est un opérateur ou bien est une feuille. Dans le modèle intermédiaire, cette notion a été faussement traduite par des liens "a-un". En réalité, elle se traduit par des liens des généralisation-spécialisation. Plus précisément, il s'agit ici d'une généralisation alternative : l'entité généralisée est soit Opérateur soit Feuille ; l'entité spécialisée est Noeud. Cette dernière hérite donc, selon le cas, de l'une des deux entités généralisées.
Le nombre d'occurrences de Noeud est égal à la somme du nombre d'occurrences de Opérateur et du nombre d'occurrences de Feuille. Il faut que les identifiants de Opérateur, Feuille et Noeud soient de même domaine sémantique (par exemple tous des numéros).

[ Noeud ]--1,1---père---( connecte )---fils---0,n->[ Noeud ]
[ Noeud ]===>[ Opérateur ]
[ Noeud ]===>[ Feuille ]


En conclusion, on peut dire que chaque problème n'a pas une solution unique en matière de modélisation, comme j'ai déjà eu l'occasion de le dire souvent sur ce forum. Selon le degré d'abstraction souhaité, le potentiel d'évolutivité du modèle, et d'autres critères, on peut opter pour un modèle ou un autre.


JPhi33

[Djobird]

Merci beaucoup je regarde ca de plus pres ^^