L'utilisation de calculatrice n'est pas autorisée pour cette épreuve.
Sous-décalages et algorithmique des morphismes
Dans ce sujet on s'intéresse à des suites bi-infinies de symboles (les configurations), des ensembles de telles suites (les sous-décalages), et des applications entre ces ensembles (les morphismes). Ces différents objets peuvent être vus à la fois d'un point de vue combinatoire et d'un point de vue topologique, ce qui en fait leur richesse.
Les algorithmes devront être écrits en Caml Light ou dans un format pseudo-code proche.
Préliminaires
Ensembles. Si E est un ensemble fini, on notera |E| son cardinal. Un alphabet A est un ensemble fini non vide, dont les éléments sont appelés les lettres. Étant donnés deux entiers ℓ ≤ r ∈ ℤ, on notera [ℓ; r] pour l'ensemble d'entiers {ℓ, ℓ + 1, …, r − 1, r}. Si f : E → F est une fonction, alors l'image de X ⊆ E par f est l'ensemble f(X) = {f(x) : x ∈ X}. On rappelle le principe des tiroirs infinis : si E est un ensemble infini et F est un ensemble fini, alors pour toute fonction f : E → F il existe un x ∈ F tel que l'image réciproque de {x} par f est infinie.
Arithmétique. Étant donné un entier n, rappelons que ( nmod2 ) désigne le reste de la division entière de n par 2 .
Partie I. Configurations, topologie et sous-décalages
Une configuration est un élément de A^ℤ, autrement dit une application x : ℤ → A, ou encore un mot bi-infini. Pour alléger les notations on notera x_i la lettre x(i). Sur l'exemple ci-dessous, x est une configuration de {◻, ◻}^ℤ, et la lettre x_0 est ◻.
Un motif est un élément de A^([ℓ; r]), où ℓ ≤ r ∈ ℤ, autrement dit une fonction p : [ℓ; r] → A. L'ensemble [ℓ; r] est le support du motif p. Si x ∈ A^ℤ est une configuration, on note x_([ℓ; r]) le motif correspondant à la restriction de x à [ℓ; r]. Un motif p ∈ A^([ℓ; r]) apparaît dans la configuration x s'il existe un entier i ∈ ℤ tel que x_(i + j) = p_j pour tout j ∈ [ℓ; r]. Dans ce cas, on écrit p⊏x. Si p ∈ A^([ℓ; r]) et p^′ ∈ A^([ℓ^′; r^′]) sont deux motifs tels que [ℓ; r] ⊆ [ℓ^′; r^′] et p_i = p_i^′ pour tout i ∈ [ℓ; r], on dit que p est un sous-motif de p^′ et on écrit p⊑p^′ (ou encore p⊏p^′ si [ℓ; r] ⊊ [ℓ^′; r^′] ).
Étant donné un motif p ∈ A^([ℓ; r]), le cylindre porté par p est l'ensemble de toutes les configurations qui coïncident avec p sur son support :
[ [p] ] = {x ∈ A^ℤ : x_([ℓ; r]) = p}.
En d'autres termes, le cylindre [ [p] ] est exactement l'ensemble des configurations qui prolongent le motif p.
Question 1. On considère le motif p = 1100 ∈ {0, 1}^([0; 3]). On définit trois configurations x, y, z ∈ {0, 1}^ℤ comme suit − x = 0^ℤ; − y ∈ {0, 1}^ℤ définie par y_i = 0 ⇔ i ≥ 0; − z ∈ {0, 1}^ℤ définie par z_i = 0 ⇔ i ≥ 2.
Pour chacune d'elle, préciser si
le motif p apparaît dans la configuration;
la configuration appartient au cylindre [ [p] ].
Nous allons munir l'espace des configurations A^ℤ d'une application d_A : A^ℤ × A^ℤ → ℝ^+, que l'on appellera distance. Par analogie avec le cas des espaces vectoriels normés, cette distance permettra de définir une topologie. Si x et y sont deux configurations différentes de A^ℤ, on définit la distance d_A entre x et y par
d_A(x, y) = 2^(− min{|i| : x_i ≠ y_i}),
et on ajoute la convention que d_A(x, x) = 0 pour toute configuration x ∈ A^ℤ. Autrement dit, deux configurations sont d'autant plus proches qu'elles partagent un grand motif central commun. Par exemple, la configuration x ci-dessus et la configuration y dessinée ci-dessous sont à distance 1/4, car x_0 = y_0, x_1 = y_1 et x_(− 1) = y_(− 1) mais x_(− 2) ≠ y_(− 2).
y ∈ {◻, ◻}^ℤ
On notera simplement d pour la distance d_A lorsqu'il n'y a pas d'ambiguïté.
Question 2. Calculer les distances d(x, y), d(y, z), et d(x, z) pour les configurations x, y et z de la question 1.
La distance d permet de définir, toujours par analogie avec le cas des espaces vectoriels normés, les notions d'ensemble ouvert et d'ensemble fermé. Si x ∈ A^ℤ est une configuration et r est un réél strictement positif, on appelle boule ouverte de rayon r et de centre x l'ensemble des configurations à distance de x strictement plus petite que r :
B(x, r) = {y ∈ A^ℤ : d(x, y) < r}
On dit qu'un ensemble U ⊆ A^ℤ est ouvert si pour toute configuration x ∈ U, il existe un rayon r > 0 tel que la boule ouverte B(x, r) est incluse dans U. On dit qu'un ensemble F ⊆ A^ℤ est fermé si son complémentaire est ouvert.
Question 3. Montrer qu'une intersection quelconque d'ensembles fermés est un ensemble fermé.
Une suite d'éléments de A^ℤ est une fonction s : ℕ → A^ℤ. Par analogie avec le cas des espaces vectoriels normés, on dit qu'une telle suite s est convergente s'il existe une configuration x ∈ A^ℤ telle que
∀ε > 0, ∃N ∈ ℕ, ∀n ≥ N, d(s(n), x) < ε
La configuration x (qui est nécessairement unique) est la limite de la suite s.
On admet pour toute la suite le fait suivant :
Un ensemble X ⊆ A^ℤ est fermé si et seulement si X contient la limite de toute suite convergente d'éléments de X.
Question 4. Soit p ∈ A^([ℓ; r]) un motif, avec ℓ ≤ r ∈ ℤ. Montrer que le cylindre [ [p] ] est à la fois ouvert et fermé pour la topologie définie par la distance d.
On définit la translation σ : A^ℤ → A^ℤ par (σ(x))_j = x_(j + 1) pour toute configuration x et tout entier j ∈ ℤ.
Question 5. Vérifier que σ est une bijection, et exprimer son inverse σ^(− 1).
On définit à présent les itérées de σ : par convention σ^0 est l'identité, et pour tout i ∈ ℤ∖{0}, on a σ^(|i|) = σ ∘ σ^(|i| − 1) et σ^(− |i|) = σ^(− 1) ∘ σ^(− |i| + 1). Un ensemble X ⊆ A^ℤ est invariant par translation si σ^i(x) ∈ X pour tout x ∈ X et tout i ∈ ℤ. Un sous-décalage est un ensemble X ⊆ A^ℤ qui est à la fois fermé et invariant par translation.
Question 6. Parmi les ensembles de configurations définis ci-dessous, lesquels sont des sousdécalages? Justifier vos réponses.
X_1 = {x ∈ {0, 1}^ℤ : x_i = 0 ⇒ |i| est pair }.
X_2 = {x ∈ {0, 1}^ℤ : |{i ∈ ℤ : x_i = 1}| = 1} 。
X_3 = {x ∈ {0, 1}^ℤ : |{i ∈ ℤ : x_i = 1}| ≤ 1} 。
La question suivante montre la compacité de l'espace A^ℤ muni de la distance d, qui est une propriété fondamentale et qui sera utilisée à plusieurs reprises dans la suite.
Question 7. Montrer que toute suite d'éléments de A^ℤ a une suite extraite qui converge dans A^ℤ. Indication : pour construire la limite de la suite extraite convergente, on pourra utiliser le principe des tiroirs infinis sur des supports imbriqués de taille croissante.
Si X est un ensemble de configurations, le langage de X est l'ensemble L(X) des x_([ℓ; r]) pour x ∈ X et ℓ ≤ r ∈ ℤ. De plus, on note L(X)^– pour l'ensemble des motifs p ∈ A^([ℓ; r]) avec ℓ ≤ r ∈ ℤ et tels que p ∉ L(X).
Nous introduisons maintenant trois notions utiles à l'étude des langages d'ensembles de configurations.
Un ensemble de motifs L est stable par sous-motif si pour tout motif p ∈ L, chacun de ses sous-motifs est aussi dans cet ensemble: ∀p^′⊑p, p^′ ∈ L.
Un ensemble de motifs L est prolongeable si pour tout motif p ∈ A^([ℓ; r]) tel que p ∈ L, il existe un motif p^′ ∈ A^([ℓ^′; r^′]) avec [ℓ − 1; r + 1] ⊆ [ℓ^′; r^′] et tel que p^′ ∈ L et p⊏p^′.
Un ensemble de motifs L est stable par translation si pour tout motif p ∈ L, on a σ(p) ∈ L et σ^(− 1)(p) ∈ L, où, pour p ∈ A^([ℓ; r]), les motifs σ(p) et σ^(− 1)(p) sont définis par
Question 8. Montrer que si un ensemble de motifs L est le langage d'un sous-décalage, alors L est à la fois stable par translation, stable par sous-motif et prolongeable.
Si E est un ensemble de motifs, on définit X_E comme étant l'ensemble des configurations dans lesquelles aucun motif de E n'apparaît, c'est-à-dire :
Montrer que pour tout ensemble de motifs E, l'ensemble X_E est un sous-décalage. Indication : on pourra écrire X_E à l'aide de cylindres.
Montrer que pour tout sous-décalage X, on a X = X_(L(X)^–), où X_(L(X)^–) est l'ensemble des configurations qui évitent les motifs de L(X)^–, comme défini ci-dessus.
En déduire que X ⊆ A^ℤ est un sous-décalage si et seulement s'il existe un ensemble de motifs E tel que X = X_E.
Question 10. Montrer que si un ensemble de motifs L est à la fois stable par translation, stable par sous-motif et prolongeable, alors c'est le langage d'un sous-décalage.
Partie II. Morphismes
Dans cette partie, on étudie les morphismes. Les morphismes sont des fonctions sur les configurations possédant certaines propriétés.
On fixe deux alphabets A et B. Une fonction locale est la donnée d'un intervalle V = [ − ℓ; r] avec ℓ, r ∈ ℕ, appelé voisinage, et d'une application φ : A^(ℓ + r + 1) → B. Une application Φ : A^ℤ → B^ℤ est un morphisme s'il existe une fonction locale ( [ − ℓ; r], φ ) telle que pour toute configuration x ∈ A^ℤ, en notant y = Φ(x), pour tout entier i ∈ ℤ on a
Ce morphisme Ψ est-il injectif? surjectif?
3. Montrer que la translation σ peut être vue comme un morphisme, dont on précisera le voisinage et la fonction locale.
Par analogie avec le cas des espaces vectoriels normés, on dit qu'une fonction f : A^ℤ → B^ℤ est continue si
On admet, et on pourra utiliser dans toute la suite, la formulation suivante du théorème de Heine :
Si f : A^ℤ → B^ℤ est une fonction continue, alors elle est uniformément continue.
Question 12.
Montrer que la translation σ est continue.
Montrer que Φ : A^ℤ → B^ℤ est un morphisme si et seulement si Φ est continue et commute avec la translation σ. Indication : on pourra utiliser le théorème de Heine.
On fixe, pour toute la suite de cette partie, deux alphabets A, B, un morphisme Φ : A^ℤ → B^ℤ, et sa fonction locale (V, φ). Sans perte de généralité, on suppose pour toute la suite de cette partie que le voisinage V est de la forme V = [ − r; r] pour r ∈ ℕ.
Un motif est orphelin pour Φ s'il n'apparaît dans aucune configuration appartenant à Φ(A^ℤ).
Question 13. Les morphismes Φ et Ψ de la question 11 possèdent-ils des motifs orphelins?
La fonction locale ( V, φ ) permet de définir les fonctions locales étendues aux motifs, qui sont, pour m ∈ ℕ, les fonctions φ_m : A^([ − (m + r); m + r]) → B^([ − m; m]) telles que
φ_m(u) : [ − m; m], ⟶ B; i, ⟼ φ(u_(− r + i), …, u_(r + i))
pour tout motif u ∈ A^([ − (m + r); m + r]).
Question 14.
Montrer que Φ est surjectif si et seulement si toutes ses fonctions locales étendues aux motifs φ_m le sont.
Montrer que s'il existe m ∈ ℕ tel que la fonction locale étendue φ_m n'est pas surjective, alors Φ a un motif orphelin.
En déduire que Φ est surjectif si et seulement si Φ ne possède pas de motif orphelin.
On dit que deux configurations x, y ∈ A^ℤ sont asymptotiques si l'ensemble {i ∈ ℤ : x_i ≠ y_i} est fini. On dit que Φ est pré-injectif si pour toutes configurations asymptotiques x, y ∈ A^ℤ, on a x ≠ y ⇒ Φ(x) ≠ Φ(y).
On admet pour toute la suite la propriété suivante des morphismes de A^ℤ dans lui-même : − Φ : A^ℤ → A^ℤ est surjectif si et seulement si Φ est pré-injectif.
Partie III. Algorithmes par les graphes
Dans cette partie on présente deux algorithmes qui permettent de déterminer si un morphisme de A^ℤ dans lui-même est surjectif ou bijectif. Ces algorithmes sont basés sur une représentation des morphismes à l'aide de graphes orientés.
Pour toute cette partie, on fixe un alphabet A ainsi qu'une bijection code_n : A^n → [0; |A|^n − 1] pour chaque n ∈ ℕ.
Soit Φ : A^ℤ → A^ℤ un morphisme de fonction locale ( [ − ℓ; r], φ ), où ℓ, r ∈ ℕ. On définit le graphe de φ comme étant le graphe orienté G_φ = (S, R) dont
l'ensemble des sommets S est l'ensemble A^(ℓ + r) des mots de taille ℓ + r sur l'alphabet A;
l'ensemble des arêtes R ⊆ S × S contient ( w, w^′ ) si et seulement si ( w = au et w^′ = ub ) avec a, b ∈ A.
De plus, le graphe G_φ est equipé d'une fonction d'étiquetage, qui à chaque arête (au, ub) ∈ R associe φ(aub).
On remarque que tous les sommets du graphe G_φ ont degrés entrant et sortant |A|. Par exemple, pour le morphisme Φ : {0, 1}^ℤ → {0, 1}^ℤ donné par la fonction locale ( [ − 1; 1], φ ) de la question 11, on obtient le graphe G_φ suivant :
Dans un tel graphe G_φ, une configuration x ∈ A^ℤ peut être vue comme un chemin bi-infini de sommets, et on obtient l'image de cette configuration par le morphisme Φ en lisant les étiquettes reliant les sommets successifs de ce chemin.
Question 15. Dessiner le graphe G_ψ pour le morphisme Ψ : {0, 1}^ℤ → {0, 1}^ℤ donné par la fonction locale ( [ − 1; 1], ψ ) de la question 11. On indiquera les valeurs de la fonction d'étiquetage de G_ψ sur les arêtes de G_ψ.
On définit à présent un autre graphe H_φ qui va nous permettre d'étudier simultanément deux configurations. Il nous permettra de vérifier l'injectivité (et donc la bijectivité) d'un morphisme, mais aussi sa surjectivité. Le graphe H_φ = (S^2, W) est défini par
W = {((s_1, t_1), (s_2, t_2)) : (s_1, s_2) et (t_1, t_2) ont les mêmes étiquettes dans G_φ} ⊆ S^2 × S^2.
Notons que si ((s_i, t_i))_(i ∈ ℤ) est un chemin bi-infini dans H_φ, alors en notant a_i et b_i respectivement la première lettre de s_i et de t_i, les configurations (a_i)_(i ∈ ℤ) et (b_i)_(i ∈ ℤ) ont même image par Φ. Le graphe D_φ est obtenu en supprimant dans H_φ tous les sommets non reliés dans les
Figure 1 - Le graphe H_φ pour la fonction locale ( [ − 1; 1], φ ) de la question 11.
deux sens à des composantes fortement connexes. Par exemple, le graphe H_φ pour la fonction locale ([ − 1; 1], φ) de la question 11 est représenté sur la figure 1 . On remarque que H_φ = D_φ et on note deux composantes fortement connexes dans H_φ.
Question 16. Dessiner les graphes H_ψ et D_ψ pour le morphisme Ψ : {0, 1}^ℤ → {0, 1}^ℤ donné par la fonction locale ( [ − 1; 1], ψ ) de la question 11, en veillant à disposer les sommets des graphes comme dans l'exemple ci-dessus.
Les questions 17, 20 et 22 ci-dessous demandent des algorithmes sur des graphes. Ces graphes seront représentés par listes d'adjacence. De plus, ces algorithmes portent ultimement sur des graphes de la forme H_φ, c'est-à-dire des graphes dont les sommets sont des couples (v, w) ∈ S^2. On se donne donc les types Caml Light suivants :
type sommet == int * int ;;
type graphe = (sommet * sommet list) list ;;
On dira que g : graphe représente un graphe si
pour tout u : sommet, g contient au plus un élément de la forme ( u , voisins), et
pour tout u : sommet, si u est un élément de voisins' pour un élément (v, voisins') de g , alors g a un élément de la forme ( u , voisins).
Le graphe G représenté par g a alors pour sommets les u : sommet tels que g contient un élément de la forme ( u, voisins ), et G a une arête de u vers v si et seulement si voisins contient v .
Soit g : graphe représentant un graphe G, et soit H un graphe dont les sommets sont dans S^2, où S est de la forme A^n. On dit que g représente H par code_n lorsque :
l'ensemble des sommets de G est l'ensemble des (code_n(s), code_n(t)) tels que (s, t) est un sommet de H, et − G a une arête de (code_n(s), code_n(t)) vers (code_n(s^′), code_n(t^′)) si et seulement si H a une arête de ( s, t ) vers ( s^′, t^′ ).
En plus des fonctionnalités de base du langage Caml Light, le candidat pourra utiliser les fonctions suivantes sans les programmer :
mem : 'a -> 'a list -> bool
mem x 1 renvoie true si et seulement si x est un élément de 1 .
filter : ('a -> bool) -> 'a list -> 'a list
filter p 1 renvoie la liste des éléments x de 1 tels que px = true.
On ne demande pas des programmes de complexité optimale : seule leur correction sera évaluée. Les candidats sont donc encouragés à proposer des solutions simples.
Question 17. 1. Écrire une fonction chemin : graphe → sommet → sommet → bool telle que si g : graphe représente le graphe G, alors chemin g u v renvoie true si u et v sont des sommets de G et s'il existe dans G un chemin de u vers v , et renvoie false sinon.
2. On dit qu'un sommet u est non-isolé s 'il existe un sommet v ≠ u ainsi qu'un chemin de u à v et un chemin de v à u. Un sommet est isolé s'il n'est pas non-isolé.
Écrire une fonction isole : graphe -> sommet -> bool telle que si g : graphe représente le graphe G, alors isole u renvoie true si u est un sommet isolé dans G, et renvoie false sinon. La fonction doit renvoyer false si u n'est pas un sommet de G.
3. Écrire une fonction elagage : graphe → graphe telle que si g : graphe représente le graphe G, alors elagage g renvoie un g^′ : graphe représentant le plus grand sousgraphe de G dont tous les sommets appartiennent à une composante fortement connexe de G.
Question 18. Montrer que tous les sommets de la forme (w, w) ∈ S^2 sont dans la même composante fortement connexe de D_φ.
Dans le graphe D_φ, on appelle G^–_φ la composante fortement connexe contenant tous les sommets de la forme (w, w), où w ∈ S.
Question 19. Montrer que le morphisme de fonction locale ( [ − ℓ; r], φ ) est bijectif si et seulement si G^–_φ ne contient que des sommets de la forme ( w, w ), et G^–_φ est la seule composante fortement connexe de D_φ. Indication : on se rappellera que Φ est surjectif si et seulement si Φ est préinjectif.
Question 20. Soit Φ un morphisme de fonction locale ( [ − ℓ; r], φ ). Écrire une fonction bijectif : graphe -> bool telle que si g : graphe représente H_φ par code_(ℓ + r + 1), alors bijectif g revoie true si Φ est un morphisme bijectif, et renvoie false sinon.
Question 21. Montrer que le morphisme de fonction locale ( [ − ℓ; r], φ ) est surjectif si et seulement si G^–_φ ne contient que des sommets de la forme ( w, w ). Indication : on se rappellera que Φ est surjectif si et seulement si Φ est pré-injectif.
Question 22. Soit Φ un morphisme de fonction locale ( [ − ℓ; r], φ ). Écrire une fonction sujectif : graphe → bool telle que si g : graphe représente H_φ par code_(ℓ + r + 1), alors surjectif g revoie true si Φ est un morphisme surjectif, et renvoie false sinon.
.jpg)
