ENS Informatique Fondamentale (Maths Info) MP 2013Sujet

(Durée : 4 heures)

La rigueur et la qualité de la rédaction seront prises en compte dans l'évaluation de chaque question, en particulier celles faisant intervenir des quantificateurs et des récurrences.

Ce sujet comprend 7 pages numérotées de 1 à 7 .

Nous allons étudier les langages associés à deux classes d'objets discrets : les langages reconnus par un graphe, et les langages construits à partir de l'itération de règles de réécriture appelées substitutions. Dans les deux cas, nous allons estimer le taux de croissance de la fonction qui comptabilise le nombre d'éléments du langage ayant une longueur donnée. Pour cela, il faudra prouver l'existence et calculer l'entropie du langage.

Dans la première partie, nous introduirons le concept de fonction de complexité pour le langage reconnu par un graphe.

Dans une deuxième partie, nous démontrerons une version restreinte du théorème de PerronFrobenius. Il s'agira de comprendre comment le quadrant positif d'un espace euclidien est transformé par l'action d'une matrice à coefficients positifs. Nous nous limiterons volontairement au cas des matrices carrées de taille 2 .

Dans la troisième partie, nous utiliserons le théorème de Perron-Frobenius pour montrer que la fonction de complexité du langage reconnu par un graphe fortement connexe croît exponentiellement vite. Dans la quatrième partie, nous montrerons, au contraire, que la fonction de complexité du langage associé à une substitution est plutôt de nature linéaire. Dans la dernière partie, nous majorerons plus finement le taux de croissance linéaire d'une substitution donnée.

Les parties 1 et 2 sont indépendantes. La partie 3 dépend des parties 1 et 2 . La partie 4 dépend de la partie 2 . La partie 5 dépend de la partie 4 .

Si M est une matrice, (M)_(i, j) désigne le coefficient d'indice (i, j) de M, où i indique la ligne correspondante de la matrice et j sa colonne.

La notation log désigne la fonction logarithme en base 2.

Soit A un ensemble fini non vide. A^∗ désigne l'ensemble des suites finies d'éléments de A, qui sont appelées mots sur l'alphabet A. Les mots finis non vides sont indexés à partir de 1 , ils sont de la forme w = (w_k)_(1 ⩽ k ⩽ n), où w_k ∈ A. On les notera w = w_1…w_n. L'entier n est alors la longueur du mot, notée |w|. L'unique mot de longueur 0 , appelé mot vide, est noté ε. On conviendra que la notation w_1…w_n dénote ε lorsque n = 0. Si w = w_1…w_n est un mot, tout sous-mot de w constitué de lettres consécutives - de la forme w_k…w_(k + p) - est appelé facteur de w. Tout début de w, de la forme w_1…w_p, est appelé préfixe de w. Toute fin de w, de la forme w_p…w_n, est appelée suffixe de w. Le mot vide ε est donc un facteur, un préfixe et un suffixe de tout mot fini.

Un langage est une partie de A^∗. La fonction de complexité f_L d'un langage L comptabilise le nombre d'éléments de longueur n dans L :

Un graphe orienté fini G est la donnée d'un ensemble fini de sommets A = {1, 2…, r}, et d'un ensemble fini d'arêtes E ⊂ A^2. En particulier, tout sommet i d'un graphe peut avoir une arête le joignant à lui-même. On supposera dans la suite qu'un graphe a au moins 2 sommets, c'est-à-dire r ⩾ 2. On désigne par φ, ψ : E → A les deux applications qui associent respectivement à toute arête sa source et sa cible : φ associe à l'arête (i, j) le sommet i, et ψ lui associe le sommet j. La matrice d'adjacence du graphe G est la matrice carrée M de taille r telle que (M)_(i, j) = 1 si et seulement si le couple (i, j) est dans E; autrement dit, si et seulement s'il existe une arête e de source i(φ(e) = i) et de cible j(ψ(e) = j).

Soit k ⩾ 1 un entier. Un chemin de longueur k de source i et de cible j est une suite ( e_1, …, e_k ) d'arêtes, telles que φ(e_1) = s, ψ(e_t) = φ(e_(t + 1)) pour tout 1 ⩽ t < k et ψ(e_k) = j. En particulier, un chemin peut passer plusieurs fois par une même source ou une même arête. Un graphe est dit fortement connexe si, pour tout couple de sommets (i, j) ∈ A^2, il existe un chemin de source i et de cible j.

