Projet de Calcul Formel

— Maîtrise d’Informatique —

1 Modalités

Le projet sera écrit en Maple et sera réalisé par binômes (2 personnes). Un dossier comportant le rapport et un listing commenté des programmes écrits sera rendu au secrétariat de la maîtrise. Il sera apporté un soin tout particulier à la lisibilité et à la clarté des programmes.

2 Rappels Mathématiques

2.1 Puissances extérieures d’une matrice

Soit A une matrice n × n et soit p un entier compris entre 1 et n. On appelle p-ième puissance extérieure de A la matrice de dimension C_{n}^{p} × C_{n}^{p} notée ∧^{p}A dont les entrées sont les déterminants mineurs p × p de A. Si l’on indice les lignes et les colonnes de ∧^{p}A par les parties à p éléments de {1, …, n} (ordonnées par un ordre quelconque mais identique pour les lignes et les colonnes), l’élément à l’intersection de la ligne {i_{1}, …, i_{p}} et de la colonne {j_{1}, …, j_{p}} est le mineur obtenu en gardant de la matrice A les lignes d’indices {i_{1}, …, i_{p}} et les colonnes d’indices {j_{1}, …, j_{p}}. Par exemple pour n = 4,

∧^{1}A = A = ( \begin{matrix}a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ a_{41} & a_{42} & a_{43} & a_{44} \end{matrix} )

\begin{aligned}& ∧^{2}A = \\ ( & \begin{matrix}| \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix} | & | \begin{matrix}a_{11} & a_{13} \\ a_{21} & a_{23} \end{matrix} | & | \begin{matrix}a_{11} & a_{14} \\ a_{21} & a_{24} \end{matrix} | & | \begin{matrix}a_{12} & a_{13} \\ a_{22} & a_{23} \end{matrix} | & | \begin{matrix}a_{12} & a_{14} \\ a_{22} & a_{24} \end{matrix} | & | \begin{matrix}a_{13} & a_{14} \\ a_{23} & a_{24} \end{matrix} | \\ | \begin{matrix}a_{11} & a_{12} \\ a_{31} & a_{32} \end{matrix} | & | \begin{matrix}a_{11} & a_{13} \\ a_{31} & a_{33} \end{matrix} | & | \begin{matrix}a_{11} & a_{14} \\ a_{31} & a_{34} \end{matrix} | & | \begin{matrix}a_{12} & a_{13} \\ a_{32} & a_{33} \end{matrix} | & | \begin{matrix}a_{12} & a_{14} \\ a_{32} & a_{34} \end{matrix} | & | \begin{matrix}a_{13} & a_{14} \\ a_{33} & a_{34} \end{matrix} | \\ | \begin{matrix}a_{11} & a_{12} \\ a_{41} & a_{42} \end{matrix} | & | \begin{matrix}a_{11} & a_{13} \\ a_{41} & a_{43} \end{matrix} | & | \begin{matrix}a_{11} & a_{14} \\ a_{41} & a_{44} \end{matrix} | & | \begin{matrix}a_{12} & a_{13} \\ a_{42} & a_{43} \end{matrix} | & | \begin{matrix}a_{12} & a_{14} \\ a_{42} & a_{44} \end{matrix} | & | \begin{matrix}a_{13} & a_{14} \\ a_{43} & a_{44} \end{matrix} | \\ | \begin{matrix}a_{21} & a_{22} \\ a_{31} & a_{32} \end{matrix} | & | \begin{matrix}a_{21} & a_{23} \\ a_{31} & a_{33} \end{matrix} | & | \begin{matrix}a_{21} & a_{24} \\ a_{31} & a_{34} \end{matrix} | & | \begin{matrix}a_{22} & a_{23} \\ a_{32} & a_{33} \end{matrix} | & | \begin{matrix}a_{22} & a_{24} \\ a_{32} & a_{34} \end{matrix} | & | \begin{matrix}a_{23} & a_{24} \\ a_{33} & a_{34} \end{matrix} | \\ | \begin{matrix}a_{21} & a_{22} \\ a_{41} & a_{42} \end{matrix} | & | \begin{matrix}a_{21} & a_{23} \\ a_{41} & a_{43} \end{matrix} | & | \begin{matrix}a_{21} & a_{24} \\ a_{41} & a_{44} \end{matrix} | & | \begin{matrix}a_{22} & a_{23} \\ a_{42} & a_{43} \end{matrix} | & | \begin{matrix}a_{22} & a_{24} \\ a_{42} & a_{44} \end{matrix} | & | \begin{matrix}a_{23} & a_{24} \\ a_{43} & a_{44} \end{matrix} | \\ | \begin{matrix}a_{31} & a_{32} \\ a_{41} & a_{42} \end{matrix} | & | \begin{matrix}a_{31} & a_{33} \\ a_{41} & a_{43} \end{matrix} | & | \begin{matrix}a_{31} & a_{34} \\ a_{41} & a_{44} \end{matrix} | & | \begin{matrix}a_{32} & a_{33} \\ a_{42} & a_{43} \end{matrix} | & | \begin{matrix}a_{32} & a_{34} \\ a_{42} & a_{44} \end{matrix} | & | \begin{matrix}a_{33} & a_{34} \\ a_{43} & a_{44} \end{matrix} | \end{matrix} & ) \end{aligned}

