CCINP Informatique optionnelle MP 2024

SESSION 2024 @: oncoure MP7IN
COMMUN

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

INFORMATIQUE

Durée : 4 heures

NB. : 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, 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.

« Écrire le mot FIN à la fin de votre composition.

Les calculatrices sont interdites.

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

1/7
Partie | - Coloration de graphes

L'objectif de cette partie est de proposer une implémentation en Python d'une 
solution au problème
de coloration d'un graphe.

1.1 - Définitions et propriétés

Soit G = (S,A) un graphe fini non orienté avec S son ensemble de sommets et À 
son ensemble
d'arêtes. On suppose que le graphe est simple c'est-à-dire qu'il ne comporte 
pas de boucles et que
chaque paire de sommeis est reliée par au plus une arête. On note », le 
cardinal de l'ensemble S.
Les sommets sont numérotés de 0 à n -- 1. Étant donné un entier naturel k, une 
k-coloration des
sommets de G est une application c : S -- {0,1,..,k--- 1} telle que pour chaque 
arête {x, y} d'extré-
mités x et y, c(x) £ c(y). Si c(x) = i, on considèrera que la couleur : est 
affectée au sommet x. Si G
admet une k-coloration, il est k-coloriable. On définit le nombre chromatique 
y(G) d'un graphe G fini
par r(G) = min{k EUR N, G est k-coloriablel}.

Une clique est un sous-ensemble de sommets du graphe, adjacents 2 à 2. On dit 
qu'un graphe est
complet si il est une clique. On notera K, le graphe complet à p sommets.

On pose w(G) = max tp e NIK, est une clique de G}, avec N l'ensemble des 
entiers naturels.

Figure 1 - de gauche à doite, le graphe G; et le graphe K4

