Changes between Version 6 and Version 7 of CaoCourseTme5


Ignore:
Timestamp:
Mar 7, 2007, 7:10:52 PM (18 years ago)
Author:
alain
Comment:

--

Legend:

Unmodified
Added
Removed
Modified

  • CaoCourseTme5

    v6 v7  
    1717 * soit une autre expression Booléenne.
    1818
    19 = A. Structures de données et fonctions de base =
     19= A) Structures de données et fonctions de base =
    2020
    2121La structure C permettant de représenter une variable Booléenne possède trois champs : Le champs NAME représente le nom de la variable, le champs INDEX définit un numéro, et le champs VALUE représente la valeur logique de la variable.
    … …  
    6464}}}
    6565
    66 = B. Représentation Graphique =
     66= B) Représentation Graphique =
    6767
    6868Soit l’expression  {{{E0 = (a’ . (b + c + d’) . e) + c}}}       
    … …  
    7070La notation a’ signifie NOT(a)
    7171
    72  *  '''B.1''': Re-écrire cette expression sous une forme préfixée, et représentez graphiquement l’arbre ABL  correspondant à l’expression E0.
     72 *  '''B.1)''' Re-écrire cette expression sous une forme préfixée, et représentez graphiquement l’arbre ABL  correspondant à l’expression E0.
    7373
    74 = C. Fonction d’affichage =
     74= C) Fonction d’affichage =
    7575
    7676Récupérez l'archive [attachment:tme5.tar.gz TME5]. En la décompressant, vous obtiendrez un répertoire {{{tme5}}} contenant les fichiers dont vous avez besoin pour ce TME, et en particulier un {{{Makefile}}} et un fichier {{{main.c}}} que vous devrez complêter:
    7777
    78  *  '''C.1''': Ecrire en langage C la fonction récursive display_abl() présentée en cours. cette fonction prend en entrée un pointeur p sur un bipointeur représentant la racine d'un arbre ABL, et affiche sur le terminal standard l’expression Booléenne normalisée correspondante.
     78 *  '''C.1)''' Ecrire en langage C la fonction récursive display_abl() présentée en cours. cette fonction prend en entrée un pointeur p sur un bipointeur représentant la racine d'un arbre ABL, et affiche sur le terminal standard l’expression Booléenne normalisée correspondante.
    7979{{{
    8080void display_abl(bip_t *p)
    8181}}}
    82  *  '''C.2''': Mofifiez la fonction main() pour qu'elle effectue les opérations suivantes: construction en mémoire de l’arbre ABL correspondant à l’expression Booléenne E0 en utilisant la fonction parse_abl(), puis affichage de cette expression sur le terminal standard, au moyen de la fonction display_abl(). Compilez ce programme et exécutez-le.
     82 *  '''C.2)''' Mofifiez la fonction main() pour qu'elle effectue les opérations suivantes: construction en mémoire de l’arbre ABL correspondant à l’expression Booléenne E0 en utilisant la fonction parse_abl(), puis affichage de cette expression sur le terminal standard, au moyen de la fonction display_abl(). Compilez ce programme et exécutez-le.
    8383
    8484= D. Calcul du nombre de littéraux =
    … …  
    8888int count_abl(bip_t *p)
    8989}}}
    90  *  '''D.1''': Rappeler la relation de récurrence permettant d’exprimer le nombre de littéraux d’une expression Booléenne, connaissant le nombre de littéraux de chacun de ses opérandes.
    91  *  '''D.2''': Ecrire le code de la fonction en langage C, et modifier le programme main() de la question C) pour afficher également le nombre de littéraux de l’expression construite en mémoire.
    92  *  '''D.3''': Exécutez le programme pour les expressions Booléennes suivantes :
     90 *  '''D.1)''' Rappeler la relation de récurrence permettant d’exprimer le nombre de littéraux d’une expression Booléenne, connaissant le nombre de littéraux de chacun de ses opérandes.
     91 *  '''D.2)''' Ecrire le code de la fonction en langage C, et modifier le programme main() de la question C) pour afficher également le nombre de littéraux de l’expression construite en mémoire.
     92 *  '''D.3)''' Exécutez le programme pour les expressions Booléennes suivantes :
    9393{{{
    9494E1 = (a.b) + (a.c) + (b.c)
    … …  
    9696}}}
    9797
    98 = E. Calcul du support =
     98= E) Calcul du support =
    9999
    100100On appelle support d’une expression Booléenne l’ensemble de toutes les variables qui apparaissent au moins une fois dans cette expression.
    … …  
    106106bip_t *support_abl(bip_t *p)
    107107}}}
    108  *  '''E.1''': Commencer par écrire la fonction display_varlist() qui affiche sur le terminal standard la liste des noms des variables contenues dans une liste chaînée de bipointeurs.
     108 *  '''E.1)''' Commencer par écrire la fonction display_varlist() qui affiche sur le terminal standard la liste des noms des variables contenues dans une liste chaînée de bipointeurs.
    109109{{{
    110110void display_varlist(bip_t *p)
    … …  
    112112Pour éviter de confondre cet ensemble de noms avec une expression Booléenne, on affichera cette liste entre deux accolades de la façon suivante : { a b c d }
    113113Valider cette fonction en construisant explicitement dans la fonction main() une liste chainée de variables au moyen des fonctions cons_bip() et consvar(), et affichez cette liste.
    114  *  '''E.2''': Ecrire la relation de récurrence qui permet d’exprimer le support d’une expression Boléenne, connaissant le support de chacun de ses opérandes.
    115  *  '''E.3''': Ecrire la fonction union_list() qui effectue l’union de deux ensembles.
     114 *  '''E.2)''' Ecrire la relation de récurrence qui permet d’exprimer le support d’une expression Boléenne, connaissant le support de chacun de ses opérandes.
     115 *  '''E.3)''' Ecrire la fonction union_list() qui effectue l’union de deux ensembles.
    116116{{{
    117117bip_t *union_list(bip_t *p1, bip_t *p2)
    … …  
    119119Cette fonction prend en entrée deux pointeurs sur deux listes chainées  L1 et L2, et renvoie un pointeur sur la liste chaînée représentant l’union des deux listes. Les deux listes L1 et L2 ne doivent pas être modifiés par la fonction union_list().
    120120Attention: l’union est une opération différente de la simple concaténation, car chaque élément ne doit figurer qu’une seule fois dans la liste. On considère que les deux ensembles L1 et L2 qu'on veut réunir respectent cette condition. Valider cette fonction union_list() en construisant explicitement deux listes de variables non disjointes. On affichera les deux listes L1 et L2, ainsi que la liste résultant de l’union de L1 et L2.
    121  * '''E.4''': Ecrire effectivement la fonction support_abl(), en veillant à éviter les « fuites de mémoire ». On parle de fuite de mémoire chaque fois qu’un programme fait de l’allocation dynamique de mémoire sans libérer la mémoire qui n’est plus utilisée. Soyez attentifs à libérer la mémoire allouée par la fonction cons_bip() ...
    122  *  '''E.5''': Intégrez la fonction support_abl() dans le programme main(), et vérifiez que cette fonction calcule correctement le support des trois expressions E0, E1 et E2.
     121 * '''E.4)''' Ecrire effectivement la fonction support_abl(), en veillant à éviter les « fuites de mémoire ». On parle de fuite de mémoire chaque fois qu’un programme fait de l’allocation dynamique de mémoire sans libérer la mémoire qui n’est plus utilisée. Soyez attentifs à libérer la mémoire allouée par la fonction cons_bip() ...
     122 *  '''E.5''') Intégrez la fonction support_abl() dans le programme main(), et vérifiez que cette fonction calcule correctement le support des trois expressions E0, E1 et E2.
    123123
    124 = F. Fonction d’évaluation =
     124= F) Fonction d’évaluation =
    125125
    126126Pour les plus courageux (ou les plus rapides), on cherche maintenant à écrire une fonction d’évaluation d’une expression Booléenne représentée par un ABL, quand on connaît les valeurs de toutes les variables constituant son support. On ne considère que deux valeurs possibles pour le champs VALUE : 0 et 1.
    … …  
    129129}}}
    130130
    131  *  '''F.1''':  Rappeler les relations de récurrence qui relient la valeur d’une expression Booléenne à la valeur de ses opérandes, en analysant successivement le cas des 4 opérateurs NOT, OR, AND et XOR.
    132  *  '''F.2''': Ecrire en langage C la fonction récursive eval_abl(), et valider cette fonction en l’intégrant dans le programme main().
     131 *  '''F.1)'''  Rappeler les relations de récurrence qui relient la valeur d’une expression Booléenne à la valeur de ses opérandes, en analysant successivement le cas des 4 opérateurs NOT, OR, AND et XOR.
     132 *  '''F.2)''' Ecrire en langage C la fonction récursive eval_abl(), et valider cette fonction en l’intégrant dans le programme main().
    133133 
    134134= Compte-rendu =