Changes between Version 3 and Version 4 of CaoCourseTme5


Ignore:
Timestamp:
Mar 7, 2007, 5:32:29 PM (18 years ago)
Author:
alain
Comment:

--

Legend:

Unmodified
Added
Removed
Modified

  • CaoCourseTme5

    v3 v4  
    1515 * soit une variable Booléenne, définie par son nom.
    1616 * soit une autre expression Booléenne.
     17
     18= Structures de données et fonctions de base =
    1719
    1820La 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.
    … …  
    3941
    4042On suppose qu’on dispose des fonctions suivantes :
     43
    4144{{{
    4245extern var_t  *cons_var(char *name, unsigned int index, unsigned int value)
    43 }}}
    44 Cette fonction crée un objet de type var_t, vérifie qu'il n'existe pas de variable portant le même nom ou le même index, initialise les champs NAME, INDEX et VALUE de la structure de donnée, et renvoie un pointeur sur la variable ainsi créée.
    45 {{{
    4646extern var_t *get_var_index(unsigned int x)
    4747extern var_t *get_var_name(char *s)
    48 }}}
    49 Les variables sont rangées dans un dictionnaire qui permet de retrouver rapidement une variable. Les deux fonctions ci-dessus renvoient un pointeur vers la variable désignée soit par son nom, soit par son index, et affichent un message d’erreur si la variable n’existe pas.
    50 {{{
    5148extern bip_t  *cons_bip(bip_t *next, void *data)
    52 }}}
    53 Cette fonction crée un bipointeur de type bip_t, en affectant la valeur data au champs DATA, et la valeur next au champs NEXT, et renvoie un pointeur sur le bipointeur ainsi créé.
    54 {{{
    55 extern void free_bip(bip_t *p)
    56 }}}
    57 Cette fonction permetb de libérer la mémoire allouée par la fonction cons_bip().
    58 {{{
     49extern void  free_bip(bip_t *p)
    5950extern bip_t *parse_abl( char *expr)
    6051}}}
    61 Cette fonction prend en entrée une chaîne de caractères décrivant  une expression Booléenne préfixée possédant un nombre quelconque de niveaux de parenthèsage. Elle construit en mémoire l’arbre ABL représentant cette expression Booléenne et renvoie un pointeur sur le bipointeur correspondant à la racine.
    62 Attention: Cette fonction n’accepte que les expressions Booléennes préfixées. Les seuls opérateurs acceptés sont NOT, OR, AND et XOR. Elle affiche un message d’erreur en cas d’erreur de syntaxe, ou si elle rencontre un nom de variable non déclarée préalablement.
    63  
    64 = A. Représentation Graphique =
     52
     53 * La fonction cons_var() crée un objet de type var_t, vérifie qu'il n'existe pas de variable portant le même nom ou le même index, initialise les champs NAME, INDEX et VALUE de la structure de donnée, range la variable dans un dictionnaire, et renvoie un pointeur sur la variable ainsi créée.
     54 * Les deux fonctions get_var_index() et get_var_name() renvoient un pointeur vers la variable désignée soit par son nom, soit par son index, et affichent un message d’erreur si la variable n’existe pas.
     55 * La fonction cons_bip() crée un bipointeur de type bip_t, en affectant la valeur data au champs DATA, et la valeur next au champs NEXT, et renvoie un pointeur sur le bipointeur ainsi créé. La fonction free_bip() permet de libérer la mémoire allouée par la fonction cons_bip().
     56 * La fonction parse_abl() prend en entrée une chaîne de caractères décrivant  une expression Booléenne préfixée possédant un nombre quelconque de niveaux de parenthèsage. Elle construit en mémoire l’arbre ABL représentant cette expression Booléenne et renvoie un pointeur sur le bipointeur correspondant à la racine. Cette fonction n’accepte que les expressions Booléennes préfixées, et les seuls opérateurs acceptés sont NOT, OR, AND et XOR. Elle affiche un message d’erreur en cas d’erreur de syntaxe, ou si elle rencontre un nom de variable non déclarée préalablement.
     57
     58Pour utiliser ces structures de données et ces fonctions, vous devez inclure dans votre programmes les fichiers suivants:
     59{{
     60#include <bip.h>
     61#include <var.h>
     62#include <parse_abl.h>
     63}}}
     64
     65= B. Représentation Graphique =
    6566
    6667Soit l’expression  {{{E0 = (a’ . (b + c + d’) . e) + c}}}       
    … …  
    6869La notation a’ signifie NOT(a)
    6970
    70  *  '''A.1''': Re-écrire cette expression sous une forme préfixée, et représentez graphiquement l’arbre ABL  correspondant à l’expression E0.
    71 Notez que les opérateurs AND, OR et XOR peuvent avoir une arité (c’est à dire un nombre d’opérandes) supérieur à 2. Par exemple (OR a b c) = a + b + c.
     71 *  '''B.1''': Re-écrire cette expression sous une forme préfixée, et représentez graphiquement l’arbre ABL  correspondant à l’expression E0.
    7272
    73 = B. Fonction d’affichage =
     73= C. Fonction d’affichage =
    7474
    75  *  '''B.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 noeud ABL, et affiche sur le terminal standard l’expression Booléenne représentée par l’arbre ABL dont  p est la racine.
     75Ré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 fichier {{{main.c}}} que vous devrez complêter:
     76
     77 *  '''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.
    7678{{{
    7779void display_abl(bip_t *p)
    7880}}}
    79  *  '''B.2''': Ecrivez le programme main() qui construit en mémoire l’arbre ABL correspondant à l’expression E0 de la partie A, en utilisant la fonction parse_abl(), puis affiche cette expression sur le terminal standard, au moyen de la fonction display_abl(). Compilez ce programme et exécutez-le.
     81 *  '''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.
    8082
    81 = C. Calcul du nombre de littéraux =
     83= D. Calcul du nombre de littéraux =
    8284
    8385On cherche maintenant à écrire en langage C la fonction récursive count_abl(). cette fonction prend en entrée un pointeur p sur la racine d’un arbre ABL, et renvoie un entier représentant le nombre de littéraux (c’est và dire le nombre de feuilles de l’arbre ABL correspondant à des variables).
    … …  
    8587int count_abl(bip_t *p)
    8688}}}
    87  *  '''C.1''': Ecrire 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.
    88  *  '''C.2''': Ecrire le code de la fonction en langage C, et modifier le programme main() de la question B pour afficher également le nombre de littéraux de l’expression construite en mémoire.
     89 *  '''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.
     90 *  '''D.2''': Ecrire le code de la fonction en langage C, et modifier le programme main() de la question B pour afficher également le nombre de littéraux de l’expression construite en mémoire.
    8991 *  '''C.3''': Exécutez le programme pour les expressions Booléennes suivantes :
    9092{{{