Pour tout chemin (e_1, …, e_k) du graphe G, on appelle codage du chemin dans A le mot φ(e_1)…φ(e_k)ψ(e_k) ∈ A^∗. Ce mot énumère dans l'ordre les sommets parcourus par le chemin. Ainsi, un chemin de longueur k est codé par un mot de longueur k + 1. Un cycle est un chemin dont la cible est égale à la source.

Les chemins de longueur 0 sont tous les chemins vides associés à un sommet du graphe : ils ne parcourent aucune arête. Ils sont codés par le nom de leur sommet, et il y en a exactement r. Les cycles de longueur 1 relient un sommet i à lui-même, et leur codage est ii.

Le langage du graphe G, noté L(G), est l'ensemble des codages de chemins finis de G. La fonction de complexité du graphe, notée f_G, est celle de son langage.

Question 1.1. On appelle graphe complet sur r lettres le graphe de sommets A = {1, …, r} dont l'ensemble d'arêtes est égal à E = A^2. Donner, en la justifiant, la fonction de complexité du graphe complet sur r lettres.

Question 1.2. Soit G un graphe à r sommets A = {1, 2…, r} et tel que tout sommet est la source d'exactement k arêtes. Quelle est la fonction de complexité de ce graphe? Le justifier.

Question 1.3. Soit G un graphe à r sommets A = {1, 2…, r}, et M sa matrice d'adjacence.
(a). Montrer que le nombre de chemins de longueur k ⩾ 1 dans le graphe d'un sommet i à un sommet j est égal à (M^k)_(i, j), le coefficient d'indice (i, j) de la k-ème puissance de la matrice d'adjacence du graphe.
(b). En déduire que :

(c). Exprimer le nombre de cycles de longueur n dans le graphe G en fonction des coefficients des puissances de M.

Question 1.4. On considère le graphe présenté dans la Figure 1.
(a). Donner, en le justifiant, le langage de ce graphe.
(b). Soient λ > 1 et μ < 1 les valeurs propres de la matrice d'adjacence M de ce graphe. Montrer que

(c). En déduire que la suite (1/nlogf_G(n))_(n ⩾ 1) admet une limite, et expliciter cette limite.

Une matrice M est irréductible si et seulement si pour tout couple d'indice ( i, j ), il existe une puissance de M dont le coefficient d'indice ( i, j ) est strictement positif.

Question 2.1. Montrer qu'un graphe est fortement connexe si et seulement si sa matrice d'adjacence est irréductible.

On note ℍ = ℝ^+ × ℝ^+le quadrant supérieur droit du plan euclidien. Le plan euclidien est muni de la norme 1 définie par ‖((w_1)/(w_2))‖ = |w_1| + |w_2|. Pour tout t ∈ ℝ, on note v_t = (t/(1 − t)).

(a). Soit M = (a, b; c, d) une matrice irréductible à coefficients positifs ou nuls. Montrer que b > 0 et c > 0.
(b). Montrer que v_0 et v_1 ne sont pas des vecteurs propres de M.
(c). Soit t ∈ [0, 1] fixé. Montrer qu'il existe un unique f(t) ∈ [0, 1] tel que (Mv_t)/(‖Mv_t‖) = v_(f(t)).

(a). Montrer qu'il existe t_0 tel que (Mv_(t_0))/(‖Mv_(t_0)‖) = v_(t_0). En déduire que v_(t_0) est un vecteur propre de M à coordonnées strictement positives.
(b). On note λ_M la valeur propre de M associée au vecteur propre v_(t_0). Montrer que λ_M est une racine simple du polynôme caractéristique de M.

(a). Montrer qu'il existe deux constantes c_0, d_0 > 0 telles que pour tout entier n ⩾ 0,

(b). Soit μ une autre valeur propre de M. En comparant |μ|^n et d_0(λ_M)^n, montrer que |μ| ⩽ λ_M.
(c). Soit w un vecteur propre de M avec des coefficients strictement positifs. Montrer qu'il est proportionnel à v_(t_0).

