Planche : 1


Deux exemples d’arbres

Planche : 2


Un grand classique

Une expression booléenne e (ou proposition) est :

Note :


Planche : 3


La classe des propositions

Selon le principe d’un champ « nature ».

class Prop {
  final static int FALSE=0, TRUE=1, VAR=2, NOT=3, OR=4, AND=5 ;
  int nature ; int asVar ; Prop leftright ;

  private Prop (int nature) { this.nature = nature ; }

  private Prop (int natureint asVar) {
    this.nature = nature ; this.asVar = asVar ;
  }

  private Prop (int natureProp left) {
    this.nature = nature ; this.left = left ;
  }

  private Prop (int natureProp leftProp right) {
    this.nature = nature ; this.left = left ; this.right = right ;
  }}

Planche : 4


Construction des termes

Il devient hasardeux de se fier aux constructeurs. Des détails, liés à la réalisation concrète prennent trop d’importance.

On utilisera plutôt des méthodes statiques bien nommées.

  static Prop mkTrue() { return new Prop(TRUE) ; }

  static Prop mkVar(int no) { return new Prop(VARno) ; }

  static Prop mkNot(Prop e) { return new Prop(NOTe) ; }

  static Prop mkAnd(Prop e1Prop e2) {
    return new Prop(ANDe1e2) ;
  }
  …

C’est la technique dite factory.


Planche : 5


Bonus

Une certaine déconnexion entre



On peut d’alleurs exprimer d’autres connecteurs logiques, sans changer les cellules d’arbre, par ex.

  static Prop mkImplies (Prop e1Prop e2) {
    return mkOr(mkNot(e1), e2) ;
  }

Planche : 6


Affichage

Comme d’habitude, redéfinir toString.

  public String toString() {
    switch (nature) {
    case TRUEreturn "true" ;
    case FALSEreturn "false" ;
    case VARreturn "x" + asVar ;
    case NOTreturn  "!(" + left + ")" ;
    case ORreturn  "(" + left + " || " + right + ")" ;
    case ANDreturn  "(" + left + " && " + right + ")" ;
    defaultthrow new Error("Prop (toString)") ;
    }
  }

Bénéfice : System.out.println(e) fonctionne.

Parcours ? Infixe en quelque sorte.


Planche : 7


Fonctionnement

Planche : 8


Coût de toString()

Considérer la suite d’expressions

E0 = x0,      Ek+1 = xk+1 ∨ Ek

Planche : 9


toString « linéaire »

Avec le StringBuilder et sa méthode append(String s), qui ajoute la chaîne s à la fin du StringBuilder, pour un coût proportionnel à s.length().

 private void inStringBuilder(StringBuilder r) {
    switch (nature) {
    case TRUE:
      r.append("true") ; break ;
    case FALSE:
      r.append("false") ; break ;
    case VAR:
      r.append("x" + asVar) ; break ;
    case NOT:
      r.append("!(") ;
      left.inStringBuilder(r) ;
      r.append(")") ;
      break ;
  …

Planche : 10


toString « linéaire » II
    …
    case AND:
      r.append("(") ;
      left.inStringBuilder(r) ;
      r.append(" && ") ;
      right.inStringBuilder(r) ;
      r.append(")") ;
      break ;
    }
  }

  public String toString() {
    StringBuilder r = new StringBuilder () ;
    inStringBuilder(r) ;
    return r.toString() ;
  }
}

Planche : 11


Évaluation des propositions

Les règles sont normalement bien connues :

