Cours sur les arbres : Deux exemples d'arbres

Description

-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...)[e-mail]://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 ...

Sujets

• informatique

Informations

• Publié par: Armyo
• Nombre de lectures: 153
• Langue: Français

Extrait

1

3

INF 421 — 06

Deux

usages

des

Luc Maranget

arbres

[e-mail] http://www.enseignement.polytechnique.fr/profs/ informatique/Luc.Maranget/421/

Un grand classique Uneexpressionbool´eennee(ou proposition) est :

◮Vrai ou faux,TouF,

◮Une variablex 0 , . . . x N−1 , ◮o´intgaeanL¬(e),

◮Une conjonction (e 1 ∧e 2 ), une disjonction (e 1 ∨e 2 ). 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

◮rbratseseLmeers: 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;

privateProp(intnature) {this.nature=nature; }

privateProp(intnature,intasVar) { this.nature=nature;this.asVar=asVar; }

privateProp(intnature,Prop left) { this.nature=nature;this.left=left; }

privateProp(intnature,Prop left,Prop right) { this.nature=nature;this.left=left;this.right=right; }}

5

7

Construction des termes Ildevienthasardeuxdesefierauxconstructeurs.Desde´tails,li´es`a lare´alisationconcr`eteprennenttropd’importance. Onutiliseraplutˆotdesme´thodesstatiquesbiennomme´es. staticProp mkTrue() {return newProp(TRUE) ; }

staticProp mkVar(intno) {return newProp(VAR,no) ; }

staticProp mkNot(Prop e) {return newProp(NOT,e) ; }

staticProp mkAnd(Prop return newProp(AND, } . . .

e1,Prop e2) { e1,e2) ;

C’est la technique ditefactory.

Affichage Commed’habitude,red´efinirtoString. publicString toString() { switch(nature) { caseTRUE:return"true"; caseFALSE:return"false"; caseVAR:return"x"+asVar; caseNOT:return"!("+left+")"; caseOR:return"("+left+" || "+right+")"; caseAND:return"("+left+" && "+right+")"; default:throw newError("Prop (toString)") ; } }

B´ene´fice:System.out.println(e)fonctionne. Parcours ? Infixe en quelque sorte.

6

8

Bonus Unecertainede´connexionentre

◮)ontisiporoepnuici,tse’ceuqecon,(catiecifiSp´

◮Impelicmahcstfait,immentc’etaoi(noclpe´emtnnatureetc.)

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

x 0

∨

∨

x 1

x 2

◮toString()du sousarbre de gauche : ⊲Deux feuilles"x0"et"x1". ⊲atncCo:noitane´"("+"x0"+" || "+"x1"+")". Soit au final pour ce sousarbre"(x0 || x1)".

◮toString()du sousarbre de droite :"x2".

◮Et finalement :"("+"(x0 || x1)"+" || "+"x2"+")"

9

11

CoˆutdetoString() Conside´rerlasuited’expressions

E 0 =x 0 ,

E k+1 =x k+1 ∨E k

◮L’arbreE k repelbmessa`toˆtul.lenuetsi

∨ x k ∨ x k−1

. . .

x 1

◮L’arbreE k de2epso`sk+ 1 nœuds.

∨

x 0

◮E k .toString()tniuesrpdooisnatent´taonsclee,uqitardauqtse des chaˆınes de taille au moins 3 + 5 +∙ ∙ ∙+ (2k+ 1).

toString✭liaernie´✮II . . . caseAND: r.append("(") ; left.inStringBuilder(r) ; r.append(" && ") ; right.inStringBuilder(r) ; r.append(")") ; break; } }

publicString toString() { StringBuilder r=newStringBuilder() ; inStringBuilder(r) ; returnr.toString() ; } }

10

12

