Planche 1
PC8
Jean-Jacques.Levy@inria.fr
http://www.polytechnique.fr/poly/~levy/
INRIA -- Rocquencourt
tel: 01 39 63 56 89


secrétariat: Catherine Bensoussan
cb@lix.polytechnique.fr
Aile 00, LIX
tel: 34 67

http://w3.edu.polytechnique.fr/informatique/

Planche 2
Plan

  1. Représentation des arbres
  2. Calcul formel
  3. Piles
  4. Arbres de recherche
  5. Arbres équilibrés
  6. Exercices
Planche 3
Arbres en Java

Simple généralisation de la structure de Liste.

class ArbreInt {

  int valeur;
  ArbreInt filsG;
  ArbreInt filsD;

  ArbreInt (int v, ArbreInt a, ArbreInt b) {
     valeur = v; filsG = a; filsD = b;
  }
}
Planche 4
Arbres en Ocaml

Arbres non modifiables:

type 'a arbre = Vide | Noeud of 'a * 'a arbre * 'a arbre;;
Arbres modifiables:

type 'a arbre = Vide | Noeud of 'a noeud

and 'a noeud = {mutable valeur: 'a; 
                mutable filsG: 'a arbre; 
                mutable filsD: 'a arbre} ;;
Planche 5
Représentation des termes

On veut faire du calcul symbolique sur des termes. On représente les termes par des arbres. Par exemple:

class Terme {

  final static int ADD = 0, SUB = 1, MUL = 2, DIV = 3, MINUS = 4, 
                   VAR = 5, CONST = 6;
  int op;
  int valeur; String nom;
  Terme a1, a2, a3;

  Terme (int op, Terme a) {this.op = op; a1 = a; }
  Terme (int op, Terme a, Terme b) {this.op = op; a1 = a; a2 = b; }
  Terme (String s) {op = VAR; nom = s; }
  Terme (int v) {op = CONST; valeur = v; }
}
Planche 6
Exemples de termes 

Terme t = new Terme (MUL, 
             new Terme (ADD, new Terme ("x"), new Terme (1)),
             new Terme (ADD,
                new Terme (MUL, new Terme (3), new Terme ("x")),
                new Terme (2)));


Planche 7
Représentation des termes 

type terme = Add of terme * terme 
           | Sub of terme * terme 
           | Mul of terme * terme
           | Div of terme * terme
           | Minus of terme
           | Var of string
           | Const of int;;

let t = Mul (Add (Var "x", Const 1), 
             Add (Mul (Const 3, Var "x"), Const 2));;
Planche 8
Impression d'un terme

On suit la syntaxe des termes pour imprimer. 

public String toString () { return toStrS (this); }

static String toStrS (Terme t) { switch (t.op) {
  case ADD: return toStrS (t.a1) + "+" + toStrS (t.a2);
  case SUB: return toStrS (t.a1) + "-" + toStrP (t.a2);
  default: return toStrP (t);
  }
}

static String toStrP (Terme t) { switch (t.op) {
  case MUL: return toStrP (t.a1) + "*" + toStrP (t.a2);
  case DIV: return toStrP (t.a1) + "/" + toStrF (t.a2);
  default: return toStrF (t);
  }
}
Planche 9
Impression d'un terme 

static String toStrF (Terme t) { switch (t.op) {
  case MINUS: return "-" + toStrF (t.a1);
  case VAR: return t.nom;
  case CONST: return t.valeur + "";
  default: return "(" + toStrS (t) + ")";
  }
}

... System.out.println (t); ...
Planche 10
Impression d'un terme en ML 

open Printf;;

let imprimer t =
  let rec impS t = match t with
    Add(u,v) -> impS u; printf " + "; impS v
  | Sub(u,v) -> impS u; printf " - "; impP v
  | _ ->  impP t 
  and impP t = match t with
  | Mul(u,v) -> impP u; printf " * "; impP v
  | Div(u,v) -> impP u; printf " / "; impF v
  | _ ->  impF t
  and impF t = match t with
    Minus (u) -> printf "-"; impF u
  | Var (x) -> printf "%s" x
  | Const (n) -> printf "%d" n
  | _ -> printf "("; impS t; printf ")"
