VENDREDI 18 AVRIL 2025
14h00-18h00
FILIERE MP etMPI - EPREUVE n
INFO-FONDAMENTALE (ULSR)
Durée : 4 heures
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve
Forêts de factorisation
Le sujet comporte 12 pages, numérotées de 1 à 12.
Préliminaires
Étant donnés deux ensembles et , on note l'ensemble des fonctions de dans .
Dans ce sujet, un alphabet est toujours un ensemble fini dont les éléments sont appelés des lettres. Étant donné un alphabet , on notera l'ensemble des mots finis sur . On notera le mot vide par . On notera aussi l'ensemble des mots finis non vides sur . On notera la concaténation des mots . La longueur d'un mot sera notée .
On notera les lettres d'un mot de longueur . Pour tous indices , on notera le mot formé des lettres . On dit qu'un mot est un facteur de s'il existe des indices et tels que .
On notera bien que dans ce sujet, les mots sont indicés à partir de 1 et que le facteur d'un mot contient la lettre et la lettre .
Exemple 1. Sur l'alphabet , le mot aaba est de longueur . Ses lettres sont et . Le facteur est le mot lui-même, le facteur est le mot ab et le facteur est le mot aba.
Lorsque du code est demandé, on écrira la solution en pseudo-code ou dans un langage de programmation au choix de la candidate ou du candidat. On pourra s'inspirer de la syntaxe suivante, donnée à titre indicatif
Fonction PremiersFibonacci(n)
début
fib $\longleftarrow$ tableau de $n$ entiers initialisés
fib $[1] \longleftarrow 1$
$\mathrm{fib}[2] \longleftarrow 1$
pour tout les $k$ allant de 3 àn faire
$\mathrm{fib}[k] \longleftarrow \mathrm{fib}[k-2]+\mathrm{fib}[k-1]$
renvoyer fib
Les parties I et II sont à traiter en premier. Les parties III, IV et V sont indépendantes et peuvent être traitées dans n'importe quel ordre.
Partie I. Semi-groupes
Un semi-groupe ( ) est un magma associatif, c'est-à-dire un ensemble muni d'une loi interne «•» associative : pour tous . Un semi-groupe ( ) est dit fini si l'ensemble est fini. La taille d'un semi-groupe fini ( ) est le cardinal de . Dans la suite, on notera l'opération « » sous forme multiplicative, c'est-à-dire . Notons que tout groupe est un semi-groupe. Voici d'autres exemples de semi-groupes.
Exemple 2. L'ensemble des entiers naturels muni de la multiplication est un semi-groupe. Ce même ensemble muni de l'addition est aussi un semi-groupe.
Exemple 3. Soit un alphabet. L'opération de concaténation sur les mots est associative. Ainsi, ( ) et ( ) sont des semi-groupes. Dans la suite, ces semi-groupes seront notés et respectivement.
On dit qu'un élément d'un semi-groupe est neutre (ou identité) si pour tout . On dit qu'un élément d'un semi-groupe est idempotent si . Tout élément identité est idempotent mais l'inverse n'est pas nécessairement vrai.
Question 1. Montrer que dans tout semi-groupe, s'il existe un élément neutre alors il est unique.
Soit un ensemble. On note le semi-groupe ( ) où par (ainsi, est la fonction qui à associe . On prêtera attention à l'ordre de composition inversé par rapport à o. On appelle le semi-groupe de transition sur .
Exemple 4. Soit . On peut remarquer que est un semi-groupe, où id est la fonction identité, et , et .
Question 2. Montrer que dans l'exemple précédent, id est neutre, et est idempotent mais pas neutre.
On note le sous-ensemble de , où et sont définis comme dans l'exemple 4 .
Question 3. Montrer que ( ) est un semi-groupe dont on donnera la table de multiplication.
Dans toute la suite, on identifiera avec l'ensemble des booléens , en identifiant « 0 » avec id et « 1 » avec . On remarque alors que la loi interne interne % est l'opérateur «OU exclusif », noté et défini par et .
Soient et deux semi-groupes. Un morphisme de semi-groupe est une application qui préserve la loi interne : pour tous .
Exemple 5. Soit . La fonction est définie pour tout mot par
On admettra que est un morphisme de semi-groupe.
Question 4. Montrer que si, et seulement si, contient un nombre pair de a.
Soit un automate fini déterministe (AFD). On suppose sans perte de généralité que l'automate est complet, c'est-à-dire que la fonction de transition est de la forme . On étend en une fonction définie récursivement par et pour tous et . On admettra l'identité suivante : pour tous et .
On note le langage reconnu par l'automate . On pose
De plus, on définit une fonction comme suit. Étant donné un mot , on définit comme étant la fonction de vers qui à associe . Ainsi, .
Question 5. Montrer que est un morphisme de semi-groupe de dans .
Question 6. Montrer que .
Question 7. Montrer que .
On a donc . Dans toute la suite, on admettra le résultat suivant qui établit une correspondance entre langages réguliers et semi-groupes finis.
Lemme 1. Soit un alphabet. Un ensemble est un langage régulier si et seulement s'il existe semi-groupe fini ( ), un ensemble et un morphisme de semi-groupe tels que .
Partie II. Forêts de factorisation
Soit un alphabet, ( ) un semi-groupe et un morphisme de semi-groupe.
Un arbre de factorisation d'un mot (pour ) est un arbre étiqueté par qui satisfait les conditions suivantes.
L'arbre de factorisation d'une lettre est constitué d'une racine sans enfants étiquetée par cette lettre :
Considérons un mot , avec non vides. Soient et des arbres de factorisation de et respectivement. Alors l'arbre dont la racine est étiquetée par et qui possède deux enfants et , est un arbre de factorisation de :
Règle de l'idempotence : Considérons un mot , avec non vides et . On suppose que est un élément idempotent de . Soient des arbres de factorisation de respectivement. Alors l'arbre dont la racine est et qui possède enfants , est un arbre de factorisation de :
On prêtera attention à plusieurs points de cette définition :
on ne s'intéresse qu'aux mots non vides,
il peut exister plusieurs arbres de factorisation pour un même mot (voir exemples plus bas),
l'ordre des enfants d'un nœud est important,
lorsqu'un nœud possède trois enfants ou plus (dernier cas), il doit vérifier la règle de l'idempotence.
On utilisera les conventions graphiques suivantes:
une double barre horizontale indiquera une application de la règle de l'idempotence (voir cas 2 de l'exemple 6 ci-dessous);
lorsque l'on écrit un nœud dans un arbre, on écrira afin de faciliter les raisonnements sur la règle de l'idempotence.
Exemple 6. Soit définie à l'exemple 5 page 2 . On rappelle que si contient un nombre pair de a, et sinon. On va donner des exemples d'arbres de factorisation pour . Regardons quelques exemples de mots :
: on applique le deuxième cas de la définition avec et . Ainsi, et sont des lettres et . En appliquant deux fois le premier cas de la définition, on obtient l'arbre de factorisation suivant pour :
On notera que et .
2. : on peut appliquer le dernier cas de la définition avec et . Ceci est possible car est idempotent (règle de l'idempotence). Pour , on utilise ensuite un arbre de factorisation similaire à celui vu plus haut pour .
On obtient alors l'arbre :
Question 8. Donner un arbre de factorisation pour bbaa qui est différent de celui de l'exemple 6.
Considérons le mot aaa. Puisque, n'est pas idempotent dans le semi-groupe , il n'est pas possible d'appliquer la règle de l'idempotence. Autrement dit, l'arbre suivant n'est pas un arbre de factorisation de aaa.
cet arbre n'est pas valide
Question 9. Donner un arbre de factorisation de aaa.
Question 10. Donner un arbre de factorisation de aaaaaa (six «a») qui utilise la règle de l'idempotence.
On associe à un arbre de factorisation sa hauteur, définie de la façon suivante :
un arbre constitué uniquement d'une racine sans enfants est de hauteur 0 ,
pour tous arbres de hauteurs respectives , l'arbre formé par une racine dont les enfants sont est de hauteur .
Exemple 7. Poursuivons l'exemple 6. L'arbre de factorisation de ab est de hauteur 1, celui de bbaa est de hauteur 2. Un exemple plus complexe est l'arbre de hauteur 3 donné ci-dessous pour ababbbbaa.
On peut vérifier que pour tout morphisme de semi-groupe et tout mot , on peut trouver un arbre de factorisation de hauteur au plus en coupant le mot en deux à chaque étage de l'arbre. Il n'est pas clair à priori qu'il soit possible de faire mieux en général. Un résultat surprenant et fondamental est que si est fini, alors il est en fait toujours possible de trouver un arbre de factorisation de hauteur constante, c'est-à-dire qui ne dépend que de mais pas de la longueur de .
Théorème 1. Soit un alphabet, ( ) un semi-groupe fini et un morphisme de semigroupe. Alors pour tout mot non vie , il existe un arbre de factorisation de pour de hauteur au plus . De plus, il existe un algorithme qui sur tout mot calcule en temps , où est une constante qui ne dépend que de S .
Partie III. Cas des groupes
Nous allons démontrer un cas particulier du Théorème 1. Pour tout entier , on identifie avec l'ensemble . On rappelle que ( ) est un groupe où est l'addition modulo . L'inverse d'un élément sera noté . On admettra que 0 est l'unique élément idempotent de ( ). On remarque que l'addition modulo 2 se comporte comme la « OU » exclusif . On pourra ainsi identifier avec (voir page 2 ).
Dans cette partie, est un alphabet fixé et un entier fixé. On pose et on se donne un morphisme de semi-groupe quelconque. Pour chaque mot ,
est l'ensemble des valeurs par des préfixes stricts de (c'est-à-dire des préfixes non vides de qui ne sont pas égaux à ). On notera bien que et ne sont pas des préfixes stricts de .
Exemple 8. En identifiant et , la fonction définie à l'exemple 5 (page 2 ) peut être vue comme une fonction . Prenons bbaa. Alors
Question 11. On se place dans le contexte de l'exemple 8. Soit (dix «b» suivis d'un «a»). Donner . On justifiera la réponse.
On revient au cas général d'un morphisme de semi-groupe où avec , et où est un alphabet quelconque.
Question 12. Montrer que pour tous mots , on a .
Pour , on note la proposition suivante:
« Pour tout mot tel que , il existe un arbre de factorisation de hauteur au plus .»
Question 13. Montrer que est vraie.
Prenons et supposons que est vraie. Soit et notons les indices tels que pour . On a ainsi . On notera bien que puisque . Écrivons alors
Notons que dans l'écriture ci-dessus, il est possible que et donc que .
Question 14. Montrer que pour tout , on a .
Question 15. Montrer que .
Question 16. Soit . Montrer que .
On admettra que par un raisonnement similaire à celui de la question 16.
Question 17. Montrer que est vraie.
Question 18. En déduire que pour tout mot , il existe un arbre de factorisation de pour de hauteur au plus .
Partie IV. Semi-groupe de Brandt
Nous nous intéressons à un autre cas particulier du Théorème 1. On fixe un entier naturel et on définit le semi-groupe de Brant ( ) par
où est la multiplication de matrices, est la matrice identiquement zéro de taille , et est la matrice de taille dont l'entrée ( ) vaut 1 , et dont toutes les autres entrées sont nulles (l'entrée est ligne et colonne ). Par exemple
On admettra l'identité suivante pour tous :
Ainsi est bien un semi-groupe.
Question 19. Montrer que est idempotent si, et seulement si, ou .
Question 20. Soient et définie par et . Montrer que pour tout mot , on a si et seulement si .
Question 21. Soient et définis comme à la question 20 . Montrer que tout mot de admet un arbre de factorisation pour de hauteur au plus 2 .
Question 22. Soit . Montrer que pour tous , on a où est une matrice qui ne dépend que de et (et pas de ) dont on explicitera la valeur. Montrer que si de plus , alors est idempotent.
Prenons un morphisme de semi-groupe et un mot de longueur . On suppose que et on décompose de la façon suivante:
où sont des lettres, et où les mots ne contiennent pas le facteur ab. On prêtera attention au fait que les mots peuvent être vides et qu'on peut avoir .
Exemple 9. Soit . Le mot se décompose comme en (3) en écrivant
On revient au cas général d'une décomposition comme en (3) d'un mot de longueur et tel que .
Question 23. Soit . Montrer que est un élément idempotent dont la valeur ne dépend pas de .
Supposons que et que tous les sont non vides. Soient des arbres de factorisation de respectivement.
Question 24. Donner un arbre de factorisation de de hauteur au plus , où désigne la hauteur de pour . On justifiera qu'il s'agit bien d'un arbre de factorisation.
Les autres cas ( , un ou plusieurs sont vides) peuvent être traités de manière similaire. On admettra que l'on peut obtenir un arbre de factorisation de de hauteur au plus
Afin d'obtenir les arbres , on voit que l'on peut procéder récursivement de la même manière puisque , en tant que facteur de . Cette récurrence est bien fondée car .
Question 25. Montrer qu'il existe une constante ne dépendant que de et telle que tout mot avec , admet un arbre de factorisation de hauteur au plus .
Partie V. Recherche infixe
Dans cette partie, on fixe un alphabet et langage régulier . On rappelle que l'on numérote les lettres à partir de l'indice 1 et que pour tout , et indices , on note le facteur . Dans cette partie, on admettra le Théorème 1.
Considérons le problème suivant :
Entrée : un mot et une paire d'indice ( ) tels que .
Sortie : «OUI» si le facteur appartient à , «NON» sinon.
Exemple 10. Prenons et le langage contient un nombre pair de a. Considérons les cas suivants :
entrée aababb et : la sortie est OUI car aa ,
entrée aababb et : la sortie est NON car bab ,
entrée abba et : la sortie est OUI car abba .
Le problème qui nous intéresse est le suivant, que l'on appellera RECHERCHE-INFIXE :
Entrée : un mot et une liste de paires d'indices tels que pour tout , on a .
Sortie : une liste où OUI si le facteur appartient à , sinon NON.
Exemple 11. Prenons et le langage contient un nombre pair de a. On considère l'entrée donnée par le mot aababb et la liste (de longueur ). La sortie attendue est donc (OUI, NON, NON, OUI) car :
aa, qui appartient bien à , bab, qui n'appartient pas à , aaba, qui n'appartient pas à , ababb, qui appartient bien à .
On cherche d'abord à donner une solution simple mais peu efficace à ce problème. Pour ce faire, prenons un qui reconnaît le langage . Comme est fixé, est aussi fixé. En particulier, est une constante du problème. On supposera dans la suite que l'on peut calculer en temps constant pour tout et toute lettre .
Soit un mot. Le tableau est défini pour tous et pour tout par
Question 26. Donner un algorithme qui calcule en temps .
Question 27. Donner un algorithme qui résout toute instance ( ) de RECHERCHE-INFIXE en temps , où est la longueur de la liste . On justifiera la correction de l'algorithme.
On cherche maintenant à donner une solution efficace à ce problème grâce aux forêts de factorisation.
Prenons le semi-groupe fini ( ) donné par le Lemne 1 (page 3) appliqué à . Ainsi, il existe un ensemble et un morphisme de semi-groupe tel que . Puisque est fini et ne dépend que de qui est fixé, on suppose dans la suite que l'on peut multiplier deux élèments de avec «•» en temps constant. Par le Théorème 1, pour chaque mot , il existe un arbre de factorisation de pour . De plus, est de hauteur au plus et il existe un algorithme qui calcule en temps .
Dans toute la suite on suppose que l'on dispose des fonctions Racine, Indices, Enfants, Val et EnfantIndice décrites ci-dessous.
Racine renvoie, pour tout , un arbre de factorization de pour .
Soit un mot et l'arbre de factorisation renvoyé par Racine ( ). Si un noeud de correspond au facteur de et possède enfants alors
Indices ( ) renvoie la paire ( ),
Enfant ( ) renvoie, pour tout rang , le -ième enfant de ,
renvoie ,
EnfantIndice ( ) renvoie, pour tout indice , le rang de l'unique enfant de qui contient l'indice , c'est-à-dire l'unique tel que Indices(Enfant ) avec . Si n'a aucun enfant alors cette fonction provoque une erreur.
On suppose que toutes ces fonction s'exécutent en temps constant.
Exemple 12. Avec le morphisme de l'exemple 5 (page 2), un arbre de factorisation du mot est le suivant, où l'on a annoté les nœuds de l'arbre avec des flèches pour leur donner des noms :
Faisons quelques remarques sur cet arbre :
Puisque la racine a deux enfants et , on a Enfant(Racine, 1 et Enfant(Racine, 2 ) .
La racine correspond au mot entier, c'est-à-dire à donc Indices(Racine)=(1,3).
La valeur de la racine est donc Racine .
L'enfant gauche correspond au facteur donc Indices .
L'enfant droit correspond au facteur a donc Indices .
Enfin, EnfantIndice(Racine,1)=EnfantIndice(Racine,2)=1 puisque le premier enfant de la racine correspond à la plage d'indices . D'autre part, EnfantIndice(Racine, 3 puisque le deuxième enfant correspond à la plage d'indices ( 3,3 ).
Question 28. Donner les valeurs de Val(e), Val(f), Indices(g), Indices(h), EnfantIndice(e,1) et EnfantIndice(e,2).
Soit un mot et l'arbre de factorisation renvoyé par Racine . La figure 1 page 11 présente l'algorithme CalculePhi où est un nœud de tel que Indices avec . On se propose de montrer que CalculePhi renvoie . À cette fin, étant donné un nœud de , on considère la proposition
Question 29. Montrer que est vraie pour tout mot et pour toute feuille de .
Fixons un mot . On montre par induction sur la hauteur du nœud dans l'arbre . Considérons un nœud qui n'est pas une feuille et supposons que est vraie pour tout enfant de . On cherche à montrer que est vraie. Pour cela, prenons ( ) tels que , avec Indices .
Question 30. Montrer que si l'algorithme atteint la ligne 13, alors .
Fonction CalculePhi $(n, i, j)$
Entrées : : nœud $n$, indices $i \leq j$
Sorties : : la valuer de $\phi(w[i, \ldots, j])$
début
$(I, J) \longleftarrow$ Indices $(n)$
si $i=I$ et $j=J$ alors
renvoyer Val(n)
$\ell \longleftarrow$ Enfant Indice $(n, i)$
$r \longleftarrow$ Enfant Indice $(n, j)$
si $\ell=r$ alors
// $w[i, \ldots, j]$ est contenu dans le $\ell$-ième enfant de $n$
renvoyer CalculePhi (Enfant $(n, \ell), i, j$ )
$f \longleftarrow \operatorname{Enfant}(n, \ell)$
$g \longleftarrow$ Enfant $(n, r)$
$(\ldots, p) \longleftarrow$ Indices $(f)$ //on ignore l'indice de gauche
$\left(q, \_\right) \longleftarrow$ Indices $(g)$ //on ignore l'indice de droite
$v_{f} \longleftarrow$ CalculePhi $(f, i, p)$
$v_{g} \longleftarrow$ CalculePhi $(g, q, j)$
si $\ell=r$ alors
// $w[i, \ldots, j]$ est contenu dans les $\ell$-ième et ( $\ell+1$ )-ième enfants de $n$
renvoyer $v_{f} \cdot v_{g}$
sinon
// $w[i, \ldots, j]$ est contenu dans les enfants des indices $\ell$ à $r$
renvoyer $v_{f} \cdot \operatorname{Val}(\operatorname{Enfant}(n, \ell+1)) \cdot v_{g}$
Figure 1 - L'algorithme CalculePhi
On admettra qu'un raisonnement similaire permet de montrer que sous les mêmes hypothèses, on a à la ligne 14. Nous allons seulement nous intéresser à un cas possible, qui est le plus difficile. Il s'agit du cas où les conditions aux lignes 3,7 et 15 ne sont pas satisfaites. Dans ce cas, l'algorithme va renvoyer une valeur à la ligne 18 .
Question 31. Montrer que si l'algorithme atteint la ligne 18 alors il renvoie .
On admet que les autres cas de la preuve se traitent de façon similaire et que est donc vraie.
Question 32. Montrer que pour tous , CalculePhi(Racine( ), ) s'exécute en temps où est la hauteur .
Question 33. En déduire qu'il existe une constante , qui ne dépend que de , telle que pour chaque , si l'arbre est donné alors on peut calculer en temps pour tous et .
Question 34. Donner un algorithme pour RECHERCHE-INFIXE , qui résout toute instance ( ) en temps .
ENS Informatique Fondamentale (Maths Info) MP MPI 2025 - Version Web LaTeX | WikiPrépa | WikiPrépa
