TD 3 - Calcul non commutatif avec sympy

L'objectif du TD est de manipuler les séries génératrices de langages vues en cours.

In [2]:
from sympy import *

On définit un alphabet de deux lettres $A=\{a,b\}$:

In [3]:
a,b = symbols('a,b', commutative = False)

Affichons les mots de longueur 4 pour tester :

In [4]:
A4 = expand((a+b)**4)
In [5]:
print (A4)
a*b*a*b + a*b*a**2 + a*b**2*a + a*b**3 + a**2*b*a + a**2*b**2 + a**3*b + a**4 + b*a*b*a + b*a*b**2 + b*a**2*b + b*a**3 + b**2*a*b + b**2*a**2 + b**3*a + b**4

Il y en a bien 16.

Pour travailler avec des mots, ces expressions ne sont pas très lisibles. Si on a un langage (pas de multiplicités), on peut utiliser une représentation en liste :

In [6]:
print (A4.as_ordered_terms())
[a*b*a*b, a*b*a**2, a*b**2*a, a*b**3, a**2*b*a, a**2*b**2, a**3*b, a**4, b*a*b*a, b*a*b**2, b*a**2*b, b*a**3, b**2*a*b, b**2*a**2, b**3*a, b**4]
In [7]:
ll = A4.as_ordered_terms()

Pour afficher des mots plutôt que des monômes avec des * et des **, on bricole une petite expression régulière :

In [8]:
import re
pat = re.compile(r'((\w)\*\*(\d+))')
In [9]:
w = ll[3];w
Out[9]:
$\displaystyle a b^{3}$
In [10]:
pat.findall(str(w))
Out[10]:
[('b**3', 'b', '3')]
In [11]:
def mon2word(w):
    return pat.sub(lambda x: x.group(2)*int(x.group(3)),str(w)).replace('*','')
In [13]:
print(list(map(mon2word,ll)))
['abab', 'abaa', 'abba', 'abbb', 'aaba', 'aabb', 'aaab', 'aaaa', 'baba', 'babb', 'baab', 'baaa', 'bbab', 'bbaa', 'bbba', 'bbbb']

Le langage de Dyck

C'est le langage des mots de parenthèses bien formés, ou des arbres binaires. Il est défini par la grammaire (on note $( = a$ et $) = b$) $$ D\rightarrow \epsilon|aDbD $$ qu'on écrit plutôt comme une équation entre séries formelles $$ D = 1 + aDbD$$ le terme $D_n$ formé des mots de longueur $2n$ est alors $$D_n = \sum_{i=0}^{n-1}aD_ibD_{n-1-i}.$$

Ecrire une fonction dyck(n) renvoyant le terme de degré $n$.

Pour calculer ce genre de fonction récursive, ils est plus efficace d'enregistrer les valeurs déjà calculées dans un dictionnaire.

In [14]:
dd = {0:1, 1:a*b}
def dyck(n):
    # votre code ici
    if n in dd: return dd[n]
    return expand(sum([a*dyck(i)*b*dyck(n-1-i) for i in range(n)]))
In [17]:
dyck(2)
Out[17]:
a*b*a*b + a**2*b**2
In [18]:
dyck(3)
Out[18]:
a*b*a*b*a*b + a*b*a**2*b**2 + a**2*b*a*b**2 + a**2*b**2*a*b + a**3*b**3
In [19]:
dyck(4)
Out[19]:
a*b*a*b*a*b*a*b + a*b*a*b*a**2*b**2 + a*b*a**2*b*a*b**2 + a*b*a**2*b**2*a*b + a*b*a**3*b**3 + a**2*b*a*b*a*b**2 + a**2*b*a*b**2*a*b + a**2*b*a**2*b**3 + a**2*b**2*a*b*a*b + a**2*b**2*a**2*b**2 + a**3*b*a*b**3 + a**3*b**2*a*b**2 + a**3*b**3*a*b + a**4*b**4
In [20]:
D4 = dyck(4).as_ordered_terms()
In [21]:
print map(mon2word,D4)
['abababab', 'ababaabb', 'abaababb', 'abaabbab', 'abaaabbb', 'aabababb', 'aababbab', 'aabaabbb', 'aabbabab', 'aabbaabb', 'aaababbb', 'aaabbabb', 'aaabbbab', 'aaaabbbb']

On peut maintenant introduire une variable commutative $x$ :

In [22]:
var('x')
Out[22]:
x
In [23]:
d5 = dyck(5)
In [24]:
d5.subs({a:x,b:x}) # Les substitutions se font avec un dictionnaire
Out[24]:
42*x**10

Vérifier que les premiers termes de la srie obtenue en effectuant cette substitution ont bien pour coefficients les nombres de Catalan.

Le code de Fibonacci

Le code de Fibonacci est $C=\{b,ab\}$. C'est un code préfixe, c'est à dire qu'aucun de ses mots n'est préfixe d'un autre. Ceci assure que toute concaténation de mots de $C$ est déchiffrable de manière unique. Soit $F=C^*$ le langage engendré par $C$, et $F_n=A^n\cap F$ l'ensemble de ses mots de longueur $n$.

In [25]:
ff = {0:1, 1:b, 2:a*b+b*b}

def fib(n):
    # votre code ici
    if n in ff: return ff[n]
    return expand(b*fib(n-1)+a*b*fib(n-2))
In [26]:
fib(3)
Out[26]:
a*b**2 + b*a*b + b**3

Répéter les manipulations précédents pour retrouver les premiers termes de la série génératrice des nombres de Fibonacci.

Arbres binaires

On représentera un arbre binaire sous la forme o ou (o,A,B) où A et B sont des arbres binaires.

Ecrire une fonction bintrees(n) renvoyant la liste des arbres binaires à $n$ feuilles.

In [15]:
var('o')
def bintrees(n):
    if n==1: return [o]
    else:
        ll = []
        for i in range(1,n):
            ll.extend([(o,u,v) for u in bintrees(i) for v in bintrees(n-i)])
        return ll
In [16]:
print (bintrees(5))
[(o, o, (o, o, (o, o, (o, o, o)))), (o, o, (o, o, (o, (o, o, o), o))), (o, o, (o, (o, o, o), (o, o, o))), (o, o, (o, (o, o, (o, o, o)), o)), (o, o, (o, (o, (o, o, o), o), o)), (o, (o, o, o), (o, o, (o, o, o))), (o, (o, o, o), (o, (o, o, o), o)), (o, (o, o, (o, o, o)), (o, o, o)), (o, (o, (o, o, o), o), (o, o, o)), (o, (o, o, (o, o, (o, o, o))), o), (o, (o, o, (o, (o, o, o), o)), o), (o, (o, (o, o, o), (o, o, o)), o), (o, (o, (o, o, (o, o, o)), o), o), (o, (o, (o, (o, o, o), o), o), o)]

Ecrire une fonction parcours(t) renvoyant les mots de Dyck associés aux arbres par un parcours préfixe.

In [33]:
def parcours(t):
    # votre code ici
    if t == o: return ''
    return 'a'+ parcours(t[1])+'b'+ parcours(t[2])
In [34]:
map(parcours, bintrees(5))
Out[34]:
['abababab',
 'ababaabb',
 'abaabbab',
 'abaababb',
 'abaaabbb',
 'aabbabab',
 'aabbaabb',
 'aababbab',
 'aaabbbab',
 'aabababb',
 'aabaabbb',
 'aaabbabb',
 'aaababbb',
 'aaaabbbb']
In [ ]: