CCINP Informatique MPI 2026Sujet et rapport du jury

ÉPREUVE MUTUALISÉE AVEC E3A-POLYTECH

ÉPREUVE SPÉCIFIQUE - FILIÈRE MPI

INFORMATIQUE

• -Utiliser uniquement un stylo noir ou bleu foncé non effaçable pour la rédaction de votre composition ; d'autres couleurs, excepté le vert, bleu clair ou turquoise, peuvent être utilisées, mais exclusivement pour les schémas et la mise en évidence des résultats.
• -Ne pas utiliser de correcteur.
• -Ecrire le mot FIN à la fin de votre composition.

Partie I - Problème du voyageur de commerce

• -CYCLE-HAMILTONIEN qui, étant donné un graphe non orienté G = (S, A), décide s'il existe un cycle hamiltonien dans G,
• -COUVERTURE-SOMMET qui, étant donnés un graphe non orienté G = (S, A) et m ∈ ℕ, décide s'il existe un sous-ensemble de sommets S_c ⊆ S tel que |S_c| ≤ m et que chaque arête de A ait au moins une de ses extrémités dans S_c,
• -TSP qui, étant donnés un graphe G = (S, A, c) et un entier k ∈ ℕ, décide s'il existe un cycle hamiltonien dans G de coût inférieur ou égal à k.

• (i). on crée un nouveau graphe G^′ = (S^′, A^′) qui est un graphe complet tel que S^′ = S,
• (ii). on attribue un coût à chaque arête deG^′ :
  • -si l'arête (s, t) existe dans G, on lui attribue un coût de 1,
  • -si l'arête ( s, t ) n'existe pas dans G, on lui attribue un coût de 2,
• (iii). on fixe un seuil de coût k = |S|.

Figure 1 - Graphe exemple

• Q6.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.

• • (i). on construit m sommets a_1…a_m utilisés pour sélectionner m sommets de G,
  • (ii). 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 ∈ [ [1, 6] ]} ∪ {t_i(e), i ∈ [ [1, 6] ]} et
    A_e = {{s_i(e), s_(i + 1)(e)}}_(i ∈ [ [1, 5] ]) ∪ {{t_i(e), t_(i + 1)(e)}}_(i ∈ [ [1, 5] ]) ∪ {{s_3(e), t_1(e)}, {t_3(e), s_1(e)}} ∪ {{s_6(e), t_4(e)}, {t_6(e), s_4(e)}}.
  • (iii). pour chaque sommet s ∈ 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 ∈ [ [1, d(s) − 1] ]}, 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.
  • (iv). on complète les arêtes de G^′ en connectant les sommets a_1…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 ∈ [ [1, m] ], s ∈ S}.

1.3 - Conclusion des réductions

I.4-2-approximation du problème TSP

Algorithme 1-2-approximation du problème TSP
Entrées : 
G = (S, A, c), c : S × S → ℕ
Sortie : Un cycle hamiltonien 
H
début
    
T = arbre couvrant de coût minimal de 
G
    
L = liste des sommets visités lors d'un parcours en profondeur de 
T
    
H = cycle hamiltonien qui visite les sommets dans l'ordre de 
L.

• Q12.Quel algorithme peut-on utiliser pour réaliser l'étape 2 de l'algorithme 1 ? Quelle est la complexité de votre solution ?
  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.
• Q13.Montrer que c(T) ≤ c(H^∗).

Figure 2 - Exemple de calcul de l'étape 3 de l'algorithme 1

• Q14.Montrer que c(L) ≤ 2c(H^∗).
• Q15.Montrer qu'il est possible de supprimer la visite d'un sommet dans L sans augmenter le coût du parcours.
• Q16.En déduire comment construire H, résultat de l'algorithme 1.
• Q17.En conclure que l'algorithme 1 produit une 2-approximation de TSP.

// 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 l; // Longueur du cycle = taille du tableau cycle
};
typedef struct CH_s CH;

