ENS Informatique Fondamentale (Maths Info) MP PC 2007Sujet et corrigé

L'usage de calculatrices électroniques de poche à alimentation autonome, non imprimantes et sans document d'accompagnement, est autorisé. Cependant, une seule calculatrice à la fois est admise sur la table ou le poste de travail, et aucun échange n'est autorisé entre les candidats.

On appelle alphabet tout ensemble fini non vide. Si A est un alphabet, on appelle ses éléments des lettres. Un mot u sur l'alphabet A est une suite finie de lettres de A. La longueur de cette suite est appelée la longueur du mot, notée |u|. Par exemple, si A = {a, b}, u = aab est un mot de longueur 3 et v = baababa est un mot de longueur 7. Par convention, on considère aussi une suite de longueur 0 , appelée le mot vide et notée 1 . On note A^∗ l'ensemble de tous les mots sur l'alphabet A, y compris le mot vide.

Un ensemble M muni d'une loi de composition interne ⊙ sera noté ( M, ⊙ ) ou simplement M lorsque la loi considérée est sans ambiguïté. Si la loi ⊙ est associative et si M contient un élément neutre pour ⊙( noté 1_M), on dit que (M, ⊙) est un monoïde. Si A est un alphabet, A^∗ muni de la concaténation est un monoïde. On rappelle que la concaténation de deux mots u et v, notée uv, est la suite de lettres qui commence par la suite u et continue avec la suite v. Pour les mots u et v cités en exemple ci-dessus, on a uv = aabbaababa. Si w est un mot et k est un entier strictement positif, on note w^k la concaténation de k copies de w. On peut ainsi écrire u = a^2 b et v = ba(ab)^2 a = ba^2(ba)^2.
Si(M, ⊙) et (N, ⊗) sont des monoïdes, un morphisme φ : M ⟶ N est une application telle que φ(1_M) = 1_N et telle que φ(x⊙y) = φ(x) ⊗ φ(y) pour tout x, y ∈ M. Un isomorphisme est un morphisme bijectif. Un élément x d'un monoïde ( M, ⊙ ) est dit inversible s'il existe y ∈ M tel que x⊙y = y⊙x = 1_M. Dans ce cas, y est unique et est appelé l'inverse de x, noté x^(− 1). Rappelons qu'un groupe est un monoïde dont tout élément est inversible.

On notera card(X) le cardinal d'un ensemble fini X, c'est-à-dire le nombre d'éléments de X.

Dans ce sujet, on étudie les groupes libres. Ces groupes se caractérisent par le fait qu'ils sont entièrement déterminés par un ensemble de générateurs abstraits (ce qui justifie la terminologie, puisqu'ils sont libres de toute relation entre leurs générateurs). On examinera des propriétés élémentaires des groupes libres et quelques problèmes algorithmiques les concernant. On démontrera en particulier que tout sousgroupe d'un groupe libre est lui-même un groupe libre s'il est engendré par un nombre fini d'éléments.

Note : Quand on parle d'algorithmes ici, on demande de préciser les principes d'un algorithme et non de donner du pseudo-code.

Dans cette partie, on reprend quelques propriétés élémentaires des monoïdes et des groupes.
Question 1.1 Soient (M, ⊙) et (N, ⊗) des monoïdes et φ : M ⟶ N un morphisme.
1.1.1 Montrer que si φ est un isomorphisme alors sa réciproque φ^(− 1) : N ⟶ M est un morphisme.
1.1.2 Montrer que si M et N sont des groupes alors, pour tout x ∈ M, φ(x^(− 1)) = (φ(x))^(− 1).

Soit (M, ⊙) un monoïde et N une partie de M. On dit que ( N, ⊙ ) est un sous-monoïde de M si 1_M ∈ N et si pour tout x, y ∈ N, x⊙y ∈ N. Si, de plus, M est un groupe et pour tout x ∈ N, x^(− 1) ∈ N, on dit que ( N, ⊙ ) est un sous-groupe de M.