Q1. Le graphe G, de la figure 1 ci-dessus est-il 2-coloriable ? Justifier votre 
réponse.
Q2. Pour un entier naturel n > 1, déterminer le nombre chromatique du graphe K,.
Q3. Montrer que pour tout graphe G à n sommets, on à w(G) < y(G) < n. 1.2 - Algorithmique et programmation en Python (Informatique Commune) La coloration d'un graphe G avec (G) couleurs est un problème complexe. Dans cette sous-partie, nous présentons une heuristique permettant de construire une coloration d'un graphe donné. Dans la suite, on implémente un graphe par un dictionnaire (type dict en Python), contenant les listes d'adjacence des sommets. Les clés du dictionnaire sont les numéros des sommets et la valeur correspondant à la clé i du dictionnaire est la liste d'adjacence du sommet numéro i. Notons qu'il serait ici possible d'implémenter le graphe par des listes d'adjacence dans un tableau, dans la mesure ou les sommets sont numérotés de0 an---1. Q4. Définir en Python le dictionnaire 41 correspondant au graphe G1. Q5. Écrire une fonction Python degres_sommets(d) qui prend en paramètre un dictionnaire 4 représentant un graphe et renvoie une liste de couples (di,i), i étant le numéro d'un sommet parcourant l'ensemble {0, .,n -- 1} et ai le degré du sommet i. 2/7 Q6. On suppose qu'on dispose d'une fonction Python tri(1) qui trie une liste de couples 1 dans l'ordre décroissant par rapport à la première composante du couple. En déduire une fonction tri_degres(d) qui prend en paramètre un dictionnaire 4 représentant un graphe et renvoie une liste contenant les numéros des sommets, triés par degrés décroissants. Q7. Écrire une fonction Python test(d,c) qui prend en paramètre un dictionnaire à représentant un graphe G, un dictionnaire c dont les clés représentent les sommets du graphe G et les valeurs, leurs couleurs. La fonction renvoie True si c est une 2-coloration pour G. On considère ci-dessous, l'algorithme de coloriage de Welsh-Powel. Algorithme 1 : Welsh-Powel (coloration de graphe) Entrée : un graphe G à n sommets Sortie : liste d'entiers contenant en position i la couleur du sommet numéro i 1 Début 2 Ordonner les sommets selon les degrés décroissants dans une liste li ; 3 colorie : dictionnaire vide qui à terme, associera à chaque clé i, la couleur du sommet i ; 4 Tant qu' i/ reste des sommets à colorier faire 5 Chercher dans 1i le premier sommet non colorié et le colorier avec la plus petite couleur c non utilisée ; 6 Colorier avec cette même couleur, en respectant leur ordre dans li, tous les sommets non coloriés et non adjacents à des sommets de couleur c ; 7 Fin 8 Retourner colorie o Fin Q8. Que contient colorie si on déroule l'algorithme de coloriage ci-dessus avec le graphe G; en entrée ? Q9. Écrire une fonction Python adjacent (d,dc,s,c) qui prend en paramètre un graphe repré- senté par un dictionnaire d, un dictionnaire dc contenant la couleur des sommets coloriés, le numéro d'un sommet s, une couleur c et renvoie True si le sommet s est adjacent à l'un des sommets de couleur c, False sinon. Q10. Proposer une implémentation en Python de l'algorithme de Welsh-Powel. Application Le tableau ci-dessous représente les liens d'amitiés entre huit étudiants : Alice (A), Béatrice (B), Carl (C), David (D), Eloïs (E), Fanny (F), Gary(G) et Hedge (H). Prénom A B GC D E F G H Amie avec | B,C,G  ACEF A BEF | BDDF | BDEH | AH EG On souhaite créer des groupes de travail. Dans le contexte de l'application, un groupe contient au moins 2 étudiants tel que chaque étudiant soit dans un groupe différent de celui de ses amis. Q11. Modéliser la situation par un graphe et en déduire une solution. 3/7 Partie Il - Satisfiabilité d'une formule propositionnelle Le langage utilisé dans cette partie est OCaml. Une formule propositionnelle est construite à l'aide de constantes propositionnelles, de variables propositionnelles et de connecteurs logiques. Les connecteurs logiques seront notés - (négation), A (conjonction), V (disjonction). Dans cette partie, on étudie le problème de satisfiabilité d'une formule et son application à la détermination d'une conséquence logique entre 2 formules propositionnelles. Le problème CNF-SAT est défini de la facon suivante. Étant donné une formule sous forme normale conjonctive, admet-elle un modèle, c'est-à-dire une valuation des variables, qui rende la formule vraie ? On souhaite écrire un programme qui teste si une valuation donnée rend une telle formule vraie. Dans cette partie, on considère que si une formule contient nr variables propositionnelles, elles seront désignées par xo, x1,....., Xn-1: On définit le type OCaml suivant : type clause=Var of int|Non of clause |Ou of clause*xclause L'argument du constructeur Var correspond au numéro de la variable concernée. Une formule sous forme normale conjonctive ayant m clauses sera implémentée par une liste de m clauses. Les tableaux seront implémentés par le module Array dont les éléments suivants pourront être utilisés : - type 'a array,notations [| 1] - création d'un tableau : make : int -> 'a -> 'a array

- accès à l'élément d'indice i du tableau t : t.(i)

- modification de l'élément placé à l'indice i du tableau t : t.(i) <- v - taille du tableau : length : ?a array -> int

Q12. Donner le code OCaml correspondant à la clause c = (xo V x1) V x.

Q13. Donner le code OCamli permettant de définir la formule : f = (xo V x1 V 
1x2) À (1x1 V x).

Q14. Écrire une fonction de signature evalue_ clause : clause -> bool array -> 
bool qui
prend en paramètre une clause et une valuation représentée par un tableau 
contenant à
l'indice :, la valeur de vérité de la variable x; et renvoie la valeur de 
vérité de la clause.

Q15. Écrire une fonction de signature evalue_FNC : clause list -> bool array -> 
bool qui
prend en paramètre une clause et une valuation représentée par un tableau 
contenant à
l'indice :, la valeur de vérité de la variable x; et évalue une formule donnée 
sous forme
normale conjonctive.

Q16. Quel résultat obtient-on avec la formule F et le tableau de valuations 
[Ifalse;true;truel|] ?
Justifier.

