Changes between Version 2 and Version 3 of CaoCourseTme6
- Timestamp:
- Mar 7, 2007, 7:01:30 PM (20 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
CaoCourseTme6
v2 v3 10 10 Les ROBDD (Reduced Ordered Binary Decision Diagram) sont utilisés pour représenter de façon compacte une ou plusieurs fonctions Booléennes, partageant le même support (c’est à dire dépendant d’un même ensemble de variables Booléennes). Pour un ordre donné des variables constituant le support, cette représentation est canonique : A chaque fonction Booléenne est associé un unique graphe orienté acyclique (DAG). Le graphe étant acyclique, chaque noeud BDD définit un sous-graphe dont il est la racine. Par conséquent, chaque noeud BDD correspond à une fonction Booléenne particulière. On utilise le fait que les variables Booléennes constituant le support sont ordonnées pour identifier ces variables par leur index. 11 11 12 = A .Structures de données et fonctions de base =12 = A) Structures de données et fonctions de base = 13 13 14 14 La structure C permettant de représenter un noeud du graphe ROBDD est définie de la façon suivante : … … 52 52 }}} 53 53 54 = B .Représentation Graphique =54 = B) Représentation Graphique = 55 55 56 56 Soit la fonction Booléenne F(a,b,c,d,e), définie par l’expression suivante … … 68 68 '''B.2''' Précisez, pour chaque noeud du ROBDD ainsi construit, quelle est la fonction Booléenne représentée par ce noeud. 69 69 70 = C .Fonctions not_bdd() et apply_bdd() =70 = C) Fonctions not_bdd() et apply_bdd() = 71 71 72 72 Les fonctions apply_bdd() et not_bdd() ont été présentées en cours. Vous trouverez le code de ces fonctions dans le fichier bdd.c. … … 87 87 Représentez graphiquement l’arbre d’appels des fonctions lorsqu’on appelle la fonction not_bdd() avec pour argument le pointeur p4. Quel est le nombre maximum d’appels de fonctions empilés sur la pile d’exécution? Combien de noeuds BDD vont être créés par la fonction create_bdd(), si on suppose que la structure de données ne contient initialement que les 5 noeuds pointés par p0, p1, p2, p3, et p4 au moment de l’appel de la fonction not_bdd(p4)? 88 88 89 = D .Fonction abl2bdd() =89 = D) Fonction abl2bdd() = 90 90 91 91 On cherche à écrire la fonction abl2bdd(), qui construit automatiquement le graphe ROBDD représentant une fonction Booléenne F, à partir d’un arbre ABL représentant une expression Booléenne particulière de cette fonction F. … … 108 108 Modifier le code de la fonction, et validez ces modifications sur l’exemple de l’expression Booléenne E0, ou sur des expressions encore plus complexes. 109 109 110 = E .Fonction satisfybdd() =110 = E) Fonction satisfybdd() = 111 111 112 112 Soit une fonction Booléenne quelconque F(x1, x2, x3, ... xn), dépendant de n variables. Soit la fonction Booléenne G, définie comme un produit (opérateur AND) d’un nombre queconque de variables xi (directes ou complémentées). On dit que G “satisfait” F sion a la relation G => F. (Autrement dit, si G = 1, alors F = 1). Remarquez que la condition G = 1 impose la valeur de toutes les variables appartenant au support de G (les variables directes doivent prendre la valeur 1, et les variables complémentées doivent prendre la valeur 0). Pour une fonction F donnée, il existe évidemment plusieurs … … 131 131 '''E.2''' Ecrire, en langage C, le code de la fonction satisfy_bdd(), et appliquez-la sur la fonction Booléenne F définie dans la partie, en modifiant le programme main de la fonction précédente. 132 132 133 = F .Fonction bdd2abl() =133 = F) Fonction bdd2abl() = 134 134 135 135 On souhaite pour finir écrire la fonction bdd2abl(), qui construit automatiquement un arbre ABL représentant une expression Booléenne multi-niveaux, à partir d'un ROBDD représentant une fonction Booléenne.