in impS t; printf "\n" ;;
Planche 11
Implémentation avec des sous-classes 

class Terme {
  int valeur; String nom;
  Terme a1, a2, a3;
}

class Add extends Terme {  Add (Terme x, Terme y) { a1 = x; a2 = y; } }
class Sub extends Terme {  Sub (Terme x, Terme y) { a1 = x; a2 = y; } }
class Mul extends Terme {  Mul (Terme x, Terme y) { a1 = x; a2 = y; } }
class Div extends Terme {  Div (Terme x, Terme y) { a1 = x; a2 = y; } }
class Minus extends Terme {  Minus (Terme x) { a1 = x; } }
class Var extends Terme {  Var (String s) { nom = s; } }
class Const extends Terme {  Const (int n) { valeur = n; } }

Terme t = new Mul( new Add( new Var ("x"), new Const (1)), 
                   new Add( new Mul( new Const (3), new Var ("x")),
                            new Const (2)));
Planche 12
Implémentation avec des sous-classes -- bis 

public String toString () { return toStrS (this); }

static String toStrS (Terme t) { 
  if (t instanceof Add)
      return toStrS (t.a1) + "+" + toStrS (t.a2);
  else if (t instanceof Sub)
      return toStrS (t.a1) + "-" + toStrP (t.a2);
  else return toStrP (t);
}

static String toStrP (Terme t) { 
  if (t instanceof Mul)
      return toStrP (t.a1) + "*" + toStrP (t.a2);
  else if (t instanceof Div)
      return toStrP (t.a1) + "/" + toStrF (t.a2);
  else return toStrF (t);
}
Planche 13
Implémentation avec des sous-classes -- ter 

static String toStrF (Terme t) { 
  if (t instanceof Minus)
      return "-" + toStrF (t.a1);
  else if (t instanceof Var)
      return t.nom;
  else if (t instanceof Const)
      return t.valeur + "";
  else return "(" + toStrS (t) + ")";
}
Planche 14
Implémentation orientée-objet 

abstract class Terme {
  int valeur; String nom;
  Terme a1, a2, a3;

  public abstract String toString ();
  abstract String toStr (Terme t, int precedence);
  static String norm (int pout, int pin, String s) {
    return (pout <= pin) ? s : "(" + s + ")";
  }
}

class Add extends Terme {  
  Add (Terme x, Terme y) { a1 = x; a2 = y; } 
  public String toString () {return this.toStr(0); }
  String toStr (int p) { return norm (p, 0, a1 + "+" + a2); }
}
Planche 15
Implémentation orientée-objet -- bis 

class Sub extends Terme {  
  Sub (Terme x, Terme y) { a1 = x; a2 = y; } 
  public String toString () {return this.toStr(0); }
  String toStr (int p) {  
    return norm (p, 0, a1 + "-" + a2.toStr(1));
  }
}

class Mul extends Terme {  
  Mul (Terme x, Terme y) { a1 = x; a2 = y; }
  public String toString () {return this.toStr(1); }
  String toStr (int p) {  
    return norm (p, 1,  a1.toStr(1) + "*" + a2.toStr(1));
  }
}
Planche 16
Implémentation orientée-objet -- ter 

class Div extends Terme {  
  Div (Terme x, Terme y) { a1 = x; a2 = y; }
  public String toString () {return this.toStr(1); }
  String toStr (int p) {  
    return norm (p, 1, a1.toStr(1) + "/" + a2.toStr(2));
  }
}

class Minus extends Terme {  
  Minus (Terme x) { a1 = x; }
  public String toString () {return this.toStr(2); }
  String toStr (int p) { return "-" + a2.toStr(2); }
}
Planche 17
Implémentation orientée-objet -- 4 

class Var extends Terme {
  Var (String s) { nom = s; } 
  public String toString () {return this.toStr(2); }
  String toStr (int p) { return nom; }
}