\begin{aligned}& ∧^{3}A = \\ ( & \begin{matrix}| \begin{matrix}a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{matrix} | & | \begin{matrix}a_{11} & a_{12} & a_{14} \\ a_{21} & a_{22} & a_{24} \\ a_{31} & a_{32} & a_{34} \end{matrix} | & | \begin{matrix}a_{11} & a_{13} & a_{14} \\ a_{21} & a_{23} & a_{24} \\ a_{31} & a_{33} & a_{34} \end{matrix} | & | \begin{matrix}a_{12} & a_{13} & a_{14} \\ a_{22} & a_{23} & a_{24} \\ a_{32} & a_{33} & a_{34} \end{matrix} | \\ | \begin{matrix}a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{41} & a_{42} & a_{43} \end{matrix} | & | \begin{matrix}a_{11} & a_{12} & a_{14} \\ a_{21} & a_{22} & a_{24} \\ a_{41} & a_{42} & a_{44} \end{matrix} | & | \begin{matrix}a_{11} & a_{13} & a_{14} \\ a_{21} & a_{23} & a_{24} \\ a_{41} & a_{43} & a_{44} \end{matrix} | & | \begin{matrix}a_{12} & a_{13} & a_{14} \\ a_{22} & a_{23} & a_{24} \\ a_{42} & a_{43} & a_{44} \end{matrix} | \\ | \begin{matrix}a_{11} & a_{12} & a_{13} \\ a_{31} & a_{32} & a_{33} \\ a_{41} & a_{42} & a_{43} \end{matrix} | & | \begin{matrix}a_{11} & a_{12} & a_{14} \\ a_{31} & a_{32} & a_{34} \\ a_{41} & a_{42} & a_{44} \end{matrix} | & | \begin{matrix}a_{11} & a_{13} & a_{14} \\ a_{31} & a_{33} & a_{34} \\ a_{41} & a_{43} & a_{44} \end{matrix} | & | \begin{matrix}a_{12} & a_{13} & a_{14} \\ a_{32} & a_{33} & a_{34} \\ a_{42} & a_{43} & a_{44} \end{matrix} | \\ | \begin{matrix}a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ a_{41} & a_{42} & a_{43} \end{matrix} | & | \begin{matrix}a_{21} & a_{22} & a_{24} \\ a_{31} & a_{32} & a_{34} \\ a_{41} & a_{42} & a_{44} \end{matrix} | & | \begin{matrix}a_{21} & a_{23} & a_{24} \\ a_{31} & a_{33} & a_{34} \\ a_{41} & a_{43} & a_{44} \end{matrix} | & | \begin{matrix}a_{22} & a_{23} & a_{24} \\ a_{32} & a_{33} & a_{34} \\ a_{42} & a_{43} & a_{44} \end{matrix} | \end{matrix} & ) \end{aligned}

∧^{4}A = ( | \begin{matrix}a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ a_{41} & a_{42} & a_{43} & a_{44} \end{matrix} | )

2.2 Automates

On suppose fixé un ensemble fini A appelé alphabet. Les éléments de cet ensemble sont appelés les lettres. Une suite finie de lettres s’appelle un mot sur l’alphabet A.

Un automate est un triplet A = (Q, A, E) où Q est un ensemble fini d’états, A est l’alphabet et E est un sous-ensemble de Q × A × Q appelé l’ensemble des transitions. Les automates considérés ici ne comportent ni états initiaux ni états finaux. Un automate est généralement représenté par un diagramme. Les états sont alors représentés par des cercles et les transitions par des arcs (ou flèches) étiquetés.

1  2 ab  a, c

Figure 1: Un automate

Exemple 1 L’automate A = (Q, A, E) où

Q = {1, 2}, A = {a, b, c} et E = {(1, a, 2), (2, b, 1), (2, a, 2), (2, c, 2)}

est représenté à la figure 1

