ENS Informatique MP PC 2005Sujet

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

Définitions

• Dans tout le problème, A est un alphabet fini, de cardinal k, muni d'une relation d'ordre total notée ≺. Pour simplifier les notations, on identifiera A au sous-ensemble {0, 1, …, k − 1} des entiers naturels, et ≺ à l'ordre naturel sur les entiers. On appelle lettres les éléments de A.
• A^+est l'ensemble des mots non vides sur l'alphabet A. La longueur d'un mot s ∈ A^+est notée |s|. On note s[i], 1 ≤ i ≤ |s|, la i-ème lettre du mot s, appelée aussi la lettre en position i. Le sous-mot s[i..j] de s, 1 ≤ i ≤ j ≤ |s|, est le mot composé des lettres de s en position allant de i à j. Les préfixes du mot s sont les sous-mots s[1..j] pour 1 ≤ j < |s| et ses suffixes sont les sous-mots s[i..|s|] pour 1 < i ≤ |s| (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 s et t de A^+est notée s ⋅ t. C'est le mot u de longueur |s| + |t| tel que u[i] = s[i] si 1 ≤ i ≤ |s| et u[i] = t[i − |s|] si |s| + 1 ≤ i ≤ |s| + |t|. On note s^i le mot obtenu en concaténant i fois le mot s avec lui-même (formellement, s^1 = s et s^i = s ⋅ s^(i − 1) pour i ≥ 2 ).

• On note ≤ _(lex) l'ordre lexicographique sur A^+, appelé aussi ordre du dictionnaire, et défini comme suit. Soient s et t deux mots de A^+. On note s < _(lex)t si :
  − s[1]≺t[1]
• ou ∃k, 2 ≤ k ≤ min(|s|, |t|), tel que s[i] = t[i] pour 1 ≤ i < k et s[k]≺t[k]
• ou |s| < |t| et s[i] = t[i] pour 1 ≤ i ≤ |s|

Structures de données

• Pour représenter un mot s ∈ A^+, on utilisera un tableau d'entiers de taille |s| + 1, indexé de 0 à |s| : l'élément d'indice 0 sera égal à |s| et l'élément d'indice i sera égal à s[i] pour 1 ≤ i ≤ |s|.
• Par ailleurs, on utilisera des listes d'entiers qu'on manipulera à l'aide des primitives suivantes. On note NIL la liste vide. Si Q est non vide ( Q ≠ NIL), la primitive tête (Q) renvoie le premier élément de la liste et la primitive queue (Q) renvoie la liste constituée des éléments suivants. La primitive ajoute-fin (Q, i) ajoute l'entier i à la fin de la liste Q. Si Q et Q^′ sont deux listes, la primitive concat (Q, Q^′) construit une liste composée des éléments de Q, suivis des éléments de Q^′.
• 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 O(m + n), O(m^2 logn), etc, où m, n, … 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 s et t de A^+pour l'ordre lexicographique ≤ _(lex). Quel est son coût en fonction de |s| et |t| ?
2. Proposer un algorithme de tri des n mots (calcul du tableau SIG) basé sur le pseudo-programme compare, et donner son coût dans le pire cas en fonction de n et ℓ_(max).

