J-0
00m
00j
00h
00min
00s

Version interactive avec LaTeX compilé

Télécharger PDF

CCINP Informatique MPI 2023

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Logo ccinp
🔗 Explorer
Banque
CCINP
Année
2023
Filière
MPI
Matière
Info
CCINP MPICCINP 2023MPI InfoInfo 2023
2025_08_29_59dbffb5169ae9e5d480g

ÉPREUVE MUTUALISÉE AVEC E3A-POLYTECH ÉPREUVE SPÉCIFIQUE - FILIÈRE MPI

NFORMATIQUE

Durée : 4 heures
N.B. : le candidat attachera la plus grande importance à la clarté, à la précision et à la concision de la rédaction. Si un candidat est amené à repérer ce qui peut lui sembler être une erreur d'énoncé, il le signalera sur sa copie et devra poursuivre sa composition en expliquant les raisons des initiatives qu'il a été amené à prendre.

RAPPEL DES CONSIGNES

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

Les calculatrices sont interdites.

Le sujet est composé de trois parties, toutes indépendantes.

Partie I-Palindromes

En langue française, "ressasser" est le mot palindrome le plus long, tandis qu'il semble que "saippuakauppias" soit le plus long mot palindrome au monde, désignant un marchand de savon en Finlande. L'objet de cette partie est de compter le nombre de palindromes présents dans un mot donné.
Soit un alphabet fini contenant au moins deux lettres. On note un mot sur , composé de lettres . La longueur de est notée . Pour , on note le mot . L'ensemble des mots construits sur et contenant le mot vide est noté .
Définition 1 (Miroir)
Soit . Le miroir de , noté , est le mot . Par convention .
Définition 2 (Palindrome)
est un palindrome si et seulement si .
Par convention, le mot vide n'est pas considéré comme un palindrome.
On dira qu'un palindrome est pair (respectivement impair) lorsque sa longueur est paire (resp. impaire).
On recherche donc dans cette partie le nombre de palindromes facteurs d'un mot (comptés avec les multiplicités éventuelles), soit le cardinal de l'ensemble . Dit autrement, on recherche le nombre de palindromes contenus dans .
Q1. Si , donner le nombre de palindromes contenus dans le mot .
En parcourant naïvement les lettres d'un mot donné, on peut proposer un algorithme en pseudo-code permettant de compter le nombre palindromes de (algorithme 1).
Algorithme 1 - Décompte naïf du nombre de palindromes contenus dans un mot donné.
Entrées : Un mot $u$.
Sorties: Le nombre de palindromes contenus dans $u$.
début
    $\mathrm{nb}=0$
    pour $i=0$ à $|u|-1$ faire
        pour $j=0$ à $|u|-1$ faire
            estPalindrome=True
            pour $k=i$ à $j-1$ faire
                si $u[i] \neq u[j-k-1]$ alors
                    estPalindrome=False
                    Sortir du pour $k$
            si estPalindrome alors
                $\mathrm{nb}=\mathrm{nb}+1$
    retourner $n b$
