Informatique
CCINPMPI2026
Cherchez d'abord seul. En cas de blocage, ouvrez une indication, réessayez, puis seulement la solution.
Rédigé par IA, non vérifié
Signaler une erreur# CCINP MPI — Informatique 2026 · Corrigé guidé
*Corrigé rédigé par IA (La Belle Copie), non officiel. Signalez toute erreur.*
## Présentation du sujet
**Cadre.** Épreuve spécifique de la filière MPI (MPI5IN, mutualisée avec e3a-Polytech). Elle dure 4 heures, sans calculatrice. Le sujet compte **deux parties indépendantes** et 41 questions. Le langage est imposé : **C** dans la partie I, **OCaml** dans la partie II.
**Découpage.**
| Partie | Thème | Questions | Notions mobilisées |
|---|---|---|---|
| I.1–I.3 | NP-complétude du voyageur de commerce (TSP) | Q1–Q11 | classe NP, certificats, réductions polynomiales, transitivité, gadgets |
| I.4 | 2-approximation de TSP métrique | Q12–Q22 | arbre couvrant minimal (Kruskal), parcours en profondeur, inégalité triangulaire, C : fichiers, `malloc`/`free`, pointeurs |
| II.1 | Quatre définitions de la suite de Prouhet-Thue-Morse | Q23–Q29 | écriture binaire, récurrences (simple et forte), morphismes de mots, OCaml récursif sur les listes, exceptions |
| II.2 | Mot infini de Thue-Morse : carrés, cubes, entrelacements | Q30–Q41 | combinatoire des mots, facteurs, arguments de parité et d'alignement |
**Ce que fait chaque partie.** La partie I démontre que TSP est NP-complet par la chaîne COUVERTURE-SOMMET $\le_p$ CYCLE-HAMILTONIEN $\le_p$ TSP. La première réduction utilise le gadget classique à 12 sommets ; on n'en étudie que la construction. La partie passe ensuite au problème d'optimisation : sous inégalité triangulaire, parcourir un arbre couvrant minimal en profondeur et court-circuiter les sommets déjà vus coûte au plus deux fois l'optimum. On programme cet algorithme en C. La partie II montre que quatre définitions de la suite PTM coïncident (parité du nombre de bits, doublement par complémentation, récurrence sur les indices, itération du morphisme $\mu$). Elle prouve ensuite que les mots $T_n$ n'ont pas de cube, en passant par la propriété plus forte « n'est pas un entrelacement », qui se transmet de $T_n$ à $\mu(T_n)=T_{n+1}$.
**Difficulté et longueur.** Le sujet est long mais très guidé. Les difficultés se concentrent sur Q8 (traversées du gadget, si l'on veut justifier qu'il n'y en a pas d'autre), Q14 (chaque arête parcourue deux fois), Q35 (traduire la définition d'entrelacement en indices) et surtout **Q39**, la question la plus technique, où l'alignement sur les blocs de $\mu$ est décisif.
**Questions à ne pas laisser passer.** Q1, Q2, Q3, Q4, Q5, Q6, Q7, Q9, Q12, Q13, Q18, Q21, Q23, Q24, Q25, Q29, Q32, Q34 et Q36. Ce sont des applications directes du cours ou de l'énoncé. Q40 et Q41 se font en trois lignes même si Q39 a résisté : on peut utiliser le résultat d'une question non traitée.
**Gestion du temps.** Comptez environ deux heures par partie. Dans la partie I, le C se rédige vite si les questions de gestion mémoire (Q20–Q22) sont pensées ensemble. Dans la partie II, ne restez pas bloqué sur Q39 : Q40 et Q41 s'en déduisent immédiatement.
**Remarques sur l'énoncé.** Trois imprécisions sans conséquence, à signaler sur la copie :
1. En Q8, les arêtes supplémentaires viennent des étapes (iii) et (iv), et non de l'étape (ii).
2. La définition 3 est posée « pour $n>0$ », ce qui laisse $t_1$ indéterminé. Il faut la lire pour $n\ge 0$.
3. La définition 4 est posée « pour $i\in\mathbb N^\ast$ », ce qui laisse $u_1$ indéterminé. Il faut la lire pour $i\ge 0$.
---
## Partie I — Problème du voyageur de commerce
On démontre que TSP est NP-complet : appartenance à NP, puis deux réductions polynomiales. Le seul outil est la définition de NP par certificat et la notion de réduction. Les sous-parties I.1 à I.3 ne demandent aucun code.
### Question 1
> [!INDICATION]
> Un problème est dans NP s'il admet des certificats de taille polynomiale vérifiables en temps polynomial. Quel objet prouve qu'une instance $(G,k)$ est positive ?
> [!INDICATION]
> Le certificat est un ordre de visite des sommets. Énumérez tout ce qu'il faut tester pour qu'il décrive un cycle hamiltonien de coût $\le k$, et chiffrez le coût de chaque test.
#### Solution
Soit une instance $(G,k)$ de TSP, avec $G=(S,A,c)$ donné par sa matrice des coûts et $n=|S|$.
- **Certificat** : une suite $\sigma=(s_0,\dots,s_{n-1})$ de $n$ sommets. Sa taille est $O(n\log n)$ bits, polynomiale en celle de l'instance.
- **Vérification** :
1. $\sigma$ est une permutation de $S$ : avec un tableau de booléens `vu`, on rejette tout sommet rencontré deux fois, en $O(n)$ ;
2. chaque arête $\{s_i,s_{i+1\bmod n}\}$ existe, c'est-à-dire que son coût n'est pas $+\infty$ : $O(n)$ ;
3. $\sum_{i=0}^{n-1}c(s_i,s_{i+1\bmod n})\le k$ : $O(n)$.
Si les tests réussissent, $(s_0,\dots,s_{n-1},s_0)$ est un cycle hamiltonien de coût $\le k$. Réciproquement, un tel cycle fournit un certificat accepté. La vérification se fait en temps polynomial, donc **TSP ∈ NP**.
> [!PIEGE]
> Le test 1 n'est pas décoratif. Sans lui, la suite $(0,0,\dots,0)$ passerait les tests 2 et 3, puisque $c(s,s)=0$. Dire « on essaie tous les cycles » montre que le problème est décidable, pas qu'il est dans NP.
> [!JURY]
> Une preuve d'appartenance à NP nomme explicitement le certificat, majore sa taille et chiffre le coût de la vérification. Ces trois éléments sont attendus, même brièvement.
### I.1 — Réduction de CYCLE-HAMILTONIEN vers TSP
### Question 2
> [!INDICATION]
> C'est la question 1 sans le coût : quel test devient sans objet ?
#### Solution
Le certificat est une suite $(s_0,\dots,s_{n-1})$ de sommets, de taille $O(n)$. On vérifie que c'est une permutation de $S$ ($O(n)$) et que $\{s_i,s_{i+1\bmod n}\}\in A$ pour tout $i$ ($n$ tests en $O(1)$ avec une matrice d'adjacence). Un certificat est accepté si et seulement si $G$ a un cycle hamiltonien. Donc **CYCLE-HAMILTONIEN ∈ NP**.
### Question 3
> [!INDICATION]
> Une réduction polynomiale demande deux choses : une sortie de taille polynomiale et un temps de calcul polynomial. Combien d'arêtes a $G'$ ?
> [!INDICATION]
> Pour chaque paire de sommets, combien d'opérations faut-il pour décider du coût $1$ ou $2$ ? Cela dépend de la représentation de $G$ : annoncez-la.
#### Solution
Soit $n=|S|$, avec $G$ donné par matrice d'adjacence (sinon on la construit en $O(n^2+|A|)$). $G'$ a $n$ sommets et $\binom n2$ arêtes. Le coût de chacune s'obtient par un accès en $O(1)$ à la matrice de $G$, et $k=n$ en $O(1)$. La sortie a une taille $O(n^2)$ et la construction se fait en **$O(n^2)$** : elle est polynomiale.
> [!METHODE]
> Pour toute réduction, on écrit séparément la taille de l'instance produite et le coût de sa construction. Un algorithme qui produirait une sortie exponentielle ne serait jamais polynomial, même si chaque écriture coûtait $O(1)$.
### Question 4
> [!INDICATION]
> Un cycle hamiltonien de $G$ est-il encore un cycle hamiltonien de $G'$ ? Combien d'arêtes a-t-il, et combien coûte chacune ?
#### Solution
Soit $H=(s_0,\dots,s_{n-1},s_0)$ un cycle hamiltonien de $G$. Comme $S'=S$ et que $G'$ est complet, $H$ est un cycle hamiltonien de $G'$. Ses $n$ arêtes sont des arêtes de $G$, donc chacune coûte $1$ : $c(H)=n=k$. **TSP répond Vrai sur $(G',k)$.**
> [!PIEGE]
> Un cycle hamiltonien sur $n$ sommets a $n$ arêtes, et non $n-1$ : il ne faut pas oublier l'arête de retour. C'est ce décompte qui rend le seuil $k=|S|$ exact.
### Question 5
> [!INDICATION]
> Minorez le coût de n'importe quel cycle hamiltonien de $G'$.
> [!INDICATION]
> Un cycle de coût $\le n$ formé de $n$ arêtes de coût $1$ ou $2$ : que peut-on dire de chacune de ses arêtes ?
#### Solution
Soit $H'$ un cycle hamiltonien de $G'$ tel que $c(H')\le n$. Il a $n$ arêtes de coût $\ge 1$, donc $c(H')\ge n$, d'où $c(H')=n$. Une seule arête de coût $2$ porterait le coût à $n+1$ au moins : toutes coûtent donc $1$ et sont des arêtes de $G$. Comme $S'=S$, $H'$ est un cycle hamiltonien de $G$. **CYCLE-HAMILTONIEN répond Vrai sur $G$.**
Avec Q3 et Q4 : $\text{CYCLE-HAMILTONIEN}\le_p\text{TSP}$.
> [!METHODE]
> L'encadrement $n\le c(H')\le n$, qui force l'égalité terme à terme, est un argument standard des réductions par pondération 1/2.
### I.2 — Réduction de COUVERTURE-SOMMET vers CYCLE-HAMILTONIEN
Il s'agit de la réduction classique, présentée par exemple dans le manuel de Cormen et al. L'énoncé admet l'équivalence et ne demande que d'étudier la construction sur le graphe de la figure 1. On y lit les arêtes $e_1=\{\alpha,\delta\}$, $e_2=\{\beta,\delta\}$, $e_3=\{\gamma,\delta\}$, $e_4=\{\delta,\epsilon\}$, $e_5=\{\alpha,\beta\}$ et $e_6=\{\gamma,\epsilon\}$.
### Question 6
> [!INDICATION]
> Repérez le sommet de plus grand degré et raisonnez selon qu'il appartient ou non à la couverture.
> [!INDICATION]
> Si $\delta$ est dans la couverture, quelles arêtes restent à couvrir ? Ont-elles une extrémité commune ?
#### Solution
**$m=2$ : Faux.**
- Si $\delta\notin S_c$, les arêtes $e_1,\dots,e_4$ imposent $\alpha,\beta,\gamma,\epsilon\in S_c$ : $|S_c|\ge 4$.
- Si $\delta\in S_c$, il reste $e_5=\{\alpha,\beta\}$ et $e_6=\{\gamma,\epsilon\}$, qui sont disjointes : il faut deux sommets de plus, et $|S_c|\ge 3$.
**$m=3$ : Vrai**, avec $S_c=\{\alpha,\gamma,\delta\}$ : $\delta$ couvre $e_1$ à $e_4$, $\alpha$ couvre $e_5$ et $\gamma$ couvre $e_6$.
> [!PIEGE]
> Un « non » se démontre : présenter deux ou trois tentatives infructueuses ne prouve rien. Attention aussi à la lecture de la figure : l'arête $e_6$ relie $\gamma$ à $\epsilon$ et ne passe pas par $\delta$. La somme des degrés, $12=2\times 6$, permet de le contrôler.
### Question 7
> [!INDICATION]
> Appliquez la définition de $A_e$ avec $s=\beta$ et $t=\delta$ : deux chaînes de six sommets, puis quatre arêtes « croisées ».
#### Solution
Les sommets $\beta_1,\dots,\beta_6$ sont sur la ligne du haut et $\delta_1,\dots,\delta_6$ sur celle du bas, chaque $\delta_i$ sous $\beta_i$. Les arêtes sont :
- les chaînes $\beta_1-\beta_2-\cdots-\beta_6$ et $\delta_1-\delta_2-\cdots-\delta_6$ (10 arêtes) ;
- les obliques $\{\beta_3,\delta_1\}$ et $\{\delta_3,\beta_1\}$, qui forment un X sur les colonnes 1 à 3 ;
- les obliques $\{\beta_6,\delta_4\}$ et $\{\delta_6,\beta_4\}$, qui forment un X sur les colonnes 4 à 6.
On a bien $5+5+4=14$ arêtes. Seuls les quatre coins $\beta_1,\delta_1,\beta_6,\delta_6$ seront reliés au reste de $G'$.
> [!METHODE]
> Comptez les arêtes de votre dessin : l'énoncé en annonce 14, c'est un contrôle gratuit.
### Question 8
> [!INDICATION]
> Un cycle hamiltonien de $G'$ ne peut entrer dans le gadget et en sortir que par $s_1,t_1,s_6,t_6$. Sa trace sur $G_e$ est donc un ensemble de chaînes disjointes qui couvrent les 12 sommets, d'extrémités dans ces quatre sommets.
> [!INDICATION]
> Les sommets $s_2,s_5,t_2,t_5$ ne sont reliés qu'à deux voisins dans le gadget : quelles arêtes sont alors forcées ?
> [!INDICATION]
> Une fois les quatre chaînes de trois sommets forcées, discutez selon que l'arête $\{s_3,s_4\}$ est utilisée ou non. Un cycle hamiltonien ne contient pas de cycle plus petit.
#### Solution
On note $s_i=s_i(e)$ et $t_i=t_i(e)$. Les trois traversées sont, au sens près :
$$\begin{array}{ll}
\text{(a)} & s_1\,s_2\,s_3\,t_1\,t_2\,t_3\,t_4\,t_5\,t_6\,s_4\,s_5\,s_6 \quad\text{(entrée } s_1,\ \text{sortie } s_6)\\
\text{(b)} & t_1\,t_2\,t_3\,s_1\,s_2\,s_3\,s_4\,s_5\,s_6\,t_4\,t_5\,t_6 \quad\text{(entrée } t_1,\ \text{sortie } t_6)\\
\text{(c)} & s_1\cdots s_6\ \text{ puis, lors d'un autre passage, }\ t_1\cdots t_6
\end{array}$$
**Exhaustivité.** Les sommets $s_2,s_5,t_2,t_5$ ont degré 2 et ne sont pas des extrémités. Les chaînes $s_1s_2s_3$, $s_4s_5s_6$, $t_1t_2t_3$ et $t_4t_5t_6$ sont donc forcées. Les sommets $s_3,s_4,t_3,t_4$ ont besoin d'une arête de plus, prise parmi $\{s_3,s_4\}$, $\{s_3,t_1\}$, $\{t_3,s_1\}$, $\{t_3,t_4\}$, $\{s_6,t_4\}$ et $\{t_6,s_4\}$.
- Si $\{s_3,s_4\}$ est prise : avec $\{t_3,t_4\}$, on obtient (c) ; sinon $t_3$ se raccorde à $s_1$ et $t_4$ à $s_6$, ce qui donne (b).
- Sinon, $s_3$ se raccorde à $t_1$ et $s_4$ à $t_6$. $t_3$ ne peut pas se raccorder à $s_1$, car cela fermerait le cycle $s_1s_2s_3t_1t_2t_3s_1$. Donc $\{t_3,t_4\}$ est prise, ce qui donne (a).
Le cas (a) correspond à « $s$ sélectionné, pas $t$ », le cas (b) à l'inverse et le cas (c) à « les deux sélectionnés ». Aucune traversée n'existe si ni $s$ ni $t$ n'est sélectionné : c'est ce qui force la propriété de couverture.
> [!PIEGE]
> On peut croire qu'une chaîne de $s_1$ à $t_6$ couvrant le gadget existe. La discussion montre que non, et c'est précisément l'intérêt du gadget.
### Question 9
> [!INDICATION]
> Listez les arêtes incidentes à $\gamma$ et à $\delta$, choisissez un ordre et annoncez-le. Combien d'arêtes l'étape (iii) produit-elle pour un sommet de degré $d$ ?
#### Solution
On prend l'ordre croissant des indices.
$$A_\gamma=\bigl\{\{\gamma_6(e_3),\gamma_1(e_6)\}\bigr\}$$
$$A_\delta=\bigl\{\{\delta_6(e_1),\delta_1(e_2)\},\ \{\delta_6(e_2),\delta_1(e_3)\},\ \{\delta_6(e_3),\delta_1(e_4)\}\bigr\}$$
On a bien $|A_s|=d(s)-1$ : pour $\delta$, ces arêtes enfilent les quatre gadgets en un chemin de $\delta_1(e_1)$ à $\delta_6(e_4)$, et l'étape (iv) relie les $a_i$ à ces deux extrémités.
> [!PIEGE]
> $\gamma_i(e)$ n'a de sens que si $\gamma$ est une extrémité de $e$. L'ordre des arêtes étant arbitraire, il doit être annoncé : $A_\delta$ en dépend.
### Question 10
> [!INDICATION]
> Comptez sommets et arêtes étape par étape. Quelle formule relie $\sum_s d(s)$ au nombre d'arêtes ?
> [!INDICATION]
> L'étape (iv) relie chaque $a_i$ à deux sommets pour chaque $s\in S$ : c'est elle qui donne le terme dominant. Que faire d'un sommet isolé ?
#### Solution
Soient $n=|S|$ et $p=|A|$. On retire au préalable les sommets isolés : ils ne changent pas la réponse et l'étape (iv) n'a pas de sens pour eux. Alors :
- $|S'|=m+12p$ ;
- $|A'|=14p+\sum_s(d(s)-1)+2mn=16p-n+2mn$, car $\sum_s d(s)=2p$ ;
- avec $m\le n$, $|A'|\le 16p+2n^2$.
Coût de chaque étape : (i) $O(n)$, (ii) $O(p)$, (iii) $O(n+p)$ (on range d'abord les arêtes incidentes à chaque sommet), (iv) $O(mn)=O(n^2)$. Au total : **$O(n^2+p)$**, polynomial.
### I.3 — Conclusion des réductions
### Question 11
> [!INDICATION]
> NP-complet signifie : dans NP, et NP-difficile. Quelles questions fournissent chacun des deux points ?
> [!INDICATION]
> Composez les deux réductions. Pourquoi la composée de deux réductions polynomiales est-elle polynomiale ? Pensez à la taille de la sortie de la première.
#### Solution
- TSP ∈ NP (Q1).
- $\text{COUVERTURE-SOMMET}\le_p\text{CYCLE-HAMILTONIEN}$ (Q10 et l'équivalence admise).
- $\text{CYCLE-HAMILTONIEN}\le_p\text{TSP}$ (Q3–Q5).
- **Transitivité.** Si $f$ se calcule en temps $P(|x|)$, alors $|f(x)|\le P(|x|)$, et $g(f(x))$ se calcule en temps $P(|x|)+Q(P(|x|))$, qui est polynomial.
Tout problème de NP se réduit à COUVERTURE-SOMMET, qui est NP-complet, donc à TSP par transitivité : TSP est NP-difficile. **TSP est NP-complet.**
> [!PIEGE]
> Le sens des réductions est essentiel : on réduit le problème connu difficile **vers** le problème étudié. L'oubli de l'appartenance à NP est l'autre faute classique.
### I.4 — 2-approximation du problème TSP
On suppose désormais $G$ complet et $c$ vérifiant l'inégalité triangulaire. L'algorithme 1 calcule un arbre couvrant minimal $T$, le parcourt en profondeur (liste $L$) et ne garde que la première visite de chaque sommet. Les questions Q13 à Q17 forment une preuve en chaîne, puis Q18 à Q22 la programment en C.
### Question 12
> [!INDICATION]
> D'après la figure 2, l'« étape 2 » est le calcul de l'arbre $T$. Quel algorithme glouton du programme calcule un arbre couvrant de poids minimal ?
> [!INDICATION]
> Pour la complexité, distinguez le tri des arêtes de la gestion des composantes, puis exprimez le résultat en fonction de $n$ seul, puisque $G$ est complet.
#### Solution
On utilise l'**algorithme de Kruskal** : trier les arêtes par coût croissant, puis retenir chaque arête qui relie deux composantes distinctes, avec une structure union-find. La complexité est $O(p\log p)$ (tri), plus $p$ opérations union-find quasi constantes. Pour un graphe complet, $p=n(n-1)/2$, d'où **$O(n^2\log n)$**.
> [!METHODE]
> Sur un graphe complet, le nombre d'arêtes n'est pas un paramètre libre : traduisez toujours une complexité en $O(p\log p)$ en fonction de $n$. Pour un graphe dense donné par matrice, Prim en version naïve atteint $O(n^2)$.
### Question 13
> [!INDICATION]
> Retirez une arête d'un cycle hamiltonien : quel objet obtenez-vous ?
> [!INDICATION]
> Deux faits sont à justifier : cet objet est un arbre couvrant, et les coûts sont positifs.
#### Solution
Soit $H^\ast$ un cycle hamiltonien optimal ($n\ge 2$). En retirant l'une de ses arêtes $\{u,v\}$, on obtient une chaîne passant par les $n$ sommets : un graphe connexe à $n$ sommets et $n-1$ arêtes, donc un arbre couvrant $P$. Comme $c\ge 0$, $c(P)=c(H^\ast)-c(u,v)\le c(H^\ast)$. Par minimalité de $T$, $c(T)\le c(P)$, d'où
$$c(T)\le c(H^\ast).$$
### Question 14
> [!INDICATION]
> Combien de fois chaque arête de $T$ est-elle empruntée par le parcours $L$ ? Regardez la figure 2.
> [!INDICATION]
> Démontrez-le par récurrence sur l'arbre, en décrivant $L$ comme la racine, puis les parcours des sous-arbres séparés par des retours à la racine.
#### Solution
Si $r$ a pour fils $v_1,\dots,v_k$, de sous-arbres $T_1,\dots,T_k$, alors
$$L(T,r)=(r)\cdot L(T_1,v_1)\cdot(r)\cdots L(T_k,v_k)\cdot(r),$$
et $L=(r)$ pour un arbre réduit à sa racine. Par récurrence sur la taille de l'arbre, deux éléments consécutifs de $L$ sont adjacents dans $T$, et chaque arête de $T$ est empruntée exactement deux fois : une à la descente, une à la remontée. Donc
$$c(L)=2c(T)\le 2c(H^\ast).$$
Sur la figure 2, on vérifie que $|L|=15=2\times 8-1$, soit 14 arêtes empruntées, deux fois 7.
> [!JURY]
> Affirmer « chaque arête est parcourue deux fois » sans justification revient à admettre le contenu de la question. Une récurrence courte sur la structure de l'arbre est attendue.
### Question 15
> [!INDICATION]
> Que devient le coût quand on remplace le détour $v_{j-1}\to v_j\to v_{j+1}$ par l'arête directe $v_{j-1}\to v_{j+1}$ ? Quelle hypothèse de I.4 garantit que cette arête existe ?
#### Solution
Soit $L=(v_0,\dots,v_q)$, et $v_j$ ($1\le j\le q-1$) un sommet qui apparaît aussi ailleurs. On le supprime. L'arête $\{v_{j-1},v_{j+1}\}$ existe car $G$ est complet. Le parcours reste fermé et visite toujours tous les sommets, et
$$c(L')-c(L)=c(v_{j-1},v_{j+1})-c(v_{j-1},v_j)-c(v_j,v_{j+1})\le 0$$
par l'inégalité triangulaire.
> [!PIEGE]
> On ne supprime qu'une occurrence **répétée**, et jamais les extrémités $v_0$ et $v_q$. Sinon le parcours cesse de couvrir tous les sommets ou de se refermer.
### Question 16
> [!INDICATION]
> Itérez la question 15. Quelle occurrence de chaque sommet choisir de garder pour décrire simplement le résultat ?
#### Solution
On supprime, tant qu'il y en a, les occurrences $v_j$ ($1\le j\le q-1$) qui ne sont pas la première de leur sommet. La longueur décroît strictement, donc le procédé termine. Il reste $H$ : **les sommets dans l'ordre de leur première apparition dans $L$ (ordre préfixe du parcours de $T$), suivis de la racine.** Ses $n$ premiers sommets sont distincts et $G$ est complet, donc $H$ est un cycle hamiltonien. Sur la figure 2, $H=[1,2,3,8,4,5,6,7,1]$.
### Question 17
> [!INDICATION]
> Une $\rho$-approximation est une solution admissible, de coût au plus $\rho$ fois l'optimum, calculée en temps polynomial. Vérifiez les trois points.
#### Solution
$H$ est un cycle hamiltonien, donc admissible. Chaque suppression de Q16 ne fait pas croître le coût (Q15), donc $c(H)\le c(L)\le 2c(H^\ast)$ (Q14). Le temps de calcul est polynomial : $O(n^2\log n)$ pour Kruskal, $O(n^2)$ pour le parcours, $O(n)$ pour l'extraction. Donc
$$c(H^\ast)\le c(H)\le 2c(H^\ast),$$
et **l'algorithme 1 est une 2-approximation de TSP.**
> [!METHODE]
> Le schéma « borne inférieure calculable (ici l'arbre couvrant minimal) + solution construite à partir d'elle » est celui de la plupart des algorithmes d'approximation. Sans inégalité triangulaire, aucun facteur constant n'est atteignable en temps polynomial, sauf si P = NP. On le voit en reprenant la réduction de I.1 avec un très grand coût à la place de $2$.
### Question 18
> [!INDICATION]
> Lisez d'abord $n$ et $p$, puis allouez la matrice. Quelles valeurs y mettre avant de lire les arêtes ? Revoyez la définition de $c$ dans l'énoncé.
> [!INDICATION]
> Le graphe est non orienté : chaque arête lue remplit deux cases.
#### Solution
On suppose les sommets numérotés de $0$ à $n-1$ (sinon, retrancher $1$ après lecture). $+\infty$ est représenté par une constante.
```c
const int INFINI = 1000000000;
Graphe* creer_graphe(char* nom_fichier) {
FILE* f = fopen(nom_fichier, "r");
assert(f != NULL);
int n = 0;
int p = 0;
fscanf(f, "%d %d", &n, &p);
Graphe* G = malloc(sizeof(Graphe));
G->n = n;
G->C = malloc(n * sizeof(int*));
for (int i = 0; i < n; i = i + 1) {
G->C[i] = malloc(n * sizeof(int));
for (int j = 0; j < n; j = j + 1) {
if (i == j) {
G->C[i][j] = 0;
} else {
G->C[i][j] = INFINI;
}
}
}
for (int k = 0; k < p; k = k + 1) {
int s = 0;
int t = 0;
int c = 0;
fscanf(f, "%d %d %d", &s, &t, &c);
G->C[s][t] = c;
G->C[t][s] = c;
}
fclose(f);
return G;
}
```
Complexité : $O(n^2+p)$.
> [!PIEGE]
> `malloc` n'initialise pas la mémoire : sans la double boucle, la matrice contient des valeurs arbitraires. Il faut aussi penser à `fclose`.
### Question 19
> [!INDICATION]
> L'arbre n'est connu que par le tableau `parent`. Comment reconnaître les fils d'un sommet $s$, et combien cela coûte-t-il ?
> [!INDICATION]
> L'indice d'écriture est partagé par tous les appels récursifs : on le modifie à travers le pointeur.
#### Solution
On enregistre chaque sommet à sa découverte (ordre préfixe), puis on explore ses fils, c'est-à-dire les $v\neq s$ tels que `parent[v] == s`.
```c
void dfs(ACM* a, int s, int* chemin, int* indice) {
chemin[*indice] = s;
*indice = *indice + 1;
for (int v = 0; v < a->n; v = v + 1) {
if (v != s && a->parent[v] == s) {
dfs(a, v, chemin, indice);
}
}
}
```
Le test `v != s` couvre la convention `parent[racine] == racine`. La complexité est $O(n)$ par appel et $n$ appels, soit $O(n^2)$. Aucun tableau de sommets visités n'est nécessaire, car un arbre enraciné n'a pas de cycle.
> [!PIEGE]
> Il faut écrire `*indice = *indice + 1` : `indice = indice + 1` déplacerait le pointeur au lieu d'incrémenter l'entier.
> [!METHODE]
> L'énoncé peut aussi se lire comme l'enregistrement de la liste $L$ complète, avec les remontées ($2n-1$ cases). Il suffit alors de réécrire `s` après chaque appel récursif. La fonction `calcule_CH` ci-dessous convient aux deux lectures.
### Question 20
> [!INDICATION]
> Allouez d'abord la structure, puis son tableau. Combien de cases faut-il pour un cycle **refermé** ?
> [!INDICATION]
> Pour être correct quelle que soit la forme de `chemin`, ne gardez que la première occurrence de chaque sommet : c'est exactement la question 16.
#### Solution
```c
CH* calcule_CH(int* chemin, int n) {
CH* h = malloc(sizeof(CH));
h->l = n + 1;
h->cycle = malloc((n + 1) * sizeof(int));
bool* vu = malloc(n * sizeof(bool));
for (int s = 0; s < n; s = s + 1) {
vu[s] = false;
}
int k = 0;
int i = 0;
while (k < n) {
int s = chemin[i];
if (!vu[s]) {
vu[s] = true;
h->cycle[k] = s;
k = k + 1;
}
i = i + 1;
}
h->cycle[n] = h->cycle[0];
free(vu);
return h;
}
```
Le champ `l` vaut $n+1$, la taille du tableau. Si `chemin` est l'ordre préfixe, la boucle recopie ses $n$ cases. Si c'est $L$, elle s'arrête dès que les $n$ sommets distincts ont été vus. Sur la liste $L$ de la figure 2, le résultat est $[1,2,3,8,4,5,6,7,1]$.
> [!PIEGE]
> Allouer $n$ cases au lieu de $n+1$ provoque une écriture hors du tableau lors de la fermeture. Il ne faut pas non plus oublier de libérer le tableau auxiliaire `vu`.
### Question 21
> [!INDICATION]
> Dans quel ordre libérer une structure et le tableau qu'elle référence ?
#### Solution
```c
void free_ACM(ACM* a) {
free(a->parent);
free(a);
}
void free_CH(CH* cycle) {
free(cycle->cycle);
free(cycle);
}
```
Le tableau interne est libéré en premier : après `free(a)`, lire `a->parent` serait un comportement indéfini.
### Question 22
> [!INDICATION]
> Enchaînez les trois étapes de l'algorithme 1. Par quel sommet commencer le parcours, alors que seul le tableau `parent` est connu ?
> [!INDICATION]
> Faites l'inventaire des allocations : lesquelles sont temporaires, et laquelle constitue le résultat ?
#### Solution
```c
CH* TSP2(Graphe* G) {
ACM* a = Recherche_ACM(G);
int racine = 0;
for (int s = 0; s < a->n; s = s + 1) {
if (a->parent[s] < 0 || a->parent[s] == s) {
racine = s;
}
}
int* chemin = malloc(G->n * sizeof(int));
int indice = 0;
dfs(a, racine, chemin, &indice);
CH* h = calcule_CH(chemin, G->n);
free(chemin);
free_ACM(a);
return h;
}
```
La racine est le sommet sans vrai parent, quelle que soit la convention (`-1` ou lui-même). `chemin` et l'ACM sont temporaires et libérés. Le `CH` est renvoyé, et l'appelant le libérera par `free_CH`. La complexité est $O(n^2\log n)$.
> [!PIEGE]
> Lancer le parcours depuis un sommet qui n'est pas la racine ne visite que son sous-arbre. Libérer `h` avant de le renvoyer serait une faute grave.
> [!JURY]
> Quand l'énoncé insiste sur l'allocation et la désallocation, chaque `malloc` doit avoir son `free` à l'endroit pertinent. Le correcteur vérifie ce point en priorité.
---
## Partie II — Suite de Prouhet-Thue-Morse
On établit d'abord l'équivalence de quatre définitions de la suite (II.1). Toutes reposent sur la même observation d'arithmétique binaire. On étudie ensuite les répétitions dans les mots $T_n$ (II.2) : il y a toujours des carrés, mais jamais de cube. L'outil central est la décomposition de $\mu(m)$ en blocs $01$/$10$ alignés sur les positions paires.
### II.1 — Définitions
### Question 23
> [!INDICATION]
> $T_3$ a $2^3$ lettres. Écrivez $0,\dots,7$ en binaire et comptez les $1$.
#### Solution
| $n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| $b_n$ | 0 | 1 | 1 | 2 | 1 | 2 | 2 | 3 |
| $t_n$ | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
$$T_3=01101001$$
> [!METHODE]
> Contrôle immédiat : $T_3$ doit commencer par $T_2=0110$ et finir par son complémentaire $1001$.
### Question 24
> [!INDICATION]
> Quel est le bit de poids faible de $n$ ? Quelle opération supprime ce bit ?
#### Solution
L'écriture binaire de $n>0$ est celle de $n/2$ suivie du chiffre $n\bmod 2$, donc $b_n=(n\bmod 2)+b_{n/2}$.
```ocaml
let rec compte_bits_a_un n =
if n = 0 then 0
else n mod 2 + compte_bits_a_un (n / 2)
```
La fonction est correcte pour $n\ge 0$, en $O(\log n)$ appels.
> [!PIEGE]
> Pour $n<0$, `n mod 2` peut valoir $-1$ en OCaml : la fonction n'a de sens que pour $n\ge 0$, ce qu'il est bon de préciser.
### Question 25
> [!INDICATION]
> $t_i$ ne dépend que de la parité de $b_i$. Faites varier $i$ de $0$ à $2^n-1$.
#### Solution
```ocaml
let rec puissance2 n =
if n = 0 then 1 else 2 * puissance2 (n - 1)
let affiche_ptm n =
for i = 0 to puissance2 n - 1 do
print_int (compte_bits_a_un i mod 2)
done
```
L'application de fonction est prioritaire sur `mod` : c'est bien $b_i \bmod 2$ qui est affiché. La borne de la boucle `for` n'est évaluée qu'une fois. Complexité : $O(n\,2^n)$. `affiche_ptm 3` affiche `01101001`.
### Question 26
> [!INDICATION]
> Pour $0\le i<2^n$, comparez les écritures binaires de $i$ et de $2^n+i$.
> [!INDICATION]
> Formulez une propriété $\mathcal P(n)$ portant sur **tous** les indices $i<2^n$, puis faites la récurrence sur $n$.
#### Solution
**Lemme.** Si $0\le i<2^n$, ajouter $2^n$ à $i$ ajoute un chiffre $1$ de poids $2^n$ sans retenue, puisque tous les chiffres de $i$ de rang $\ge n$ sont nuls. Donc $b_{2^n+i}=b_i+1$ et $t_{2^n+i}=\overline{t_i}$.
Soit $(t'_j)$ la suite de la définition 2, et $\mathcal P(n)$ : « $t'_i=t_i$ pour tout $i<2^n$ ».
- $\mathcal P(0)$ : $t'_0=t_0=0$.
- Si $\mathcal P(n)$ est vraie et $j<2^{n+1}$ : soit $j<2^n$ et on conclut par $\mathcal P(n)$, soit $j=2^n+i$ avec $i<2^n$ et $t'_j=\overline{t'_i}=\overline{t_i}=t_j$.
Donc **les définitions 1 et 2 coïncident**, et $T_{n+1}=T_n\overline{T_n}$.
> [!PIEGE]
> L'hypothèse $i<2^n$ est indispensable : $b_{4+5}=b_9=2$, alors que $b_5+1=3$.
### Question 27
> [!INDICATION]
> Comparez l'écriture binaire de $n$ avec celles de $2n$ et de $2n+1$.
> [!INDICATION]
> Pour obtenir $t_m$, la définition 3 fait appel à $t_{\lfloor m/2\rfloor}$ et non à $t_{m-1}$ : quel type de récurrence faut-il ? Regardez aussi comment la définition 3 détermine $t_1$.
#### Solution
**Lemme.** Pour $n\ge 0$, l'écriture binaire de $2n$ est celle de $n$ suivie de $0$, et celle de $2n+1$ celle de $n$ suivie de $1$. Donc $t_{2n}=t_n$ et $t_{2n+1}=\overline{t_n}$.
**Énoncé.** Posées « pour $n>0$ », les relations ne définissent pas $t_1$. On les lit pour $n\ge 0$, d'où $t_1=\overline{t_0}=1$.
Soit $(t''_m)$ la suite de la définition 3. On procède par récurrence forte. $t''_0=0=t_0$. Pour $m\ge 1$, on écrit $m=2n+r$ avec $r\in\{0,1\}$ et $n<m$. L'hypothèse de récurrence donne $t''_n=t_n$, et le lemme donne $t''_m=t_m$. **La définition 3 donne la même suite.**
> [!JURY]
> Lorsqu'un énoncé présente une imprécision (ici $n>0$ au lieu de $n\ge 0$), on la signale en une phrase et on indique la lecture retenue. On ne la contourne pas en silence.
### Question 28
> [!INDICATION]
> Écrivez $\mu(a)$ en fonction de $a$ et de $\overline a$.
> [!INDICATION]
> Appliquez $\mu$ lettre à lettre à $T_i$ : quelles sont les lettres d'indices $2j$ et $2j+1$ du résultat ? Comparez avec la définition 3.
#### Solution
On a $\mu(a)=a\overline a$. Par récurrence sur le nombre de facteurs, $\mu(a_0\cdots a_{p-1})=\mu(a_0)\cdots\mu(a_{p-1})$. On lit $u_{i+1}=\mu(u_i)$ pour tout $i\ge 0$ (sinon $u_1$ n'est pas défini). Montrons $u_i=T_i$ par récurrence.
- $u_0=0=T_0$.
- Si $u_i=T_i$, alors $u_{i+1}=\mu(T_i)=t_0\overline{t_0}\cdots t_{2^i-1}\overline{t_{2^i-1}}$. Ses lettres d'indices $2j$ et $2j+1$ sont $t_j=t_{2j}$ et $\overline{t_j}=t_{2j+1}$ (Q27). Ce mot a $2^{i+1}$ lettres, donc $u_{i+1}=T_{i+1}$.
**Pour tout $i\in\mathbb N^\ast$, $u_i=T_i$**, et en particulier $T_{i+1}=\mu(T_i)$.
### Question 29
> [!INDICATION]
> Filtrez sur la tête de la liste : un cas pour 0, un pour 1, un cas « attrape-tout » placé en dernier pour l'exception.
> [!INDICATION]
> Quel mot $u_0$ faut-il itérer, et combien de fois ?
#### Solution
```ocaml
exception INVALID_ARGUMENT
let rec morphisme m =
match m with
| [] -> []
| 0 :: q -> 0 :: 1 :: morphisme q
| 1 :: q -> 1 :: 0 :: morphisme q
| _ -> raise INVALID_ARGUMENT
let thue_morse_4 n =
let rec itere k mot =
if k = 0 then mot else itere (k - 1) (morphisme mot)
in
itere n [0]
```
`thue_morse_4 n` vaut $\mu^n(0)=u_n=T_n$ par Q28. Par exemple, `thue_morse_4 3 = [0;1;1;0;1;0;0;1]`.
> [!PIEGE]
> L'exception doit être **déclarée** avant d'être levée. La liste vide est un mot binaire légitime, elle ne doit pas provoquer d'exception.
### II.2 — Mot infini de Thue-Morse
### Question 30
> [!INDICATION]
> Il suffit de traiter un facteur de longueur 4. Deux lettres consécutives égales donnent déjà un carré.
> [!INDICATION]
> Sur un alphabet à deux lettres, à quoi ressemble un mot sans deux lettres consécutives égales ?
#### Solution
On cherche un carré **non vide**. Soit $a_0a_1a_2a_3$ un facteur d'un mot de longueur $\ge 4$. Si $a_i=a_{i+1}$ pour un $i$, alors $a_ia_i$ est un carré. Sinon, comme $|\Sigma|=2$, le facteur alterne : $a_0a_1a_0a_1=(a_0a_1)^2$. **Tout mot binaire de longueur $\ge 4$ contient un carré.** La borne est optimale, car $010$ est sans carré.
> [!METHODE]
> L'argument repose entièrement sur $|\Sigma|=2$. Sur trois lettres, il existe des mots sans carré arbitrairement longs, et on les construit justement à partir de la suite de Thue-Morse.
### Question 31
> [!INDICATION]
> On ne peut pas construire la première moitié « à l'endroit » en descendant : récupérez le couple renvoyé par l'appel récursif et ajoutez l'élément courant en tête au retour.
> [!INDICATION]
> Pour éviter de calculer la longueur au préalable, parcourez la liste avec deux curseurs : l'un avance d'un élément, l'autre de deux.
#### Solution
```ocaml
let divise_mot m =
let rec aux lent rapide =
match rapide with
| _ :: _ :: r ->
(match lent with
| x :: q -> let (g, d) = aux q r in (x :: g, d)
| [] -> assert false)
| _ -> ([], lent)
in
aux m m
```
Après $k$ appels, `lent` est le suffixe de longueur $|m|-k$ et `rapide` celui de longueur $|m|-2k$. Pour $|m|=2h$, on s'arrête quand $k=h$ : `lent` est alors la seconde moitié, et les $h$ éléments sautés sont replacés en tête au retour. Complexité : $O(|m|)$.
> [!METHODE]
> Une variante plus directe calcule $h=|m|/2$ puis appelle une fonction récursive `prend h m` qui renvoie le couple (préfixe, reste). Une version où `divise_mot` elle-même est récursive (retirer le premier et le dernier élément) existe aussi, mais elle est quadratique.
### Question 32
> [!INDICATION]
> Commencez par la parité. Un mot de longueur paire est un carré si et seulement si…
#### Solution
```ocaml
let est_carre m =
List.length m mod 2 = 0 &&
(let (g, d) = divise_mot m in g = d)
```
Un mot de longueur impaire n'est pas un carré. Sinon, $m=ww$ si et seulement si les deux moitiés sont égales. L'opérateur `&&` est paresseux, donc `divise_mot` n'est appelée que sur une longueur paire. `est_carre []` vaut `true`, conformément à la définition, avec $w=\varepsilon$.
### Question 33
> [!INDICATION]
> D'après la définition 3, que vaut le couple $t_{2n}t_{2n+1}$ ?
> [!INDICATION]
> Trois positions consécutives contiennent toujours un couple $(2n,2n+1)$ complet : discutez selon la parité de la première position.
#### Solution
Pour tout $n$, $t_{2n}t_{2n+1}=t_n\overline{t_n}\in\{01,10\}$. Un facteur $t_it_{i+1}t_{i+2}$ contient le bloc $(i,i+1)$ si $i$ est pair, et le bloc $(i+1,i+2)$ si $i$ est impair. Ce bloc contient un 0 et un 1 : **ni $000$ ni $111$ n'apparaît dans $T$.**
> [!PIEGE]
> Sans la discussion sur la parité de $i$, on n'a traité que les facteurs qui commencent à une position paire.
### Question 34
> [!INDICATION]
> Deux compteurs décroissent : d'abord $i$, pour atteindre le début de la sous-liste, puis $l$, pour la construire. Quel cas de base réalise la troncature ?
#### Solution
```ocaml
let rec sousliste lst i l =
if l <= 0 then []
else
match lst with
| [] -> []
| x :: q ->
if i > 0 then sousliste q (i - 1) l
else x :: sousliste q 0 (l - 1)
```
Exemples : `sousliste [1;2;3;4;5] 1 3 = [2;3;4]` et `sousliste [1;2;3] 2 5 = [3]` (troncature). Complexité : $O(\min(|lst|,i+l))$.
### Question 35
> [!INDICATION]
> Si $xy=yz$, comparez $|x|$ et $|z|$. Réécrivez la condition sous la forme « deux facteurs de même longueur, décalés de $d$, sont égaux ».
> [!INDICATION]
> Paramétrez par la longueur $\ell=|xy|$, la position $i$ et le décalage $d=|x|$. Quelles bornes garantissent que $x$, $y$ et $z$ sont non vides et que $xyz$ tient dans le mot ?
#### Solution
$m$ est un entrelacement si et seulement s'il existe $\ell\ge 2$, $i\ge 0$ et $1\le d\le\ell-1$ tels que $i+d+\ell\le|m|$ et que les facteurs de longueur $\ell$ en positions $i$ et $i+d$ soient égaux. Dans un sens, on pose $\ell=|xy|$ et $d=|x|=|z|$. Dans l'autre, on prend $x=m[i,i+d[$, $y=m[i+d,i+\ell[$ et $z=m[i+\ell,i+\ell+d[$.
```ocaml
let est_entrelacement m =
let n = List.length m in
let rec test_d l i d =
d < l && i + d + l <= n &&
(sousliste m i l = sousliste m (i + d) l || test_d l i (d + 1))
in
let rec test_i l i =
i + l + 1 <= n && (test_d l i 1 || test_i l (i + 1))
in
let rec test_l l =
l + 1 <= n && (test_i l 0 || test_l (l + 1))
in
test_l 2
```
Chaque boucle s'arrête dès que $i+d+\ell>n$, ce qui est légitime puisque cette somme croît avec chaque paramètre. Complexité : $O(n^4)$. Sur l'exemple de l'énoncé, `est_entrelacement [1;0;1;0;1;0;0;1] = true`.
> [!METHODE]
> Avant d'écrire une recherche exhaustive, traduisez la définition en contraintes d'indices. C'est cette traduction qui donne les bornes des boucles, et c'est là que se cachent les faux positifs.
### Question 36
> [!INDICATION]
> Cherchez le découpage $x,y,z$ le plus simple possible d'un cube $www$.
#### Solution
Pour un facteur $www$ avec $w\neq\varepsilon$, on pose $x=y=z=w$ : ils sont non vides et $xy=ww=yz$. **$m$ est un entrelacement.**
> [!PIEGE]
> La réciproque est fausse : $01010$ est un entrelacement ($x=01$, $y=0$, $z=10$) sans cube. C'est la contraposée qui servira en Q41.
### Question 37
> [!INDICATION]
> Utilisez le résultat admis pour vous ramener au cas $|y|=1$, avec $y=a$. Que dit l'égalité $xa=az$ de la première lettre de $x$ ?
> [!INDICATION]
> Dans $xyz=x(az)$, remplacez $az$ par l'expression égale qui fait apparaître $x$ deux fois.
#### Solution
Il existe un facteur $xyz$ avec $y=a\in\Sigma$ et $xa=az$, $x$ non vide. La première lettre de $x$ est celle de $az$, c'est-à-dire $a$ : on écrit $x=av$. Alors
$$xyz=x(az)=x(xa)=(av)(av)a=avava.$$
**$m$ contient un facteur $avava$.** Si $v=\varepsilon$, ce facteur est le cube $aaa$.
### Question 38
> [!INDICATION]
> Un mot dont tous les couples $(2i,2i+1)$ valent $01$ ou $10$ : combien contient-il de $0$ ?
#### Solution
Un mot de longueur $2k$ dont les couples $(2i,2i+1)$ sont $01$ ou $10$ contient exactement $k$ zéros. $m$ en contient donc $n$, et $0m0$, de longueur $2n+2$, en contient $n+2$. S'il s'écrivait $b_0\cdots b_{2n+1}$ avec des couples $01$ ou $10$, il en contiendrait $n+1$. Contradiction. De même, $1m1$ contient $n+2$ uns au lieu de $n+1$. **Aucun des deux mots n'a cette forme.**
> [!METHODE]
> Un invariant de comptage (ici le nombre de zéros) remplace avantageusement une propagation lettre à lettre. On peut aussi propager : le premier bloc de $0m0$ force $a_0=1$, puis $a_1=0$, et ainsi de suite jusqu'au dernier bloc, qui vaut $00$.
### Question 39
> [!INDICATION]
> $\mu(m)$ est une suite de blocs $m_j\overline{m_j}$ aux positions $(2j,2j+1)$. Un facteur de $\mu(m)$ qui commence à une position paire et a une longueur paire est l'image par $\mu$ d'un facteur de $m$, et ce facteur est unique.
> [!INDICATION]
> L'indication de l'énoncé, $|v|$ impair, se démontre avec la question 38. Si $|v|$ était pair, les deux occurrences de $ava$ dans $avava$ seraient décalées d'un nombre impair de positions : l'une est alignée, et dans l'autre c'est $v$ qui est aligné.
> [!INDICATION]
> Avec $|av|$ pair, discutez selon la parité de la position $p$ du facteur $avava$. Si $p$ est impair, ajoutez la lettre qui précède pour vous ramener au cas pair.
#### Solution
Appelons **aligné** un mot de longueur paire dont les couples $(2i,2i+1)$ valent $01$ ou $10$. Dans $\mu(m)$, tout facteur qui commence à une position paire et a une longueur paire est aligné. Il vaut $\mu(X)$ pour un unique facteur $X$ de $m$, obtenu en lisant une lettre sur deux.
Supposons que $\mu(m)$ soit un entrelacement. D'après Q37, il contient $avava$ en position $p$.
***$|v|$ est impair.*** Sinon, $ava$ apparaît aux positions $p$ et $p+|v|+1$, qui sont de parités différentes. En la position paire, $ava$ (de longueur paire) est aligné. En la position impaire, $v$ commence une position plus loin, donc en position paire, et il est de longueur paire : $v$ est aligné. On aurait un mot $ava$ aligné avec $v$ aligné, ce que Q38 interdit. Donc $|av|=2k$ avec $k\ge 1$.
***Cas $p$ pair.*** Les deux copies de $av$, en $p$ et $p+2k$, sont $\mu$ de facteurs de $m$ de longueur $k$, égaux par unicité : on note $X$ ce facteur. Le dernier $a$, en position paire $p+4k$, est la première lettre du bloc $\mu(m_{p/2+2k})$, donc $m_{p/2+2k}=a$. Ainsi $m$ contient $XXa$. Comme la première lettre de $X$ est celle de $\mu(X)=av$, on a $X=aV$, et $m$ contient $aVaVa$.
***Cas $p$ impair.*** La lettre en position $p-1$ est $b=\overline a$, car elle forme un bloc avec le $a$ en position $p$. La dernière lettre de $v$ est en position paire $p+2k-1$ et forme un bloc avec le $a$ qui la suit : elle vaut aussi $b$. Écrivons $v=v'b$. Le facteur qui commence en $p-1$ et a pour longueur $4k+1$ est $b(av')b(av')b$. Il est de la même forme, avec un mot central de longueur $|v|$ impaire, et il commence à une position paire. Le cas précédent s'applique.
***Conclusion.*** $m$ contient un facteur $\alpha U\alpha U\alpha$. Avec $x=\alpha U$, $y=\alpha$ et $z=U\alpha$, on a $xy=yz$ : **$m$ est un entrelacement.**
> [!PIEGE]
> Il ne faut pas oublier le cas où $avava$ commence à une position impaire, ni « relever » un facteur de $\mu(m)$ en facteur de $m$ sans avoir vérifié qu'il est aligné.
> [!METHODE]
> La technique de **désubstitution** consiste à repérer les blocs $\mu(a)$, à aligner le motif sur ces blocs, puis à lire une lettre sur deux. C'est l'outil standard pour transférer une propriété de $\mu(m)$ à $m$.
### Question 40
> [!INDICATION]
> Récurrence sur $n$. Quel lien Q28 donne-t-elle entre $T_{n+1}$ et $T_n$ ? Lisez Q39 par contraposée.
#### Solution
$T_0=0$ a une seule lettre, alors qu'un entrelacement contient un facteur $xyz$ de longueur $\ge 3$ : $T_0$ n'est pas un entrelacement. Si $T_n$ n'en est pas un, alors $T_{n+1}=\mu(T_n)$ (Q28) n'en est pas un non plus, sinon Q39 ferait de $T_n$ un entrelacement. **Pour tout $n$, $T_n$ n'est pas un entrelacement.**
> [!JURY]
> Une récurrence est bien rédigée quand l'initialisation est vraiment justifiée (ici par un argument de longueur) et que chaque résultat antérieur utilisé est cité par son numéro.
### Question 41
> [!INDICATION]
> Contraposée de Q36, combinée à Q40.
#### Solution
Si $T_n$ contenait un cube $www$ avec $w\ne\varepsilon$, ce serait un entrelacement (Q36), ce que Q40 exclut. **Pour tout $n\in\mathbb N$, $T_n$ ne contient pas de cube.** Par passage à la limite, comme l'admet l'énoncé, le mot infini $T$ est sans cube. Il n'est pas pour autant sans carré : $T_2=0110$ contient $11$, conformément à Q30.
> [!METHODE]
> On démontre une propriété **plus forte** que celle visée (sans entrelacement plutôt que sans cube), parce qu'elle seule se transmet par $\mu$ et rend la récurrence possible.
---
## Bilan
**Méthodes à retenir.**
- **Appartenance à NP** : nommer le certificat, majorer sa taille, chiffrer la vérification (Q1, Q2).
- **Réduction polynomiale** : taille de la sortie et coût de la construction, puis les deux sens de l'équivalence. Un encadrement $n\le c\le n$ permet de forcer l'égalité terme à terme (Q3–Q5).
- **NP-complétude** : appartenance à NP, réduction depuis un problème NP-complet, transitivité de $\le_p$ (Q11).
- **Approximation** : minorer l'optimum par une quantité calculable (l'arbre couvrant minimal), construire une solution dont le coût est contrôlé par cette quantité, puis court-circuiter grâce à l'inégalité triangulaire (Q13–Q17).
- **C** : lire les dimensions avant d'allouer, initialiser ce que `malloc` laisse indéterminé, passer un compteur partagé par pointeur, libérer les tableaux internes avant les structures, et ne jamais libérer le résultat renvoyé (Q18–Q22).
- **Arithmétique binaire** : $b_{2n}=b_n$, $b_{2n+1}=b_n+1$ et $b_{2^n+i}=b_i+1$ pour $i<2^n$. Ces trois identités suffisent pour toute la partie II.1.
- **Combinatoire des mots** : décomposition de $\mu(m)$ en blocs alignés, désubstitution, invariant de comptage (Q33, Q38, Q39).
- **OCaml** : récursion sur les listes avec reconstruction au retour (Q31, Q34), exceptions déclarées, ordre des motifs de filtrage (Q29), opérateurs paresseux `&&` et `||` pour les recherches exhaustives (Q35).
**Prérequis à revoir.** La définition de NP et des réductions, Kruskal et union-find, le parcours en profondeur d'un arbre, la gestion de fichiers en C (`fopen`, `fscanf`, `fclose`), la récurrence forte et l'écriture en base 2.
**Questions classiques transposables.** La réduction CYCLE-HAMILTONIEN $\le_p$ TSP par coûts 1 et 2, l'algorithme de 2-approximation de TSP métrique par arbre couvrant minimal, l'équivalence des définitions de la suite de Thue-Morse, et l'absence de cube (plus généralement de chevauchement) dans le mot de Thue-Morse. On retrouve régulièrement ces thèmes à l'écrit comme à l'oral.
Aide sur le corrigé
Connectez-vous pour demander une explication.