From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 30388BCAB for ; Mon, 23 May 2005 08:54:36 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j4N6sZX8006309 for ; Mon, 23 May 2005 08:54:35 +0200 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id IAA30123 for ; Mon, 23 May 2005 08:54:35 +0200 (MET DST) Received: from fedex.univ-mlv.fr (fedex.univ-mlv.fr [193.50.159.86]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j4N6sY8Z006306 for ; Mon, 23 May 2005 08:54:34 +0200 Received: from etudiant.univ-mlv.fr (badboys.univ-mlv.fr [193.50.159.4]) by fedex.univ-mlv.fr (Postfix) with ESMTP id 6D009BD44 for ; Mon, 23 May 2005 08:54:34 +0200 (CEST) Message-ID: <42917E2A.2040501@etudiant.univ-mlv.fr> Date: Mon, 23 May 2005 08:54:34 +0200 From: " dsingh01" <" dsingh01"@etudiant.univ-mlv.fr> Organization: Universite de Marne-la-Vallee User-Agent: Mozilla/5.0 (X11; U; Linux i686; rv:1.6) Gecko/20040413 Debian/1.6-5 X-Accept-Language: fr, en-gb, en-us MIME-Version: 1.0 To: caml-list@inria.fr Subject: Question Content-Type: multipart/mixed; boundary="------------030102010106080202020306" X-j-chkmail-Score: MSGID : 42917E2B.000 on concorde : j-chkmail score : X : 0/40 1 X-j-chkmail-Score: MSGID : 42917E2A.000 on concorde : j-chkmail score : X : 0/40 1 X-Miltered: at concorde with ID 42917E2B.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 42917E2A.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; ocaml:01 beginners:01 ocaml:01 beginners:01 pouvez-vous:01 recoive:01 pouvez-vous:01 recoive:01 d'objets:01 decrit:01 grammaire:01 combinatoire:01 decrit:01 grammaire:01 d'objets:01 X-Attachments: name="enonce.txt" name="enonce.txt" X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.1 required=5.0 tests=HTML_50_60,HTML_MESSAGE, HTML_TITLE_EMPTY autolearn=disabled version=3.0.2 X-Spam-Level: This is a multi-part message in MIME format. --------------030102010106080202020306 Content-Type: multipart/alternative; boundary="------------050301050604070506080703" --------------050301050604070506080703 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit Bonjour; pour recevoir une aide pour la réalisation d'un projet de caml,j'ai envoyé un mail à cette adresse ocaml_beginners@yahoogroups.com mais je n'ai pas eu de réponse . Pouvez-vous faire en sorte que je recoive une réponse ou alors pouvez-vous m'aidez pour le projet que voici: --------------050301050604070506080703 Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: 7bit Bonjour;
pour recevoir une aide pour la réalisation d'un projet de caml,j'ai envoyé un mail à cette adresse
mais je n'ai pas eu de réponse .
Pouvez-vous faire en sorte que je recoive une réponse ou alors pouvez-vous m'aidez pour le projet que voici:

--------------050301050604070506080703-- --------------030102010106080202020306 Content-Type: text/plain; name="enonce.txt" Content-Transfer-Encoding: 8bit Content-Disposition: inline; filename="enonce.txt" Projet de programmation fonctionnelle: GENERATION D'OBJETS COMBINATOIRES DÉCRIT PAR UNE GRAMMAIRE Le but de ce projet est de compter et d'engendrer l'ensemble des objets combinatoire décrit par une grammaire. Il est ainsi possible d'engendrer une grande variété d'objets comme des arbres ou des mots. 1 Exemples 1.1 Les arbres binaires complets Un arbre binaire complet est soit une feuille, soit un noeud sur lequel on a greffé deux arbres binaires complets. Cette définition se traduit dans le type ocaml: type tree = Leaf | Node of tree*tree;; Ainsi, on peut décrire l'ensemble des arbres binaires par les définitions récursives suivantes: - l'ensemble "Trees" des arbres est la réunion (que l'on notera en ocaml par le constructeur Union) de deux ensembles : l'ensemble "Nodes" des noeuds et l'ensemble "Leaf" des feuilles; -l'ensemble "Nodes" des noeuds est obtenu à partir de l'ensemble des paires d'arbres, c'est-à-dire le produit cartésien (noté par le constructeur Prod) de l'ensemble des arbres avec lui même; -il n'y a qu'un seul arbres possible constitué d'une feuille. C'est le singleton (constructeur Singleton) Leaf Une telle définition est appelée grammaire. On écrira en ocaml la grammaire des arbres de la manière suivante: let consNode fg fd = Node (fg,fd);; (* fonction qui construit un arbre à partir des deux sous-arbres *) let gramTrees = valuGrammar ["Tree", Union ("Leaf", "Node"); "Leaf", Singleton Leaf; "Node", Prod("Tree", "Tree", consNode)];; Le but de ce projet est d'implanter un algorithme permettant de compter et d'engendrer automatiquement la liste des objets décrit par une grammaire de ce type: par exemple il y a 5 arbres binaires complets à quatre feuilles: Ce que l'on peut obtenir par le programme # count gramTrees "Tree" 4;; - : int = 5 La liste des objets décrits par la grammaire peut ensuite être obtenue comme suit. # derivation gramTrees "Tree" 4;; - : tree objects list = [Pair (Pair (Pair (Atom Leaf, Atom Leaf), Atom Leaf), Atom Leaf); Pair (Pair (Atom Leaf, Pair (Atom Leaf, Atom Leaf)), Atom Leaf); Pair (Pair (Atom Leaf, Atom Leaf), Pair (Atom Leaf, Atom Leaf)); Pair (Atom Leaf, Pair (Pair (Atom Leaf, Atom Leaf), Atom Leaf)); Pair (Atom Leaf, Pair (Atom Leaf, Pair (Atom Leaf, Atom Leaf)))] Une telle expression qui décrit la suite des opérations dans la grammaire est appelé une dérivation de la grammaire. À chaque dérivation correspond un arbre. Voici la liste des arbres correspondants aux dérivations précédentes: # generation gramTrees "Tree" 4;; - : tree list = [Node (Node (Node (Leaf, Leaf), Leaf), Leaf); Node (Node (Leaf, Node (Leaf, Leaf)), Leaf); Node (Node (Leaf, Leaf), Node (Leaf, Leaf)); Node (Leaf, Node (Node (Leaf, Leaf), Leaf)); Node (Leaf, Node (Leaf, Node (Leaf, Leaf)))] 1.2 Les mots de Fibonacci On appelle mot de Fibonacci tout mot sur l'alphabet A et B qui ne contient pas deux B a la suite. Un tel mot w est décrit par la grammaire suivante: -soit w est vide; -soit w est de la forme Au où u est un mot de Fibonacci; -soit w est le mot B; -soit w est de la forme BAu où u est un mot de Fibonacci; Ceci ce traduit en ocaml par la grammaire: let gramFibo = valuGrammar ["Fib", Union ("Vide", "Cas1"); "Cas1", Union ("CasAu", "Cas2"); "Cas2", Union ("AtomB", "CasBAu"); "Vide", Epsilon ""; "CasAu", Prod ("AtomA", "Fib", (^)); "AtomA", Singleton "A"; "AtomB", Singleton "B"; "CasBAu", Prod ("AtomB", "CasAu", (^)) ];; Notons la fonction (^) qui concatène deux chaîne de caractères. Voici la liste des mots de Fibonacci de longueur 3: AAA, AAB, ABA, BAA, BAB. Ce qui se vérifie par # count gramFibo "Fib" 3;; - : int = 5 # generation gramFibo "Fib" 3;; - : string list = ["AAA"; "AAB"; "ABA"; "BAA"; "BAB"] Voici comment ils sont dérivés par la grammaire: # derivation gramFibo "Fib" 3;; - : string objects list = [Pair (Atom "A", Pair (Atom "A", Pair (Atom "A", Eps ""))); Pair (Atom "A", Pair (Atom "A", Atom "B")); Pair (Atom "A", Pair (Atom "B", Pair (Atom "A", Eps ""))); Pair (Atom "B", Pair (Atom "A", Pair (Atom "A", Eps ""))); Pair (Atom "B", Pair (Atom "A", Atom "B"))] On peut de la même manière obtenir les 21 mots de Fibonacci de longueur 6: # generation gramFibo "Fib" 6;; - : string list = ["AAAAAA"; "AAAAAB"; "AAAABA"; "AAABAA"; "AAABAB"; "AABAAA"; "AABAAB"; "AABABA"; "ABAAAA"; "ABAAAB"; "ABAABA"; "ABABAA"; "ABABAB"; "BAAAAA"; "BAAAAB"; "BAAABA"; "BAABAA"; "BAABAB"; "BABAAA"; "BABAAB"; "BABABA"] 2 Définitions formelles Soit 'a un type caml. Une grammaire décrit récursivement un sous-ensemble de l'ensemble des objets de type 'a. Elle est constitué d'un ensemble de règles ayant chacune un nom (chaîne de caractères). Le nom d'une règle est appelé symbole non-terminal ou plus simplement non-terminal de la grammaire. Une règle de grammaire R décrit un ensemble qui est 1 soit un singleton dont le seul élément est un objet atomique de type 'a et qui sera de poids 1 (par exemple la feuille d'un arbre). 2 soit un ensemble dont le seul élément est un objet vide de type 'a et qui sera de poids 0 (par exemple la chaîne vide). 3 soit l'union de deux ensembles décrit par deux non-terminaux N_1 et N_2; 4 soit le produit cartésien de deux ensembles décrit par deux non-terminaux N_1 et N_2; L'ensemble est alors constitué des paires d'éléments (e1, e2) appartenant à N_1 x N_2. Dans ce cas, il faut de plus donner à ocaml une fonction qui construit l'objet ocaml correspondant à la paire (e1, e2). La taille ou poids d'un objet est le nombre d'atomes qu'il contient. Le poids d'un élément correspondant à une paire (e1, e2) est donc la somme des poids de e1 et de e2. À chaque non-terminal on associe la taille du plus petit objet qui en dérive. Cette taille est appelé valuation du non-terminal. 2.1 Structures de données Une grammaire sera stockées sous la forme de listes d'associations. On définit donc le type liste d'association par: type ('clef, 'valeur) assoc = ('clef * 'valeur) list;; Une grammaire est une table qui associe à chaque non-terminal une règle de grammaire: type 'a rule = | Singleton of 'a | Epsilon of 'a | Union of string * string | Prod of string * string * ('a->'a->'a);; type 'a simpleGrammar = (string, 'a rule) assoc;; Voici le type décrivant les objets dérivés correspondant aux règles: type 'a objects = | Atom of 'a | Eps of 'a | Pair of ('a objects) * ('a objects);; où 1 Atom x est le seul objet dérivé de la règle Singleton x; 2 Eps e est le seul objet dérivé de la règle Epsilon e; 3 si e1 est un objet dérivé du non-terminal nt1 et e2 est un objet dérivé du non-terminal nt2 alors Pair (e1,e2) est un objet par la règle (nt1,nt2,_). De plus, une fois calculée, on a besoin de stocker la valuation à l'intérieur de la grammaire. Une telle grammaire est dite valuée. On utilisera les types ocaml suivants: type valuation = (string, int) assoc;; type 'a valuatedGrammar = (string, 'a rule*int) assoc;; 2.2 Pour s'entraîner 1 Donner la grammaire ocaml de tous les mots sur l'alphabet A, B. 2 Donner la grammaire ocaml des mots de Dyck, c'est-à-dire les mots sur l'alphabet (,) et qui sont correctement parenthésés. 3 Écrire une fonction qui vérifie qu'une grammaire est correcte, c'est-à-dire que chaque non-terminal apparaissant dans une règle est bien défini par la grammaire. 3 Algorithmes On écrira le programme en quatres temps: 1 Calcul de la valuation d'une grammaire (ce qui permet de vérifier la grammaire); 2 Calcul du nombre d'objets de poids donné; 3 Calcul des dérivations des objets d'un poids donné; 4 Calcul des objets d'un poids donné; Le calcul de la valuation est nécessaire aux étapes suivantes qui sont indépendantes. Je les ai néanmoins classé par ordre croissant de difficulté. 3.1 Calcul de la valuation La valuation du non-terminal nt est la taille du plus petit objet qui en dérive. La valuation d'une grammaire est l'ensemble des valuations des terminaux. Elle vérifie les quatres règles suivantes: 1 la valuation d'un Singleton est 1; 2 la valuation d'un Epsilon est 0; 3 la valuation de l'union Union des non-terminaux N_1 et N_2 est le minimum des valuations de N_1 et de N_2; 4 la valuation du produit Prod des non-terminaux N1 et N2 est la somme des valuations de N_1 et de N_2; Pour la calculer, on procède comme suit. On part de la valuation V_0 (incorrecte) qui associe à chaque non-terminal la valeur infini. En appliquant une fois non récursivement (pour éviter les boucles infinies) les règles précédentes à partir de V_0, on calcule une nouvelle valuation V_1. On calcule ensuite de même une valuation V_2 a partir de V_1. On recommence tant que la valuation V_n est différente de V_n-1. La valuation cherchée V = V_n est obtenue quand V_n=V_n-1. Note: Si V(N) := V_n(N) = infini pour un certain non terminal N, alors aucun objet ne dérive de ce non-terminal. On considère alors que la grammaire est incorrecte. 3.1 À faire: En ocaml on définira donc le type et l'exception suivante type intInf = Infinity | Int of int;; exception InfiniteValuation of string;; 4 Écrire les fonctions plusIntInf et minIntInf pour calculer la somme et le plus petit de deux entiers ou infinis. val plusIntInf : intInf -> intInf -> intInf val minIntInf : intInf -> intInf -> intInf 5 Écrire une fonction nextValuation qui calcule la valuation V_i à partir de la grammaire et de V_i-1: val nextValuation : 'a simpleGrammar -> (string * intInf) list -> (string * intInf) list 6 Écrire la fonction makeValuation qui calcule la valuation d'une grammaire et en déduire une fonction valuGrammar qui calcule la grammaire valuée associée à une grammaire simple et qui renvoie une exception InfiniteValuation nt si un terminal nt a une valuation infinie. val makeValuation : 'a simpleGrammar -> (string * intInf) list val valuGrammar : 'a simpleGrammar -> 'a valuatedGrammar Toutes les fonctions suivantes travaillerons sur la grammaire valuée. 3.2 Comptage du nombre d'objets Le comptage du nombre d'objets de poids i se fait en appliquant récursivement les règles suivantes: Soit N un non-terminal. On note C_N(i) le nombre d'objet de poids i. 1 si N est un Singleton alors C_N(1) = 1 et C_N(i) = 0 si i est différent de 1; 2 si N est un Epsilon alors alors C_N(0) = 1 et C_N(i) = 0 si i est différent de 0; 3 si N est l'union Union des non-terminaux N_1 et N_2 alors C_N(i) = C_{N_1}(i) + C_{N_2}(i),; 4 si N est le produit Prod des non-terminaux N_1 et N_2: C_N(i) = sum_{k+l=i} C_{N_1}(k) + C_{N_2}(l),; Pour aller plus vite et éviter des boucles infinies, on ne considérera dans la somme précédente que les cas où k >= V(N_1) et l >= V(N_2), où V(N) désigne la valuation du non-terminal N. En effet, par définition C_N(i) = 0 si V(N) > i. 3.2.1 A faire 7 Écrire la fonction count qui compte le nombre d'objets d'une grammaire dérivant d'un non-terminal et d'un poids donné: val count : 'a valuatedGrammar -> string -> int -> int 3.3 Calcul de la liste des dérivations et des objets L'algorithme est exactement le même dans les deux cas, seul diffère le type du résultat. On applique récursivement les définitions des constructeurs Singleton, Epsilon, Union et Prod pour retourner la liste des objets de taille i. En particulier, si N est le produit Prod des non-terminaux N_1 et N_2, la liste des objets dérivant de N et de poids i est la concaténation des listes de tous les produits cartésiens d'élément dérivant de N_1 et de taille k et d'élément dérivant de N_2 et de taille l, pour tous les couples k,l tels que k+l=i, k >= V(N_1) et l >= V(N_2) (comme précédemment V(M) désigne la valuation du non-terminal M). Par exemple, pour obtenir les arbres de taille 3, on procède de la manière suivante Calcul de Tree = Union (Leaf, Node) avec i=3. -Application de Leaf = Singleton Leaf avec i=3, on retourne la liste vide []; -Application de Node = Prod(Tree, Tree) avec i=3. La valuation de Tree est 1. Il y a donc deux possibilités 3=1+2 ou 3=2+1. 1 -Application de Tree = Union (Leaf, Node)} avec i=2. -Leaf est vide avec i=2 on retourne la liste vide. -Application de Node = Prod(Tree, Tree) avec i=2. La valuation de Tree est 1. Une seule décomposition est possible 1+1... On appelle donc deux fois Tree avec i=1... (Je n'écrit pas les appels récursifs)...qui retourne la liste [Atom Leaf]. On retourne donc la liste :[Pair (Atom Leaf, Atom Leaf)] -Application de Tree = Union (Leaf, Node) avec i=1.On retourne la liste : [Atom Leaf] Le produit cartésien des deux listes précédentes est la liste formée du seul élément [Pair (Pair (Atom Leaf, Atom Leaf), Atom Leaf)] 2 -Application de Tree = Union (Leaf, Node) avec i=1.On retourne la liste [Atom Leaf] -Application de Tree = Union (Leaf, Node) avec i=2.On retourne donc la liste [Pair (Atom Leaf, Atom Leaf)] Le produit cartésien des deux listes précédentes est la liste formée du seul élément [Pair (Atom Leaf, Pair (Atom Leaf, Atom Leaf))] On retourne donc la liste des deux dérivations: [Pair (Pair (Atom Leaf, Atom Leaf), Atom Leaf); Pair (Atom Leaf, Pair (Atom Leaf, Atom Leaf))] Pour i=6, il faut essayer les décompositions 6=5+1, 6=4+2, 6=3+3, 6=2+4 et 6=1+5. Étudions le cas 3+3. Par appel récursif on trouve deux arbres de poids 3: [Node (Node (Leaf, Leaf), Leaf); Node (Leaf, Node (Leaf, Leaf))] Le produit cartésien est donc formé de 4 éléments qui correspondent aux 4 arbres suivants: Node (Node (Leaf, Node (Leaf, Leaf)), Node (Node (Leaf, Leaf), Leaf)); Node (Node (Node (Leaf, Leaf), Leaf), Node (Node (Leaf, Leaf), Leaf)); Node (Node (Leaf, Node (Leaf, Leaf)), Node (Leaf, Node (Leaf, Leaf))); Node (Node (Node (Leaf, Leaf), Leaf), Node (Leaf, Node (Leaf, Leaf))); 3.3.1 À faire: 8 Écrire une fonction val cartProd : 'a objects list -> 'a objects list -> 'a objects list qui calcule le produit cartésien de deux listes d'objets. 9 Écrire la fonction val derivation : 'a valuatedGrammar -> string -> int -> 'a objects list qui calcule la liste des objets dérivant d'un non-terminal d'une grammaire et d'un poids donné. 10 Écrire la fonction val cartProdCons : ('a -> 'a -> 'a) -> 'a list -> 'a list -> 'a list qui construit en utilisant une fonction de construction (par exemple consNode ou (^) la liste des objets correspondants aux dérivation d'un non-terminal d'une grammaire et d'un poids donné. 11 En déduire la fonction val generation : 'a valuatedGrammar -> string -> int -> 'a list qui répond au problème posé. --------------030102010106080202020306--