-1- -2-INF 421 — 06 Luc Maranget Deux exemples d’arbres◮ Les arbres-termes :Le calcul propositionnel.Deux usages des arbres◮ Les arbres structurants :Diviser le plan en quatre (et puis enquatre, et puis...)Luc.Maranget@inria.frhttp://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/-3- -4-Un grand classique La classe des propositionsSelon le principe d’un champ (( nature ).Une expression bool´eenne e (ou proposition) est :class Prop {◮ Vrai ou faux, T ou F,final static int FALSE=0, TRUE=1, VAR=2, NOT=3, OR=4, AND=5 ;int nature ; int asVar ; Prop left, right ;◮ Une variable x ,...x ,0 N−1private Prop (int nature) { this.nature = nature ; }◮ La n´egation ¬(e),◮ Une conjonction (e ∧e ), une disjonction (e ∨e ).1 2 1 2private Prop (int nature, int asVar) {this.nature = nature ; this.asVar = asVar ;Note :}◮ Conceptuellement c’est aussi simple que les expressionsprivate Prop (int nature, Prop left) {arithm´etiques.this.nature = nature ; this.left = left ;}◮ Techniquement, il y a un peu plus de sortes de termes.private Prop (int nature, Prop left, Prop right) {this.nature = nature ; this.left = left ; this.right = right ;}}-5- -6-Construction des termes BonusIl devient hasardeux de se fier aux constructeurs. Des d´etails, li´es a` Une certaine d´econnexion entrela r´ealisation concr`ete prennent trop d’importance.◮ Sp´ecification, (ce que c’est, ici une proposition)On utilisera plutotˆ des m´ethodes statiques bien ...
Un grand classique Uneexpressionbool´eennee(ou proposition) est :
◮Vrai ou faux,TouF,
◮Une variablex0, . . . xN−1, ◮o´intgaeanL¬(e),
◮Une conjonction (e1∧e2), une disjonction (e1∨e2). Note:
◮Conceptuellement c’est aussi simple que les expressions arithm´etiques.
◮Techniquement, il y a un peu plus de sortes de termes.
2
4
Deuxexemplesd’arbres
◮rbratseseLmeers: Le calcul propositionnel.
◮Les arbres structurants: Diviser le plan en quatre (et puis en quatre, et puis. . . )
La classe des propositions Selon le principe d’un champ✭nature✮. classProp{ fin a l static intFALSE=0,TRUE=1,VAR=2,NOT=3,OR=4,AND=5 ; intnature;intasVar;Prop left,right;
On peut d’alleurs exprimer d’autres connecteurs logiques, sans changer les cellules d’arbre, par ex. staticProp mkImplies(Prop e1,Prop e2) { returnmkOr(mkNot(e1),e2) ; }
Fonctionnement
x0
∨
∨
x1
x2
◮toString()du sousarbre de gauche : ⊲Deux feuilles"x0"et"x1". ⊲atncCo:noitane´"("+"x0"+" || "+"x1"+")". Soit au final pour ce sousarbre"(x0 || x1)".
◮toString()du sousarbre de droite :"x2".
◮Et finalement :"("+"(x0 || x1)"+" || "+"x2"+")"
9
11
CoˆutdetoString() Conside´rerlasuited’expressions
E0=x0,
Ek+1=xk+1∨Ek
◮L’arbreEkrepelbmessa`toˆtul.lenuetsi
∨ xk∨ xk−1
. . .
x1
◮L’arbreEkde2epso`sk+ 1 nœuds.
∨
x0
◮Ek.toString()tniuesrpdooisnatent´taonsclee,uqitardauqtse des chaˆınes de taille au moins 3 + 5 +∙ ∙ ∙+ (2k+ 1).