Forêts de factorisation : semi-groupes finis, langages réguliers et algorithmes de recherche infixe efficaces
Afficher ou masquer la section
Le sujet établit un théorème fondamental de théorie des langages formels : tout mot admet, pour un morphisme vers un semi-groupe fini, un arbre de factorisation de hauteur constante indépendante de sa longueur. Il commence par relier semi-groupes finis et langages réguliers, définit les arbres de factorisation, puis démontre le théorème dans deux cas particuliers, celui des groupes cycliques et celui du semi-groupe de Brandt, avant d'exploiter ce résultat pour construire un algorithme efficace testant l'appartenance de nombreux facteurs d'un mot à un langage régulier.
1Partie I : semi-groupesOn définit les semi-groupes, les éléments neutres et idempotents, les morphismes de semi-groupes, et on établit la correspondance entre langages réguliers et morphismes vers un semi-groupe fini.
2Partie II : forêts de factorisationOn définit la notion d'arbre de factorisation d'un mot pour un morphisme de semi-groupe, avec sa règle spécifique d'idempotence, et on énonce le théorème central garantissant l'existence d'un arbre de hauteur bornée par une constante ne dépendant que du semi-groupe.
3Partie III : cas des groupesOn démontre le théorème central dans le cas particulier d'un morphisme vers le groupe cyclique Z/kZ, par récurrence sur le nombre de valeurs prises par les préfixes du mot.
4Partie IV : semi-groupe de BrandtOn démontre le théorème central dans le cas particulier du semi-groupe de Brandt, formé de matrices élémentaires, en décomposant le mot autour des occurrences d'un facteur fixé.
5Partie V : recherche infixeOn construit un algorithme calculant efficacement, à partir d'un arbre de factorisation, l'appartenance d'un grand nombre de facteurs d'un mot à un langage régulier donné.
Ces sujets peuvent vous intéresser
Pas encore de corrigé pour ce sujet : voici des sujets proches corrigés.
VENDREDI 18 AVRIL 2025
14h00-18h00
FILIERE MP etMPI - EPREUVE n ^∘10
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 A et B, on note B^A l'ensemble des fonctions de A dans B.
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 u ⋅ v la concaténation des mots u, v ∈ Σ^∗. La longueur d'un mot u sera notée |u|.
On notera u[1], …, u[n] les lettres d'un mot u de longueur n. Pour tous indices 1 ≤ i ≤ j ≤ n, on notera u[i, …, j] le mot formé des lettres u[i], …, u[j]. On dit qu'un mot x est un facteur de u s'il existe des indices i et j tels que x = u[i, …, j].
On notera bien que dans ce sujet, les mots sont indicés à partir de 1 et que le facteur w[i, …, j] d'un mot w contient la lettre w[i] et la lettre w[j].
Exemple 1. Sur l'alphabet Σ = {a, b}, le mot u = aaba est de longueur |u| = 4. Ses lettres sont u[1] = a, u[2] = a, u[3] = b et u[4] = a. Le facteur u[1, …, 4] est le mot u lui-même, le facteur u[2, …, 3] est le mot ab et le facteur u[2, …, 4] 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 ( S, ⋅ ) est un magma associatif, c'est-à-dire un ensemble S muni d'une loi interne «•» associative : a ⋅ (b ⋅ c) = (a ⋅ b) ⋅ c pour tous a, b, c ∈ S. Un semi-groupe ( S, ⋅ ) est dit fini si l'ensemble S est fini. La taille d'un semi-groupe fini ( S, ⋅ ) est le cardinal |S| de S. Dans la suite, on notera l'opération « ⋅ » sous forme multiplicative, c'est-à-dire a ⋅ b = ab. 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 x d'un semi-groupe S est neutre (ou identité) si xy = yx = y pour tout y ∈ S. On dit qu'un élément e d'un semi-groupe S est idempotent si e^2 = e. 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 X un ensemble. On note T(X) le semi-groupe ( X^X, 9^∘ ) où g est définie pour tous f, g ∈ X^X^∘ par f ∘ g = g ∘ f (ainsi, f ∘ g est la fonction qui à x ∈ X associe g(f(x)) ∈ X. On prêtera attention à l'ordre de composition inversé par rapport à o. On appelle T(X) le semi-groupe de transition sur X.
Exemple 4. Soit X = {a, b}. On peut remarquer que T(X) = {id, f, g, h} est un semi-groupe, où id est la fonction identité, f(a) = b et f(b) = a, g(a) = g(b) = a, et h(a) = h(b) = b.
Question 2. Montrer que dans l'exemple précédent, id est neutre, et g est idempotent mais pas neutre.
On note 𝔹 le sous-ensemble {id, f} de T(X), où f et X sont définis comme dans l'exemple 4 .
Question 3. Montrer que ( 𝔹, 9^∘ ) est un semi-groupe dont on donnera la table de multiplication.
Dans toute la suite, on identifiera 𝔹 avec l'ensemble des booléens {0, 1}, en identifiant « 0 » avec id et « 1 » avec f. On remarque alors que la loi interne interne % est l'opérateur «OU exclusif », noté ⊕ et défini par 1 ⊕ 0 = 0 ⊕ 1 = 1 et 0 ⊕ 0 = 1 ⊕ 1 = 0.
Soient (S, ⋅) et (T, ⋆) deux semi-groupes. Un morphisme de semi-groupe est une application φ : S → T qui préserve la loi interne : φ(x ⋅ y) = φ(x)⋆φ(y) pour tous x, y ∈ S.
Exemple 5. Soit Σ = {a, b}. La fonction Ψ_a : Σ^∗ → (𝔹, ⊕) est définie pour tout mot w ∈ Σ^∗ par
On admettra que Ψ_a est un morphisme de semi-groupe.
Question 4. Montrer que Ψ_a(w) = 0 si, et seulement si, w contient un nombre pair de a.
Soit A = (Q, q_0, δ, F) 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 δ : Q × Σ → Q. On étend δ en une fonction δ^∗ : Q × Σ^∗ → Q définie récursivement par δ^∗(q, ε) = q et δ^∗(q, wσ) = δ(δ^∗(q, w), σ) pour tous q ∈ Q, w ∈ Σ^∗ et σ ∈ Σ. On admettra l'identité suivante : pour tous u, v ∈ Σ^∗ et q ∈ Q.
δ^∗(q, uv) = δ^∗(δ^∗(q, u), v)
On note L le langage reconnu par l'automate A. On pose
T(A) = T(Q), F^′ = {f ∈ Q^Q : f(q_0) ∈ F}
De plus, on définit une fonction ψ : Σ^∗ → T(A) comme suit. Étant donné un mot w ∈ Σ^∗, on définit ψ(w) ∈ T(A) comme étant la fonction de Q vers Q qui à q ∈ Q associe δ^∗(q, w). Ainsi, ψ(w)(q) = δ^∗(q, w).
Question 5. Montrer que ψ est un morphisme de semi-groupe de Σ^∗ dans T(A).
Question 6. Montrer que ψ^(− 1)(F^′) ⊆ L.
Question 7. Montrer que L ⊆ ψ^(− 1)(F^′).
On a donc L = ψ^(− 1)(F^′). 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 L ⊆ Σ^∗ est un langage régulier si et seulement s'il existe semi-groupe fini ( S, ⋅ ), un ensemble F ⊆ S et un morphisme de semi-groupe φ : Σ^∗ → S tels que φ^(− 1)(F) = L.
Partie II. Forêts de factorisation
Soit Σ un alphabet, ( S, ⋅ ) un semi-groupe et φ : Σ^+ → S un morphisme de semi-groupe.
Un arbre de factorisation d'un mot w ∈ Σ^+(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 w = w_1 w_2, avec w_1, w_2 ∈ Σ^+non vides. Soient A_1 et A_2 des arbres de factorisation de w_1 et w_2 respectivement. Alors l'arbre dont la racine est étiquetée par w = w_1 w_2 et qui possède deux enfants A_1 et A_2, est un arbre de factorisation de w :
Règle de l'idempotence : Considérons un mot w = w_1…w_n, avec w_1, …, w_n ∈ Σ^+non vides et n ≥ 3. On suppose que φ(w_1) = ⋯ = φ(w_n) est un élément idempotent de S. Soient A_1, …, A_n des arbres de factorisation de w_1, …, w_n respectivement. Alors l'arbre dont la racine est w = w_1…w_n et qui possède n enfants A_1, …, A_n, est un arbre de factorisation de w :
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 w (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 w dans un arbre, on écrira w/φ(w) afin de faciliter les raisonnements sur la règle de l'idempotence.
Exemple 6. Soit Ψ_a définie à l'exemple 5 page 2 . On rappelle que Ψ_a(w) = 0 si w contient un nombre pair de a, et Ψ_a(w) = 1 sinon. On va donner des exemples d'arbres de factorisation pour Ψ_a. Regardons quelques exemples de mots :
u = ab : on applique le deuxième cas de la définition avec w_1 = a et w_2 = b. Ainsi, w_1 et w_2 sont des lettres et u = w_1 w_2. En appliquant deux fois le premier cas de la définition, on obtient l'arbre de factorisation suivant pour u = ab :
On notera que Ψ_a(a) = 1, Ψ_a(b) = 0 et Ψ_a(ab) = 0.
2. w = bbaa : on peut appliquer le dernier cas de la définition avec w_1 = b, w_2 = b et w_3 = aa. Ceci est possible car Ψ_a(w_1) = Ψ_a(w_2) = Ψ_a(w_3) = 0 est idempotent (règle de l'idempotence). Pour w_3, on utilise ensuite un arbre de factorisation similaire à celui vu plus haut pour u = ab.
On obtient alors l'arbre :
Question 8. Donner un arbre de factorisation pour w = bbaa qui est différent de celui de l'exemple 6.
Considérons le mot aaa. Puisque, Ψ_a(a) = 1 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 A_1, …, A_k de hauteurs respectives h_1, …, h_k, l'arbre formé par une racine dont les enfants sont A_1, …, A_k est de hauteur 1 + max(h_1, …, h_k).
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 y = ababbbbaa.
On peut vérifier que pour tout morphisme de semi-groupe φ : Σ^+ → S et tout mot w ∈ Σ^+, on peut trouver un arbre de factorisation de hauteur au plus ⌈log_2|w|⌉ 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 S 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 S mais pas de la longueur de w.
Théorème 1. Soit Σ un alphabet, ( S, ⋅ ) un semi-groupe fini et φ : Σ^+ → S un morphisme de semigroupe. Alors pour tout mot non vie w ∈ Σ^+, il existe un arbre de factorisation T_w de w pour φ de hauteur au plus 3|S|. De plus, il existe un algorithme qui sur tout mot w ∈ Σ^+calcule T_w en temps A|w|, où A 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 k ≥ 1, on identifie ℤ/kℤ avec l'ensemble {0, …, k − 1}. On rappelle que ( ℤ/kℤ, + ) est un groupe où « + » est l'addition modulo k. L'inverse d'un élément x ∈ ℤ/kℤ sera noté « − x». On admettra que 0 est l'unique élément idempotent de ( ℤ/kℤ, + ). On remarque que l'addition modulo 2 se comporte comme la « OU » exclusif ⊕. On pourra ainsi identifier ℤ/2ℤ avec 𝔹 (voir page 2 ).
Dans cette partie, Σ est un alphabet fixé et k ≥ 2 un entier fixé. On pose S = (ℤ/kℤ, +) et on se donne un morphisme de semi-groupe φ : Σ^+ → S quelconque. Pour chaque mot w ∈ Σ^+,
P(w) = {φ(w[1, …, j]) : 1 ≤ j ≤ |w| − 1}
est l'ensemble des valeurs par φ des préfixes stricts de w (c'est-à-dire des préfixes non vides de w qui ne sont pas égaux à w ). On notera bien que ε et w ne sont pas des préfixes stricts de w.
Exemple 8. En identifiant ℤ/2ℤ et 𝔹, la fonction Ψ_a définie à l'exemple 5 (page 2 ) peut être vue comme une fonction Ψ_a : Σ^∗ → ℤ/2ℤ. Prenons w = bbaa. Alors
Question 11. On se place dans le contexte de l'exemple 8. Soit w = b^(10)a (dix «b» suivis d'un «a»). Donner P(w). On justifiera la réponse.
On revient au cas général d'un morphisme de semi-groupe φ : Σ^+ → S où S = ℤ/kℤ avec k ≥ 2, et où Σ est un alphabet quelconque.
Question 12. Montrer que pour tous mots x, y ∈ Σ^+, on a φ(y) = φ(xy) − φ(x).
Pour p = 0, …, k, on note H(p) la proposition suivante:
« Pour tout mot w ∈ Σ^+tel que |P(w)| ≤ p, il existe un arbre de factorisation de hauteur au plus 3p.»
Question 13. Montrer que H(0) est vraie.
Prenons p ∈ {1, …, k} et supposons que H(p − 1) est vraie. Soit t ∈ P(w) et notons j_1 < ⋯ < j_ℓ les indices tels que φ(w[1, …, j_i]) = t pour i = 1, …, ℓ. On a ainsi {j : φ(w[1, …, j]) = t} = {j_1, …, …, j_ℓ}. On notera bien que ℓ > 0 puisque t ∈ P(w). Écrivons alors
Notons que dans l'écriture ci-dessus, il est possible que ℓ = 1 et donc que w = xy.
Question 14. Montrer que pour tout i = 1, …, ℓ − 1, on a φ(v_i) = 0.
Question 15. Montrer que |P(x)| < |P(w)|.
Question 16. Soit i = 1, …, ℓ − 1. Montrer que |P(v_i)| < |P(w)|.
On admettra que |P(y)| < |P(w)| par un raisonnement similaire à celui de la question 16.
Question 17. Montrer que H(p) est vraie.
Question 18. En déduire que pour tout mot w ∈ Σ^+, il existe un arbre de factorisation de w pour φ de hauteur au plus 3|S|.
Partie IV. Semi-groupe de Brandt
Nous nous intéressons à un autre cas particulier du Théorème 1. On fixe un entier naturel n ≥ 1 et on définit le semi-groupe de Brant ( B_n, ⋅ ) par
B_n = {0_n} ∪ {M_(i, j) : i, j ∈ {1, …, n}}
où ^« ⋅ ^⋅ > est la multiplication de matrices, 0_n est la matrice identiquement zéro de taille n × n, et M_(i, j) est la matrice de taille n × n dont l'entrée ( i, j ) vaut 1 , et dont toutes les autres entrées sont nulles (l'entrée (i, j) est ligne i et colonne j ). Par exemple
Ainsi B_n est bien un semi-groupe.
Question 19. Montrer que x ∈ B_n est idempotent si, et seulement si, x = 0 ou x ∈ {M_(i, i) : i = 1, …, n}.
Question 20. Soient Σ = {a, b} et φ : Σ^+ → B_2 définie par φ(a) = M_(1, 2) et φ(b) = M_(2, 1). Montrer que pour tout mot w ∈ Σ^+, on a φ(w) = M_(1, 1) si et seulement si w ∈ (ab)^+.
Question 21. Soient Σ et φ définis comme à la question 20 . Montrer que tout mot de (ab)^+admet un arbre de factorisation pour φ de hauteur au plus 2 .
Question 22. Soit n ≥ 1. Montrer que pour tous A, B, x ∈ B_n, on a AB, AxB ∈ {0_n, M_(A, B)} où M_(A, B) ∈ B_n est une matrice qui ne dépend que de A et B (et pas de x ) dont on explicitera la valeur. Montrer que si de plus BA ≠ 0_n, alors M_(A, B) est idempotent.
Prenons φ : Σ^+ → B_n un morphisme de semi-groupe et un mot w ∈ Σ^+de longueur |w| ≥ 2. On suppose que φ(w) ≠ 0_n et on décompose w de la façon suivante:
w = a bu_1 a bu_2…a bu_(k + 1)
où a, b ∈ Σ sont des lettres, k ≥ 0 et où les mots u_1, …, u_(k + 1) ∈ Σ^∗ ne contiennent pas le facteur ab. On prêtera attention au fait que les mots u_i peuvent être vides et qu'on peut avoir a = b.
Exemple 9. Soit Σ = {a, b, c}. Le mot w = ababcaaabc 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 w ∈ Σ^+de longueur |w| ≥ 2 et tel que φ(w) ≠ 0_n.
Question 23. Soit 1 ≤ i ≤ k. Montrer que φ(bu_i a) est un élément idempotent dont la valeur ne dépend pas de u_i.
Supposons que k > 0 et que tous les u_i sont non vides. Soient A_1, …, A_(k + 1) des arbres de factorisation de u_1, …, u_(k + 1) respectivement.
Question 24. Donner un arbre de factorisation de w de hauteur au plus 5 + max(h_1, …, h_(k + 1)), où h_i désigne la hauteur de A_i pour 1 ≤ i ≤ k + 1. On justifiera qu'il s'agit bien d'un arbre de factorisation.
Les autres cas ( k = 0, un ou plusieurs u_i sont vides) peuvent être traités de manière similaire. On admettra que l'on peut obtenir un arbre de factorisation de w de hauteur au plus
5 + max(h_1, …h_(k + 1)) où h_i = {hauteur de A_i, si u_i ≠ ε,; 0, sinon.
Afin d'obtenir les arbres A_1, …, A_(k + 1), on voit que l'on peut procéder récursivement de la même manière puisque φ(u_i) ≠ 0_n, en tant que facteur de w. Cette récurrence est bien fondée car |u_i| < |w|.
Question 25. Montrer qu'il existe une constante C ne dépendant que de Σ et telle que tout mot w ∈ Σ^+ avec φ(w) ≠ 0_n, admet un arbre de factorisation de hauteur au plus C.
Partie V. Recherche infixe
Dans cette partie, on fixe un alphabet Σ et langage régulier L ⊆ Σ^+. On rappelle que l'on numérote les lettres à partir de l'indice 1 et que pour tout w ∈ Σ^+, et indices 1 ≤ i ≤ j ≤ |w|, on note w[i, …, j] le facteur w[i]…w[j]. Dans cette partie, on admettra le Théorème 1.
Considérons le problème suivant :
Entrée : un mot w ∈ Σ^+et une paire d'indice ( i, j ) tels que 1 ≤ i ≤ j ≤ |w|.
Sortie : «OUI» si le facteur w[i, …, j] appartient à L, «NON» sinon.
Exemple 10. Prenons Σ = {a, b} et le langage L = {w ∈ Σ^+ : w contient un nombre pair de a}. Considérons les cas suivants :
entrée w = aababb et (i, j) = (1, 2) : la sortie est OUI car w[1, …, 2] = aa ∈ L,
entrée w = aababb et (i, j) = (3, 5) : la sortie est NON car w[3, …, 5] = bab ∉ L,
entrée w = abba et (i, j) = (1, 4) : la sortie est OUI car w[1, …, 4] = abba ∈ L.
Le problème qui nous intéresse est le suivant, que l'on appellera RECHERCHE-INFIXE _L :
Entrée : un mot w ∈ Σ^+et une liste de paires d'indices I = [(i_1, j_1); …; (i_n, j_n)] tels que pour tout k ∈ {1, …, n}, on a 1 ≤ i_k ≤ j_k ≤ |w|.
Sortie : une liste (b_1, …, b_n) où b_k = OUI si le facteur w[i_k, …, j_k] appartient à L, sinon b_k = NON.
Exemple 11. Prenons Σ = {a, b} et le langage L = {w ∈ Σ^+ : w contient un nombre pair de a}. On considère l'entrée donnée par le mot w = aababb et la liste [(1, 2), (3, 5), (1, 4), (2, 6)] (de longueur n = 4 ). La sortie attendue est donc (OUI, NON, NON, OUI) car :
w[1, …, 2] = aa, qui appartient bien à L, − w[3, …, 5] = bab, qui n'appartient pas à L, − w[1, …, 4] = aaba, qui n'appartient pas à L, − w[2, …, 6] = ababb, qui appartient bien à L.
On cherche d'abord à donner une solution simple mais peu efficace à ce problème. Pour ce faire, prenons un AFDA = (Q, q_0, δ, F) qui reconnaît le langage L. Comme L est fixé, A est aussi fixé. En particulier, |Q| est une constante du problème. On supposera dans la suite que l'on peut calculer δ(q, σ) en temps constant pour tout q ∈ Q et toute lettre σ ∈ Σ.
Soit w ∈ Σ^∗ un mot. Le tableau T_w est défini pour tous 1 ≤ i ≤ j ≤ |w| et pour tout q ∈ Q par
T_w[q, i, j] = δ^∗(q, w[i, …, j])
Question 26. Donner un algorithme qui calcule _w en temps O(|Q| ⋅ |w|^2).
Question 27. Donner un algorithme qui résout toute instance ( w, I ) de RECHERCHE-INFIXE _L en temps O(|Q| ⋅ |w|^2 + n), où n est la longueur de la liste I. 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 ( S, ⋅ ) donné par le Lemne 1 (page 3) appliqué à L. Ainsi, il existe un ensemble F ⊆ S et un morphisme de semi-groupe φ : Σ^+ → S tel que φ^(− 1)(F) = L. Puisque S est fini et ne dépend que de L qui est fixé, on suppose dans la suite que l'on peut multiplier deux élèments de Q avec «•» en temps constant. Par le Théorème 1, pour chaque mot w ∈ Σ^+, il existe un arbre de factorisation T_w de w pour φ. De plus, T_w est de hauteur au plus 3|S| et il existe un algorithme qui calcule T_w en temps O(|w|).
Dans toute la suite on suppose que l'on dispose des fonctions Racine, Indices, Enfants, Val et EnfantIndice décrites ci-dessous.
Racine (w) renvoie, pour tout w ∈ Σ^+, un arbre de factorization T_w de w pour φ.
Soit w ∈ Σ^+un mot et T_w l'arbre de factorisation renvoyé par Racine ( w ). Si un noeud n de T_w correspond au facteur w[i, …, j] de w et possède N enfants alors
Indices ( n ) renvoie la paire ( i, j ),
Enfant ( n, ℓ ) renvoie, pour tout rang 1 ≤ ℓ ≤ N, le ℓ-ième enfant de n,
Val(n) renvoie φ(w[i, …, j]),
EnfantIndice ( n, k ) renvoie, pour tout indice 1 ≤ i ≤ j, le rang ℓ de l'unique enfant de n qui contient l'indice k, c'est-à-dire l'unique ℓ tel que Indices(Enfant (n, ℓ) ) = (i^′, j^′) avec i^′ ≤ k ≤ j^′. Si n 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 Ψ_a de l'exemple 5 (page 2), un arbre de factorisation du mot w = aba 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 e et f, on a Enfant(Racine, 1) = e et Enfant(Racine, 2 ) = f.
La racine correspond au mot entier, c'est-à-dire à w = w[1, …, 3] donc Indices(Racine)=(1,3).
La valeur de la racine est Ψ_a(aba) = 0 donc Val( Racine ) = 0.
L'enfant gauche e correspond au facteur w[1, …, 2] = ab donc Indices (e) = (1, 2).
L'enfant droit f correspond au facteur w[3, …, 3] = a donc Indices (f) = (3, 3).
Enfin, EnfantIndice(Racine,1)=EnfantIndice(Racine,2)=1 puisque le premier enfant de la racine (f) correspond à la plage d'indices (1, 2). D'autre part, EnfantIndice(Racine, 3) = 2 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 w ∈ Σ^+un mot et T_w l'arbre de factorisation renvoyé par Racine (w). La figure 1 page 11 présente l'algorithme CalculePhi (n, i, j) où n est un nœud de T_w tel que Indices (n) = (I, J) avec I ≤ i ≤ j ≤ J. On se propose de montrer que CalculePhi (n, i, j) renvoie φ(w[i, …, j]). À cette fin, étant donné un nœud n de T_w, on considère la proposition
HR_w(n) : «Pour tous indices (i, j) tels que I ≤ i ≤ j ≤ J, avec(I, J) = Indices(n), on a; CalculePhi (n, i, j) = φ(w[i, …, j]).»
Question 29. Montrer que HR_w(n) est vraie pour tout mot w ∈ Σ^+et pour toute feuille n de T_w.
Fixons un mot w. On montre HR_w(n) par induction sur la hauteur du nœud n dans l'arbre T_w. Considérons un nœud n qui n'est pas une feuille et supposons que HR_w(f) est vraie pour tout enfant f de n. On cherche à montrer que HR_w(n) est vraie. Pour cela, prenons ( i, j ) tels que I ≤ i ≤ j ≤ J, avec (I, J) = Indices (n).
Question 30. Montrer que si l'algorithme atteint la ligne 13, alors v_f = φ(w[i, …, p]).
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 v_d = φ(w[q, …, j]) à 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 φ(w[i, …, j]).
On admet que les autres cas de la preuve se traitent de façon similaire et que HR_w(n) est donc vraie.
Question 32. Montrer que pour tous 1 ≤ i ≤ j ≤ |w|, CalculePhi(Racine( w ), i, j ) s'exécute en temps O(2^h) où h est la hauteur T_w.
Question 33. En déduire qu'il existe une constante A, qui ne dépend que de L, telle que pour chaque w ∈ Σ^+, si l'arbre T_w est donné alors on peut calculer φ(w[i, …, j] en temps A pour tous i et j.
Question 34. Donner un algorithme pour RECHERCHE-INFIXE _L, qui résout toute instance ( w, I ) en temps O(|w| + |I|).
Questions fréquentes
4 questions
Sur quels chapitres porte le sujet Info Fondamentale MP MPI des ENS 2025 ?
Afficher ou masquer la section
Sur quels chapitres porte le sujet Info Fondamentale MP MPI des ENS 2025 ?
+
Il porte sur les automates finis et les langages réguliers, les structures algébriques comme les semi-groupes, les arbres et la récursivité, ainsi que sur l'analyse de complexité d'algorithmes.
Les parties du sujet sont-elles indépendantes ?
+
Les parties I et II doivent être traitées en premier, car elles posent les définitions utilisées ensuite. Les parties III, IV et V sont indépendantes entre elles et peuvent être traitées dans n'importe quel ordre.
Ce sujet nécessite-t-il d'écrire du code informatique ?
+
Oui, certaines questions, notamment dans la partie V, demandent de donner un algorithme en pseudo-code et d'en justifier la complexité temporelle.
Faut-il connaître la théorie des automates avant d'aborder ce sujet ?
+
Des notions de base sur les automates finis déterministes sont utilisées dans la partie I, mais l'essentiel du sujet porte sur les structures de semi-groupes et les arbres de factorisation, qui sont entièrement définis dans l'énoncé.
.jpg)
.jpg)
.jpg)
.jpg)