On appelle λ_M la valeur propre de Perron-Frobenius de M et v_λ son vecteur propre de PerronFrobenius. Nous venons de montrer que λ_M domine toutes les valeurs propres en module, et que v_λ est unique à multiplication près par un scalaire. Il s'agit du théorème de Perron-Frobenius, qui est vrai en toute dimension finie.

Un cas particulier du théorème de Perron-Frobenius est celui des matrices dites primitives, c'est à dire celles qui admettent une puissance dont tous les coefficients sont strictement positifs.

(a). Une matrice primitive est-elle irréductible? Justifier la réponse.
(b). Une matrice irréductible est-elle primitive ? Justifier la réponse.

Question 2.6. On suppose que M = (a, c; b, d) est une matrice primitive à coefficients entiers positifs ou nuls. On note λ_M la valeur propre de Perron-Frobenius de M.
(a). Soit μ la deuxième racine du polynôme caractéristique de M. Montrer que μ est une valeur propre réelle de M et que |μ| < λ_M.
(b). Soit v ∈ ℍ un vecteur non nul. En étudiant la projection de v sur le sous-espace propre associé à λ, montrer que la suite (λ_M)^(− n)M^n v converge vers un vecteur non nul que l'on explicitera.

Cette convergence des suites (λ_M)^(− n)M^n v vers des vecteurs appartenant à une droite uniquement déterminée par la matrice est à la base de nombreuses applications algorithmiques, dont la plus fameuse est le classement de pages web par des moteurs de recherche. Dans la suite, nous allons nous concentrer sur l'application de ces résultats à l'étude des langages associés à des objets discrets.

Dans cette partie, nous allons utiliser le théorème de Perron-Frobenius pour montrer que la fonction de complexité du langage d'un graphe admet un taux de croissance exponentiel.

Question 3.1. Soit (a_n)_(n ⩾ 1) une suite de réels positifs ou nuls tels que a_(m + n) ⩽ a_m + a_n pour tous m, n ⩾ 1.
(a). Montrer que pour tous k, m ∈ ℕ^∗, et tout j ∈ ℕ avec j < k, on a

(b). Montrer que la suite ((a_n)/n)_(n ⩾ 1) converge vers inf{(a_n)/n, n ⩾ 1}.

Question 3.2. Soit G un graphe fortement connexe et f_G sa fonction de complexité.
(a). Montrer que la suite (1/nlogf_G(n))_(n ⩾ 1) est bien définie et admet une limite.
(b). Que vaut cette limite pour un graphe complet sur deux sommets?
(c). Que vaut cette limite dans le cas du graphe de Fibonacci décrit dans la Figure 1?

Pour un graphe G fortement connexe, on appelle entropie de G le taux de croissance logarithmique de la fonction de complexité de son langage :

Question 3.3. Soit G un graphe fortement connexe sur deux sommets. Soit λ_G la plus grande valeur propre de la matrice d'adjacence de G. Monter que l'entropie de G est égale à logλ_G.

Plus généralement, on admet que l'entropie d'un graphe fortement connexe (de taille quelconque) est égale au logarithme de la valeur propre dominante de sa matrice d'adjacence.

Question 3.4. Le nombre log3/2 est-il l'entropie d'un graphe fortement connexe? Donner une justification.

Question 3.5. Soit M = (a, c; b, d) une matrice irréductible et inversible, à coefficients entiers positifs ou nuls. On associe à M une matrice carrée à coefficients dans {0, 1} de taille a + b + c + d comme suit :

(a). Montrer que N est la matrice d'adjacence d'un graphe fortement connexe.
(b). Soit ( λ_1, λ_2 ) un vecteur propre de M. Construire un vecteur propre de N pour la même valeur propre.
(c). Montrer que les valeurs propres non nulles de N sont celles de M.

Question 3.6. Construisez un graphe fortement connexe qui admet log√2 pour entropie.

(a). Construisez un graphe fortement connexe qui admet log(3 − √2) pour entropie.
(b). Ce graphe est-il unique?

On introduit maintenant un nouveau type de langage : celui engendré par une substitution sur deux lettres. Il s'agit d'une règle de transformation σ qui associe aux deux lettres 1 et 2 des mots finis non vides sur {1, 2} : σ(1) = W_1 et σ(2) = W_2. On étend σ par concaténation : σ(VW) = σ(V)σ(W) pour tous V, W ∈ {1, 2}^∗.