toString✭lin´eaire✮ Avec leStringBuilderamtseeodth´eappend(String s), qui ajoute la chaˆınesalnfia`udStringBuildernuocopru,ˆut proportionnela`s.length(). private voidinStringBuilder(StringBuilder r) { switch(nature) { caseTRUE: r.append("true") ;break; caseFALSE: r.append("false") ;break; caseVAR: r.append("x"+asVar) ;break; caseNOT: r.append("!(") ; left.inStringBuilder(r) ; r.append(")") ; break; . . .

´ Evaluation des propositions Lesr`eglessontnormalementbienconnues:

e F T

¬(e) T F

e 1 F F T T

e 2 F T F T

(e 1 ∨e 2 ) F T T T

(e 1 ∧e 2 ) F F F T

L’e´valuationsefaitrespectivement`aunenvironnement(unetable d’associations :x i 7→b). Lesassociationsont´ete´vueslorsdel’amphi04.Icionpeututiliser untableaudirectement(variablesindic´ees). static booleaneval(Prop e,boolean[]env) {. . .}

13

15

´ Evaluation static booleaneval(Prop e,boolean[]env) { switch(e.nature) { caseTRUE:return true; caseFALSE:return fa lse; caseVAR:returnenv[e.asVar] ; caseNOT:return!eval(e.left,env) ; caseOR: returneval(e.left,env) ||eval(e.right,env) ; caseAND: returneval(e.left,env) &&eval(e.right,env) ; default: throw newError("Prop (eval)") ; } }

Application du calcul des propositions Ladirectiond’unecre`chesouhaiter´eglementerlesjouetsapport´es par les enfants. Lesjouetssontde´critsseloncinqcrite`res:petit/grand,vert/pas vert,peluche/paspeluche,´electrique/pas´electrique,avecpiles/sans piles. C’esta`dire,nousavonscinqvariablesbool´eennes. Prop petit=mkVar(0) ; Prop vert=mkVar(1) ; . . . Prop piles=mkVar(4) ;

14

16

Uncodagedynamiqueeste´galementpossible booleaneval(boolean[]env) { switch(nature) { caseTRUE:return true; caseFALSE:return fa lse; caseVAR:returnenv[asVar] ; caseNOT:return!left.eval(env) ; caseOR: returnleft.eval(env) ||right.eval(env) ; caseAND: returnleft.eval(env) &&right.eval(env) ; default: throw newError("Prop (eval)") ; } }

Statiqueoudynamique?Icic’estunequestiondegoˆut,pourla suite, je choisis statique.

Lesre`glesdelacr`eche

◮titeiate,ellfuasspleucels.heouetLesjdepeeˆrtevtndsio Prop r1=mkOr(petit,peluche) ;

◮Un jouet est soit, vert, soit grand, soit les deux. Prop r2=mkOr(vert,mkNot(petit)) ;

◮noatccmortqieussets´elecLesjou,seleuelpirsgnpasd´e Prop r3=mkImplies(electrique,piles) ;

◮Il est interdit d’apporter des piles et une peluche. Prop r4=mkNot(mkAnd(piles,peluche)) ;

◮Touts les jouets verts sont des peluches. Prop r5=mkImplies(vert,peluche) ;

17

19

Lesre`glesdelacr`echeII Lesre`glesdelacre`chesontlaconjonctiondescinqre`gles e´le´mentaires. Prop rs=mkAnd(r1,mkAnd(r2,mkAnd(r3,mkAnd(r4,r5)))) ; Lecontrˆole`al’entr´ee Oscararriveavecson(grand)traine´lectriquerougeetsespiles, peutilrentrer ? ◮Le jouet n’est pas petit, n’est pas vert, n’est pas une peluche, este´lectrique,etilyadespiles: boolean[]oscar= {false,false,false,true,true} ;

◮useestinterdit(`acaeuelrtiadnO’csraifieracefemiltqen´vnO delapremi`erer`egle).Lamachinelev´erifieraencoreplus facilement. booleanokOscar=eval(rs,oscar) ;

De´tour:touslesenvironnementspossibles Afficher un environnement (✭jouet✮´ennac,f:elido) static voidprintln(boolean[]env) { for(inti= 0 ;i<env.length;i++) { System.out.print(env[i] ?’T’:’F’) ; // NB: expression conditionnelle✭e1 ? e2 : e3✮ } System.out.println() ; }

Ensuitelesaffichertous,donce´crireunem´ethode static voidprintAll(intn) {. . .}

n qui affiche les 2 environnements possibles.

18

20

Unequestionbienl´egitime

◮edjstliastuuote´es?oraisY

◮Existetil un environnementenv(un✭jouet✮) tel que : eval(rs,env)renvoietrue?

Cettetaˆchesed´ecomposeclairementendeux:

1. Pour chaque jouet possible,. . .

2.´evaluerlesr`egles.

n Pourquoi2? Voiciunerepre´sentationimag´eedelar´ecurrencepratiqu´ee.

P n+1

=

T T

. T F F

. F

P n

P n

Soit :tiasnoiSre´mune´leustoeronirnvsesta`ennmnvariables, alorsonsait´enum´erertouslesenvironnemnts`anvariables.+ 1