e¬(e
FT
TF
    
e1e2(e1 ∨ e2)(e1 ∧ e2
FFFF 
FTTF  
TFTF  
TTTT 

L’évaluation se fait respectivement à un environnement (une table d’associations : xib).

Les associations ont été vues lors de l’amphi 04. Ici on peut utiliser un tableau directement (variables indicées).

static boolean eval(Prop eboolean [] env) { … }

Planche : 12


Évaluation
  static boolean eval(Prop eboolean [] env) {
    switch (e.nature) {
    case TRUEreturn true ;
    case FALSEreturn false ;
    case VARreturn env[e.asVar] ;
    case NOTreturn !eval(e.leftenv) ;
    case OR:
      return eval(e.leftenv) ||  eval(e.rightenv) ;
    case AND:
      return eval(e.leftenv) &&  eval(e.rightenv) ;
    default:
      throw new Error("Prop (eval)") ;
    }
  }

Planche : 13


Un codage dynamique est également possible
  boolean eval(boolean [] env) {
    switch (nature) {
    case TRUEreturn true ;
    case FALSEreturn false ;
    case VARreturn env[asVar] ;
    case NOTreturn ! left.eval(env) ;
    case OR:
      return left.eval(env) ||  right.eval(env) ;
    case AND:
      return left.eval(env) &&  right.eval(env) ;
    default:
      throw new Error("Prop (eval)") ;
    }
  }

Statique ou dynamique ? Ici c’est une question de goût, pour la suite, je choisis statique.


Planche : 14


Application du calcul des propositions

La direction d’une crèche souhaite réglementer les jouets apportés par les enfants.

Les jouets sont décrits selon cinq critères : petit/grand, vert/pas vert, peluche/pas peluche, électrique/pas électrique, avec piles/sans piles.

C’est à dire, nous avons cinq variables booléennes.

  Prop petit = mkVar(0) ;
  Prop vert = mkVar(1) ;
  …
  Prop piles = mkVar(4) ;

Planche : 15


Les règles de la crèche

Planche : 16


Les règles de la crèche II

Les règles de la crèche sont la conjonction des cinq règles élémentaires.

  Prop rs = mkAnd(r1mkAnd(r2mkAnd(r3mkAnd(r4r5)))) ;
Le contrôle à l’entrée

Oscar arrive avec son (grand) train électrique rouge et ses piles, peut-il-rentrer ?


Planche : 17


Une question bien légitime



Cette tâche se décompose clairement en deux :

  1. Pour chaque jouet possible,…
  2. évaluer les règles.

Planche : 18


Détour : tous les environnements possibles

Afficher un environnement (« jouet ») donné, facile :

static void println(boolean [] env) {
  for (int i = 0 ; i < env.length ; i++) {
    System.out.print(env[i] ? 'T' : 'F') ;
    // NB: expression conditionnelle « e1 ? e2 : e3 »
  }
  System.out.println() ;
}

Ensuite les afficher tous, donc écrire une méthode

static void printAll(int n) { … }

qui affiche les 2n environnements possibles.


Planche : 19


Pourquoi 2n ?

Voici une représentation imagée de la récurrence pratiquée.

Pn+1    =   
T
T
T
  Pn    
F
F
F
  Pn    

Soit : Si on sait énumérer tous les environnemnts à n variables, alors on sait énumérer tous les environnemnts à n+1 variables.


Planche : 20


D’énumérer à afficher

Nous pourrions construire une grosse matrice Pn.

static boolean [] [] allEnv(int n) {
   boolean [] [] r =
     new boolean [1 << n][n] ; // Decalage à gauche ∼ × 2n.
   if (n == 0) { 
     return r ; // En effet : { {} } (une ligne vide)
   } else { 
     boolean [] [] t = allEnv(n-1) ;
     int kmax = t.length ;
     for (int k = 0 ; k < kmax ; k++) {
        r[k][0] = true ; r[k+kmax][0] = false ;
        for (int i = 0 ; i < n-1 ; i++)
          r[k][i+1] = r[k+kmax][i+1] = t[k][i] ;
     }
     return r ;
   }}

Puis l’afficher ligne par ligne, mais… gaspillage de mémoire.


Planche : 21


La bonne idée

Pas besoin de construire tous les environnements possibles, juste pour les afficher.

static void printAll(int n) { printAll(0, new boolean [n]) ; }

static void printAll(int vboolean [] env) {
  if (v >= env.length) {
    println(env) ;
  } else {
     env[v] = true ;  printAll(v+1, env) ;
     env[v] = false ; printAll(v+1, env) ;
  }
}

Note : Mission de printAll(venv) : afficher tous les environnements (de taille n = env.length) qui commencent par b0b1bv−1 donnés.


Planche : 22


Afficher tous les jouets autorisés

Comme l’affichage de tous les environements, avec une vérification supplémentaire.

static void printAllowed(Prop rsint vboolean [] env) {
  if (v >= env.length) {
     if (eval(rsenv)) println(env) ;
  } else {
     env[v] = true ;  printAllowed(rsv+1, env) ;
     env[v] = false ; printAllowed(rsv+1, env) ;
  }
}

static void printAllowed(Prop rsint n) {
   printAllowed(rs, 0, new boolean [n]) ;
}

Accessoirement Sont autorisés : TTTFF FTTFF FFTFF, par ex. grand, vert, peluche, pas électrique et sans piles.


Planche : 23


Existe-t-il au moins un jouet autorisé ?

Pour tous les environnements, on évalue rs, jusqu’à trouver true.

static boolean satisfiable(Prop rsint vboolean [] env) {
  if (v >= env.length) {
     return eval(rsenv) ;
  } else {
     env[v] = true ;
     if (satisfiable(rsv+1, env)) return true ;
     env[v] = false ;
     return satisfiable(rsv+1, env) ;
  }
}

Remarquer Le parcours interrompu par une évaluation positive.


Planche : 24


Culture

Planche : 25


Un usage géométrique des arbres

Une vision hiérarchique des images (carrées). Une image est :


Planche : 26


Exemple

Planche : 27


Exemple en couleurs, une image

Planche : 28


Une échelle de couleurs

Notre image contient peu de couleurs, chaque couleur est en fait une valeur (ici de 0 à 31).

On rencontre souvent ce style d’images qui rendent compte de phénomènes physiques ou mathématiques.


Planche : 29


Exemple en couleurs, le quadtree

Planche : 30


Exemple en couleurs, un peu des deux

Planche : 31


Type des quadtrees
class Quad {
  int nature ;
  final static int LEAF=0, NODE=1 ;

  int color ; // Les feuilles
  Quad (int color) {
    this.nature = LEAF ; this.color = color ;
  }

  Quad swnwnese ; // Les noeuds internes
  Quad(Quad swQuad nwQuad neQuad se) {
    this.nature = NODE ;
    this.sw = sw ; this.nw = nw ;
    this.ne = ne ; this.se = se ;
  }
}

Implicitement Un Quad est une image (carrée).


Planche : 32


Deux représentations possibles de nos images

Rappelons que ici une couleur est un entier entre 0 et 31.

Ces deux structures de données sont deux réalisations machine de la même chose (l’image).



Remarque importante

Planche : 33


Exemple d’opération : trouver la couleur

Planche : 34


Trouver le bon quadrant

Planche : 35


Trouver la couleur d’un point dans le quadtree
static int getColor(Quad qint sizeint iint j) {
  if (q.nature == LEAF) {
    return q.color ;
  } else {
     int t = size/2 ;
     if (i < t) { // A l'ouest.
       if (j < t)
          return getColor(q.swtij) ;
        else
          return getColor(q.nwtij-t) ;
     } else { // A l'est.
       if (j < t)
          return getColor(q.seti-tj) ;
        else
          return getColor(q.neti-tj-t) ;
     }
  }
}

Planche : 36


Code itératif
static int getColor(Quad qint sizeint iint j) {
  while (q.nature == NODE) {
     size /= 2 ; // pour size = size / 2 ;
     if (i < size) { // A l'ouest.
       if (j < size) {
          q = q.nw ;
        } else {
          q = q.sw ; j -= size ;
        }
     } else { // A l'est.
       i -= size ;
       if (j < size) {
         q = q.ne ;
       } else {
         q = q.se ; j -= size ;
       }
    }
  }
  return q.color ;
}

Planche : 37


Intérêt du quadtree

Planche : 38


Autre intérêt

Certaines opérations sont plus faciles/naturelles/voire efficaces que sur les tableaux de couleurs.


Planche : 39


Exemple : la rotation

La rotation positive d’un quart de tour :

NE → NW → SW → SE → NE

C’est à dire NE (tourné d’un quart de tour) devient NW, etc.


Planche : 40


Programmation de la rotation
  static Quad rot(Quad q) {
    if (q.nature == LEAF) {
      return q ;
    } else {
      Quad sw = rot(q.sw) ;
      Quad nw = rot(q.nw) ;
      Quad ne = rot(q.ne) ;
      Quad se = rot(q.se) ;
      return new Quad (nwnesesw) ;
    }
  }

Planche : 41


Autre intérêt

L’affichage : si afficher un carré de couleur ne dépend pas de la taille du carré.

Hypothèse réaliste

Dès lors le quadtree est intéressant, car il minimise les opérations de dessin.


Planche : 42


Dessin traditionnel
static void draw(int [] [] img) {
  for (int i = 0 ; i < SIZE ; i++) {
    for (int j = 0 ; j < SIZE ; j++) {
      fillSquare(i,j,1,img[i][j]) ;
      // Remplir un carré avec une couleur
      // arguments (i, j, t, c)
      //   * (i,j) -> position coin en bas à gauche
      //   * t -> côté du carré
      //   * c -> couleur
    }
  }
}

Planche : 43


Dessin du Quadtree

On considère qu’un quatree représente un carré, de coordonnées (i,j) et de taille sz.

static void draw(Quad q) { draw(q, 0, 0, SIZE) ; }

static void draw(Quad qint iint jint sz) {
    if (q.nature == LEAF) {
      fillSquare(ijszq.color) ;
    } else {
      int nsz = sz/2 ;
      draw(q.swijnsz) ;
      draw(q.nwij+nsznsz) ;
      draw(q.nei+nszj+nsznsz) ;
      draw(q.sei+nszjnsz) ;
    }
  }

Planche : 44


Fabrication du quadtree

Astuce : éviter les divisions inutiles.



static boolean monochrome(Quad q1Quad q2Quad q3Quad q4) {
 return
   (q1.nature == LEAF && q2.nature == LEAF &&
    q3.nature == LEAF && q4.nature == LEAF) &&
   (q1.color == q2.color && q2.color == q3.color &&
    q3.color == q4.color) ;
  }

Planche : 45


Fabrication du quadtree

À partir de l’image « standard » int [] [] t, supposée carrée et de taille 2n.

C’est en quelque sorte l’opération inverse du dessin.

static Quad toQuad(int [] [] t) {
  return toQuad(t, 0, 0, t.length) ;
}

Planche : 46


Programmation

Traduire la sous-image <i,j,sz> en quadtree.

  static Quad toQuad(int [] [] tint iint jint sz) {
    if (sz == 1) {
      return new Quad(t[i][j]) ;
    } else {
      int nsz = sz/2 ;
      Quad sw = toQuad(tijnsz) ;
      Quad nw = toQuad(tij+nsznsz) ;
      Quad ne = toQuad(ti+nszj+nsznsz) ;
      Quad se = toQuad(ti+nszjnsz) ;
      if (monochrome(swnwnese)) {
        return sw ;
      } else {
        return new Quad (swnwnese) ;
      }
    }
  }

Ce document a été traduit de LATEX par HEVEA