La matrice d'incidence M_σ de la substitution est définie comme suit : (M_σ)_(i, j) comptabilise le nombre d'occurrences de la lettre i dans σ(j). Par exemple, la matrice d'incidence de la substitution définie par σ(1) = 1222 et σ(2) = 1 est (1, 1; 3, 0).

On suppose que σ(1) commence par 1 . On note L(p) l'ensemble des facteurs de σ^p(1). Le langage associé à la substitution est

Question 4.1. Soit n > 0 et p un entier tel que

(a). Montrer que L(q) ⊂ L(q + 1) pour tout entier q ⩾ 1.
(b). Montrer que pour tout w ∈ L de longueur n, il existe a, b ∈ {1, 2} tel que w est un facteur de σ^p(ab).
(c). Montrer que f_L(n) ⩽ 8max{|σ^p(1)|, |σ^p(2)|}, où f_L désigne la fonction de complexité de L.

Question 4.2. On suppose que la matrice M_σ est primitive.
(a). Soit V un mot sur l'alphabet {1, 2}^∗ et l(V) le vecteur qui comptabilise les nombres de 1 et 2 dans le mot V. Montrer que l(σ(V)) = M_σ l(V).
(b). Exprimer la longueur du mot |σ^n(1)| en fonction de M_σ.
(c). En utilisant le théorème de Perron-Frobenius, montrer qu'il existe λ > 0 et deux constantes α, β > 0 tels que pour tout entier p assez grand,

(a). Montrer que la fonction de complexité du langage d'une substitution primitive sur deux lettres vérifie f_L(n) ⩽ Kn avec K > 0.
(b). En déduire que lim1/nlogf_L(n) existe et donner sa valeur.

Par analogie avec le cas des graphes, nous avons donc montré que l'entropie du langage associé à une substitution primitive sur deux lettres est nulle. On admet plus généralement que ce résultat est vrai pour toute substitution primitive sur n lettres.

Question 4.4. Soit n > 0. Montrer que le langage d'un graphe sur n sommets dont la matrice d'adjacence est primitive et inversible ne peut pas être égal au langage d'une substitution primitive sur n lettres.

On considère maintenant la substitution définie par σ(1) = 12 et σ(2) = 21. Comme dans la partie 4, on désigne par L le langage engendré par les facteurs des mots σ^n(1). On sait avec la question 4.3 que la fonction de complexité f_L est majorée par une suite linéaire. Le but de cette partie va être d'estimer plus précisément le coefficient de cette suite linéaire.

Question 5.1. Soit un mot W ∈ L. Montrer que W s'écrit sous la forme

− V ∈ L,

Question 5.2. Soit W ∈ L un mot de longueur au moins 5.
(a). Montrer que W admet comme facteur le mot 11 ou le mot 22.
(b). Montrer l'unicité du triplet (A, V, B) introduit à la question 5.1 pour décomposer W.

Question 5.3. Soit f_L la fonction de complexité de L. Soit n > 0.
(a). Montrer que f_L(1) = 2 et f_L(2) = 4.
(b). Soit p_0(n) l'ensemble des éléments W ∈ L de longueur n dont la décomposition introduite à la question 5.1 est de la forme W = σ(V) ou W = σ(V)B. Montrer que pour tout entier n, on a p_0(2n) = f_L(n) et p_0(2n + 1) = f_L(n + 1).
(c). Soit p_1(n) l'ensemble des éléments W ∈ L de longueur n dont la décomposition introduite à la question 5.1 est de la forme W = Aσ(V) ou W = Aσ(V)B, avec A ≠ ε. Exprimer p_1(2n) et p_1(2n + 1) en fonction de f_L(n) et f_L(n + 1).

Question 5.4. Soit f_L la fonction de complexité de L. Soit n > 0.
(a). Montrer que si n ⩾ 3, alors n se décompose sous la forme n = 2^r + q + 1 avec r ⩾ 0 et 0 < q ⩽ 2^r. Montrer que cette décomposition est unique.
(b). Montrer que pour tout entier qui se décompose sous la forme n = 2^r + q + 1, on a

(c). En déduire que f_L(n) ⩽ 4n pour tout entier n.