Changes between Version 4 and Version 5 of 2010CaoTme4
- Timestamp:
- Apr 1, 2010, 6:47:08 PM (15 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
2010CaoTme4
v4 v5 22 22 23 23 [[Image(BDD-1.png)]] 24 24 25 25 26 = A) Structures de données et fonctions de base = … … 184 185 185 186 186 = B) Représentation Graphique =187 = C) Représentation Graphique = 187 188 188 189 Soit la fonction Booléenne F(a,b,c,d,e), définie par l’expression suivante … … 196 197 E0 = OR( AND (NOT (a) OR (b c NOT (d) e)) c) 197 198 198 ''' B.1''' En utilisant la décomposition de Shannon, représentez graphiquement le graphe199 '''C.1''' En utilisant la décomposition de Shannon, représentez graphiquement le graphe 199 200 ROBDD associé à la fonction F(a,b,c,d,e) pour l’ordre a > b > c > d > e , puis pour 200 201 l’ordre e > d > c > b > a. 201 202 202 ''' B.2''' Précisez, pour chaque noeud du ROBDD ainsi construit, quelle est la fonction203 '''C.2''' Précisez, pour chaque noeud du ROBDD ainsi construit, quelle est la fonction 203 204 Booléenne représentée par ce noeud. 204 205 205 206 206 = C) Méthodes Bdd::neg() et Bdd::apply() =207 = D) Méthodes Bdd::neg() et Bdd::apply() = 207 208 208 209 Les méthodes {{{Bdd::apply()}}} et {{{bdd::neg()}}} ont été présentées en cours. Vous 209 210 trouverez le code de ces fonctions dans le fichier {{{Bdd.cpp}}}. 210 211 211 ''' C.1''' Soient F1 et F2 deux fonctions Booléennes, et les fonctions F1H, F1L, F2H, F2L212 '''D.1''' Soient F1 et F2 deux fonctions Booléennes, et les fonctions F1H, F1L, F2H, F2L 212 213 définies par la décomposition de Shannon suivant la variable x : 213 214 … … 220 221 l’une des deux fonctions F1 ou F2 est égale à une des deux fonctions constantes 0 ou 1. 221 222 222 ''' C.2''' Soit la fonction F, définie par l’expression E1 = a . (b + c) Représentez223 '''D.2''' Soit la fonction F, définie par l’expression E1 = a . (b + c) Représentez 223 224 graphiquement le ROBDD représentant la fonction F, pour l’ordre des variables a > b > 224 225 c. On appelle p0, p1, p2, p3, p4 les pointeurs sur les 5 noeuds BDD contenus dans ce … … 238 239 239 240 240 = D) Méthode Bdd::fromEbm() =241 = E) Méthode Bdd::fromEbm() = 241 242 242 243 On cherche à écrire la méthode {{{Bdd::fromEbm()}}}, qui construit automatiquement le … … 248 249 possible de construire le graphe ROBDD en utilisant uniquement ces deux fonctions. 249 250 250 ''' D.1''' Décrire en français, l’algorithme de cette méthode {{{Bdd::fromEbm()}}} dans le251 '''E.1''' Décrire en français, l’algorithme de cette méthode {{{Bdd::fromEbm()}}} dans le 251 252 cas particulier où tous les opérandes AND, OR ou XOR présents dans l’arbre ABL n’ont que 252 253 deux opérandes. On traite successivement les trois cas suivants: … … 260 261 est l'un des trois opérateurs OR, AND ou XOR. 261 262 262 ''' D.2''' Ecrire en langage C++ la méthode {{{Bdd::fromEbm()}}} dans le cas particulier de263 '''E.2''' Ecrire en langage C++ la méthode {{{Bdd::fromEbm()}}} dans le cas particulier de 263 264 la question précédente. Pour valider cette fonction, on écrira un programme main(), qui 264 265 effectue successivement les opérations suivantes : … … 275 276 * Affichage du graphe ROBDD ainsi construit, en utilisant la fonction Bdd::display(). 276 277 277 ''' D.3''' Comment faut-il modifier la fonction {{{Bdd::fromEbm()}}}, pour traiter le cas278 '''E.3''' Comment faut-il modifier la fonction {{{Bdd::fromEbm()}}}, pour traiter le cas 278 279 général, où les opérateurs OR, AND et XOR peuvent avoir une arité quelconque? Modifier le 279 280 code de la fonction, et validez ces modifications sur l’exemple de l’expression Booléenne … … 281 282 282 283 283 = E) Méthode Bdd::satisfy() =284 = F) Méthode Bdd::satisfy() = 284 285 285 286 Soit une fonction Booléenne quelconque F(x1, x2, x3, ... xn), dépendant de n … … 302 303 représentant F retourne un pointeur sur le noeud représentant G. 303 304 304 ''' E.1''' La décomposition de Shannon de la fonction F suivant la variable x d’index le305 '''F.1''' La décomposition de Shannon de la fonction F suivant la variable x d’index le 305 306 plus élévé définit les cofacteurs FH et FL : F = x . FH + x’ . FL Pour alléger les 306 307 notations, on note sat(F) la fonction Booléenne construite par la méthode … … 310 311 ou FL sont égales à 0 ou 1. 311 312 312 ''' E.2''' Ecrire, en langage C++, le code de la méthode {{{Bdd::satisfy()}}}, et313 '''F.2''' Ecrire, en langage C++, le code de la méthode {{{Bdd::satisfy()}}}, et 313 314 appliquez-la sur la fonction Booléenne F définie dans la partie, en modifiant le programme 314 315 main de la fonction précédente. 315 316 316 317 317 = F) Méthode Bdd::toEbm() =318 = G) Méthode Bdd::toEbm() = 318 319 319 320 On souhaite pour finir écrire la méthode Bdd::toEbm(), qui construit automatiquement une … … 328 329 (cofacteurs de Shannon). 329 330 330 ''' F.1''' Quelle expression Booléenne dépendant de x, FH et FL peut-on associer à la331 '''G.1''' Quelle expression Booléenne dépendant de x, FH et FL peut-on associer à la 331 332 fonction F dans le cas général ou FH et FL sont quelconques ? (aucune des deux fonctions 332 333 FH ou FL n’est égale à 0 ou à 1) 333 334 334 ''' F.2''' Comment cette expression Booléenne se simplifie-t-elle lorsque l’une des deux335 '''G.2''' Comment cette expression Booléenne se simplifie-t-elle lorsque l’une des deux 335 336 fonctions FH ou FL est égale à 0 ou à 1. Etudier un par un les 4 cas particuliers. 336 337 337 ''' F.3''' En utilisant les résultats des questions précédentes, proposez un algorithme.338 '''G.3''' En utilisant les résultats des questions précédentes, proposez un algorithme.