Un automate peut aussi être représenté sous forme matricielle. La matrice M associée à un automate A = (Q, A, E) est de dimension n × n où n est le cardinal de Q. Les lignes et les colonnes de la matrice M sont indicées par les éléments de Q. L’élément m_{p,q} de M où p et q appartiennent à Q est un polynôme homogène de degré 1 en les lettres de l’alphabet. Il est égal à la somme des lettres a de A telles que (p, a, q) soit une transition de l’automate A.

Exemple 2 La matrice associée à l’automate de la figure 1 est égale à

( \begin{matrix}0 & a \\ b & a + c \end{matrix} )

Plus généralement, à toute matrice dont les éléments sont des polynômes homogènes de degré 1 à coefficients quelconques, on associe un automate dont les flèches sont étiquetées par les lettres munies d’un coefficient. Il s’agit alors d’un automate avec multiplicités. Les automates classiques (ceux définis précédemment) correspondent au cas où tous les coefficients sont 0 ou 1 (1 si la transition existe et 0 sinon).

1  2 a 2b  −2a, c

Figure 2: Un automate avec multiplicités

Exemple 3 L’automate de la figure 2 est associé à la matrice ( \begin{matrix}0 & a \\ 2b & −2a + c \end{matrix} ).

2.3 Puissances extérieures d’un automate

Étant donné un automate A = (Q, A, E) et un entier k compris entre 1 et |Q|, on définit l’automate ∧^{k}A appelé k-ième puissance extérieure de A. On suppose que les états de Q sont totalement ordonnés. Les états de l’automate ∧^{k}A sont alors les suites strictement croissantes de longueur k d’éléments de Q. Les transitions sont étiquetées par des lettres munies d’un coefficient appartenant à {0, −1, 1}. A tout choix de k transitions de A

(p_{1}, a, q_{1}), …, (p_{k}, a, q_{k})

de l’automate A telles que les p_{1} < ⋯ < p_{k} et que les q_{i} soient distincts, on associe la transition de ∧^{k}A

((p_{1}, …, p_{k}), εa, (σ(q_{1}), …, σ(q_{k})))

où la permutation σ de Q dans Q est telle que σ(q_{1}) < ⋯ < σ(q_{k}). Le coefficient ε ∈ {−1, 1} est alors égal à la signature de la permutation σ. Dans le cas où l’automate A est avec multiplicités, la multiplicité de la transition de ∧^{k}A est égale au produit εα_{1} … α_{k} où les α_{i} sont les multiplicités respectives des transitions (p_{i}, α_{i}a, q_{i}).

1  2  3 b  a a  c  a d

Figure 3: Automate A

Exemple 4 On considère l’automate de la figure 3. Les deuxième et troisième puissances extérieures de cet automate sont données aux figures 4 et 5

1, 2  1, 3  2, 3 −a  a a

Figure 4: Puissance extérieure d’ordre 2 de A

\begin{aligned}& 1, 2, 3 \\ −a \end{aligned}

Figure 5: Puissance extérieure d’ordre 3 de A

2.4 Fonction zêta d’un automate

La fonction ζ_{A} associée à un automate A, est une série formelle en les lettres de l’alphabet donnée par la formule

ζ_{A} = ∏_{i=1}^{n} (det(I − Q_{i}))^{(−1)^{i}}  (1)

où la matrice Q_{i} désigne la matrice associée à la i-ième puissance extérieure de l’automate A et I désigne la matrice identité de même dimension que Q_{i}. En fait, la fonction ζ peut être directement définie de façon algébrique sur le langage reconnu par l’automate. On démontre alors que la fonction ζ peut être calculée par la formule 1 (cf. [Béa95]).

Exemple 5 Pour l’automate de la figure 3, on a

det(I − Q_{1}) = 1 − a − b − a^{2} + ab + a^{3} − acd
det(I − Q_{2}) = (1 + a)(1 − a^{2})
det(I − Q_{3}) = 1 + a

et la fonction zêta est égale à ζ_{A} = \frac{1 − a^{2}}{1 − a − b − a^{2} + ab + a^{3} − acd}.

3 Travail demandé

• Écrire une fonction calculant la puissance extérieure d’une matrice.

• Exprimer de façon matricielle la puissance extérieure d’un automate.

• Écrire une fonction calculant de façon matricielle la puissance extérieure d’un automate.

• Écrire une fonction calculant la fonction ζ d’un automate.

Références

[Béa93] Marie-Pierre Béal. Codage symbolique. Masson, 1993.

[Béa95] Marie-Pierre Béal. Puissance extérieure d’un automate déterministe, application au calcul de la fonction zêta d’un système sofique. R.A.I.R.O.-Informatique Théorique et Applications, 1995.