Filière MP (groupes MPI et I)
Épreuve commune aux ENS de Paris, Lyon et Cachan

Définitions

• Dans tout le problème, est un alphabet fini, de cardinal , muni d'une relation d'ordre total notée . Pour simplifier les notations, on identifiera au sous-ensemble des entiers naturels, et à l'ordre naturel sur les entiers. On appelle lettres les éléments de .
• est l'ensemble des mots non vides sur l'alphabet . La longueur d'un mot est notée . On note , la -ème lettre du mot , appelée aussi la lettre en position . Le sous-mot de , est le mot composé des lettres de en position allant de à . Les préfixes du mot sont les sous-mots pour et ses suffixes sont les sous-mots pour (noter qu'on ne considère pas le mot lui-même comme son propre préfixe, ni comme son propre suffixe).
• La concaténation de deux mots et de est notée . C'est le mot de longueur tel que si et si . On note le mot obtenu en concaténant fois le mot avec lui-même (formellement, et pour ).

• On note l'ordre lexicographique sur , appelé aussi ordre du dictionnaire, et défini comme suit. Soient et deux mots de . On note si :
  
• ou , tel que pour et
• ou et pour

Structures de données

• Pour représenter un mot , on utilisera un tableau d'entiers de taille , indexé de 0 à : l'élément d'indice 0 sera égal à et l'élément d'indice sera égal à pour .
• Par ailleurs, on utilisera des listes d'entiers qu'on manipulera à l'aide des primitives suivantes. On note NIL la liste vide. Si est non vide ( NIL), la primitive tête renvoie le premier élément de la liste et la primitive queue renvoie la liste constituée des éléments suivants. La primitive ajoute-fin ajoute l'entier à la fin de la liste . Si et sont deux listes, la primitive concat construit une liste composée des éléments de , suivis des éléments de .
• Enfin, une liste est triée si ses éléments sont rangés par ordre croissant (au sens large).

Algorithmes et pseudo-programmes

• Pour les questions qui demandent la conception d'un algorithme : il s'agit de décrire en français, de façon concise mais précise, les idées essentielles de votre réponse.
• Pour les questions qui demandent l'écriture d'un pseudo-programme : il s'agit d'exprimer votre algorithme dans un langage de votre choix, avec les structures de données (tableaux ou listes) décrites ci-avant, et les structures de contrôle (boucles, conditionnelles, ...) classiques.
• Le coût d'un algorithme ou d'un pseudo-programme est le nombre d'opérations élémentaires qu'il effectue. Une opération élémentaire est une comparaison ou un test d'égalité entre deux lettres, un appel à l'une des primitives précédentes sur les listes d'entiers, un accès en lecture ou en écriture à une case de tableau, un incrément de compteur de boucle.
• Le coût d'un algorithme ou d'un pseudo-programme ne sera pas calculé exactement mais seulement estimé en ordre de grandeur, avec des expressions du type , etc, où sont des paramètres en entrée de l'algorithme. Bien sûr, on s'attachera à concevoir des algorithmes et des pseudo-programmes de coût le plus faible possible.

Partie 1. Tri par paquets et ordre lexicographique

Question 1.1.

1. Écrire un pseudo-programme compare qui compare deux mots et de pour l'ordre lexicographique . Quel est son coût en fonction de et ?
2. Proposer un algorithme de tri des mots (calcul du tableau SIG) basé sur le pseudo-programme compare, et donner son coût dans le pire cas en fonction de et .

$Q \leftarrow$ NIL
pour $i$ croissant de 1 à $n$ faire
    ajoute-fin $(Q, i)$
fin pour
pour $j$ décroissant de $\ell$ à 1 faire
    pour $p$ croissant de 0 à $k-1$ faire
        $P[p] \leftarrow$ NIL
    fin pour
    tant que ( $Q \neq$ NIL) faire
        $i \leftarrow$ tête $(Q)$
        $Q \leftarrow$ queue $(Q)$
        ajoute-fin $(P[\operatorname{tab}[i][j]], i)$
    fin tant que
    pour $p$ croissant de 0 à $k-1$ faire
        $Q \leftarrow \operatorname{concat}(Q, P[p])$
    fin pour
fin pour
pour $i$ croissant de 1 à $n$ faire
    $\operatorname{SIG}[i] \leftarrow$ tête $(Q)$
    $Q \leftarrow$ queue $(Q)$
fin pour

$Q \leftarrow$ NIL
pour $p$ croissant de 0 à $k-1$ faire
    $P[p] \leftarrow$ NIL
fin pour
pour $j$ décroissant de $\ell_{\max }$ à 1 faire
    $Q \leftarrow \operatorname{concat}$ (Longueur $[j], Q$ )
    tant que ( $Q \neq$ NIL) faire
        $i \leftarrow$ tête $(Q)$
        $Q \leftarrow$ queue $(Q)$
        ajoute-fin $(P[\operatorname{tab}[i][j]], i)$
    fin tant que
    tant que (Présent $[j] \neq$ NIL) faire
        $p \leftarrow$ tête $($ Présent $[j])$
        Présent $[j] \leftarrow$ queue(Présent $[j]$ )
        $Q \leftarrow \operatorname{concat}(Q, P[p])$
        $P[p] \leftarrow$ NIL
    fin tant que