Question 1.2 Soit R une partie d'un monoïde ( M, ⊙ ).
1.2.1 Soit R^∗ l'ensemble consistant en l'élément neutre 1_M et les produits finis d'éléments de R, c'est- a˙-dire les éléments r_1⊙⋯⊙r_n avec n ≥ 1 et chaque r_i ∈ R. Montrer que R * est un sous-monoïde de M qui est minimal pour l'inclusion parmi tous les sous-monoïdes contenant R.
1.2.2 Si M est un groupe, soit R^(− 1) = {r^(− 1)|r ∈ R}. Montrer alors que (R ∪ R^(− 1))^∗ est un sous-groupe de M qui est minimal pour l'inclusion parmi tous les sous-groupes contenant R.

Dans ce dernier cas, on appelle (R ∪ R^(− 1))^∗ le sous-groupe engendré par R.

Soit A un alphabet. Pour chaque lettre a ∈ A, on introduit une nouvelle lettre a¯ et on note A~ l'alphabet {a|a ∈ A} ∪ {a¯|a ∈ A}. On étend l'application a ↦ a¯ à A~ en posant a¯^– = a pour tout a ∈ A.

Soient u, v ∈ A~^∗. On dit que u se réduit en une étape en v, noté u → ^1 v, si u = u_1 aa¯u_2 avec a ∈ A~, u_1, u_2 ∈ A~^∗ et v = u_1 u_2. Si k ≥ 1, on note u → ^k v s'il existe des mots u_0, …, u_k ∈ A~^∗ tels que u = u_0, v = u_k et u_i → ^1 u_(i + 1) pour i = 0, 1, …, k − 1. On note encore u → ^0 v si u = v, u→−^(≤ k)v s'il existe ℓ ≤ k tel que u → ^ℓ v, et u→−^∞v s'il existe k tel que u → ^k v. Enfin, on dit qu'un mot u ∈ A~^∗ est réduit s'il n'existe aucun mot v tel que u → ^1 v, c'est-à-dire si u ne contient pas deux lettres consécutives de la forme aa¯ avec a ∈ A~. En particulier, le mot vide est réduit.

Question 2.1 Montrer que pour tout mot u ∈ A~^∗, il existe un mot réduit v tel que u→−^∞v. Calculer un tel mot v lorsque u = aba¯ab¯b¯aabb¯a¯a¯aabb¯a¯ab.

Question 2.2 Soient u, x, y ∈ A~^∗. Montrer que si u → ^1 x et u → ^1 y, alors il existe z tel que x→−^(≤ 1)z et y→−^(≤ 1)z.

Question 2.3 Montrer que pour tout mot u ∈ A~^∗, il existe un unique mot réduit v tel que u→−^∞v.
Question 2.4 Donner un algorithme qui, étant donné u ∈ A~^∗, calcule l'unique mot réduit v tel que u→−^∞v. Estimer la complexité (le nombre d'opérations élémentaires) de cet algorithme en fonction de la longueur n = |u|. Essayer de réduire cette complexité autant que possible en ordre de grandeur.

Soit A un alphabet. On note F(A) l'ensemble des mots réduits de A~^∗ et ρ : A~^∗ ⟶ F(A) l'application qui à u ∈ A~^∗ associe ρ(u) l'unique mot réduit tel que u→−^∞ρ(u). On définit une loi de composition interne sur F(A) en posant u⊙v = ρ(uv). Enfin, on étend l'application a ⟼ a¯ à A~^∗ en posant

Question 3.1 Montrer que si u, v, w ∈ A~^∗ alors u⊙(v⊙w) = ρ(uvw). En déduire que (F(A), ⊙) est un groupe et que, pour tout u ∈ F(A), u^(− 1) = u¯.

On appelle F(A) le groupe libre sur A. On appelle groupe libre tout groupe isomorphe à un groupe de la forme F(A).

