sujets-info/2026-ccinp-mpi
3
0
Bifurcation 0
Code Tickets Demandes d'ajout Activité
Fichiers
main
2026-ccinp-mpi/2026-ccinp-mpi-informatique.tex
T
Florian Hatat 0ca0ddb298 Partie 2 remise en forme, avant relecture
2026-04-23 12:40:59 +02:00

594 lignes
28 KiB
TeX
Brut Lien permanent Annotations Historique

Ce fichier contient des caractères Unicode invisibles.
Ce fichier contient des caractères Unicode invisibles à l'œil nu, mais peuvent être traités différemment par un ordinateur. Si vous pensez que c'est intentionnel, vous pouvez ignorer cet avertissement. Utilisez le bouton Échappe pour les dévoiler.
\documentclass[10pt,a4paper]{article}
\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{stmaryrd}
\usepackage{tikz}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{minted}
\usepackage{fullpage}
\usepackage{enumerate}
\usepackage{subcaption}
\theoremstyle{definition}
\newtheorem{question}{Question}
\newtheorem{definition}{Définition}
\newtheorem{theorem}{Théorème}
% Algorithmes
\renewcommand{\listalgorithmname}{Liste des algorithmes}
\floatname{algorithm}{Algorithme}
\renewcommand{\algorithmicreturn}{\textbf{renvoyer}}
\renewcommand{\algorithmicprocedure}{\textbf{procédure}}
\renewcommand{\algorithmicfunction}{\textbf{fonction}}
\renewcommand{\algorithmicrequire}{\textbf{Entrée~:}}
\renewcommand{\algorithmicensure}{\textbf{Sortie~:}}
\renewcommand{\algorithmiccomment}[1]{\hfill\texttt{// #1}}
\renewcommand{\algorithmicend}{\textbf{fin}}
\renewcommand{\algorithmicif}{\textbf{si}}
\renewcommand{\algorithmicthen}{\textbf{alors}}
\renewcommand{\algorithmicelse}{\textbf{sinon}}
\renewcommand{\algorithmicfor}{\textbf{pour}}
\renewcommand{\algorithmicforall}{\textbf{pour tout}}
\renewcommand{\algorithmicdo}{\textbf{faire}}
\renewcommand{\algorithmicwhile}{\textbf{tant que}}
\newcommand{\algorithmicelsif}{\algorithmicelse\ \algorithmicif}
\newcommand{\algorithmicendif}{\algorithmicend\ \algorithmicif}
\newcommand{\algorithmicendfor}{\algorithmicend\ \algorithmicfor}
\title{Épreuve d'informatique MPI}
\author{Concours commun INP}
\date{2026-04-22}
\begin{document}
\maketitle
\section{Problème du voyageur de commerce}
Cette partie comporte des questions nécessitant un code C.
Soit $G=(S, A)$ un graphe non orienté à $|S|=n$ sommets. On note ce graphe
$G=(S, A, c)$ lorsqu'il est muni d'une fonction de valuation des arêtes $c: S
\times S \rightarrow \mathbb{N}$ telle que pour tout $s \in S, c(s, s)=0$ et
$c(s, t)=+\infty$ s'il n'existe pas d'arête entre $s$ et $t$.
\begin{definition}[Cycle hamiltonien]
Un cycle hamiltonien dans $G=(S, A)$ est un chemin qui passe une fois
et une seule par chaque sommet de $G$ et qui commence et termine par le
même sommet.
\end{definition}
On considère les problèmes suivants :
\begin{itemize}
\item CYCLE-HAMILTONIEN qui, étant donné un graphe non orienté $G=(S, A)$, décide s'il existe un cycle hamiltonien dans $G$,
\item COUVERTURE-SOMMET qui, étant donnés un graphe non orienté $G=(S, A)$ et $m \in \mathbb{N}$, décide s'il existe un sous-ensemble de sommets $S_{c} \subseteq S$ tel que $|S_{c}| \leq m$ et que chaque arête de $A$ ait au moins une de ses extrémités dans $S_{c}$,
\item TSP qui, étant donnés un graphe $G=(S, A, c)$ et un entier $k \in \mathbb{N}$, décide s'il existe un cycle hamiltonien dans $G$ de coût inférieur ou égal à $k$.
\end{itemize}
On admet dans la suite que COUVERTURE-SOMMET est NP-complet. On souhaite alors montrer que TSP est NP-complet.
\begin{question}
Montrer que TSP est dans NP.
\end{question}
\subsection{Réduction de CYCLE-HAMILTONIEN vers TSP}
\begin{question}
Montrer que CYCLE-HAMILTONIEN est dans NP.
\end{question}
Soit $G=(S, A)$ une instance de CYCLE-HAMILTONIEN. On construit l'instance correspondante de TSP comme suit :
\begin{enumerate}[(i)]
\item on crée un nouveau graphe $G'=(S', A')$ qui est un graphe complet tel que $S'=S$,
\item on attribue un coût à chaque arête de $G'$ :
\begin{itemize}
\item si l'arête ( $s, t$ ) existe dans $G$, on lui attribue un coût de 1 ,
\item si l'arête ( $s, t$ ) n'existe pas dans $G$, on lui attribue un coût de 2 ,
\end{itemize}
\item on fixe un seuil de coût $k=|S|$.
\end{enumerate}
\begin{question}
Montrer que la construction de $G'$ est polynomiale en la taille de $G$.
\end{question}
\begin{question}
Montrer que si CYCLE-HAMILTONIEN renvoie Vrai sur l'entrée $G$ alors TSP renvoie Vrai sur l'entrée $(G', k)$.
\end{question}
\begin{question}
Montrer que si TSP renvoie Vrai sur l'entrée $G'$ alors CYCLE-HAMILTONIEN renvoie Vrai sur l'entrée $G$.
\end{question}
\subsection{Réduction de COUVERTURE-SOMMET vers CYCLE-HAMILTONIEN}
Soient une instance de COUVERTURE-SOMMET donnée par le graphe $G=(S, A)$ et un entier $m \leq|S|$. On doit construire un graphe $G'=(S', A')$ tel que $G'$ a un cycle hamiltonien si et seulement si $G$ a une couverture de sommets de taille au plus $m$. On admettra cette équivalence dans la suite. On s'intéresse, pour les questions \ref{q:exemple-couverture} à \ref{q:construction-gprime}, uniquement à la construction de $G'$ à partir de $G$. De plus, pour les questions \ref{q:exemple-couverture} à \ref{q:ensembles-etape3}, on utilisera le graphe $G$ décrit dans la figure \ref{fig:graphe-exemple}.
\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=1.5]
\node[draw,circle] (alpha) at (1,2) {$\alpha$};
\node[draw,circle] (beta) at (0,1) {$\beta$};
\node[draw,circle] (gamma) at (3,2) {$\gamma$};
\node[draw,circle] (delta) at (2,1) {$\delta$};
\node[draw,circle] (epsilon) at (2,0) {$\epsilon$};
\draw
(alpha) edge[above right] node {$e_1$} (delta)
(beta) edge[above] node {$e_2$} (delta)
(delta) edge[above left] node {$e_3$} (gamma)
(delta) edge[left] node {$e_4$} (epsilon)
(beta) edge[above left] node {$e_5$} (alpha)
(gamma) edge[below right] node {$e_6$} (epsilon)
;
\end{tikzpicture}
\caption{\label{fig:graphe-exemple}Graphe exemple}
\end{center}
\end{figure}
\begin{question}\label{q:exemple-couverture}
Le problème COUVERTURE-SOMMET répond-il Vrai pour $m=2$ ? pour $m=3$ ? Si oui, donner pour chaque valeur de $m$ un sous-ensemble $S_{c}$ correspondant.
\end{question}
La construction de $G'$ passe par les étapes suivantes :
\begin{enumerate}[(i)]
\item\label{etape1} on construit $m$ sommets $a_{1} \ldots a_{m}$ utilisés pour sélectionner $m$ sommets de $G$,
\item\label{etape2} pour chaque arête $e=(s, t)$ de $G$, on construit un graphe gadget $G_{e}=(S_{e}, A_{e})$ à 12 sommets et 14 arêtes avec $S_{e}=\{s_{i}(e), i \in \llbracket 1,6 \rrbracket\} \cup\{t_{i}(e), i \in \llbracket 1,6 \rrbracket\}$ et
\[A_{e}=\{\{s_{i}(e), s_{i+1}(e)\}\}_{i \in \llbracket 1,5 \rrbracket} \cup\{t_{i}(e), t_{i+1}(e)\}\}_{i \in \llbracket 1,5 \rrbracket} \cup\{\{s_{3}(e), t_{1}(e)\},\{t_{3}(e), s_{1}(e)\}\} \cup\{\{s_{6}(e), t_{4}(e)\},\{t_{6}(e), s_{4}(e)\}\}\]
\item\label{etape3} pour chaque sommet $s \in S$ de degré $d(s)$, on connecte tous les graphes gadgets où $s$ apparaît. Pour ce faire, on construit un ensemble d'arêtes $A_{s}=\{\{s_{6}(e_{s[j]}), s_{1}(e_{s[j+1]})\}, j \in \llbracket 1, d(s)-1 \rrbracket\}$, où les $e_{s[j]}$ sont les arêtes incidentes à $s$ ordonnées arbitrairement. Cette étape créé un chemin dans $G'$ composé exactement des sommets $u_{i}(e)$ tels que $u=s$.
\item on complète les arêtes de $G'$ en connectant les sommets $a_{1} \ldots a_{m}$ aux premiers et derniers sommets de chaque chemin créé dans l'étape précédente. Pour ce faire, on construit les arêtes $A_{c}=\{\{a_{i}, s_{1}(e_{s[1]})\},\{a_{i}, s_{6}(e_{s[d(s)]})\}, i \in \llbracket 1, m \rrbracket, s \in S\}$.
\end{enumerate}
Le graphe $G'$ est alors défini par $S'=\{a_{i}, i \in \llbracket 1, m \rrbracket\} \cup(\cup_{e \in A} S_{e})$ et $A'=(\cup_{e \in A} A_{e}) \cup(\cup_{s \in S} A_{s}) \cup A_{c}$.
\begin{question}
Dessiner le graphe gadget de l'arête $e_{2}=(\beta, \delta)$. Représenter les $\beta_{i}(e_{2})$ sur une même ligne, les $\delta_{i}(e_{2})$ sur une même ligne, chaque $\beta_{i}(e_{2})$ étant à la verticale de $\delta_{i}(e_{2})$.
\end{question}
Soit $e=(s, t)$ une arête de $G$. Le graphe gadget $G_{e}$ permet de garantir qu'au moins une extrémité de $e$ figure parmi les $m$ sommets sélectionnés dans l'étape \ref{etape1}. Dans la construction finale de $G'$, les seuls sommets de $G_{e}$ qui seront impliqués dans des arêtes supplémentaires construites dans l'étape \ref{etape2} sont $s_{1}(e), t_{1}(e), s_{6}(e)$ et $t_{6}(e)$.
\begin{question}
Donner alors les trois traversées possibles du gadget $G_{e}$ par un cycle hamiltonien dans $G'$.
\end{question}
\begin{question}\label{q:ensembles-etape3}
Donner les ensembles $A_{\gamma}$ et $A_{\delta}$ produits par l'étape \ref{etape3}.
\end{question}
\begin{question}\label{q:construction-gprime}
Montrer que $G'$ peut être construit à partir de $G$ et $m$ en temps polynomial.
\end{question}
\subsection{Conclusion des réductions}
\begin{question}
En déduire que TSP est NP complet.
\end{question}
\subsection{2-approximation du problème TSP}
On change ici la manière de voir le problème TSP. On passe du problème de décision au problème d'optimisation : étant donné un graphe $G=(S, A, c)$, trouver dans $G$ le chemin de coût total minimal qui passe exactement une fois par chaque sommet et revient au sommet de départ.
On ajoute maintenant une contrainte sur la fonction $c$ : on demande à ce qu'elle respecte l'inégalité triangulaire, c'est-à-dire : $V(s, t, u) \in S^{3} c(s, u) \leq c(s, t)+c(t, u)$. On suppose de plus que le graphe $G$ est complet.
On montre alors, dans la suite, qu'il existe une 2-approximation du problème TSP. À cette fin, on propose l'algorithme \ref{algo:2approx}.
\begin{algorithm}
\caption{2-approximation du problème TSP}
\label{algo:2approx}
\begin{algorithmic}
\State{\textbf{Entrées :} $G=(S, A, c)$, $c: S \times S \rightarrow \mathbb{N}$}
\State{\textbf{Sortie :} Un cycle hamiltonien $H$}
\State{$T \gets \text{arbre couvrant de coût minimal de $G$}$}
\State{$L \gets \text{liste des sommets visités lors d'un parcours en profondeur de $T$}$}
\State{$H \gets \text{cycle hamiltonien qui visite les sommets dans l'ordre de $L$}$.}
\end{algorithmic}
\end{algorithm}
% Énoncé d'origine modifié.
% La question d'origine disait :
% « Quel algorithme peut-on utiliser pour réaliser l'étape 2 de
% l'algorithme 1 ? Quelle est la complexité de votre solution ? »
% On ne sait pas exactement à quoi fait référence cette étape 2. La ligne
% numérotée 2 dans le sujet d'origine contient uniquement le texte "début", et
% la deuxième affectation, portant sur L, n'est pas particulièrement
% intéressante. Cela ressemble à une erreur d'énoncé, où la question aurait dû
% porter sur le calcul de l'arbre couvrant de poids minimum.
\begin{question}
Quel algorithme peut-on utiliser pour réaliser le calcul de $T$ dans l'algorithme \ref{algo:2approx} ? Quelle est la complexité de votre solution ?
\end{question}
On note $H^{*}$ un cycle hamiltonien de coût optimal pour le problème TSP. On note également $c(E)$ le coût associé à un chemin $E$, qu'il soit représenté par une suite ordonnée d'arêtes ou de sommets.
\begin{question}
Montrer que $c(T) \leq c(H^{*})$.
\end{question}
On ajoute un sommet dans $L$ dès qu'on le rencontre lors du parcours en profondeur de $T$. Dans $L$, certains sommets sont donc visités plus d'une fois. La figure 2 donne un exemple de la construction de $L=[1,2,3,2,8,2,1,4,5,6,5,7,5,4,1]$.
\begin{figure}[h]
\caption{Exemple de calcul de $L$ par l'algorithme \ref{algo:2approx}}
\label{fig:exemple-calcul-l}
\begin{center}
\begin{subfigure}[b]{0.3\textwidth}
\begin{tikzpicture}[scale=0.75]
\begin{scope}[every node/.style={draw, circle}]
\node (n1) at (1,4) {$1$};
\node (n2) at (1,2) {$2$};
\node (n3) at (0,1) {$3$};
\node (n4) at (3,4) {$4$};
\node (n5) at (4,3) {$5$};
\node (n6) at (3,2) {$6$};
\node (n7) at (5,2) {$7$};
\node (n8) at (2,0) {$8$};
\end{scope}
% Pas de \foreach pour dessiner la clique, car
% certaines arêtes sont courbées manuellement.
\draw
(n1) edge (n2)
(n1) edge (n3)
(n1) edge (n4)
(n1) edge (n5)
(n1) edge (n6)
(n1) edge (n7)
(n1) edge (n8)
(n2) edge (n3)
(n2) edge (n4)
(n2) edge (n5)
(n2) edge (n6)
(n2) edge[bend right] (n7)
(n2) edge (n8)
(n3) edge[bend left=20] (n4)
(n3) edge (n5)
(n3) edge (n6)
(n3) edge (n7)
(n3) edge (n8)
(n4) edge (n5)
(n4) edge (n6)
(n4) edge[bend left] (n7)
(n4) edge (n8)
(n5) edge (n6)
(n5) edge (n7)
(n5) edge[bend left=10] (n8)
(n6) edge (n7)
(n6) edge (n8)
(n7) edge (n8)
;
\end{tikzpicture}
\caption{Graphe $G$}
\end{subfigure}
\begin{subfigure}[b]{0.3\textwidth}
\begin{tikzpicture}[scale=0.75]
\begin{scope}[every node/.style={draw, circle}]
\node (n1) at (1,4) {$1$};
\node (n2) at (1,2) {$2$};
\node (n3) at (0,1) {$3$};
\node (n4) at (3,4) {$4$};
\node (n5) at (4,3) {$5$};
\node (n6) at (3,2) {$6$};
\node (n7) at (5,2) {$7$};
\node (n8) at (2,0) {$8$};
\end{scope}
\draw
(n1) edge (n2)
(n1) edge (n4)
(n2) edge (n3)
(n2) edge (n8)
(n4) edge (n5)
(n5) edge (n6)
(n5) edge (n7)
;
\end{tikzpicture}
\caption{Construction de $T$}
\end{subfigure}
\begin{subfigure}[b]{0.3\textwidth}
\begin{tikzpicture}[scale=0.75]
\begin{scope}[every node/.style={draw, circle}]
\node (n1) at (1,4) {$1$};
\node (n2) at (1,2) {$2$};
\node (n3) at (0,1) {$3$};
\node (n4) at (3,4) {$4$};
\node (n5) at (4,3) {$5$};
\node (n6) at (3,2) {$6$};
\node (n7) at (5,2) {$7$};
\node (n8) at (2,0) {$8$};
\end{scope}
\draw
(n1) edge (n2)
(n1) edge (n4)
(n2) edge (n3)
(n2) edge (n8)
(n4) edge (n5)
(n5) edge (n6)
(n5) edge (n7)
;
% Petit chemin à la main
\path[every node/.style={draw,circle,fill=black,inner sep=0.5mm}]
node (p1) at ([xshift=-1mm]n1.west) {}
node (p2) at ([xshift=-1mm,yshift=1mm]n2.north west) {}
node (p3) at ([xshift=-1mm]n3.west) {}
node (p8) at ([xshift=-1mm]n8.west) {}
node (p4) at ([xshift=-2mm]n4.south west) {}
node (p5) at ([xshift=-2mm]n5.west) {}
node (p6) at ([xshift=-1mm]n6.west) {}
node (p7) at ([xshift=-2mm]n7.west) {}
;
\draw[->] plot[smooth] coordinates {
([yshift=-1mm]p1)
(p1)
(p2)
([xshift=-1mm]n3.north west)
(p3)
([xshift=-1mm]n3.south west)
([yshift=-1mm]n3.south)
([xshift= 1mm]n3.south east)
([yshift=-2mm]n2.south)
(p8)
([xshift=-1mm]n8.south west)
([yshift=-1mm]n8.south)
([xshift= 1mm]n8.east)
([xshift= 1mm]n2.east)
([xshift= 3mm,yshift=-2mm]n1.south east)
(p4)
(p5)
([xshift=-1mm]n6.north west)
(p6)
([xshift=-1mm]n6.south west)
([yshift=-1mm]n6.south)
([xshift= 1mm]n6.south east)
([yshift=-2mm]n5.south)
(p7)
([xshift=-1mm,yshift=-1mm]n7.south west)
([yshift=-1mm]n7.south)
([xshift= 1mm,yshift=-1mm]n7.south east)
([xshift= 1mm,yshift=1mm]n7.east)
([xshift= 1mm,yshift=1mm]n5.north east)
([xshift= 1mm,yshift=1mm]n4.north east)
([yshift=1mm]n1.north)
};
\end{tikzpicture}
\caption{Construction de $L$}
\end{subfigure}
\end{center}
\end{figure}
\begin{question}
Montrer que $c(L) \leq 2 c(H^{*})$.
\end{question}
\begin{question}
Montrer qu'il est possible de supprimer la visite d'un sommet dans $L$ sans augmenter le coût du parcours.
\end{question}
\begin{question}
En déduire comment construire $H$, résultat de l'algorithme \ref{algo:2approx}.
\end{question}
\begin{question}
En conclure que l'algorithme \ref{algo:2approx} produit une 2-approximation de TSP.
\end{question}
Les sommets du graphe étant codés par des entiers, on donne les structures de données suivantes :
\begin{minted}{c}
// Structure de graphe
struct Graphe_s {
int n; // Nombre de sommets
int** C; // Matrice des coûts
};
typedef struct Graphe_s Graphe;
// Structure Arbre Couvrant de coût minimal
struct ACM_s {
int* parent; // Tableau indiquant le parent de chaque sommet dans l'arbre
int n; // Nombre de sommets de l'arbre
};
typedef struct ACM_s ACM;
// Structure Cycle Hamiltonien
struct CH_s {
int* cycle; // Sommets dans l'ordre d'apparition dans le cycle
int 1; // Longueur du cycle = taille du tableau cycle
};
typedef struct CH_s CH;
\end{minted}
On admet, de plus, disposer d'une fonction de prototype \mintinline{c}{ACM* Recherche_ACM(Graphe* G)} qui calcule l'arbre couvrant de coût minimal de $G$. Cette fonction alloue la structure \mintinline{c}{ACM} :
\begin{minted}{c}
ACM* a = malloc(sizeof(ACM));
a->n = n;
a->parent = malloc(n * sizeof(int));
\end{minted}
avant de la calculer et de la renvoyer.
Soit un fichier texte, présent sur le disque et correctement écrit, de la forme :
\begin{verbatim}
fichier.txt
n p
s1 t1 c1
s2 t2 c2
...
sp tp cp
\end{verbatim}
où \mintinline{c}{n} est le nombre de sommets du graphe, \mintinline{c}{p} le nombre d'arêtes, les \mintinline{c}{p} lignes suivantes donnant les deux sommets \mintinline{c}{si} et \mintinline{c}{ti} et le coût \mintinline{c}{ci} de l'arête correspondante.
\begin{question}
Écrire une fonction de prototype \mintinline{c}{Graphe* creer_graphe(char* nom_fichier)} qui créé un graphe à partir de la lecture d'un fichier texte dont le nom est spécifié dans la chaîne de caractères \mintinline{c}{nom_fichier}. On rappelle les fonctions suivantes de gestion des fichiers :
\begin{itemize}
\item \mintinline{c}{FILE *fopen(char *nom_fichier, char *accessMode)} ouvre un fichier de nom \mintinline{c}{nom_fichier} selon le mode d'ouverture spécifié par \mintinline{c}{accessMode}. Pour une ouverture en mode lecture texte, on peut prendre \mintinline{c}{accessMode="r"} ;
\item \mintinline{c}{int fclose(FILE *f)} ferme le fichier pointé par \mintinline{c}{f} ;
\item \mintinline{c}{int fscanf(FILE *f, char *s, ...)} lit dans le fichier pointé par \mintinline{c}{f} une chaîne de caractères et utilise le paramètre \mintinline{c}{s} pour préciser le format à utiliser pour décoder la chaîne de caractères. Les valeurs lues sont stockées, une à une, dans les paramètres suivants de la fonction, dont la mémoire doit avoir été allouée. Ainsi, \mintinline{c}{fscanf(f,"%d %d" ,&i ,&j);} lit dans \mintinline{c}{f} une ligne composée de deux entiers, séparés par un espace et les stocke aux adresses \mintinline{c}{&i} et \mintinline{c}{&j}.
\end{itemize}
\end{question}
\begin{question}
Écrire une fonction de prototype \mintinline{c}{void dfs(ACM* a, int s, int* chemin, int* indice)} qui réalise un parcours en profondeur de l'arbre \mintinline{c}{a} dont la racine est \mintinline{c}{s}. \mintinline{c}{chemin} est un tableau d'entiers, \mintinline{c}{chemin[i]} contenant le $i$\ieme{} sommet du parcours : à chaque fois qu'un sommet est exploré, il est ajouté au tableau chemin à la position spécifiée par \mintinline{c}{*indice} (passage par pointeur de l'entier).
\end{question}
\begin{question}
Écrire une fonction de prototype \mintinline{c}{CH* calcule_CH(int* chemin, int n)} qui transforme le chemin calculé par \mintinline{c}{dfs} en un cycle hamiltonien. On prendra soin d'allouer correctement la structure de donnée retournée par la fonction et de refermer le chemin pour obtenir un cycle.
\end{question}
\begin{question}
Écrire des fonctions \mintinline{c}{void free_ACM(ACM* a)} et \mintinline{c}{void free_CH(CH* cycle)} qui désallouent la mémoire précédemment allouée. On supposera que la fonction \mintinline{c}{Recherche_ACM} n'effectue pas d'allocation mémoire supplémentaire.
\end{question}
\begin{question}
Écrire une fonction de prototype \mintinline{c}{CH* TSP2(Graphe* G)} qui calcule une 2-approximation de TSP. On prendra soin d'allouer/désallouer la mémoire lorsque cela est nécessaire.
\end{question}
\section{Suite de Prouhet-Thue-Morse}
Cette partie comporte des questions nécessitant un code OCaml.
L'objectif de cette partie est d'étudier quelques définitions et propriétés de la suite de Prouhet-ThueMorse (abrégé PTM), du nom des mathématiciens français, norvégien et américain Eugène Prouhet, Axel Thue et Marston Morse.
\paragraph{Notations}
Dans toute la suite, on note :
\begin{itemize}
\item $\Sigma=\{0,1\}$ un alphabet, $\Sigma^{*}$ l'ensemble des mots sur $\Sigma, \varepsilon$ le mot vide et $|m|$ la longueur d'un mot $m$,
\item $\cdot$ l'opérateur de concaténation de mots de $\Sigma^{*}$,
\item si $m \in \Sigma^{*}, \bar{m}$ le mot obtenu en remplaçant dans $m$ les $0$ par des $1$ et les $1$ par des $0$,
\item pour $n \in \mathbb{N}, t_{n}$ le $n$\ieme{} terme de la suite PTM,
\item pour $n \in \mathbb{N}, T_n=t_{0} t_{1} \cdots t_{2^{n}-1}$ le mot construit l'aide des $2^{n}$ premiers termes de la suite PTM.
\end{itemize}
\subsection{Définitions}
Il existe plusieurs manières de définir la suite PTM. Nous proposons ici d'en illustrer quelques unes et de montrer leur équivalence.
\begin{definition}[Première définition]
Pour $n \in \mathbb{N}$, on écrit $n$ en base $2$ sous la forme $n=\sum_{i} d_{i} 2^{i}$ et on note $b_{n}=\sum_{i} d_{i}$. On définit alors $t_{0}=0$ et pour $n>0$, $t_{n}=\begin{cases}1 & \text {si $b_n$ impair} \\ 0 & \text {sinon}\end{cases}$.
\end{definition}
\begin{question}
Donner $T_3$.
\end{question}
\begin{question}
Écrire une fonction récursive de signature \mintinline{ocaml}{compte_bits_a_un : int -> int} telle que \mintinline{ocaml}{compte_bits_a_un n} renvoie le nombre de bits à $1$ dans l'écriture en base $2$ de l'entier $n$.
\end{question}
\begin{question}
En déduire une fonction de signature \mintinline{ocaml}{affiche_ptm : int -> unit} qui affiche le mot $T_n$. On écrira une fonction auxiliaire récursive de signature \mintinline{ocaml}{puissance2 : int -> int} qui calcule $2^n$. Pour afficher les $t_i$, on utilisera la fonction \mintinline{ocaml}{print_int} de signature \mintinline{ocaml}{print_int : int -> unit}.
\end{question}
\begin{definition}[Deuxième définition]
On pose $t_{0}=0$. On suppose que pour $n>0$ on a construit le mot $T_n$. On construit alors le mot $T_{n+1}$ et donc les termes $t_{2^{n}}, \cdots t_{2^{n+1}-1}$ de la suite PTM par négation binaire : $\forall i \in \llbracket 0,2^{n}-1 \rrbracket, t_{2^{n}+i}=\bar{t}_{i}$. Autrement dit, $T_{n+1}=T_n \bar{T}_{n}$.
\end{definition}
\begin{question}
Montrer par récurrence que cette définition calcule la même suite que la première définition.
\end{question}
\begin{definition}[Troisième définition]
On définit la suite PTM de manière récursive : $t_{0}=0$ et pour tout $n>0 t_{2 n}=t_{n}, t_{2 n+1}=\overline{t_{n}}$.
\end{definition}
\begin{question}
Montrer que cette définition calcule la même suite que la première ou la deuxième définition.
\end{question}
\begin{definition}[Quatrième définition]\label{def:quatrieme}
Un morphisme sur $\Sigma^{*}$ est une fonction $\mu: \Sigma^{*} \rightarrow \Sigma^{*}$ vérifiant $\mu(\varepsilon)=\varepsilon$ et : $\forall u, v \in \Sigma^{*} \mu(u \cdot v)=\mu(u) \cdot \mu(v)$.
\end{definition}
On définit alors le morphisme suivant sur les éléments de $\Sigma: \mu(a)= \begin{cases}01 & \text {si $a=0$} \\ 10 & \text {si $a=1$}\end{cases}$ et la suite $(u_i, i \in \mathbb{N})$ par : $u_{0}=0$ et pour tout $i \in \mathbb{N}^{*}, u_{i+1}=\mu(u_{i})$.
\begin{question}
Montrer que pour tout $i \in \mathbb{N}^{*}$, $u_{i}=T_{i}$.
\end{question}
On représente maintenant un mot de $\Sigma^{*}$ par une liste d'entiers.
\begin{question}
Écrire une fonction de signature \mintinline{ocaml}{thue_morse_4 : int -> int list}, un appel à \mintinline{ocaml}{thue_morse_4 n} générant $T_n$. Cette fonction fera appel à une fonction récursive de signature \mintinline{ocaml}{morphisme : int list -> int list} renvoyant l'application du morphisme $\mu$ sur la liste d'entiers en entrée. On lèvera une exception \mintinline{ocaml}{INVALID_ARGUMENT} si le mot donné en entrée n'est pas binaire.
\end{question}
\subsection{Mot infini de Thue-Morse}
Le mot infini de Thue-Morse $T$ est le mot obtenu en itérant $\mu$ une infinité de fois, en partant du symbole $0$. Nous allons ici nous intéresser à la structure de $T$.
\begin{definition}[Carré, cube]
Soit $m \in \Sigma^{*}$. $m$ est un carré s'il s'écrit $m=w \cdot w$, où $w \in \Sigma^{*}$. C'est un cube si $m=w \cdot w \cdot w$, où $w \in \Sigma^{*}$.
\end{definition}
Par exemple, le mot $m=110110110$ est un cube avec $w=110$.
\begin{question}
Montrer qu'il n'existe pas de mots de $\Sigma^{*}$ de longueur supérieure ou égale à $4$ sans carrés.
\end{question}
\begin{question}
Écrire une fonction récursive de signature \mintinline{ocaml}{divise_mot : int list -> int list * int list} qui divise un mot $m$ en deux sous-mots de taille identique, le premier constitué des $|m| / 2$ premiers éléments de $m$, le second des éléments restants. On supposera ici que $|m|$ est paire.
\end{question}
\begin{question}
En déduire une fonction de signature \mintinline{ocaml}{est_carre : int list -> bool} qui détermine si un mot $m$ est un carré. On prendra soin de vérifier que $|m|$ est paire.
\end{question}
\begin{question}
Montrer que $T$ ne contient aucun cube de la forme $000$ ou $111$.
\end{question}
\begin{definition}[Entrelacement]
$m \in \Sigma^{*}$ est un entrelacement s'il contient un facteur de la forme $xyz$ où $x, y, z$ sont des facteurs non vides de $m$ et $x y=y z$. On dit que les deux facteurs $x y$ et $y z$ se chevauchent sur la partie commune $y$.
\end{definition}
Par exemple, le mot $101\mathbf{0}1001$ est un entrelacement, puisqu'il contient le facteur $010$ en positions $2$ et $4$, qui se chevauchent sur le $0$ en position $4$ (en gras).
\begin{question}
Écrire une fonction récursive de signature \mintinline{ocaml}{sousliste : int list -> int -> int -> int list} telle que \mintinline{ocaml}{sousliste lst i l} renvoie la sous-liste de \mintinline{ocaml}{lst} qui commence à l'indice \mintinline{ocaml}{i} et de longueur \mintinline{ocaml}{l}. Si la sous-liste dépasse la fin de la liste \mintinline{ocaml}{lst}, elle est tronquée.
\end{question}
\begin{question}
Écrire une fonction de signature \mintinline{ocaml}{est_entrelacement : int list -> bool} telle que l'appel \mintinline{ocaml}{est_entrelacement m} renvoie \mintinline{ocaml}{true} si \mintinline{ocaml}{m} est un entrelacement, \mintinline{ocaml}{false} sinon. On pourra tester récursivement toutes les longueurs de facteurs possibles et, pour un facteur donné, vérifier s'il apparaît ailleurs dans le mot avec chevauchement. On utilisera obligatoirement la fonction \mintinline{ocaml}{sousliste}.
\end{question}
\begin{question}
Montrer que si un mot $m$ contient un facteur cube, alors c'est un entrelacement.
\end{question}
On admet dans la suite que si un mot est un entrelacement dont la partie commune est de longueur $k \geq 1$, alors c'est également un entrelacement de partie commune de longueur $1$.
\begin{question}\label{q:facteur-avava}
Montrer que si un mot $m$ est un entrelacement, alors il contient un facteur de la forme $avava$, où $a \in \Sigma$ et $v \in \Sigma^{*}$.
\end{question}
\begin{question}
Soit $m=a_{0} a_{1} \cdots a_{2 n-1} \in \Sigma^{*}$ tel que, pour tout $i \in \llbracket[0, n-1]$, $a_{2 i} a_{2 i+1}$ s'écrit soit $01$, soit $10$. Montrer qu'il n'est pas possible d'écrire les mots $0 m 0$ et $1 m 1$ sous la forme $b_{0} b_{1} \cdots b_{2 n+1}$, où, pour tout $i \in \llbracket 0, n \rrbracket$, $b_{2 i} b_{2 i+1}$ s'écrit soit $01$, soit $10$.
\end{question}
Soit $m \in \Sigma^{*}$. On construit le mot $\mu(m)$ où $\mu$ est défini après la définition \ref{def:quatrieme}. Si $\mu(m)= wavavaz$ où $a \in \Sigma$ et $v, w, z \in \Sigma^{*}$, on peut montrer qu'alors $v$ contient un nombre impair de symboles.
\begin{question}
Montrer, en utilisant la question \ref{q:facteur-avava} et l'indication précédente, que si $\mu(m)$ est un entrelacement, alors $m$ est un entrelacement.
\end{question}
\begin{question}
Montrer par récurrence que pour tout $n \in \mathbb{N}$, $T_n$ n'est pas un entrelacement.
\end{question}
\begin{question}
En déduire que pour tout $n \in \mathbb{N}$, $T_n$ ne contient pas de cube.
\end{question}
Par passage à la limite, on admet alors que $T$ n'est pas un entrelacement et ne contient donc pas de cube.
\end{document}
Référencer dans un nouveau ticket Voir Git Blâme Copier le lien permanent