Q17. On souhaite énumérer toutes les valuations possibles pour un nombre de 
variables fixé.
Étant donné une valuation, on considérera que si la valeur true correspond à 1 
et la valeur
false correspond à 0, la valuation suivante correspond à l'ajout de 1 au nombre 
binaire
associé. Ainsi, la valuation suivante de [Ifalse;true;falsel] est 
[|false;true;truel|].
On considère que la valuation suivante de TItrue;true;truel] n'existe pas.

Écrire une fonction de signature suivant : bool array -> bool qui prend en 
paramètre
un tableau de booléens, lui attribue la valuation "suivante" si possible et 
renvoie true; sinon
renvoie false.

4/7
Q18. En déduire une fonction de signature satisfiable : clause list -> int -> 
bool qui
prend en paramètre une formule en forme normale conjonctive, son nombre de 
variables et
renvoie true si il existe une valuation qui rend la formule vraie, false sinon.

Q19. Quelle est la complexité en temps de cette fonction par rapport aux 
paramètres d'entrée ?

Q20. Proposer une stratégie de retour sur trace pour résoudre le problème de 
satisfiabilité d'une
formule.

Conséquence logique entre 2 formules
Définition

Une formule $ est une conséquence logique d'un ensemble fini de n formules L = 
{F;,,..,F,},n
étant un entier naturel supérieur ou égal à 1, si tout modèle de # est un 
modèle de I". On note l'E @.
On admettra que toute formule admet une formule équivalente sous forme normale 
conjonctive.

Q21. Déduire de la fonction précédente, un algorithme en pseudo-code permettant 
de déterminer
si une formule F est une conséquence logique d'un ensemble de formules FL: 
F;,..,F;.

Q22. Afin de déterminer si I + &, on peut prouver le séquent I + 6. Justifier 
cette méthode, puis
construire un arbre de preuve qui démontre le séquent T' : P-- 0,0 --R,P + P où 
P,O,R
désignent des variables propositionnelles représentant des formules logiques, à 
partir des
règles d'inférence de la déduction naturelle ; les règles et notations 
utilisées seront clairement
mentionnées.

Partie III - Automates et reconnaissance de motifs
Dans cette partie, le langage utilisé est OCaml.

On s'intéresse à la reconnaissance de motifs dans un texte en utilisant une 
méthode naïve, puis
des automates.

1.1 - Autour de l'algorithme naïf de recherche de caractères

Définitions

Un alphabet A est un ensemble fini non vide d'éléments appelés lettres. Un mot 
défini sur À est
une suite finie d'éléments de A. Le mot vide sera noté EUR. L'ensemble des mots 
sur l'alphabet A est
noté A°. La longueur d'un mot x, notée |x| est le nombre de lettres de ce mot. 
Pour i allant de 0 à |xl--1,
x; désignera la lettre en position : . Ainsi, aab est un mot de longueur 3, sur 
tout alphabet contenant
les lettres a et b.

Un mot x est un facteur d'un mot y si il existe 2 mots z et » tels que y = uxv. 
Dans ce cas, on dit qu'il y
a une occurrence de x dans y. Quand z = EUR, x est un préfixe de y et quand v = 
EUR, x est un suffixe de y.
Soit x un mot non vide. Un entier 0 < p < |x| est une période de x si x; = x;,, pour 0 < i < |x| - p-- 1. On définit la période de x comme étant la plus petite des périodes. Un bord d'un mot non vide x est un facteur de x, différent de x et qui est à la fois un préfixe et un suffixe de la chaîne de caractères. Par exemple, EUR, a,aa,aabaa Sont les bords du mot aabaabaa. On note Bord(x) le plus long bord de x. On constate que lorsqu'il est défini, le bord d'un bord d'un mot x est aussi un bord de x. On le note Bord"'(x). On définit ainsi récursivement Bord"(x) avec n un entier naturel. 9/7 En OCamil, les fonctions suivantes pourront être utilisées sur le type string : - String.length : longueur de la chaîne de caractères - s.[i] : accès à la lettre d'indice ;: de la chaîne s - 7 : opérateur concaténation Q23. Justifier le fait que tout mot non vide possède au moins une période. Q24. Écrire une fonction de signature occurrence : string -> string -> bool qui 
prend en
paramètre 2 chaînes de caractères x, y et renvoie true si il existe une 
occurrence de x dans
y, false Sinon.