Question 3.2 Sous quelles hypothèses le groupe F(A) est-il commutatif (c'est-à-dire tel que u⊙v = v⊙u pour tout u, v ∈ F(A) ) ?

Question 3.3 Soit G un groupe et soit φ : A ⟶ G une application. Montrer qu'il existe un et un seul morphisme φ_F : F(A) ⟶ G tel que φ_F(a) = φ(a) pour tout a ∈ A ⊆ F(A).

Dans la situation de la question 3.3, on dit que le morphisme φ_F est induit par l'application φ, ou qu'il la prolonge. Dans la suite, on utilisera librement le résultat de cette question : toute application de A dans un groupe G induit un unique morphisme de F(A) dans G.

Question 3.4 Soit A et B deux alphabets de même cardinal. Montrer que F˙(A) et F(B) sont isomorphes.

Soit X une partie finie non vide de F(A). On dit que X est une base de F(A) s'il existe un alphabet B de même cardinal que X et une bijection φ : B ⟶ X ⊆ F(A) tels que le morphisme φ_F : F(B) ⟶ F(A) induit par φ est un isomorphisme.

Le but de cette partie est de montrer que toutes les bases de F(A) ont le même cardinal.
Question 4.1 Vérifier que A est une base de F(A). Montrer que la condition pour qu'une partie X de F(A) soit une base ne dépend pas du choix de l'alphabet B et de la bijection φ.

Question 4.2 Supposons que A = {a, b}.
4.2.1 Soient x = aba¯ et y = ab. Exprimer a et b comme produits (pour la loi ⊙ ) d'éléments de la forme x, x^(− 1), y et y^(− 1) et en déduire que X = {aba¯, ab} est une base de F(A).
4.2.2 Montrer que {aba¯b¯, ba¯b¯a} n'est pas une base de F(A). On montrera que si B = {c, d}, le morphisme induit par φ : B ⟶ F(A) tel que φ(c) = aba¯b¯ et φ(d) = ba¯b¯ a n'est pas surjectif.

Question 4.3 Soient A et B deux alphabets et soit φ : F(A) ⟶ F(B) un morphisme. On considère un ℝ-espace vectoriel V(A) de dimension card (A) et une base E_A de V(A). Comme V(A) muni de l'addition est un groupe, on peut définir un morphisme σ_F : F(A) ⟶ V(A) induit par une bijection σ : A ⟶ E_A ( A et E_A ont même cardinal). De même, on définit V(B), une base E_B de V(B) et un morphisme ρ_F : F(B) ⟶ V(B) à partir d'une bijection ρ : B ⟶ E_B.
4.3.1 Montrer qu'il existe une application linéaire φ^ : V(A) ⟶ V(B) telle que ρ_F ∘ φ = φ^ ∘ σ_F, comme ci-dessous :

4.3.2 Montrer que si le morphisme φ : F(A) ⟶ F(B) est surjectif, alors card (B) ≤ card(A). Pour cela, on pourra montrer que l'application linéaire φ^ est surjective.
4.3.3 Montrer que toutes les bases de F(A) ont le même cardinal.

Le cardinal commun des bases de F(A), à savoir card (A), est appelée le rang de F(A). Si G est un groupe isomorphe à F(A), on dit que G est un groupe libre de rang card (A). Si φ : G ⟶ F(A) est un isomorphisme et si B est une partie de G telle que φ(B) est une base de F(A), on dit que B est une base de G.

Question 4.4 Soit A = {a, b}, soit C = {c_1, …, c_n} un alphabet à n éléments, n ≥ 1, et soit φ le morphisme φ : F(C) ⟶ F(A) induit par l'application c_i ⟼ a^i ba¯^i(i ∈ {1, …, n}.
4.4.1 Montrer que si i ∈ {1, …, n} et k est un entier relatif non nul, alors φ(c_i^k) = a^i b^k a¯^i. (Si k < 0, b^k dénote le mot b¯^(|k|).)
4.4.2 Montrer que φ est injectif.
4.4.3 En déduire qu'un groupe libre de rang 2 admet comme sous-groupes des groupes libres de tout rang fini.

Soit u ∈ A~^∗. On dit que le mot u est cycliquement réduit si u est le mot vide ou si u = a_1 a_2⋯a_n ( n ≥ 1 et a_i ∈ A~ pour tout i ) est réduit et a_1 ≠ a¯_n. On observera que u est cycliquement réduit si et seulement si le mot u^2 est réduit.

Question 5.1 Montrer que tout mot réduit u ∈ F(A) admet une unique factorisation de la forme u = w¯vw, où v est cycliquement réduit. En déduire que si u n'est pas le mot vide, alors pour tout entier n > 0, u^n ≠ 1.

Soient u, v ∈ F(A). On dit que u et v sont conjugués et on note u ≡ v s'il existe un mot w ∈ F(A) tel que v = w¯⊙u⊙w.

Question 5.2 Montrer que la relation de conjugaison ≡ est une relation réflexive, symétrique et transitive.

Question 5.3 Soient u et v deux mots cycliquement réduits non vides. Montrer que u et v sont conjugués si et seulement si v est une permutation cyclique de u, c'est-à-dire s'il existe des mots r, s tels que u = rs et v = sr.

Question 5.4 Donner un algorithme pour décider si deux mots u, u^′ ∈ F(A) sont conjugués.

On définit un graphe orienté A-étiqueté (on dira simplement un A-graphe) comme une paire Γ = (V, E) où V est un ensemble fini, appelé ensemble des sommets, et E est une partie de V × A × V, appelée ensemble des arêtes. Il est commode de représenter une arête ( u, a, v ) par une flèche du sommet u vers le sommet v étiquetée par la lettre a, comme illustré figure 1 .

Si e = (u, a, v) ∈ E, on note e¯ le triplet e¯ = (v, a¯, u). Soit E~ = E ∪ {e¯|e ∈ E}. Un chemin dans le A-graphe Γ est une suite finie de la forme

(n ≥ 1) où chaque (u_(i − 1), a_i, u_i) ∈ E~. On dit alors que p est un chemin de u_0 à u_n, de longueur n et d'étiquette le mot a_1 a_2⋯a_n ∈ A~^∗. Par convention, on considère que, pour tout sommet u, il existe un chemin de longueur 0 de u à u, appelé chemin vide en u. Dans le A-graphe de la figure 1 , il existe par exemple des chemins de s_0 à s_2 étiquetés ab¯, abb, aba¯, aba¯ab (il en existe une infinité d'autres), ainsi que des chemins étiquetés aba¯ba¯ et ab¯aaa¯ba¯ba¯ de s_0 à s_0.