Q2. Évaluer la complexité au pire des cas de l'algorithme 1 en fonction de .
On souhaite bien sûr améliorer cette première idée. Pour ce faire, on utilise tout d'abord le paradigme de la programmation dynamique.
Pour , on définit un tableau de booléens de taille étant vrai si est un palindrome. On a donc pour tout True.
Q3. Soit un mot. À quelles conditions sur et le mot est-il un palindrome?
Q4. En déduire une relation de récurrence vérifiée par les coefficients de .
Q5. Écrire un algorithme de programmation dynamique en pseudo-code résolvant le problème.
Évaluer sa complexité.
On insère maintenant entre chaque paire de lettres de , ainsi qu'au début et à la fin du mot, un symbole spécial noté #. On appelle ce nouveau mot . Ainsi, le mot se transforme en .
Q6. Montrer que les palindromes de , s'ils existent, sont tous impairs.
Q7. Soit un palindrome de longueur de . On construit le mot . Donner les deux palindromes correspondants à dans .
Q8. Même question si est un palindrome de longueur de .
Q9. En déduire une stratégie de recherche de tous les palindromes de .
On voit que les palindromes impairs sont importants. On va donc construire un algorithme de recherche de ce type de palindrome.
Définition 3 (Rayon d'un palindrome)
Soient et . On dit qu'il existe un palindrome centré en i de rayon si :
(i). ,
(ii). ,
(iii). est un palindrome.
Le rayon maximal d'un palindrome centré en est le plus grand rayon d'un palindrome centré en .
Par exemple, si et , alors est un palindrome centré en 4 de rayon 0 , aba est un palindrome centré en 4 de rayon 1, babab est un palindrome centré en 4 de rayon 2 et c'est le plus grand, donc .
Q10. En remarquant qu'un palindrome impair est centré sur une lettre (ou un symbole spécial dans le cas de ), proposer un algorithme en pseudo-code permettant de compter le nombre de palindromes impairs d'un mot . Évaluer sa complexité.
Q11. Soient et . En exploitant les différentes symétries, montrer qu'il existe un palindrome centré en de rayon . En déduire . Préciser à quelle condition il y a égalité.
En utilisant cette remarque, on développe un algorithme, dit de Manacher, qui construit un tableau d'entiers permettant de compter le nombre de palindromes d'un mot . Plus précisément, pour chaque position indique le rayon maximal , donc tel que la sous-chaîne de à est un palindrome. L'algorithme 2 consiste à incrémenter jusqu'à trouver le plus grand palindrome centré en .
Algorithme 2 - Algorithme de Manacher
Entrées : Un mot $u$
Sorties : Un tableau $T$.
début
    Initialiser un tableau $T$ de $|u|$ cases, initialisées à 0
    $k=0$
    pour $i=1$ à $|u|-1$ faire
        $j=i-k$
        si $T[k] \geq j$ alors
            $T[i]=\min (T[k-j], T[k]-j)$
        tant que $(i-(T[i]+1)) \geq 0$ ET $(i+T[i]+1)<|u| \mathbf{E T}(u[i-(T[i]+1)]=u[i+T[i]+1])$ faire
            $T[i]=T[i]+1$
            $k=i$
    retourner $T$
Q12. Comment trouver à partir de cet algorithme le nombre de palindromes de ?
Q13. Quelle est la complexité de cet algorithme ? Justifier.

Partie II - Traversée de rivière

Cette partie comporte des questions nécessitant un code OCaml.
Dans une vallée des Alpes, un passage à gué fait de cailloux permet de traverser la rivière. Deux groupes de randonneurs arrivent simultanément sur les berges gauche et droite de cette rivière et veulent la traverser. Le chemin étant très étroit, une seule personne peut se trouver sur chaque caillou de ce chemin (figure 1). Un randonneur sur la berge de gauche peut avancer d'un caillou (vers la droite sur la figure 1) et sauter par dessus le randonneur devant lui (un caillou à droite) si le caillou où il atterit est libre. De même, chaque randonneur de la berge de droite peut avancer d'un caillou (vers la gauche sur la figure 1) et sauter par dessus le randonneur devant lui, dans la mesure où le caillou sur lequel il atterit est libre. Une fois engagés, les randonneurs ne peuvent pas faire marche arrière. De plus, pour simplifier, on suppose qu'une fois tous les randonneurs sur le chemin, il ne reste qu'un caillou de libre.
Figure 1 - Les randonneurs et le chemin de cailloux
Le chemin de cailloux est défini par un tableau d'entiers :
type chemin_caillou = int array
Dans ce tableau, un randonneur venant de la berge de gauche est représenté par un 1, un randonneur issu de la berge de droite par un 2 et un caillou libre par un 0.
Q14. Écrire une fonction de signature caillou_vide : chemin_caillou -> int qui détermine la position du caillou inoccupé.
Q15. Écrire une fonction de signature echange : chemin_caillou -> int -> int -> chemin_caillou qui permute les valeurs codées sur deux cailloux. Le tableau d'entiers initial représentant le chemin n'est pas modifié. On pourra utiliser ici la fonction copy du module Array.
Q16. Écrire une fonction de signature randonneurG_avance : chemin_caillou -> bool qui teste si, parmi les randonneurs venant de la berge de gauche, il en existe un qui puisse avancer (vers la droite).
Q17. Écrire une fonction de signature randonneurG_saute : chemin_caillou -> bool qui teste si, parmi les randonneurs venant de la berge de gauche, il en existe un qui puisse sauter (vers la droite) au-dessus d'un randonneur.
On supposera dans la suite les fonctions de signature randonneurD_avance : chemin_caillou -> bool et randonneurD_saute : chemin_caillou -> bool écrites de manière similaire pour les randonneurs venant de la berge de droite.
Q18. Écrire une fonction de signature mouvement_chemin : chemin_caillou -> chemin_caillou list qui, en fonction de l'état du chemin, calcule l'état suivant après les opérations suivantes (si elles sont permises) :
(i). déplacement d'un randonneur venant de la berge de gauche,
(ii). déplacement d'un randonneur venant de la berge de droite,
(iii). saut d'un randonneur venant de la berge de gauche,
(iv). saut d'un randonneur venant de la berge de droite.
On donne la syntaxe OCaml pour créer une liste de entiers : List. init N (fun ).
Par exemple, List.init 5 (fun ->2); ; renvoie [ ].
Q19. Écrire une fonction de signature passage : int -> int, utilisant la question précédente, telle que l'appel passage nG nD résout le problème de passage de nG randonneurs venant de la berge de gauche et nD randonneurs venant de la berge de droite. Par exemple, passage 32 permet de passer de à .

Partie III - Calcul d'une coupe minimum d'un graphe

Un agent secret a pour mission de perturber le réseau de communications ennemi en coupant certains fils dans le réseau. Ayant peu de moyens, l'agent a pour consigne de couper le moins de fils possibles pour accomplir cette tâche. Le réseau de communications est modélisé à l'aide d'un multigraphe non orienté , où est l'ensemble des sommets du graphe et l'ensemble de ses arêtes. Résoudre le problème de l'agent secret, c'est rechercher une coupe minimum dans .

Définition 4 (Multigraphe)

Un multigraphe est un graphe dans lequel des couples de mêmes sommets peuvent être reliés par plus d'une arête.
Dans toute la suite, on considérera les multigraphes sans arêtes du type ( ) (boucles).

Définition 5 (Coupe)

Une coupe d'un multigraphe non orienté est une partition non triviale ( ) de , c'est-àdire telle que et . On dira que les arêtes reliant à sont les arêtes de la coupe.
La taille d'une coupe ( ) est définie par . Autrement dit, c'est le nombre d'arêtes de qui relient et .
Définition 6 (Coupe minimum)
Une coupe minimum est une coupe de taille minimale.
Pour trouver une coupe minimum d'un multigraphe , on pourrait énumérer l'ensemble des coupes possibles (il y en a ), ou encore utiliser un algorithme de flot (le plus efficace étant en ). Nous proposons dans la suite un algorithme probabiliste, l'algorithme de Karger, basé sur la notion de contraction d'arête.

III. 1 - Contraction d'arête

Soient un multigraphe et une arête de de sommets et . Contracter l'arête consiste à :
(i). créer un nouveau sommet dans . est un supersommet du nouveau graphe,
(ii). pour toute arête ou , ajouter une arête ( ) à . Dans le cas où ( ) et ( ) existent, deux arêtes reliant à sont créées.
(iii). Supprimer de toutes les arêtes ayant ou comme extrémité.
(iv). Supprimer et de .
Un supersommet peut donc être vu comme un ensemble de deux sommets du graphe initial, obtenu après une contraction d'arête.
Le multigraphe obtenu est appelé graphe contracté et est noté . Si plusieurs arêtes relient à dans , contracter l'une d'entre elles supprime toutes les autres du graphe . Dans toute la suite, on notera le graphe initial, avant transformations par contractions.
On considère le graphe de la figure 2.
Figure 2 - Graphe exemple
Q20. Donner le graphe obtenu par contraction d'une arête ( ).
Après plusieurs contractions, un supersommet du graphe résultant contient un sous-ensemble de sommets de .
Q21. Soit un supersommet et . Montrer qu'il existe un chemin entre et dans tel que chaque arête de a été contractée.
Q22. Montrer qu'en contractant une arête dans un multigraphe , la taille d'une coupe minimum du graphe contracté est au moins égale à la taille d'une coupe minimum de .
Q23. Montrer que la taille d'une coupe minimum de est strictement plus grande que celle d'une coupe minimum de si et seulement si l'arête ( ) est une arête de toutes les coupes minimum de .

III. 2 - Premier algorithme

On construit un premier algorithme qui essaye de trouver une coupe minimum en contractant aléatoirement une arête de , jusqu'à ce qu'il ne reste que deux sommets (algorithme 3).
Algorithme 3 - Algorithme de Karger.
$\operatorname{Karger}(G, n)$
Entrées : $G=(S, A)$ multigraphe non orienté, $n \in \mathbb{N}$
Sorties : Une coupe minimum de $G$.
début
    pour $i=|S|$ à $n$ en décrémentant de 1 faire
        Tirer aléatoirement (loi uniforme) une arête $a=(s, t) \in A$
        $G=G / s t$
// Appel
$\underline{\operatorname{Karger}(G, 2)}$
Q24. Appliquer l'algorithme 3 au graphe de la figure 2, en contractant successivement ( ), et . Chaque graphe contracté sera représenté. La coupe calculée est-elle une coupe minimum?
D'après la Q23, tant que l'on ne contracte pas une arête faisant partie de toutes les coupes minimum de , alors l'algorithme trouvera une coupe minimum. On cherche alors la probabilité de ne jamais contracter une telle arête.
Q25. Soit le degré d'un sommet . Montrer que (lemme des poignées de main).
Q26. En déduire qu'une coupe minimum a une taille d'au plus .
Soit une coupe minimum de . L'objet des questions Q27 et Q28 est de minorer la probabilité que l'algorithme 3 renvoie . Pour cela, on remarque que cet algorithme ne renvoie pas si et seulement si lors d'une itération on choisit une arête qui traverse , c'est-à-dire telle qu'un sommet est dans et l'autre dans .
Q27. Quelle est la probabilité maximum de choisir une arête qui traverse ?
Q28. En déduire que la probabilité que l'algorithme renvoie est supérieure ou égale à .
Q29. Déduire de la question précédente qu'un multigraphe non orienté possède au plus coupes minimum.

III. 3 - Deuxième algorithme

Le résultat précédent n'est pas satisfaisant d'un point de vue complexité. On peut cependant l'améliorer facilement en utilisant une technique d'amplification : on itère l'algorithme plusieurs fois et on retourne la valeur minimale obtenue (algorithme 4).
Algorithme 4 - Algorithme de Karger amplifié.
KargerAmplifie( $G, N$ )
Entrées : $G=(S, A)$ multigraphe non orienté, $N \in \mathbb{N}$.
Sorties : Une coupe minimum de $G$.
début
    $t=\infty$
    pour $i=1$ à $N$ faire
        $X=\operatorname{Karger}(G, 2)$
        si $|X|<t$ alors
            $t=|X|$
            $C=X$
    retourner $C$
Q30. Montrer que la probabilité maximale que l'algorithme 4 ne trouve pas une coupe minimum est égale à .
Q31. On rappelle que pour tout . Montrer que la probabilité que l'algorithme renvoie une coupe minimum est supérieure à . En déduire, pour fixé, la plus petite valeur de telle que cette probabilité soit supérieure à .
Q32. Les algorithmes proposés dans cette partie sont des algorithmes probabilistes. Sont-ils de type Monte Carlo ou Las Vegas? Justifier la réponse.

III. 4 - Implémentation en langage C

Cette partie comporte des questions de programmation qui seront abordées en utilisant exclusivement le langage . Les codes seront commentés de manière pertinente.
On suppose qu'un graphe est codé à l'aide de l'ensemble de ses arêtes, chaque arête étant définie par ses deux sommets, représentés par des entiers.
Q33. Définir en C des types structurés Arete et Graphe. Pour ce dernier, on s'attachera à avoir un accès direct au nombre de sommets et au nombre d'arêtes. On rappelle la définition d'un type structuré par struct nom_s type champ type champ et ensuite typedef struct nom_s nom;.
Pour tout supersommet, les forment une partition de . Pour coder ces sous-ensembles, on a donc naturellement recours à la structure de données Unir & Trouver (Union-Find), qui va permettre de trouver rapidement à quel sous-ensemble un sommet appartient (Trouver) et de fusionner deux supersommets et déjà construits (Unir).
On suppose donc disposer :
(i). d'un type subset, décrivant un supersommet d'un graphe contracté.
struct subset
{
    int parent; // recherche par compression de chemin pour Trouver
    int rang; // Union par rang.
};
typedef struct subset subset;
(ii). d'une fonction de prototype int Trouver(subset subsets[], int s), qui retourne le numéro du supersommet dans lequel le sommet se trouve (par compression de chemin),
(iii). d'une fonction de prototype void Unir(subset subsets[], int Su, int Sv) qui fusionne les deux supersommets et (union par rang) et maintient à jour la liste des supersommets.
II n'est pas demandé d'écrire ces deux dernières fonctions.
Q34. Écrire une fonction de prototype int contracteArete (Graphe G, subset subsets[], Arete a) qui contracte l'arête a. On veillera à ne pas contracter l'arête si ses deux extrémités sont dans le même supersommet. La fonction renvoie 0 si aucune arête est contractée et -1 sinon.
Q35. Écrire une fonction de prototype int compteAretesCoupe(Graphe G, subset subsets[]) qui compte le nombre d'arêtes du graphe contracté final résultant de l'algorithme 3. subsets est la partition des sommets du graphe initial calculée par l'algorithme 3.
Q36. En déduire une fonction de prototype int kargerMinCut (Graphe GO) qui renvoie la taille de la coupe calculée par l'algorithme 3 sur le graphe . Les supersommets initiaux sont les sommets de , chacun ayant un rang nul et un numéro parent égal au numéro du sommet. Pour effectuer un tirage aléatoire uniforme, on utilisera la fonction int rand(); de la librairie stdlib.h qui renvoie un nombre aléatoire entre 0 et RAND_MAX 32767. RAND_MAX est une constante définie dans stdlib.h.
Q37. Donner la complexité au pire des cas de cet algorithme.

FIN

FIN
CCINP Informatique MPI 2023 - Version Web LaTeX | WikiPrépa | WikiPrépa