fin pour
pour $i$ croissant de 1 à $n$ faire
    $\operatorname{SIG}[i] \leftarrow$ tête $(Q)$
    $Q \leftarrow$ queue $(Q)$
fin pour

Question 1.2.

1. Exécuter l'algorithme TriPaquets1 sur l'exemple suivant : , , et .
2. Montrer que le coût de l'algorithme TriPaquets1 est en .
3. Quelle propriété vérifie à la fin de la première itération de la boucle sur (c'est-à-dire lorsque )?
4. Même question à la fin de la -ème itération de cette boucle? Conclusion?
5. Pourquoi l'algorithme TriPaquets1 procède-t-il à partir de la dernière lettre des mots et non pas de la première?

Question 1.3.

1. Expliquer comment se ramener au cas de mots de longueur pour utiliser l'algorithme TriPaquets1. Quel est le coût?
2. On va améliorer l'algorithme TriPaquets1; on procède en trois étapes:

Partie 2. Cycles de De Bruijn

• si et
• si et .

Question 2.1.

1. Dans un mot de , combien de fois apparaît chaque lettre de l'alphabet ?
2. Proposer un algorithme qui vérifie si un mot est un élément de . Quel est son coût (en fonction de et de ? Peut-on diminuer le coût en augmentant l'espace mémoire utilisé?
3. Que peut-on dire du mot infini construit par récurrence? (Indication : s'intéresser au cas .)

Question 2.2.

• pour est la plus grande lettre de , si elle existe, telle que (de longueur ) n'est pas un sous-mot de .

1. Écrire un pseudo-programme suivant qui calcule (si c'est possible) à partir de pour . Quel serait le coût d'un pseudo-programme pour tout le calcul du mot (en fonction de et ?
2. On va montrer que et que (les mots et ont été construits de cette façon).
   (a) Soit le suffixe de de taille . Montrer que pour toute lettre de est un sous-mot de . En déduire que (c'est-à-dire que se termine par zéros).
   (b) Montrer que tous les mots de de longueur qui finissent par zéros apparaissent dans , pour tout . Conclure.

Partie 3. Colliers, primaires et cycles

Question 3.1.

1. Vérifier que si est périodique et , alors est périodique.
2. Pour et , donner tous les mots de de longueur inférieure ou égale à . Même question pour et .
3. Pour les deux exemples précédents, que peut-on dire du mot obtenu en énumérant dans l'ordre lexicographique, et en les concaténant, tous les mots de dont la longueur divise ?

Question 3.2.

1. Soit et . Montrer que pour et pour ( est donc inchangé par décalage circulaire de positions).
2. Soit et . Montrer que . (Indication : considérer les décalages circulaires de jm positions.)

Question 3.3.

1. Montrer que tout mot peut s'écrire de manière unique avec non périodique et .
2. Écrire un pseudo-programme racine qui, étant donné , calcule le mot non périodique tel que . Quel est son coût en fonction de ?
3. Montrer que tout collier peut s'écrire avec et . Montrer que (la somme porte sur les diviseurs positifs de ).
4. Que vaut la somme ?

Question 3.4.

1. Soit . Montrer l'équivalence des trois propriétés suivantes:
   (i) .
   (ii) est inférieur à tous ses décalages cycliques : avec .
   (iii) est inférieur à tous ses suffixes : avec .
2. Factorisation en mots primaires:
   (a) Soit avec . Montrer que .
   (b) Montrer que tout mot peut s'écrire sous la forme , où et .
   (c) Montrer que dans la factorisation précédente, est plus petit (pour l'ordre ) que tout suffixe de . En déduire l'unicité de cette factorisation.
   (d) Montrer enfin que si , alors est le plus long préfixe de appartenant à .

Question 3.5.

1. Soit . Montrer que pour tout .
2. (Difficile.) Soit et un préfixe de . Soit une lettre de et . Montrer que si alors .
3. Soit et le premier primaire dans la factorisation de en mots primaires. Montrer que est la -extension de .
4. Montrer que si et seulement si est la -extension d'un mot de longueur . Montrer l'unicité de .
5. Soit et le primaire dont est la -extension. Montrer que si et seulement si , et que si et seulement si divise .

Question 3.6.

1. Soit . Déterminer le successeur de dans , c'est-à-dire le mot tel que et pour tout . (Indication : incrémenter une lettre de pour obtenir .)
2. Écrire un pseudo-programme successeur qui calcule le successeur d'un mot .
3. Donner un algorithme qui énumère dans l'ordre lexicographique, tous les préprimaires de longueur égale à . Donner un algorithme qui énumère dans l'ordre lexicographique, tous les primaires dont la longueur divise .
4. (Très difficile.) Montrer que si on énumère dans l'ordre lexicographique, en les concaténant, tous les primaires dont la longueur divise , on obtient un mot . Montrer que pour tout (ainsi est le plus petit cycle de De Bruijn pour l'ordre lexicographique).