Si un chemin ne comporte pas deux arêtes consécutives de la forme (u, a, v)(v, a¯, u) avec (u, a, v) ∈ E~, on dit qu'il est réduit. Enfin, on dit que le graphe Γ est réduit si, pour tout sommet u et toute lettre a ∈ A, E contient au plus une arête de la forme (u, a, v) et au plus une arête de la forme (v, a, u). Le A-graphe de la figure 1 n'est pas réduit puisque deux arêtes étiquetées a partent du sommet s_2.

Dans toute cette partie, on considère un A-graphe fini réduit Γ = (V, E).

Question 6.1 Montrer que l'étiquette d'un chemin est réduite si et seulement si le chemin est réduit.
Question 6.2 Montrer que si x est l'étiquette d'un chemin du sommet s au sommet t, alors ρ(x) est l'étiquette d'un chemin réduit de s à t.

Si s_0 ∈ V est un sommet de Γ, on note G(Γ, s_0) l'ensemble des étiquettes des chemins réduits de s_0 à s_0.

Question 6.3 Montrer que G(Γ, s_0) est un sous-groupe de F(A).
On dit que le A-graphe Γ est connexe si, pour tous sommets u, v de Γ, il existe au moins un chemin de u à v (et donc au moins un chemin réduit, d'après la question 6.2). On dit que Γ est une forêt si, pour tous sommets u, v de Γ, il existe au plus un chemin réduit de u à v. Une forêt connexe est appelée un arbre.

Question 6.4 Que peut-on dire de G(Γ, s_0) lorsque Γ est une forêt ?
Pour le reste de cette partie, le A-graphe fini réduit Γ = (V, E) est supposé connexe et on fixe un sommet s_0 ∈ V de Γ.

Si V^′ ⊆ V et E^′ ⊆ E ∩ (V^′ × A × V^′), on dit que le graphe Γ^′ = (V^′, E^′) est un sous-graphe de Γ, et qu'il est couvrant si V = V^′. On parle enfin de sous-arbre couvrant si de plus Γ^′ est un arbre.

Question 6.5 Montrer que Γ admet un sous-arbre couvrant et donner un algorithme de calcul d'un tel arbre.

Soit T = (V, E_T) un sous-arbre couvrant de Γ. Pour tout sommet s de Γ, soit x_s l'étiquette de l'unique chemin réduit de s_0 à s dans T. Pour chaque arête e = (s, a, t) de Γ n'appartenant pas à T, posons b_e = x_s ax_t^–. On notera que par construction, b_e est un mot réduit.

Question 6.6 Montrer que tout élément de G(Γ, s_0)∖{1} est le produit, dans F(A), de mots de la forme b_e ou b_e^–.

Indication. On pourra pour cela considérer un élément x ∈ G(Γ, s_0), un chemin réduit p d'étiquette x de s_0 à s_0, une factorisation p = p_0 e_1 p_1⋯e_r p_r où les p_i sont des chemins réduits dans T et les e_i sont des éléments de E~∖E~_T, puis montrer que l'étiquette de p_i(0 < i < r) est égale à x¯_(t_i)⊙x_(s_(i + 1)) où t_i est le sommet final de e_i et s_(i + 1) le sommet initial de e_(i + 1).

Question 6.7 Soit r = card(E∖E_T). Montrer que G(Γ, s_0) est isomorphe à un groupe libre de rang r de base {b_e|e ∈ E∖E_T}.

Dans cette partie, on va montrer que tout sous-groupe finiment engendré d'un groupe libre est libre.
Soit A = (Γ, s_0) la paire consistant en un A-graphe Γ = (V, E) et un sommet s_0 ∈ V de Γ. On note L(A) l'ensemble des étiquettes des chemins de s_0 à s_0 dans le A-graphe ( V, E ) et ρ(L(A) ) l'ensemble ρ(L(A)) = {ρ(u)|u ∈ L(A)}.

Si Γ n'est pas réduit, il existe deux arêtes de E de la forme ( u, a, v ) et ( u, a, v^′ ), ou bien ( v, a, u ) et ( v^′, a, u ). Soit alors B la paire B = (Δ, t_0) obtenue à partir de A en "fusionnant" les sommets v et v^′. Plus précisément, on définit Δ = (W, F) et t_0 de la façon suivante. L'ensemble W des sommets de Δ est
W = V∖{v, v^′} ∪ {w} où w est un nouveau symbole n'appartenant pas à V. L'ensemble d'arêtes F est obtenu à partir de E en remplaçant partout v et v^′ par w et en ôtant les doublons éventuels. Le sommet t_0 est égal à s_0 si s_0 ≠ v, v^′, à w sinon. On dit alors que A se réduit en une étape en B, noté A → ^1 B.

On dit que la paire A = (Γ, s_0) est réduite si le A-graphe Γ est réduit.
Question 7.1 Montrer que si A → ^1 B, alors