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 est un ensemble fini, on notera son cardinal. Un alphabet est un ensemble fini non vide, dont les éléments sont appelés les lettres. Étant donnés deux entiers , on notera pour l'ensemble d'entiers . Si est une fonction, alors l'image de par est l'ensemble . On rappelle le principe des tiroirs infinis : si est un ensemble infini et est un ensemble fini, alors pour toute fonction il existe un tel que l'image réciproque de par est infinie.
Arithmétique. Étant donné un entier , rappelons que ( ) désigne le reste de la division entière de par 2 .
Partie I. Configurations, topologie et sous-décalages
Une configuration est un élément de , autrement dit une application , ou encore un mot bi-infini. Pour alléger les notations on notera la lettre . Sur l'exemple ci-dessous, est une configuration de , et la lettre est .
Un motif est un élément de , où , autrement dit une fonction . L'ensemble est le support du motif . Si est une configuration, on note le motif correspondant à la restriction de à . Un motif apparaît dans la configuration s'il existe un entier tel que pour tout . Dans ce cas, on écrit . Si et sont deux motifs tels que et pour tout , on dit que est un sous-motif de et on écrit (ou encore si ).
Étant donné un motif , le cylindre porté par est l'ensemble de toutes les configurations qui coïncident avec sur son support :
En d'autres termes, le cylindre est exactement l'ensemble des configurations qui prolongent le motif .
Question 1. On considère le motif . On définit trois configurations comme suit définie par ; définie par .
Pour chacune d'elle, préciser si
le motif apparaît dans la configuration;
la configuration appartient au cylindre .
Nous allons munir l'espace des configurations d'une application , que l'on appellera distance. Par analogie avec le cas des espaces vectoriels normés, cette distance permettra de définir une topologie. Si et sont deux configurations différentes de , on définit la distance entre et par
et on ajoute la convention que pour toute configuration . Autrement dit, deux configurations sont d'autant plus proches qu'elles partagent un grand motif central commun. Par exemple, la configuration ci-dessus et la configuration dessinée ci-dessous sont à distance , car et mais .
On notera simplement pour la distance lorsqu'il n'y a pas d'ambiguïté.
Question 2. Calculer les distances , et pour les configurations et de la question 1.
La distance 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 est une configuration et est un réél strictement positif, on appelle boule ouverte de rayon et de centre l'ensemble des configurations à distance de strictement plus petite que :
On dit qu'un ensemble est ouvert si pour toute configuration , il existe un rayon tel que la boule ouverte est incluse dans . On dit qu'un ensemble 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 est une fonction . Par analogie avec le cas des espaces vectoriels normés, on dit qu'une telle suite est convergente s'il existe une configuration telle que
La configuration (qui est nécessairement unique) est la limite de la suite .
On admet pour toute la suite le fait suivant :
Un ensemble est fermé si et seulement si contient la limite de toute suite convergente d'éléments de .
Question 4. Soit un motif, avec . Montrer que le cylindre est à la fois ouvert et fermé pour la topologie définie par la distance .
On définit la translation par pour toute configuration et tout entier .
Question 5. Vérifier que est une bijection, et exprimer son inverse .
On définit à présent les itérées de : par convention est l'identité, et pour tout , on a et . Un ensemble est invariant par translation si pour tout et tout . Un sous-décalage est un ensemble 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.
est pair .
。
。
La question suivante montre la compacité de l'espace muni de la distance , 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 une suite extraite qui converge dans . 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 est un ensemble de configurations, le langage de est l'ensemble des pour et . De plus, on note pour l'ensemble des motifs avec et tels que .
Nous introduisons maintenant trois notions utiles à l'étude des langages d'ensembles de configurations.
Un ensemble de motifs est stable par sous-motif si pour tout motif , chacun de ses sous-motifs est aussi dans cet ensemble: .
Un ensemble de motifs est prolongeable si pour tout motif tel que , il existe un motif avec et tel que et .
Un ensemble de motifs est stable par translation si pour tout motif , on a et , où, pour , les motifs et sont définis par
Question 8. Montrer que si un ensemble de motifs est le langage d'un sous-décalage, alors est à la fois stable par translation, stable par sous-motif et prolongeable.
Si est un ensemble de motifs, on définit comme étant l'ensemble des configurations dans lesquelles aucun motif de n'apparaît, c'est-à-dire :
Question 9.
Montrer que pour tout ensemble de motifs , l'ensemble est un sous-décalage. Indication : on pourra écrire à l'aide de cylindres.
Montrer que pour tout sous-décalage , on a , où est l'ensemble des configurations qui évitent les motifs de , comme défini ci-dessus.
En déduire que est un sous-décalage si et seulement s'il existe un ensemble de motifs tel que .
Question 10. Montrer que si un ensemble de motifs 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 et . Une fonction locale est la donnée d'un intervalle avec , appelé voisinage, et d'une application . Une application est un morphisme s'il existe une fonction locale ( ) telle que pour toute configuration , en notant , pour tout entier on a
Question 11.
Soit le morphisme donné par la fonction locale ( ) définie par
Ce morphisme est-il injectif? surjectif?
2. Soit le morphisme donné par la fonction locale définie par
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 est continue si
et qu'elle est uniformément continue si
On admet, et on pourra utiliser dans toute la suite, la formulation suivante du théorème de Heine :
Si est une fonction continue, alors elle est uniformément continue.
Question 12.
Montrer que la translation est continue.
Montrer que 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 , un morphisme , et sa fonction locale . Sans perte de généralité, on suppose pour toute la suite de cette partie que le voisinage est de la forme pour .
Un motif est orphelin pour s'il n'apparaît dans aucune configuration appartenant à .
Question 13. Les morphismes et de la question 11 possèdent-ils des motifs orphelins?
La fonction locale ( ) permet de définir les fonctions locales étendues aux motifs, qui sont, pour , les fonctions telles que
pour tout motif .
Question 14.
Montrer que est surjectif si et seulement si toutes ses fonctions locales étendues aux motifs le sont.
Montrer que s'il existe tel que la fonction locale étendue 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 sont asymptotiques si l'ensemble est fini. On dit que est pré-injectif si pour toutes configurations asymptotiques , on a .
On admet pour toute la suite la propriété suivante des morphismes de dans lui-même : 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 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 ainsi qu'une bijection pour chaque .
Soit un morphisme de fonction locale ( ), où . On définit le graphe de comme étant le graphe orienté dont
l'ensemble des sommets est l'ensemble des mots de taille sur l'alphabet ;
l'ensemble des arêtes contient ( ) si et seulement si ( et ) avec .
De plus, le graphe est equipé d'une fonction d'étiquetage, qui à chaque arête associe .
On remarque que tous les sommets du graphe ont degrés entrant et sortant . Par exemple, pour le morphisme donné par la fonction locale ( ) de la question 11, on obtient le graphe suivant :
Dans un tel graphe , une configuration 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 pour le morphisme donné par la fonction locale ( ) de la question 11. On indiquera les valeurs de la fonction d'étiquetage de sur les arêtes de .
On définit à présent un autre graphe 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 est défini par
Notons que si est un chemin bi-infini dans , alors en notant et respectivement la première lettre de et de , les configurations et ont même image par . Le graphe est obtenu en supprimant dans tous les sommets non reliés dans les
Figure 1 - Le graphe pour la fonction locale ( ) de la question 11.
deux sens à des composantes fortement connexes. Par exemple, le graphe pour la fonction locale de la question 11 est représenté sur la figure 1 . On remarque que et on note deux composantes fortement connexes dans .
Question 16. Dessiner les graphes et pour le morphisme donné par la fonction locale ( ) 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 , c'est-à-dire des graphes dont les sommets sont des couples . 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 représenté par g a alors pour sommets les u : sommet tels que g contient un élément de la forme ( ), et a une arête de u vers v si et seulement si voisins contient v .
Soit g : graphe représentant un graphe , et soit un graphe dont les sommets sont dans , où est de la forme . On dit que g représente par lorsque :
l'ensemble des sommets de est l'ensemble des tels que est un sommet de , et a une arête de vers si et seulement si a une arête de ( ) vers ( ).
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 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 , alors chemin g u v renvoie true si u et v sont des sommets de et s'il existe dans un chemin de u vers v , et renvoie false sinon.
2. On dit qu'un sommet est non-isolé 'il existe un sommet ainsi qu'un chemin de à et un chemin de à . 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 , alors isole u renvoie true si u est un sommet isolé dans , et renvoie false sinon. La fonction doit renvoyer false si u n'est pas un sommet de .
3. Écrire une fonction elagage : graphe graphe telle que si g : graphe représente le graphe , alors elagage g renvoie un : graphe représentant le plus grand sousgraphe de dont tous les sommets appartiennent à une composante fortement connexe de .
Question 18. Montrer que tous les sommets de la forme sont dans la même composante fortement connexe de .
Dans le graphe , on appelle la composante fortement connexe contenant tous les sommets de la forme , où .
Question 19. Montrer que le morphisme de fonction locale ( ) est bijectif si et seulement si ne contient que des sommets de la forme ( ), et est la seule composante fortement connexe de . Indication : on se rappellera que est surjectif si et seulement si est préinjectif.
Question 20. Soit un morphisme de fonction locale ( ). Écrire une fonction bijectif : graphe -> bool telle que si g : graphe représente par , alors bijectif g revoie true si est un morphisme bijectif, et renvoie false sinon.
Question 21. Montrer que le morphisme de fonction locale ( ) est surjectif si et seulement si ne contient que des sommets de la forme ( ). Indication : on se rappellera que est surjectif si et seulement si est pré-injectif.
Question 22. Soit un morphisme de fonction locale ( ). Écrire une fonction sujectif : graphe bool telle que si g : graphe représente par , alors surjectif revoie true si est un morphisme surjectif, et renvoie false sinon.
ENS Informatique Fondamentale (Maths Info) MP 2018 - Version Web LaTeX | WikiPrépa | WikiPrépa
