J-0
00m
00j
00h
00min
00s

Version interactive avec LaTeX compilé

Télécharger PDF

ENS Informatique MP 2001

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Logo ens
🔗 Explorer
Banque
X-ENS
Année
2001
Filière
MP
Matière
Info
X-ENS MPX-ENS 2001MP InfoInfo 2001
2025_08_29_c365dc17cb2b528a5c37g

SESSION 2001

Filière MP

INFORMATIQUE

(Épreuve commune aux ENS: Ulm, Lyon et Cachan)
Durée : 4 heures
L'usage de la calculatrice n'est pas autorisé
Les correcteurs attendent des réponses précises et concises aux questions posées. On demande à plusieurs reprises de proposer des algorithmes. On exprimera ces algorithmes avec un point de vue de haut niveau, sans décrire leur implantation effective (cf l'algorithme proposé dans l'énoncé de la question 2.9). La complexité d'un algorithme doit toujours être interprétée comme le nombre d'opérations élémentaires (calculs, comparaisons, ...) nécessaires à son exécution.
La partie 4 est largement indépendante des parties précédentes. En règle générale, les références à un résultat d'une autre partie sont explicitement mentionnées.
Soit un alphabet, c'est à dire un ensemble fini non vide. On note l'ensemble des mots finis formés de lettres de , y compris le mot vide , et . Si et sont deux mots, on note le mot obtenu par concaténation de et ; l'ensemble muni de cette loi de composition est un monoïde. On note la longueur d'un mot .
On dit qu'un mot est facteur d'un autre mot s'il existe des mots et tels que . Si de plus on peut prendre , le mot est dit préfixe de , tandis que si , le mot est dit suffixe de .
Dans les exemples, on utilisera le plus souvent les alphabets et .
L'ensemble des lettres de qui apparaissent effectivement dans un mot est noté Alph . Le cardinal d'un ensemble est noté . On note quand l'ensemble est inclus (au sens large) dans l'ensemble .

1 Morphismes et L-systèmes

Soient et deux alphabets. Un morphisme de dans est une application telle que, pour tous mots et dans .

Question 1.1.

