Concours CPGE EPITA-IPSA-ESME 2024 Épreuve de Sciences du numérique MPI Le sujet est composé d’un problème et d’un questionnaire à choix multiples. Le questionnaire à choix multiples devra être inséré dans votre copie.
Les fonctions à produire dans ce sujet devront être rédigées dans le langage spécifié dans l’intitulé des parties et se conformer aux restrictions décrites ci-après.
Il est possible d’écrire des fonctions auxiliaires non explicitement demandées à condition de les documenter et de les définir avant d’en faire usage.
Restrictions des langages C et OCaml
Conformément au programme de l’enseignement d’informatique en classe de MPI, sont autorisés les traits et éléments techniques à connaître des langages C et OCaml.
En particulier, l’usage des fonctions et modules OCaml ci-après n’est pas autorisé :
|
1 2 3 4 5 6 7 |
Array.exists List.exists module Hashtbl Array.for_all List.filter module Queue Array.init List.fold_left module Stack Array.iter List.for_all Array.map List.iter Array.mem List.map List.mem |
Problème – Coloration de graphes
On considère dans ce problème des graphes non orientés {G=(V,E)}, à {n\in\mathbb N^\star} sommets, où {V=\llbracket0,n-1\rrbracket} est l’ensemble des sommets de {G} et {E} l’ensemble de ses arêtes. {E} est un ensemble de parties à 2 éléments de {V}.
On dit que {c:V\to\mathbb N} est une coloration des sommets de {G} lorsque deux sommets voisins {v_1} et {v_2} de {V} ont toujours des couleurs {c(v_1)} et {c(v_2)} distinctes. Formellement : {\forall\{v_1,v_2\}\in E,\ c(v_1)\ne c(v_2)}. Dans le cas où une coloration de {G} existe, on dira que {G} est colorable.
De plus lorsqu’il existe {k\in\mathbb N^\star} tel que {c(V)\subseteq\llbracket0,k-1\rrbracket}, on dira que {c} est une {k}-coloration de {G} et que le graphe est {k}-colorable. Une coloration d’un graphe {G} sera dite optimale ou minimale lorsqu’il n’existera pas de coloration de {G} avec moins de couleurs.
On appelle graphe induit de {G=(V,E)} par un sous-ensemble {V'} de ses sommets, le graphe {G'=(V',E')} où {E'} est l’ensemble des arêtes de {E} ayant leurs extrémités dans {V'}. Formellement {E'=\{\{v_1,v_2\}\in E\mid(v_1,v_2)\in V'\times V'\}}.
On appelle stable d’un graphe {G=(V,E)}, tout sous-ensemble non vide {V'} de sommets de {G} vérifiant : {\forall(v_1,v_2)\in V'\times V',\quad\{v_1,v_2\}\notin E.}Autrement dit, {V'} est un stable de {G} si et seulement si le graphe induit par l’ensemble non vide de sommets {V'} ne contient pas d’arêtes.
On dira qu’un stable {S} de {G} est maximal lorsque le seul stable de {G} contenant {S} est {S} lui-même.
1 Un algorithme glouton – Langage C
Allocation mémoire
Avec les notations précédentes, un graphe G sera représenté par la donnée de son nombre de sommets n et par sa matrice d’adjacence M .
Ainsi M [i][j] vaudra 1 lorsque le graphe G contiendra l’arête {\{i,j\}} et 0 sinon.
On adoptera la structure suivante pour le représenter :
|
1 2 3 4 5 6 |
struct graph { int n; int **M; }; typedef struct graph graph; |
Itérateur de permutations
On représente une permutation {\sigma} de {\llbracket0,n-1\rrbracket} par le tableau d’entiers {[\sigma(0),\ldots,\sigma(n-1)]}. On considère l’ordre les permutations de {\llbracket0,n-1\rrbracket} comme étant l’ordre lexicographique des tableaux qui les représentent : {[a_1]\lt[b_1]\iff a_1\lt b_1.} {\begin{array}{l}\forall p\geq2,\ [a_1,\ldots,a_p]\lt[b_1,\ldots,b_p]\\[8pt]\iff a_1\lt b_1\text{ ou }\left\{\begin{array}{l}a_1=b_1,\\[8pt][a_2,\ldots,a_p]\lt[b_2,\ldots,b_p].\end{array}\right.\end{array}}Ainsi {[2,3,1,5,4]\lt[2,3,4,1,5]\lt[2,3,4,5,1]\lt[2,3,5,1,4]}.
Cette fonction ne fera rien dans le cas où {i\geq j} et on supposera que cette fonction n’est appelée que lorsque i et j sont dans {\llbracket0,n-1\rrbracket}.
Cette fonction retournera, parmi les cases dont l’indice est strictement supérieur à i et dont la valeur est supérieure à p[i], l’indice de la case de valeur minimale.
On suppose que cette fonction ne sera appelée que lorsque cet indice existera.
Lorsque la permutation suivante n’existe pas, la fonction renverra la valeur true ; dans le cas contraire, elle renverra la valeur false sans modifier la permutation.
Implémentation de l’algorithme glouton
On considère le graphe {G_t=(V_t,E_t)} représenté par la figure 1.
On considère un algorithme glouton de coloration prenant en paramètre une permutation {\sigma} de {\llbracket0,n-1\rrbracket} et un graphe G à n sommets à colorer.
L’algorithme parcourt le graphe dans l’ordre des sommets {\sigma(0),\ldots,\sigma(n-1)} et colore chaque sommet non coloré par la couleur 0 si aucun de ses voisins n’est déjà coloré avec cette couleur. L’algorithme recommence alors avec la couleur suivante jusqu’à ce que tous les sommets soient colorés.
Cette fonction retournera la coloration produite par l’algorithme glouton.
Algorithme de coloration optimale
On fixe dans cette partie un graphe {G=(V,E)} à {n\in\mathbb N^\star} sommets.
Pour chaque entier {k\in\mathbb N^\star} et toute {k}-coloration, on définit {(\star_k)} la proposition suivante : {\forall i\in\llbracket0,k-1\rrbracket} « L’ensemble {C_i} des sommets de couleur {i} est un stable maximal du sous-graphe de {G=(V,E)} induit par les sommets {V\setminus(C_0\cup\cdots\cup C_{i-1})} »
Montrer qu’elle est produite par l’exécution de l’algorithme glouton sur au moins une permutation des sommets de G.
2 Complexité
On considère le problème de décision 3-COLOR suivant : « Étant donné un graphe non orienté G à au moins 3 sommets, existe-t-il une 3-coloration de ses sommets ? » On considère également le problème de décision 3-DOMINATION suivant : « Étant donné un graphe non orienté G à au moins 3 sommets, existe-t-il un ensemble de 3 sommets de G tel que chaque sommet de G soit à une distance au plus un de l’un d’eux ? » Dans le cas où un tel ensemble existe, on dira qu’il s’agit d’un ensemble 3-dominant du graphe G.
On considère à présent la construction suivante : À partir d’un graphe {G=(V,E)}, on construit le graphe {G'=(V',E')} tel que : 1. {V'=V\cup V_s} où {V_s} est l’ensemble des stables de {G} ; 2. {E'} est l’union de l’ensemble de toutes les arêtes possibles entre les sommets de {V_s} et de l’ensemble des arêtes reliant les éléments de {v\in V} aux éléments de {v_s\in V_s} pour lesquels {v} est un sommet du stable {v_s}.
On justifiera sa réponse.
3 Coloration distribuée – Langage OCaml
Dans cette partie on représente les graphes par liste d’adjacence au moyen du type int list array. L’objectif à présent est de simuler l’exécution d’un algorithme de coloration de graphe distribué.
On identifie dans ce cadre chaque sommet du graphe à une machine reliée à d’autres machines conformément aux arêtes du graphe.
Chaque sommet du graphe peut :
— exécuter des instructions ;
— connaître la liste de ses voisins ;
— envoyer des messages (informations) à un ou plusieurs de ses voisins ;
— lire les informations qu’il a reçues ;
— choisir sa propre couleur.
Les sommets ne peuvent donc pas accéder directement à l’information globale de coloration des autres sommets ; pour cela ils sont contraints de s’envoyer des messages.
Dans la mesure où nous effectuons une simulation dont seul le résultat nous intéresse, nous pourrons dans cette partie écrire des algorithmes sans ces limitations mais dont le résultat devra être le même que si ces contraintes étaient effectives.
De plus, dans ce sujet lorsque l’on présentera un algorithme distribué, on considèrera que les sommets exécutent les instructions de façon synchrone : tous les sommets concernés par l’étape 1 exécutent les instructions de l’étape 1, puis tous les sommets concernés par l’étape 2 exécutent les instructions de l’étape 2, et ainsi de suite.
Un algorithme rapide de coloration
On considère à présent que les couleurs sont des entiers représentés par des mots binaires et on présente l’algorithme distribué fast_color suivant : 1. au départ aucun sommet n’est coloré et les sommets connaissent la liste de leurs voisins qu’ils considèrent comme actifs.
Initialement, chaque sommet considère comme actifs chacun de ses voisins ; 2. chaque sommet non coloré génère aléatoirement et de façon uniforme un bit ; 3. chaque sommet non coloré envoie le bit généré à ses voisins encore considérés comme actifs ; 4. chaque sommet non coloré lit les bits reçus de ses voisins et ne considère plus comme actifs les voisins ayant généré un bit différent du sien ; 5. chaque sommet ne considérant plus aucun de ses voisins comme actif prend pour couleur l’entier représenté par le mot binaire obtenu en concaténant les bits qu’il a généré (du dernier bit généré au premier – de gauche à droite). 6. si il reste des sommets non colorés, on recommence à l’étape 2, sinon l’algorithme se termine.
On notera c(s) le nombre entier représentant la couleur produite par l’algorithme fast_color pour le sommet s.
On pourra représenter par des pointillets les arêtes du graphe entre tout couple de sommets se considérant mutuellement inactifs.
Cette fonction renverra un tableau indexé par les numéros des sommets du graphe G et dont les cases contiennent l’entier représentant sa couleur.
La fonction aura pour signature fast_color : int list array -> (unit -> int) -> int array et on sera libre de créer des fonctions auxiliaires utiles.
Un algorithme pour améliorer la coloration
Afin de réduire le nombre de couleurs utilisées par la coloration produite, on envisage un second algorithme distribué, appelé reduce, opérant après le précédent et visant à attribuer une nouvelle couleur aux sommets : 1.
Chaque sommet stocke une liste ℓ, initialement vide, des couleurs utilisées par ses voisins ; 2. Chaque sommet s sans nouvelle couleur envoie à ses voisins la valeur c(s) produite à l’issue de fast_colour ; 3.
Chaque sommet s sans nouvelle couleur et dont la valeur c(s) est inférieure à celle de chacun de ses voisins se voit attribuer comme nouvelle couleur la plus petite couleur absente de sa liste ℓ. Il indique ensuite à tous ses voisins la couleur retenue ; 4.
Chaque sommet sans nouvelle couleur ajoute à sa liste ℓ la couleur de chacun de ses voisins s’étant vu attribué une nouvelle couleur à l’étape 3 ; 5. Tant qu’il reste des sommets sans nouvelle couleur, l’algorithme recommence à l’étape 2.
On sera libre de concevoir des fonctions auxiliaires aidant à l’élaboration de la fonction.
QCM – MPI
Document à insérer dans votre copie d’examen Dans ce questionnaire à choix multiples, chaque question comporte une ou plusieurs bonnes réponses. Chaque réponse correcte fait gagner des points, mais chaque réponse fausse annule tous les points de la question.
Les questions sont majoritairement formulées au pluriel par commodité d’expression. Cela n’implique pas nécessairement qu’elles admettent plusieurs réponses correctes.
□ 0
□ 1
□ 2
□ infini
□ {\{a^n\mid n\in\mathbb N\}}□ {\{a^nb^n\mid n\in\mathbb N\}}
□ {\{(ab)^n\mid n\in\mathbb N\}}
□ {\{a^nb^p\mid n\in\mathbb N,\ p\in\mathbb N,\ n+p=2024\}}
□ {\{\omega\in\{a,b\}^\star\mid |\omega|_a>|\omega|_b\}}
□ {\{\omega\in\{a,b\}^\star\mid |\omega|_a=|\omega|_b+1\}}
□ {a(ba)^\star\mid b(ab)^+}
□ {a(ba)^\star\mid b(ab)^\star}
□ {S\to3S\mid S4\mid pS\mid St\mid1}
□ {S\to SSS\mid SS\mid1\mid3\mid4\mid p\mid t\mid z}
□ {S\to S1S\mid SpS\mid StS\mid3\mid4}
□ {S\to SpS\mid StS\mid1\mid3\mid4}
□ {(((1\mid9)(3\mid4)^\star)((1\mid3)(5\mid9)^\star)^\star)^\star}
□ {(((1\mid9)(3\mid4)^\star)^\star((1\mid3)(5\mid9))^\star)^\star}
□ {(((1\mid9)(3\mid4)^\star)((1\mid3)(5\mid9)^\star)^\star)^\star}
□ {(((1\mid9)(3\mid4)^\star)^\star((1\mid3)(5\mid9)^\star))^\star}
□ Il y a une infinité de langages réguliers.
□ Tout langage inclus dans un langage régulier est régulier.
□ Tout automate fini a pour langage reconnu un langage régulier.
□ Une intersection finie de langages réguliers est un langage régulier.