Changes between Version 1 and Version 2 of 2010CaoTme4

Timestamp:

Apr 1, 2010, 5:38:06 PM (15 years ago)

Author:

jpc

Comment:

--

2010CaoTme4

@@ -1 +1 @@
 {{{
 #!html
-<h1>TME 4 : Représentation des fonctions Boolèennes : ROBDD</h1>
+<h1>TME 6 : Représentation des fonctions Boolèennes : ROBDD</h1>
 }}}
 [[PageOutline]]
@@ -47 +47 @@
            Bdd*               _high;     // Low cofactor pointer.
            Bdd*               _low;      // High cofactor pointer.
-           unsigned           _stamp;    // Used to flag already reached nodes in the DAG recursive walktrhough.
+           unsigned           _stamp;    // Used to flag already reached nodes in the DAG
+                                         // recursive walktrhough.
   public:                     
     static Bdd*               ConstHigh;
@@ -86 +87 @@
 }}}
 
- * Le constructeur  {{{Bdd::create()}}}, alloue un nouveau  noeud BDD et  l'ajoute dans le
+ * Le constructeur  {{{Bdd::Bdd()}}}, alloue un nouveau  noeud BDD et  l'ajoute dans le
    dictionnaire des noeuds BDD.
 
@@ -147 +148 @@
 
 
+= B) Dictionnaire de BDD =
+
+Comme  il a  été montré  en cours,  une expression  booléenne sous  la forme  canonique de
+Shannon est associée à un et un seul ROBDD. Celui-çi étant entièrement caractérisé par son
+triplet {{{(_index,_high,_low)}}}.  Lorsque la méthode {{{Bdd::create()}}}  est appelée il
+faut qu'elle puisse déterminer rapidement si un ROBDD existe ou non.
+
+Le conteneur  approprié pour ce type  d'opération est la  {{{stl::map<>}}}. La {{{map<>}}}
+associe  une valeur  (le  pointeur sur  le  ROBDD) à  une  clé (le  triplet).  Elle à  les
+propriétés suivantes:
+
+ * Une clé d'une valeur donnée sera  présente en un unique exemplaire dans la {{{map<>}}},
+   et sera associée à une unique valeur.
+
+ * On peut retrouver très efficacement une valeur en fonction d'une clé.
+
+ * N'importe quel  objet (classe) peut  servir de clé  ''sous réserve'' de  disposer d'une
+   fonction  d'ordre.    C'est  à  dire   de  disposer  d'une  surcharge   de  l'operateur
+   ''strictement inférieur''.
+
+La  définition  de  la classe  {{{Bdd}}}  comporte  donc  une classe  imbriquée  {{{Key}}}
+représentant  le triplet  et  proposant une  fonction  d'ordre. La  relation d'ordre  sera
+simplement l'ordre lexicographique du triplet. Soit:
+
+{{{
+if ( lhs->_index != rhs->_index ) return lhs->_index < rhs->_index;
+
+if ( lhs->_high->getIndex() != rhs->_high->getIndex() )
+  return lhs->_high->getIndex() < rhs->_high->getIndex();
+
+return lhs->_low->getIndex() < rhs->_low->getIndex();
+}}}
+
+
+
 = B)  Représentation Graphique =