$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 : n = 5, ℓ = 3, s_1 = 210, s_2 = 100, s_3 = 112, s_4 = 102, et s_5 = 110.
2. Montrer que le coût de l'algorithme TriPaquets1 est en O((k + n)ℓ).
3. Quelle propriété vérifie Q à la fin de la première itération de la boucle sur j (c'est-à-dire lorsque j = ℓ )?
4. Même question à la fin de la j-è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 n mots de longueur ℓ_(max) 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 k = 2, u_2 = 0011 ∈ DB(2) et u_3 = 00011101 ∈ DB(3)
• si k = 3, v_2 = 002212011 ∈ DB(2) et v_3 = 000222122021121020120011101 ∈ DB(3).

Question 2.1.

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

Question 2.2.

• pour i ≥ n, s[i + 1] est la plus grande lettre de A, si elle existe, telle que s[i − n + 2..i + 1] (de longueur n ) n'est pas un sous-mot de s[1..i].

1. Écrire un pseudo-programme suivant qui calcule (si c'est possible) s[i + 1] à partir de s[1..i] pour i ≥ n. Quel serait le coût d'un pseudo-programme pour tout le calcul du mot s (en fonction de k, n et |s|) ?
2. On va montrer que |s| = k^n + n − 1 et que s[1..k^n] ∈ DB(n) (les mots u_2, u_3, v_2 et v_3 ont été construits de cette façon).
   (a) Soit z le suffixe de s de taille n − 1. Montrer que pour toute lettre a de A, a ⋅ z est un sous-mot de s. En déduire que z = 0^(n − 1) (c'est-à-dire que s se termine par n − 1 zéros).
   (b) Montrer que tous les mots de A^+de longueur n qui finissent par n − r zéros apparaissent dans s, pour tout r ≥ 1. Conclure.

Partie 3. Colliers, primaires et cycles

Question 3.1.

1. Vérifier que si s ∈ A^+est périodique et t ∼ s, alors t est périodique.
2. Pour n = 4 et k = 2, donner tous les mots de L^+de longueur inférieure ou égale à n. Même question pour n = 3 et k = 3.
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 L^+dont la longueur divise n ?

Question 3.2.

1. Soit n = |s| et m = |x|. Montrer que s[i] = s[i + m] pour 1 ≤ i ≤ n − m et s[i] = s[i + m − n] pour n − m + 1 ≤ i ≤ n ( s est donc inchangé par décalage circulaire de m positions).
2. Soit d = PGCD(m, n) et z = s[1..d]. Montrer que s = z^(n/d). (Indication : considérer les décalages circulaires de jm positions.)

Question 3.3.

1. Montrer que tout mot s ∈ A^+peut s'écrire de manière unique s = t^p avec t ∈ A^+non périodique et p ≥ 1.
2. Écrire un pseudo-programme racine qui, étant donné s ∈ A^+, calcule le mot t non périodique tel que s = t^p. Quel est son coût en fonction de |s| ?
3. Montrer que tout collier s ∈ C^+peut s'écrire s = t^p avec t ∈ L^+et p ≥ 1. Montrer que C_n = ∑_(d|n)L_d (la somme porte sur les diviseurs positifs de n ).
4. Que vaut la somme ∑_(d|n)dL_d ?

Question 3.4.

1. Soit s ∈ A^+. Montrer l'équivalence des trois propriétés suivantes:
   (i) s ∈ L^+.
   (ii) s est inférieur à tous ses décalages cycliques : s = u ⋅ v avec u, v ∈ A^+ ⇒ u ⋅ v < _(lex)v ⋅ u.
   (iii) s est inférieur à tous ses suffixes : s = u ⋅ v avec u, v ∈ A^+ ⇒ s < _(lex)v.
2. Factorisation en mots primaires:
   (a) Soit u, v ∈ L^+avec u < _(lex)v. Montrer que u ⋅ v ∈ L^+.
   (b) Montrer que tout mot s ∈ A^+peut s'écrire sous la forme s = p_1 ⋅ p_2⋯p_m, où p_i ∈ L^+(1 ≤ i ≤ m) et p_m ≤ _(lex)… ≤ _(lex)p_2 ≤ _(lex)p_1.
   (c) Montrer que dans la factorisation précédente, p_m est plus petit (pour l'ordre ≤ _(lex) ) que tout suffixe de s. En déduire l'unicité de cette factorisation.
   (d) Montrer enfin que si s ∉ L^+, alors p_1 est le plus long préfixe de s appartenant à L^+.

Question 3.5.

1. Soit p ∈ L^+. Montrer que p^m ∈ P^+pour tout m ≥ 1.
2. (Difficile.) Soit s ∈ L^+et t un préfixe de s. Soit a une lettre de A et u = t ⋅ a. Montrer que si s < _(lex)u alors u ∈ L^+.
3. Soit s ∈ P^+et p_1 le premier primaire dans la factorisation de s en mots primaires. Montrer que s est la |s|-extension de p_1.
4. Montrer que s ∈ P^+si et seulement si s est la |s|-extension d'un mot p ∈ L^+de longueur |p| ≤ |s|. Montrer l'unicité de p.
5. Soit s ∈ P^+et p le primaire dont s est la |s|-extension. Montrer que s ∈ L^+si et seulement si p = s, et que s ∈ C^+si et seulement si |p| divise |s|.

Question 3.6.

1. Soit s ∈ P(n), s ≠ (k − 1)^n. Déterminer le successeur de s dans P(n), c'est-à-dire le mot t ∈ P(n) tel que s < _(lex)t et s < _(lex)u ⇒ t ≤ _(lex)u pour tout u ∈ P(n). (Indication : incrémenter une lettre de s pour obtenir t.)
2. Écrire un pseudo-programme successeur qui calcule le successeur d'un mot s ∈ P(n), s ≠ (k − 1)^n.
3. Donner un algorithme qui énumère dans l'ordre lexicographique, tous les préprimaires de longueur égale à n. Donner un algorithme qui énumère dans l'ordre lexicographique, tous les primaires dont la longueur divise n.
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 n, on obtient un mot z ∈ DB(n). Montrer que z ≤ _(lex)z^′ pour tout z^′ ∈ DB(n) (ainsi z est le plus petit cycle de De Bruijn pour l'ordre lexicographique).