Q25. Quelle est la complexité en temps de la fonction occurrence en fonction de 
la longueur des
chaînes de caractères en entrée ?

Q26. Déterminer la période du mot x = aabaabaa défini sur l'alphabet À = {a, b}.

Q27. Écrire une fonction de signature periode : string -> int qui renvoie la 
période d'une
chaîne de caractères.

Q28. Soit x une chaïîne de caractères non vide et » un entier naturel tel que 0 
< p < |x|. Montrer que P est une période de x si et seulement si il existe 3 chaînes de caractères u, v, w telles que x = uw = wy et [ul = |v| = p. Q29. Soit x une chaîne de caractères non vide et n le plus grand entier tel que Bord"(x) est bien défini. On a donc Bord""(x) = EUR. Montrer par récurrence sur la longueur des mois que Bord(x), Bord"(x), ..., Bord"(x) est la suite des bords de x dans l'ordre décroissant de leur longueur et que |x| -- |Bord(x)|, |x| -- Bord"(x)|, ..., [xl - |Bord"(x)l est la suite des périodes de x dans l'ordre croissant. Q30. Expliquer brièvement comment la connaissance des bords peut permettre d'améliorer la complexité en temps dans le pire cas, de l'algorithme naïf de recherche d'une occurrence d'un mot. 111.2 - Localisation des occurrences d'un motif à l'aide d'un automate Un automate déterministe M sur l'alphabet À est composé d'un ensemble d'états finis Q, d'un état initial go, d'un ensemble d'états terminaux T EUR Q et d'une fonction de transitions 6 : O x A -- Q.Onle désigne par un quintuplet (Q, A, go, T, 6). On dit qu'il est complet si 6 est définie pour chaque élément de OQ x A. Certains automates peuvent être utilisés comme machine de recherche pour le traitement séquentiel de textes. Étant donné un alphabet A, un motif X représente un langage non vide ne contenant pas le mot vide. Le problème de la recherche de motifs est celui de la localisation d'occurrences de mots du langage dans d'autres mots. On suppose qu'on dispose d'un automate déterministe M complet qui reconnaît le langage A°X, autrement dit, l'automate M reconnaït les mots qui ont comme suffixe un mot de X. L'algorithme suivant permet de localiser les mots de X reconnus dans un texte 7, considéré comme une chaîne de caractères. Dans la suite, l'automate M de la figure 2 ci-après sera cité en exemple. Il est défini sur l'alphabet A = {a, b,c} 6/7 ; 2 3 4 5 6 7 8 9 10 11 12 Algorithme 2 : reconnaissance de mois dans un texte Cherche (Mt ) : Début e<-- initial[M]; 1st+- liste vide ; Pour chaque lettre À de t prise dans l'ordre croissant de leurs indices faire e «-- (eZ); Si e est un état terminal alors | ajouter à 1st l'indice de 1 dans +; Fin Fin Retourner 1st ;: Fin Figure 2 - Automate M On définit en OCaml un type automate par : type auto={etats: int list; alphabet : char list; initial: int; transition: int -> char ->int; final : int list};;

Q31. Créer une variable automate qui représente l'automate M de la figure 2.

Q32. L' automate M est-il émondé ? Justifier.

Q33. Présenter les premières étapes de l'algorithme d'élimination des états 
appliqué à l'automate
M. On éliminera l'état 0.

Q34. Que représentent les indices mémorisés dans la liste 1st de l'algorithme 
cherche ? Que
contient la liste 1 de l'algorithme cherche avec l'automate ci-dessus et = 
cabaac ?

Q35. Écrire une fonction de signature cherche : auto -> string -> int list qui 
implémente
l'algorithme cherche.

Q36. Montrer la correction de l'algorithme cherche.

FIN

117