(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 est une matrice, désigne le coefficient d'indice de , où indique la ligne correspondante de la matrice et sa colonne.

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

Soit un ensemble fini non vide. désigne l'ensemble des suites finies d'éléments de , qui sont appelées mots sur l'alphabet . Les mots finis non vides sont indexés à partir de 1 , ils sont de la forme , où . On les notera . L'entier est alors la longueur du mot, notée . L'unique mot de longueur 0 , appelé mot vide, est noté . On conviendra que la notation dénote lorsque . Si est un mot, tout sous-mot de constitué de lettres consécutives - de la forme - est appelé facteur de . Tout début de , de la forme , est appelé préfixe de . Toute fin de , de la forme , est appelée suffixe de . Le mot vide est donc un facteur, un préfixe et un suffixe de tout mot fini.

Un langage est une partie de . La fonction de complexité d'un langage comptabilise le nombre d'éléments de longueur dans :

Un graphe orienté fini est la donnée d'un ensemble fini de sommets , et d'un ensemble fini d'arêtes . En particulier, tout sommet 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 . On désigne par les deux applications qui associent respectivement à toute arête sa source et sa cible : associe à l'arête le sommet , et lui associe le sommet . La matrice d'adjacence du graphe est la matrice carrée de taille telle que si et seulement si le couple est dans ; autrement dit, si et seulement s'il existe une arête de source et de cible .

Soit un entier. Un chemin de longueur de source et de cible est une suite ( ) d'arêtes, telles que pour tout et . 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 , il existe un chemin de source et de cible .

Pour tout chemin du graphe , on appelle codage du chemin dans le mot . Ce mot énumère dans l'ordre les sommets parcourus par le chemin. Ainsi, un chemin de longueur est codé par un mot de longueur . 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 . Les cycles de longueur 1 relient un sommet à lui-même, et leur codage est .

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

Question 1.1. On appelle graphe complet sur lettres le graphe de sommets dont l'ensemble d'arêtes est égal à . Donner, en la justifiant, la fonction de complexité du graphe complet sur lettres.

Question 1.2. Soit un graphe à sommets et tel que tout sommet est la source d'exactement arêtes. Quelle est la fonction de complexité de ce graphe? Le justifier.

Question 1.3. Soit un graphe à sommets , et sa matrice d'adjacence.
(a). Montrer que le nombre de chemins de longueur dans le graphe d'un sommet à un sommet est égal à , le coefficient d'indice de la -ème puissance de la matrice d'adjacence du graphe.
(b). En déduire que :

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

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 et les valeurs propres de la matrice d'adjacence de ce graphe. Montrer que

(c). En déduire que la suite admet une limite, et expliciter cette limite.

Une matrice est irréductible si et seulement si pour tout couple d'indice ( ), il existe une puissance de dont le coefficient d'indice ( ) 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 . Pour tout , on note .

(a). Soit une matrice irréductible à coefficients positifs ou nuls. Montrer que et .
(b). Montrer que et ne sont pas des vecteurs propres de .
(c). Soit fixé. Montrer qu'il existe un unique tel que .

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

(a). Montrer qu'il existe deux constantes telles que pour tout entier ,

(b). Soit une autre valeur propre de . En comparant et , montrer que .
(c). Soit un vecteur propre de avec des coefficients strictement positifs. Montrer qu'il est proportionnel à .

On appelle la valeur propre de Perron-Frobenius de et son vecteur propre de PerronFrobenius. Nous venons de montrer que domine toutes les valeurs propres en module, et que 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 est une matrice primitive à coefficients entiers positifs ou nuls. On note la valeur propre de Perron-Frobenius de .
(a). Soit la deuxième racine du polynôme caractéristique de . Montrer que est une valeur propre réelle de et que .
(b). Soit un vecteur non nul. En étudiant la projection de sur le sous-espace propre associé à , montrer que la suite converge vers un vecteur non nul que l'on explicitera.

Cette convergence des suites 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 une suite de réels positifs ou nuls tels que pour tous .
(a). Montrer que pour tous , et tout avec , on a

(b). Montrer que la suite converge vers .

Question 3.2. Soit un graphe fortement connexe et sa fonction de complexité.
(a). Montrer que la suite 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 fortement connexe, on appelle entropie de le taux de croissance logarithmique de la fonction de complexité de son langage :

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

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 est-il l'entropie d'un graphe fortement connexe? Donner une justification.

Question 3.5. Soit une matrice irréductible et inversible, à coefficients entiers positifs ou nuls. On associe à une matrice carrée à coefficients dans de taille comme suit :

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

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

(a). Construisez un graphe fortement connexe qui admet 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 et . On étend par concaténation : pour tous .

La matrice d'incidence de la substitution est définie comme suit : comptabilise le nombre d'occurrences de la lettre dans . Par exemple, la matrice d'incidence de la substitution définie par et est .

On suppose que commence par 1 . On note l'ensemble des facteurs de . Le langage associé à la substitution est

Question 4.1. Soit et un entier tel que

(a). Montrer que pour tout entier .
(b). Montrer que pour tout de longueur , il existe tel que est un facteur de .
(c). Montrer que , où désigne la fonction de complexité de .

Question 4.2. On suppose que la matrice est primitive.
(a). Soit un mot sur l'alphabet et le vecteur qui comptabilise les nombres de 1 et 2 dans le mot . Montrer que .
(b). Exprimer la longueur du mot en fonction de .
(c). En utilisant le théorème de Perron-Frobenius, montrer qu'il existe et deux constantes tels que pour tout entier assez grand,

(a). Montrer que la fonction de complexité du langage d'une substitution primitive sur deux lettres vérifie avec .
(b). En déduire que 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 lettres.

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

On considère maintenant la substitution définie par et . Comme dans la partie 4, on désigne par le langage engendré par les facteurs des mots . On sait avec la question 4.3 que la fonction de complexité 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 . Montrer que s'écrit sous la forme

,

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

Question 5.3. Soit la fonction de complexité de . Soit .
(a). Montrer que et .
(b). Soit l'ensemble des éléments de longueur dont la décomposition introduite à la question 5.1 est de la forme ou . Montrer que pour tout entier , on a et .
(c). Soit l'ensemble des éléments de longueur dont la décomposition introduite à la question 5.1 est de la forme ou , avec . Exprimer et en fonction de et .

Question 5.4. Soit la fonction de complexité de . Soit .
(a). Montrer que si , alors se décompose sous la forme avec et . Montrer que cette décomposition est unique.
(b). Montrer que pour tout entier qui se décompose sous la forme , on a

(c). En déduire que pour tout entier .