class Const extends Terme {
  Const (int n) { valeur = n; } 
  public String toString () {return this.toStr(2); }
  String toStr (int p) { return valeur + ""; }
}
La programmation procédurale organise le code selon les procédures.

La programmation OO encourage à répartir le code selon les données.

Planche 18
Formes préfixes, infixes ou postfixes

Nous avons vu l'impression d'un terme sous forme infixe. On peut aussi la faire sous forme (polonaise) préfixe (sans les parenthèses)

static String toStrPref (Terme t) {switch (t.op) {
  case ADD: return  "+ " + toStrPref (t.a1) + " " + toStrPref (t.a2);
  case SUB: return  "- " + toStrPref (t.a1) + " " + toStrPref (t.a2);
  case MUL: return  "* " + toStrPref (t.a1) + " " + toStrPref (t.a2);
  case DIV: return  "/ " + toStrPref (t.a1) + " " + toStrPref (t.a2);
  case MINUS: return "--" + toStrPref (t.a1);
  case VAR: return t.nom;
  case CONST: return t.valeur + "";
  default: return "";
  }
}
Planche 19
Forme préfixes, infixes ou postfixes -- 2

Si on veut unifier avec toString(), on peut rendre cette procédure non statique.

String toStrPref () {switch (op) {
  case ADD: return  "+ " + a1.toStrPref () + " " + a2.toStrPref ();
  case SUB: return  "- " + a1.toStrPref () + " " + a2.toStrPref ();
  case MUL: return  "* " + a1.toStrPref () + " " + a2.toStrPref ();
  case DIV: return  "/ " + a1.toStrPref () + " " + a2.toStrPref ();
  case MINUS: return "--" + a1.toStrPref ();
  case VAR: return nom;
  case CONST: return valeur + "";
  default: return "";
  }
}
Planche 20
Forme préfixes, infixes ou postfixes -- 3

Un simple changement d'ordre de parcours de la récursion dans la procédure donne la forme (polonaise) postfixe

String toStrPost () {switch (op) {
  case ADD: return  a1.toStrPost () + " " + a2.toStrPost () + " +";
  case SUB: return  a1.toStrPost () + " " + a2.toStrPost () + " -";
  case MUL: return  a1.toStrPost () + " " + a2.toStrPost () + " *";
  case DIV: return  a1.toStrPost () + " " + a2.toStrPost () + " /";
  case MINUS: return a1.toStrPost () + "--";
  case VAR: return nom;
  case CONST: return valeur + "";
  default: return "";
  }
}
Donc l'impression préfixe, infixe ou postfixe correspond simplement à des parcours d'arbres différents.

Planche 21
Evaluation des expressions arithmétiques

