Algorithmes =========== On demande d'implanter les algorithmes de calculs suivants (dans ce qui suit ``rule`` est une règle quelconque): 1. Calcul de la valuation d'une grammaire (ce qui permet de vérifier la grammaire); #. méthode ``rule.count_naive(self, n)`` qui calcule le nombre d'objets d'un poids donné ``n`` par la méthode naïve; #. méthode ``rule.count(self, n)`` qui calcule le nombre d'objets de poids ``n`` par la méthode des séries génératrices; #. méthode ``rule.list(self, n)`` qui calcule la liste des objets de poids ``n``; #. méthode ``rule.unrank(self, n)`` qui calcule le ``i``-ème élément de la liste des objets de poids ``n``, sans calculer la liste; .. warning:: Note importante: en Sage la position dans une liste commence à ``0``; #. méthode ``rule.random(self, n)`` qui choisit équitablement au hasard un objet de poids ``n`` (on utilisera ``rule.unrank(self, n, i)`` où ``i`` sera choisi aléatoirement). 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é. 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: - la valuation d'un ``Singleton`` est 1; - la valuation d'un ``Epsilon`` est 0; - 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`; - la valuation du produit ``Prod`` des non-terminaux `N_1` et `N_2` est la somme des valuations de `N_1` et de `N_2`; Pour la calculer, on utilise l'algorithme de point fixe suivant. On part de la valuation `V_0` (incorrecte) qui associe à chaque non-terminal la valeur `\infty`. 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) = \infty` 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. Par exemple, sur les arbres, le calcul se fait en `4` étapes: ======== ================================ ========== ============================ n: ``Tree`` ``Leaf`` ``Node`` -------- -------------------------------- ---------- ---------------------------- Règle: `\min(V_{n-1}(\text{Leaf}),` `V_{n-1}(\text{Tree})+` `V_{n-1}(\text{Node}))` `1` `V_{n-1}(\text{Tree})` ======== ================================ ========== ============================ 0 `\infty` `\infty` `\infty` -------- -------------------------------- ---------- ---------------------------- 1 `\infty` `1` `\infty` -------- -------------------------------- ---------- ---------------------------- 2 `1` `1` `\infty` -------- -------------------------------- ---------- ---------------------------- 3 `1` `1` `2` -------- -------------------------------- ---------- ---------------------------- 4 `1` `1` `2` -------- -------------------------------- ---------- ---------------------------- Final: `1` `1` `2` ======== ================================ ========== ============================ À faire: ~~~~~~~~ 7. Écrire un fonction ``init_grammar`` qui prend en paramètre une grammaire, qui appelle sur chaque règle de la grammaire la méthode ``set_grammar`` et qui implante l'algorithme de calcul de la valuation. Comptage naïf 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`. - si `N` est un ``Singleton`` alors `C_N(1) = 1` et `C_N(i)= 0` si `i` est différent de `1`; - si `N` est un ``Epsilon`` alors alors `C_N(0) = 1` et `C_N(i) = 0` si `i` est différent de `0`; - si `N` est l'union ``Union`` des non-terminaux `N_1` et `N_2` alors .. math:: C_N(i)= C_{N_1}(i) + C_{N_2}(i)\,; - si `N` est le produit ``Prod`` des non-terminaux `N_1` et `N_2` .. math:: C_N(i) = \sum_{k+l=i} C_{N_1}(k) + C_{N_2}(l)\,; .. note:: **Pour aller plus vite et éviter des boucles infinies**, on ne considérera dans la somme précédente que les cas où `k \geq V(N_1)` et `l \geq 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`. À faire: ~~~~~~~~ 8. Implanter pour chaque règle de grammaire une méthode ``count_naive`` qui compte le nombre d'objets d'une grammaire dérivant d'un non-terminal et d'un poids donné. Calcul de la liste des objets ----------------------------- On applique récursivement les définitions des constructeurs ``Singleton``, ``Epsilon``, ``Union`` et ``Prod`` pour construire 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éments dérivant de `N_1` et de taille `k` et d'éléments dérivant de `N_2` et de taille `l`, pour tous les couples `k,l` tels que `k+l=i`, `k \geq V(N_1)` et `l \geq 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`. #. - 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`\dots\ (Je n'écrit pas les appels récursifs) qui retourne la liste ``[Leaf]``. On retourne donc la liste ``[Node(Leaf, Leaf)]`` - Application de ``Tree = Union (Leaf, Node)`` avec `i=1`. On retourne la liste ``[Leaf]`` Le produit cartésien des deux listes précédentes est la liste formée du seul élément ``[Node(Node(Leaf, Leaf), Leaf)]`` #. - Application de ``Tree = Union (Leaf, Node)`` avec `i=1`. On retourne donc la liste ``[Leaf]`` - Application de ``Tree = Union (Leaf, Node)`` avec `i=2`. On retourne donc la liste ``[Node(Leaf, Leaf)]`` Le produit cartésien des deux listes précédentes est la liste formée du seul élément ``[Node(Leaf, Node(Leaf, Leaf))]`` On retourne donc la liste des deux arbres:: [Node(Leaf, Node(Leaf, Leaf)), Node(Node(Leaf, Leaf), 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))); Calcul à l'aide des séries génératrices --------------------------------------- En sage, chaque variable formelle doit être déclarée à l'aide de la commande ``var``. On peut ensuite manipuler des expressions où la variable apparaît. Voici par exemple la résolution à la main du cas des arbres binaires:: sage: var("tr") sage: sys = [tr == x + tr*tr] sage: sol = solve(sys, tr, solution_dict=True) sage: sol [{tr: -1/2*sqrt(-4*x + 1) + 1/2}, {tr: 1/2*sqrt(-4*x + 1) + 1/2}] On a alors deux solutions:: sage: s0 = sol[0][tr] sage: s1 = sol[1][tr] sage: taylor(s0, x, 0, 5) 14*x^5 + 5*x^4 + 2*x^3 + x^2 + x sage: taylor(s1, x, 0, 5) -14*x^5 - 5*x^4 - 2*x^3 - x^2 - x + 1 Pour trouver quelle est la bonne on peut remplacer `x` par zéro:: sage: s0.subs(x=0), s1.subs(x=0) (0, 1) Dans le cas où la série est une fraction rationnelle, on sait que le dénominateur encode la récurrence. Ceci permet un calcul beaucoup plus rapide. Pour savoir si une expression est une fraction rationnelle, il faut la factoriser, extraire le numérateur et le dénominateur et vérifier que ce sont bien des polynômes. .. note:: Dans le cas des arbres binaires, cette méthode ne marche pas :: sage: s0 -1/2*sqrt(-4*x + 1) + 1/2 sage: s0.factor().numerator().is_polynomial(x) False Voici un exemple d'une fraction rationnelle:: sage: ex = x*2/(2*x^2+x+1) + 2*x+1 sage: ex = ex.factor(); ex (4*x^3 + 4*x^2 + 5*x + 1)/(2*x^2 + x + 1) sage: ex.numerator().is_polynomial(x) True sage: ex.denominator().is_polynomial(x) True On peut alors extraire les coefficients:: sage: ex.denominator().coefficients(x) [[1, 0], [1, 1], [2, 2]] À faire: ~~~~~~~~ 9. Écrire une fonction qui transforme une grammaire en un système d'équations sur des séries génératrices. Puisque la grammaire est supposée rationnelle, le système ainsi obtenu est linéaire. La fonction ``solve`` permet de résoudre un tel système, elle fonctionne essentiellement par pivot de Gauss. La solution est alors une fraction rationnelle. 10. À l'aide de la fonction précédente, ajouter une méthode ``generating_series`` aux différentes classes représentant les règles de grammaire. La fonction ``taylor`` permet alors de calculer les premiers coefficients. Pour calculer les suivants, on utilise le fait que le dénominateur encode une récurrence vérifiée par les coefficients de la série. Ainsi, si .. math:: f(X) = \sum_{i \geq 0} f_i X^i = \frac{N(X)}{D(X)} = \frac{N(X)}{c_0 + c_1 X + c_2 X^2 + \dots + C_d X^d} et si `n` est supérieur au degré du numérateur, alors le coefficient de `X^n` de `f(X) D(X)` est nul. On peut sans perte de généralité supposer `c_0=1`. On obtient donc les équations pour tout `n>\deg(N(X))`, .. math:: \sum_{i=0}^{d} c_i f_{n - i} = 0 \qquad\text{soit}\qquad f_n = -\sum_{i=1}^{d} c_i f_{n - i} 11. Écrire une méthode qui calcule les coefficients de la série en utilisant la récurrence. Il est possible d'abaisser la complexité du calcul de `f_n` utilisant une matrice. En effet, la récurrence s'écrit .. math:: \begin{pmatrix} f_{n} \\ f_{n-1} \\ f_{n-2} \\ \vdots \\ f_{n-d+1} \end{pmatrix} = \begin{pmatrix} -c_1 & -c_2 & \dots & -c_{d-1} & -c_d \\ 1 & 0 & \dots & 0 & 0 \\ 0 & 1 & \dots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & 0 \\ \end{pmatrix} \begin{pmatrix} f_{n-1} \\ f_{n-2} \\ f_{n-3} \\ \vdots \\ f_{n-d} \end{pmatrix} Pour calculer coefficient `f_n` il suffit donc d'élever la matrice à la puissance `n` par exponentiation binaire. 12. Écrire une fonction qui calcule le coefficient de `X^n` d'une fraction rationnelle par la méthode matricielle. Calcul du `i`-ème élément : la méthode ``unrank`` ------------------------------------------------- Pour calculer l'élément de taille `n` et de rang `i`, on fait appel à la méthode ``unrank``. Voici par exemple l'arbre de taille `6` et de rang `12`:: sage: treeGram['Tree'].unrank(6, 12) Node(Leaf, Node(Node(Node(Leaf, Node(Leaf, Leaf)), Leaf), Leaf)) .. warning:: La numérotation commence à zéro. On procédera récursivement comme suit: - si l'on demande un objet dont le rang est supérieur au nombre d'objet on lève une exception ``ValueError``. - dans le cas ``EpsilonRule`` ou ``SingletonRule``, on retourne l'objet. - dans le cas d'une union: ``"U" : UnionRule("A", "B")``, on suppose connu les nombres d'objets: `C_U(n) = C_A(n) + C_B(n)`. Alors l'objet de `U` de rang `i` est l'objet de `A` de rang `i` si `i