ACM* a = malloc(sizeof(ACM));
a->n = n;
a->parent = malloc(n * sizeof(int));

fichier.txt
n p
s1 t1 c1
s2 t2 c2
...
sp tp cp

• Q18.Écrire une fonction de prototype 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 nom_fichier. On rappelle les fonctions suivantes de gestion des fichiers :
  • -FILE *fopen(char *nom_fichier, char *accessMode) ouvre un fichier de nom nom_fichier selon le mode d'ouverture spécifié par accessMode. Pour une ouverture en mode lecture texte, on peut prendre accessMode="r" ;
  • -int fclose(FILE *f) ferme le fichier pointé par f ;
  • -int fscanf(FILE ∗ f , char *s , ... ) lit dans le fichier pointé par f une chaîne de caractères et utilise le paramètre 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, fscanf( f, "%d %d",&i,&j); lit dans f une ligne composée de deux entiers, séparés par un espace et les stocke aux adresses &i et &j.
• Q19.Écrire une fonction de prototype void dfs(ACM* a, int s, int* chemin, int* indice) qui réalise un parcours en profondeur de l'arbre a dont la racine est s. chemin est un tableau d'entiers, chemin[i] contenant le i-ème sommet du parcours : à chaque fois qu'un sommet est exploré, il est ajouté au tableau chemin à la position spécifiée par *indice (passage par pointeur de l'entier).

• Q20.Écrire une fonction de prototype CH* calcule_CH(int* chemin, int n) qui transforme le chemin calculé par 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.
• Q21.Écrire des fonctions void free_ACM(ACM* a) et void free_CH(CH* cycle) qui désallouent la mémoire précédemment allouée. On supposera que la fonction Recherche_ACM n'effectue pas d'allocation mémoire supplémentaire.
• Q22.Écrire une fonction de prototype 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.

Partie II - Suite de Prouhet-Thue-Morse

• - Σ = {0, 1} un alphabet, Σ^∗ l'ensemble des mots sur Σ, ε le mot vide et |m| la longueur d'un mot m,
• -"." l'opérateur de concaténation de mots de Σ^∗,
• -si m ∈ Σ^∗, m¯ le mot obtenu en remplaçant dans m les 0 par de 1 et les 1 par des 0,
• -pour n ∈ ℕ, t_n le n-ème terme de la suite PTM,
• -pour n ∈ ℕ, T_n = t_0 t_1⋯t_(2^n − 1) le mot construit l'aide des 2^n premiers termes de la suite PTM.

• Q24.Écrire une fonction récursive de signature compte_bits_a_un : int -> int telle que compte_bits_a_un n renvoie le nombre de bits à 1 dans l'écriture en base 2 de l'entier n.
• Q25.En déduire une fonction de signature affiche_ptm : int → unit qui affiche le mot T_n. On écrira une fonction auxiliaire récursive de signature puissance 2 : int -> int qui calcule 2^n. Pour afficher les t_i, on utilisera la fonction print_int de signature print_int : int -> unit.

• Q37.Montrer que si un mot m est un entrelacement, alors il contient un facteur de la forme avava, où a ∈ Σ et v ∈ Σ^∗.
• Q38.Soit m = a_0 a_1⋯a_(2n − 1) ∈ Σ^∗ tel que, pour tout i ∈ [ [0, n − 1] ], a_(2i)a_(2i + 1) s'écrit soit 01, soit 10. Montrer qu'il n'est pas possible d'écrire les mots 0m0 et 1m1 sous la forme b_0 b_1⋯b_(2n + 1), où, pour tout i ∈ [ [0, n] ], b_(2i)b_(2i + 1) s'écrit soit 01, soit 10.

• Q39.Montrer, en utilisant Q37 et l'indication précédente, que si μ(m) est un entrelacement, alors m est un entrelacement.
• Q40.Montrer par récurrence que pour tout n ∈ ℕ, T_n n'est pas un entrelacement.
• Q41.En déduire que pour tout n ∈ ℕ, T_n ne contient pas de cube.

FIN