On donne une a-liste (liste d'association) pour associer une valeur à chaque variable.

static int eval (Terme t, AListe env) {switch (t.op) {
  case ADD: return eval (t.a1, env) + eval (t.a2, env); 
  case SUB: return eval (t.a1, env) - eval (t.a2, env); 
  case MUL: return eval (t.a1, env) * eval (t.a2, env); 
  case DIV: return eval (t.a1, env) / eval (t.a2, env); 
  case MINUS: return - eval (t.a1, env);
  case VAR: return assoc (t.nom, env);
  case CONST: return t.valeur;
  default: return 0;
  }
Planche 22
Dérivation formelle 

static Terme der (Terme t, Var x) {
  if (t instanceof Const)
    return new Const (0);
  else if (t instanceof Add)
    return new Add (der(t.a1, x), der(t.a2, x));
  else if (t instanceof Mul)
    return new Add (new Mul(t.a1, der(t.a2, x)), 
                    new Mul(der(t.a1, x), t.a2));
  else if (t instanceof Div)
    return new Div(new Sub (new Mul(der(t.a1,x), t.a2), 
                            new Mul(t.a1, der(t.a2, x))),
                   new Mul (t.a2, t.a2));
  else if (t instanceof Var)
    return new Const (x.equals(t.nom) ? 1 : 0);
  else if (t instanceof Minus)
    return new Minus (der(t.a1, x));
}
Planche 23
Dérivation formelle en ML 

let rec der t x= match t with
  | Add (t1, t2) ->  Add (der t1 x, der t2 x)
  | Mul (t1, t2) -> 
       Add (Mul (t1, der t2 x), Mul (der t1 x, t2))
  | Div (t1, t2) -> Div 
       (Sub (Mul (der t1 x, t2), Mul (t1, der t2 x)),
       Mul (t2, t2))
  | Sub (t1, t2) -> Sub (der t1 x, der t2 x)
  | Var (y) -> if x = y then Const (1) else Const (0)
  | Const (x) -> Const (0)
  | Minus (t1) -> Minus (der t1 x)
;;
Le filtrage simplifie bien l'affaire. ML est adapté au calcul symbolique. Tous les systèmes de démonstration automatiques au monde (HOL, PVS, Coq, LF, Elf) sont maintenant écrits en (O)Caml.

Planche 24
Simplifications -- Réécritures

Le résultat est peu présentable, car il faut faire des simplifications et ainsi normaliser le résultat. C'est ce que savent très bien faire des systèmes de calcul formel comme Axiom, Matematica ou Maple.

Il faut donc appliquer des règles telles que:
0 + x ® x
x + 0 ® x
0 × x ® 0
x × 0 ® 0
1 × x ® x
x × 1 ® x
x × (y + z) ® x × y + x × z
(x + y) × z ® x × z + y × z

Planche 25
Théories complètes

On peut résoudre des petits problèmes équationnels. Par exemple, la théorie des groupes libres est donnée par les 10 règles suivantes:
(x + y) + z ® x + (y + z)     (1)
0 + x ® x     (2)
(- x) + x ® 0     (3)
(- x) + (x + y) ® y     (4)
- 0 ® 0     (5)
x + 0 ® x     (6)
- (- x) ® x     (7)
x + (- x) ® 0     (8)
x + ((- x) + y) ® y     (9)
- (x + y) ® (- y) + (- x)     (10)

Toute égalité est prouvée par la mise en forme normale selon les règles de réécritures précédentes. (La méthode de complétion de Knuth et Bendix permet d'obtenir systématiquement ces règles.)

Planche 26
Ordres de parcours d'un arbre

Ce sont des manières de numéroter les noeuds (et feuilles) d'un arbres.

Remarque: nous avons vu implicitement ces parcours lors de l'impression des termes.

Planche 27
Pile

Une pile correspond à la stratégie LIFO (Last In, First Out). On peut la représenter par un tableau ou une liste (cf poly chapitre 3).

class Pile {
  final static int maxP = 100;
  int          hauteur ;
  Element      contenu[];

  Pile ()  {hauteur = 0; contenu = new Element[maxP]; }

  static void empiler (Element x, Pile p) throws ExceptionPilePleine {
    if (p.hauteur == maxP)
         throw new ExceptionPilePleine();
    p.contenu[p.hauteur++] = x;
  }
Planche 28
Pile -- 2 

  static int depiler (Pile p) throws ExceptionPileVide {  {
    if (p.hauteur == 0) 
        throw new ExceptionPile ("vide");
    int res = p.contenu [p.hauteur - 1];
    -- p.hauteur;
    return res;
  }
}
Tout programme récursif peut s'écrire itérativement avec une pile (Randell et Russel, 1960, ont ainsi inventé le concept de compilateur)

Pour l'évaluation des expressions arithmétiques, on peut donc la faire avec une pile, en empilant les valeurs et opérateurs rencontrées et en faisant des opérations entre sommet et sous-sommet de la pile.

Planche 29
Arbres de recherche

On revient à un problème standard d'algorithmique: comment faire de la recherche en table dynamique? Ie sans aucune limitation de taille.

Une technique est de faire des arbres de recherche. Les noeuds d'un tel arbre sont étiquetées par des clés (ici des entiers) de telle manière que tout noeud est supérieur aux noeuds de son sous-arbre de gauche, mais inférieur aux noeuds de son sous-arbre de gauche.

Autrement dit, l'ordre des valeurs stockées sur les noeuds respecte l'ordre infixe.

Planche 30
Recherche/insertion dans un arbre de recherche 

static Arbre recherche (int x, Arbre a) {
  if (a == null)  return null;
  else if (x == a.cle)  return a;
  else if (x < a.cle)  return recherche (a.filsG);
  else  return recherche (a.filsD);
}
static Arbre ajouter (int x, Arbre a) {
  if (a == null)  return new Arbre (x, null, null);
  else if (x == a.cle)  return a;
  else if (x < a.cle)  return new Arbre (ajouter (a.filsG), a.filsD);
  else  return new Arbre (a.filsG, ajouter (a.filsD));
}
Complexité?

Planche 31
Recherche/insertion dans un arbre de recherche en ML 

let rec recherche x a =
 match a with
 | Arbre_vide -> Arbre_vide
 | Noeud (g, y, d) -> 
    if x = y then a else
    if x < y then recherche x g
    else recherche x d;;

let rec ajouter x a = 
 match a with
   Arbre_vide -> Noeud (Arbre_vide, x, Arbre_vide)
 | Noeud (g, y, d) ->
    if x < y then Noeud (ajouter x g, y, d)
    else Noeud (g, y, ajouter x d);;
Planche 32
Arbres équilibrés

Pour garder une bonne efficacité, on essaie de garder les arbres équilibrés.

Un arbre est parfaitement équilibré ssi pour tout noeud les hauteurs des fils gauche et droit sont égales. Difficile à réaliser.

Un arbre est équilibré (arbre AVL) ssi pour tout noeud les hauteurs des fils gauche et droit ne diffèrent pas de plus que 1.

Pour maintenir un arbre équilibré, on est amené à faire des rotations lors de l'insertion d'un nouvel élément.

             A           rotG             B
            / \           -->            / \
           a   B                        A   c
              / \        <--           / \
             b   c       rotD         a   b
(cf polycopié)

Planche 33
Arbres 2-3-4

Dans un arbre AVL, il faut stocker les hauteurs ou les différences de hauteurs entre fils droit et gauche pour tout noeud (au moins 2 bits). La programmation n'est pas simple.

Si on donne un peu de flexibilité aux noeuds, on évite les rotations. Chaque noeud peut avoir 2, 3 ou 4 fils, l'arbre est toujours ordonné selon le parcours infixe. On n'insére un nouveau noeud que dans un arbre dont le père n'a pas 4 noeuds. Au cours de la recherche, on éclate tous les 4-noeuds

               A                        A C
             /  \           -->        / | \
            a  B C D                  a  B   D
              / / \ \                   /|   |\
             b  c  d e                 b c   d e

              A B                       A B D
             / | \          -->        / / \ \
            a  b  C D E               a b   C  E
                 / / \ \                   /|  |\
                c d   e f                 c d  e f
Planche 34
Arbres rouges-noirs, B-trees

Les arbres rouge-noir (ou bicolores) représentent les arbres 2-3-4 par des arbres binaires dont on colorie les arcs en rouge ou noir. La couleur rouge veut dire "arc transparent". Autrement dit, deux noeuds reliés par du rouge forment un même noeud dans l'arbre 2-3-4. Ainsi, on représente les 4 noeuds par:

     A B C    ==     B             A B   ==    B     ou   A
    / / \ \         / \           / | \       / \        / \
   a b   c d       A   C         a  b  c     A   c      a   B
                  /|   |\                   / \            / \
                 c d   e f                 a   b          b   c
L'éclatement des arbres 2-3-4 correspond à de simples changements de couleur et à quelques rotations.

Les B-trees sont une version des arbres 2-3-4 ou un noeud peut varier entre 2 et 2k noeuds. Ils interviennent pour faire des index sur les fichiers. Par exemple, dans le système de fichiers de MacOS, pour accéder à un fichier et à sa description dans le système de fenêtres.

Planche 35
Exercices en TD

This document was translated from LATEX by HEVEA.