Montrer qu'un morphisme est entièrement défini par la donnée de pour chaque lettre .
Cette observation permet d'exprimer les morphismes de manière plus compacte. Ainsi, on notera l'unique morphisme de dans tel que , et .
Un morphisme est dit non-effaçant si pour tout , effaçant dans le cas contraire; il est dit lettre-à-lettre si pour tout .
Si est un morphisme de dans lui-même, on note et plus généralement .
On appelle -système un triplet , où est un alphabet, est un morphisme de dans et ( est appelé l'axiome du D0L-système ).
À chaque D0L-système , on associe la suite infinie de mots telle que est l'axiome de et pour tout , ce qu'on peut noter . On associe aussi à le langage .
Par exemple, soit . On a
et .

Question 1.2.

Construire un DOL-système tel que mais .

Question 1.3.

Soit le morphisme de dans défini par et . On considère le D0L-système . Calculer les cinq premiers termes de . En utilisant un morphisme lettre-à-lettre , donner une formule simple permettant de passer de . Quelle est la longueur de ? En déduire que n'est pas un langage rationnel.
On appelle -système un quintuplet , où et sont des alphabets (éventuellements égaux), ( ) est un D0L-système que l'on notera , et est un morphisme de dans . Si est la suite de mots associée à , alors on associe à la suite et le langage .

Question 1.4.

Soit . Montrer que .
Existe-t-il un D0L-système G tel que L ?
Note historique : les D0L-systèmes et les HD0L-systèmes, ainsi que d'autres systèmes similaires permettant de construire des langages, sont collectivement appelés L-systèmes. Ils ont été introduits en 1968 par Aristid Lindenmayer pour modéliser la croissance de certains organismes vivants.

2 Mots infinis engendrés par L-systèmes

Soit un alphabet. Un mot infini sur est une suite à valeurs dans . On note l'ensemble de tous les mots infinis sur . Un préfixe de est un mot (fini) de la forme , avec , et un facteur de est un mot de la forme , avec .
Soit un langage et un mot infini. On dit que engendre le mot infini si les deux conditions suivantes sont vérifiées :
(i) est infini;
(ii) tout élément de est préfixe de .

Question 2.1.

Montrer que si le langage engendre deux mots infinis et , alors . Montrer que quel que soit le mot infini , il existe au moins un langage qui engendre .

Question 2.2.

Montrer qu'un langage engendre un mot infini si et seulement si est infini et pour tout couple ( ) d'éléments de , soit est préfixe de , soit est préfixe de u.
Si est un D0L-système (ou un HD0L-système), et si engendre un mot infini , on dit aussi que engendre , et on note .
Dans les questions 2.3, 2.5, 2.6 et 2.7, il est demandé de construire un D0L-système ayant certaines propriétés; à chaque fois, un seul exemple suffit : on ne cherchera pas à caractériser tous les D0L-systèmes ayant les propriétés requises ni à prouver l'unicité de l'exemple construit.

Question 2.3.

Donner un DOL-système engendrant le mot infini défini par et pour tout .

Question 2.4.

Soit un DOL-système tel que le langage associé est infini. Montrer que engendre un mot infini si et seulement si est préfixe de .

Question 2.5.

Donner un D0L-système tel que avec , et . Que vaut ? Est-ce que engendre un mot infini?

Question 2.6.

Donner un D0L-système tel que avec préfixe de mais . Que vaut ? Est-ce que engendre un mot infini?

Question 2.7.

Donner un DOL-système tel que est infini mais n'engendre pas de mot infini.
Soit un morphisme, et une lettre. On dit que est une lettre mortelle (pour ) s'il existe un entier tel que , et que est une lettre immortelle dans le cas contraire.

Question 2.8.

Quelles sont les lettres immortelles dans l'exemple de la question 2.6 ? Montrer que si est un D0L-système tel que avec , alors est infini si et seulement si le mot contient une lettre immortelle pour .

Question 2.9.

L'algorithme suivant prend en entrée un alphabet et un morphisme , et retourne l'ensemble des lettres mortelles pour . Si est un mot, on note la lettre de rang de , de sorte que .
Lettres-mortelles ( $A, f$ )
    $T \leftarrow \emptyset$
    $M \leftarrow \emptyset$
    pour tout $x \in A$ faire
        pour tout $y \in A$ faire
            $N[x, y] \leftarrow 0$
    pour tout $y \in A$ faire
        $w \leftarrow f(y)$
        pour $i$ de 0 à $|w|-1$ faire
            $N[w[i], y] \leftarrow N[w[i], y]+1$
        $L[y] \leftarrow|w|$
        si $L[y]=0$
            alors $T \leftarrow T \cup\{y\}$
    tant que $T \neq \emptyset$ faire
        choisir $x \in T$
        $T \leftarrow T \backslash\{x\}$
        $M \leftarrow M \cup\{x\}$
        pour tout $y \in A \backslash(M \cup T)$ faire
            $L[y] \leftarrow L[y]-N[x, y]$
            si $L[y]=0$
                alors $T \leftarrow T \cup\{y\}$
    retourner $M$
Justifier la validité de cet algorithme (on précisera notamment la signification de la matrice ). Montrer que sa complexité est , où et .

Question 2.10.

Proposer et justifier un algorithme prenant en entrée un D0L-système G et un entier , retournant le préfixe de longueur de si engendre un mot infini, et retournant « n'engendre pas de mot infini » sinon.
Soit un morphisme non-effaçant. Étant donné un mot infini , le langage préfixe de engendre un unique mot infini, que l'on notera . On prolonge ainsi en une application de dans .
Soit un morphisme non-effaçant et un mot infini. On dit que est un point fixe non trivial de si et s'il existe une lettre qui apparaît dans et telle que .

Question 2.11.

Soit . Donner un point fixe non trivial de . Le morphisme a-t-il un autre point fixe non trivial?

Question 2.12.

Soit . Donner deux points fixes non triviaux de . Le morphisme a-t-il d'autres points fixes non triviaux?

Question 2.13.

Montrer que si est point fixe non trivial d'un morphisme non-effaçant , alors est engendré par un DOL-système que l'on précisera. En déduire que si pour tout a au plus points fixes non triviaux.
On dit qu'un mot infini est ultimement périodique s'il existe des entiers et tels que pour tout .

Question 2.14.

Parmi les exemples de D0L-systèmes déjà construits, en donner un qui engendre un mot infini ultimement périodique. Montrer que tout mot infini ultimement périodique peut être engendré par un HD0L-système.

Question 2.15.

Soit le D0L-système défini à la question 1.3. Montrer que engendre un mot infini . Comment calculer en fonction de , sans calculer tous les termes précédents comme le fait l'algorithme de la question 2.10 ? Montrer que n'est pas ultimement périodique.
Le mot infini est appelé mot infini de Thue-Morse.

Question 2.16.

Soient et . Montrer que le HDOL-système engendre aussi le mot infini de Thue-Morse.

Question 2.17.

Soit un DoL-système. Pour entier strictement positif, on note . Montrer que si et engendrent des mots infinis, alors .

3 Hiérarchie

Soit un D0L-système. Si est non-effaçant, on dit que est un PD0Lsystème.
Soit un HD0L-système. Si est non-effaçant, on dit que est un ND0L-système. Si est lettre-à-lettre, on dit que est un CD0L-système.
On peut également combiner ces deux notations. Si est non-effaçant, on dit que est un HPD0L-système. Si et sont non-effaçants, on dit que est un NPD0L-système. Si est non-effaçant et lettre-à-lettre, on dit que est un CPD0L-système.
On a ainsi défini huit types de L-systèmes. Pour chaque type , on note l'ensemble des mots infinis sur engendrés par un -système. Les huit classes de mots infinis ainsi définies vérifient de manière évidente les inclusions suivantes :
Le but de cette partie est de voir lesquelles de ces inclusions sont strictes.
Dans les questions 3.1 et 3.2 , on utilisera la propriété suivante, qui sera démontrée dans la partie 4 :
Proposition 1. Le mot infini de Thue-Morse (voir les questions 1.3 et 2.15) ne contient aucun facteur de la forme vvv, avec .

Question 3.1.

Soit le D0L-système . Montrer que (PD0L). Est-il possible de construire un tel contre-exemple sur l'alphabet ?
Indication : observer d'abord qu'en effaçant les dans , on retrouve le mot infini de Thue-Morse , puis que si était engendré par un PD0L-système ( ), on aurait nécessairement .

Question 3.2.

Soit le NPD0L-système , où et . Montrer que .
Indication : montrer que si était engendré par un D0L-système , alors il contiendrait un mot de la forme vvvv avec .

Question 3.3.

Montrer que . En déduire que et .
Indication : on pourra procéder par récurrence sur la taille de l'alphabet, et montrer que si avec effaçant, alors il existe un alphabet de cardinal strictement inférieur à celui de et des morphismes et tels que .

Question 3.4.

Montrer que .
Indication : on pourra commencer par montrer que, pour tout morphisme , il existe un entier strictement positif tel que pour tout , puis utiliser la question 2.17 pour se ramener à un HPD0L-système tel que si et seulement si .

Question 3.5.

Montrer que NPD0L CPD0L . Illustrer cette inclusion en construisant un CPD0L-système engendrant le mot infini construit à la question 3.2.
Indication : si est le NPD0L-système de départ, on pourra, après avoir modifié et , utiliser l'alphabet intermédiaire .

Question 3.6.

En rassemblant les résultats de cette partie, conclure en précisant la nature (inclusion stricte ou égalité) de toutes les inclusions figurant dans le diagramme (1). On distinguera les cas où vaut 1, 2, ou au moins 3.

4 Mots sans carré, mots sans cube

Soit un mot fini ou infini. On dit que contient un carré s'il existe un mot non vide tel que est facteur de (le mot est appelé le carré de ). Dans le cas contraire, on dit que est sans carré. Ainsi, abcbacbab contient un carré (le carré de cba) tandis que est sans carré. On note l'ensemble des mots de sans carré.
De même, on dit que est sans cube s'il ne contient aucun facteur de la forme avec .

Question 4.1.

Montrer qu'il n'existe qu'un nombre fini de mots sans carré dans . Décrire le langage .

Question 4.2.

Proposer et justifier un algorithme prenant en entrée un mot et retournant « contient un carré » ou « est sans carré » selon la nature de . Quelle est sa complexité?

Question 4.3.

Proposer et justifier un algorithme prenant en entrée l'alphabet et un entier , et retournant la liste des mots sans carré de longueur inférieure ou égale à dans . La complexité devra être au plus en , où et est le nombre de mots sans carré retournés.
On pourra utiliser le fait qu'un mot est sans carré si et seulement si n'a aucun suffixe de la forme et son préfixe de longueur est sans carré.
Dans les questions qui suivent, on cherche à montrer que est infini. On considère pour cela le morphisme .

Question 4.4.

Montrer que est injectif.
On note l'ensemble des mots de qui ne contiennent ni , ni , ni , ni , ni comme facteurs.

Question 4.5.

Montrer que pour tout mot .

Question 4.6.

Montrer que pour tout mot et tout facteur de autre que ou , il existe un unique triplet ( ), où et tel que . Montrer que le mot est alors facteur de .

Question 4.7.

Montrer que, si et contient un carré, alors contient soit un carré, soit un mot de la forme aybya avec .
Indication : si contient , commencer par appliquer le résultat de la question 4.6 à .

Question 4.8.

Montrer qu'aucun mot de ne contient de facteur de la forme aybya.

Question 4.9.

Déduire de ce qui précède que . Construire un DOL-système tel que est infini et .
Un mot sans carré est dit indéfiniment prolongeable si pour tout , il existe et dans de longueur tels que uwv soit sans carré. Un mot sans carré est dit non prolongeable si pour toute lettre et contiennent chacun un carré.

Question 4.10.

Montrer qu'il existe dans une infinité de mots sans carré indéfiniment prolongeables, et une infinité de mots sans carré non prolongeables (on commencera par contruire un mot sans carré non prolongeable).

Question 4.11.

En utilisant le résultat de la question 2.16, montrer que le mot infini de Thue-Morse est sans cube.
ENS Informatique MP 2001 - Version Web LaTeX | WikiPrépa | WikiPrépa