Changes between Version 5 and Version 6 of CaoCourseTme5


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

--

Legend:

Unmodified
Added
Removed
Modified

  • CaoCourseTme5

    v5 v6  
    1010d'arbres ABL (Abres Binaires Lisp-Like), et à rafraîchir vos connaissances dans le domaine de la programmation
    1111des fonctions récursives.
     12
    1213Les expressions Booléennes multi-niveaux sont des expressions Booléennes préfixées pouvant comporter
    1314plusieurs niveaux d’imbrication de parenthèses. On représente une expression Booléenne comme une liste chaînée de bipointeurs.
    … …  
    4041Dans le cas des arbres ABL, le champs DATA peut contenir soit un pointeur vers un noeud de l’arbre (bip_t *), soit un pointeur vers une variable Booléenne (var_t *), soit un entier définissant le code d’un opérateur Booléen (unsigned int). Par conséquent, un cast est nécessaire chaque fois qu’on veut affecter une valeur ou lire la valeur contenue dans ce champs de la structure.
    4142
    42 On suppose qu’on dispose des fonctions suivantes :
     43On dispose des fonctions suivantes :
    4344
    4445{{{
    … …  
    5758
    5859Pour utiliser ces structures de données et ces fonctions, vous devez inclure dans votre programmes les fichiers suivants:
    59 {{
     60{{{
    6061#include <bip.h>
    6162#include <var.h>
    … …  
    7374= C. Fonction d’affichage =
    7475
    75 Ré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:
     76Ré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:
    7677
    7778 *  '''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.
    … …  
    8384= D. Calcul du nombre de littéraux =
    8485
    85 On 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).
     86On 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).
    8687{{{
    8788int count_abl(bip_t *p)
    … …  
    9192 *  '''D.3''': Exécutez le programme pour les expressions Booléennes suivantes :
    9293{{{
    93 E1= (a.b) + (a.c) + (b.c)
     94E1 = (a.b) + (a.c) + (b.c)
    9495E2 = (a.b.c) + (a.b.c’) + (a.b’.c) + (a’.b.c)
    9596}}}
    … …  
    9899
    99100On appelle support d’une expression Booléenne l’ensemble de toutes les variables qui apparaissent au moins une fois dans cette expression.
    100 Pour représenter un ensemble de variables, on utilise également des bipointeurs : Un ensemble est représenté par une liste chaînée de bipointeurs où le champs DATA pointe sur un élément de l’ensemble (ici une variable).
    101 Attention : même si on utilise la même structure de donnée bip_t, les bipointeurs utilisés pour représenter des ensembles de variables sont totalement indépendants des bipointeurs utilisés pour représenter des arbres ABL.
     101Pour représenter un ensemble de variables, on utilise également des bipointeurs : Un ensemble est représenté par une liste chaînée de bipointeurs où le champs DATA pointe sur un élément de l’ensemble (ici une structure var_t).
     102Attention : on utilise la même structure de donnée bip_t pour représenter des ensembles de variables, et pour représenter des arbres ABL.
    102103
    103104On cherche à écrire la fonction support_abl(), qui prend en entrée un pointeur p sur la racine d’un arbre ABL, et qui renvoie un pointeur sur la liste chaînée des n variables constituant son support.
    … …  
    110111}}}
    111112Pour é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 }
    112 Valider cette fonction en construisant explicitement une liste chainée de variables au moyen des fonctions cons_bip() et consvar(), et affichez cette liste.
     113Valider 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.
    113114 *  '''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.
    114115 *  '''E.3''': Ecrire la fonction union_list() qui effectue l’union de deux ensembles.
    … …  
    116117bip_t *union_list(bip_t *p1, bip_t *p2)
    117118}}}
    118 cette 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().
     119Cette 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().
    119120Attention: 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.
    120121 * '''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() ...
    121122 *  '''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.
    122123
    123 = E. Fonction d’évaluation =
     124= F. Fonction d’évaluation =
    124125
    125126Pour 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.
    … …  
    128129}}}
    129130
    130  *  '''E.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.
    131  *  '''E.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().
    132133 
    133134= Compte-rendu =