CCINP Informatique optionnelle MP 2021

SESSION 2021 @ MP7IN

CONCOURS
COMMUN
INP

ÉPREUVE MUTUALISÉE AVEC E3A-POLYTECH

ÉPREUVE SPÉCIFIQUE - FILIÈRE MP

INFORMATIQUE

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 efjaç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 indépendantes.

1/11
Partie I- Étude des partitions non croisées

Dans cette partie, on introduit et on étudie de façon élémentaire les 
partitions non croisées, objets com-
binatoires apparaissant dans divers domaines des mathématiques, notamment dans 
la théorie des proba-
bilités libres et des matrices aléatoires.

Le langage de programmation utilisé dans cette partie est le langage Python.

Dans la suite, pour tout couple (i,n) EUR N°, les notations [n] et [i,n] 
désignent respectivement les en-
sembles {1,2,...,n} et {i,i+1,...,n}. Par convention, [0] = Y et si i > n alors 
[i,n] = 0.

Définition 1 (Partition)
Soit À un sous-ensemble non vide de N. Une partition ? de À est un ensemble de 
parties de À tel que :

1. VPEP,P40:; 2. VPO)EP?,(P£OQ) -- (PNnO=0): 3. | JP=A.
PEP
Par exemple, {{2, 4,5},{7,9},{8}} est une partition de l'ensemble {2, 4, 5, 7, 
8,9}.

Définition 2 (Classe)
Soit P une partition d'un sous-ensemble À non vide de N. Soit : un élément de 
À. La classe de : est
l'unique élément P de F tel que 1 EUR P. Elle est notée CI(:).

Par exemple, pour P = {{2,4,5},{7,9},{8}}, on a CI(4) = {2,4, 5}.

Définition 3 (Partition non croisée)
Soit P une partition d'un sous-ensemble À non vide de N. On dit que F est non 
croisée si pour tout
quadruplet (a, b, c, d) EUR A* tel que a < b  (CI(a) = CI(b) = CI(c) = CI(d)).

Par exemple, P = {{2,4,5},{7,9},{8}} est bien une partition non croisée de {2, 
4,5,7,8,9}. En efïtet,
aucun quadruplet (a, b, c, d) EUR {2,4,5,7,8, 9) tel que a < b < c < d'ne vérifie la condition Cl(a) = CI(c), CI(b) = Cd). De même, Q = {{2,7,8,9}, {4,5}} en est bien une. En effet, (a, b, c,d) = (2, 7,8, 9) est l'unique quadru- plet tel que a < b < c < d vériñant Cl(a) = CI(c), CI(D) = CI(d) et ces quatre éléments sont bien dans la même classe. Par contre, R = {{2,5},{4,7,9},{8}} n'en est pas une. En effet, CI(2) = CI(S) et CI(4) = CI(7) mais CI(2) 4 CI(4). Le terme « non croisée » découle naturellement des représentations picturales des partitions (figure 1). Figure 1 - Représentations picturales de P, Q,R 2/11 Dans la suite, on s'intéresse uniquement aux partitions d'un sous-ensemble fini de N. On les représente en Python à l'aide de listes de listes croissantes d'entiers triées dans l'ordre lexicographique. Par exemple, les partitions P = {{2,4,5},{7,9},{8}} et R = {{2,5},{4,7,9},{8}} sont respectivement représentées par les listes P = [[2,4,5],[7,91,[8]]etR = [[2,5],[4,7,91,[8]1]. L.1 - Exemples et fonctions élémentaires (Informatique Pour Tous) Q1. Justifier brièvement que P = {{1,7},{2},{3,4,5},{6}} est une partition non croisée de [7] et que Q = {{1,6},{2},{3,4,5,7}} n'en est pas une. Q2. Parmi les ensembles suivants, indiquer sans justification lesquels sont des partitions de [5]. Parmi les partitions, préciser sans justification lesquelles sont non croisées. 1 P1 ={{1,3},{2,4,5}}, 2. P, = {1,3},{1,2},{4,5}}, 3. P3 = {{1,3}{2,4}}, 4, Pa = {1,4,5},{2,3}}. Q3. Décrire l'ensemble des partitions non croisées de [41]. Pour Q4, QS et Q6, on se fixe un ensemble fini À EUR N. Cet ensemble est représenté en Python par la liste croissante d'entiers À, définie au préalable. On suppose également que pour ces questions, la variable P désigne une liste de listes croissantes d'entiers triée dans l'ordre lexicographique. On définit la fonction Python mystere(P) par : def mystere(P) L = [False for _ in range(len(A))] for 1 in range(len(P)) If PI[1] == {| return False else for j] in range(len(Pf1l])) if P[i][j] not in A : return False else # A.index(a) renvoie l'indice de a dans A Kk = A.index(P[1][]l]) if LIKk] return False else LIKk] = True return not (False in [L) Q4. Uniquement dans cette question, on suppose que À = [1,2,3,4,5]. Expliciter sans justification les valeurs de : 1. mystere([[1,3],[1,5],[2,4]]) 2. mystere([[1,3,4],[2]1]) 3. mystere([[1,3,5],[2,4]1]) 4, mystere([[1,[1,2,3,4,5]]). Q5. Écrire une fonction Python classe(P,i) prenant en arguments une variable P représentant une partition Y de À et un entier i EUR À qui renvoie une liste L représentant CI(i). 3/11 On définit la fonction Python au code incomplet est_nc(P) suivante : def est _nc(P) # On rappelle que À est une liste triée dans l'ordre croissant N = Ilen(A) for 1 in range(N) for J in range(1+1l,N) for K in range(]j+1,N) for 1 in range(k+1,N) Q6. Recopier et compléter le code de la fonction est_nc(P), sachant qu'elle prend en argument une variable P représentant une partition P de À et qu'elle renvoie True s1 P est non croisée et False sinon. 1.2 - Nombre de partitions non croisées Pour tout n > 1, on note C, le nombre de partitions non croisées d'un ensemble 
À EUR N ayant exac-

tement n éléments et NC(A) l'ensemble des partitions non croisées de A. Par 
convention, Co = 1
et NC(0) = {0}.

Définition 4 (Partition non croisée emboîtée)

Soient À un ensemble fini de N de cardinal n et P une partition non croisée de 
À. On dit que ? est em-
boîtée si le minimum m et le maximum M de À sont dans la même classe (Cl(m) = 
CI(M)). L'ensemble
des partitions non croisées et emboîtées de À et son cardinal sont 
respectivement notés NCE(A) et D,.

Par exemple, S = {{1,2,5,9},{3,4}, {6,7, 8}} est une partition non croisée et 
emboîtée de [9].

Le terme « emboîtée » découle naturellement des représentations picturales des 
partitions (figure 2).

Figure 2 - Représentations picturale de S

Q7. Montrer que pour toutn eN,onaC, = D,:1.

QS. Soit n EUR N. On définit l'application D, comme suit :

n+]

D,: | JNCE(DXNC(i+Ln+1]) -- NC(n+1])

i=1
(Q1, Q) k Qi U OO».

n
En admettant que ®, est une application bijective, montrer que C,:1 = > CrCn-k-
k=0

Q9. (Informatique Pour Tous) Écrire une fonction Python calcul_C(n) qui prend 
en argument un
entier naturel n et qui renvoie la valeur C,.

4/11
Partie II - Logique et étude du problème Horn-Sat

Dans cette partie, A, V, --, désignent respectivement les connecteurs de 
conjonction, de disjonction et de
négation. Les symboles V, F désignent respectivement les valeurs de vérité VRAI 
et FAUX du calcul
propositionnel.

Dans la suite, on s'intéresse au problème Horn-Sat, qui peut être décrit de la 
façon suivante : étant
donnée une formule de Horn P, existe-t-1l une interprétation J telle que [P]; = 
V ?

L'objectif est d'expliciter un algorithme permettant de résoudre ce problème.

Définition 5 (Formule propositionnelle)
Soit X un ensemble de symboles appelés variables propositionnelles. Les 
formules propositionnelles
sur À sont alors définies de façon inductive comme suit :

- V,F sont des formules propositionnelles ;

- tout élément x de X est une formule propositionnelle ;

- si P et Q sont des formules propositionnelles, alors --P, (P A O),(P V ©) 
sont des formules pro-
positionnelles.

Dans la suite, les variables propositionnelles et formules propositionnelles 
considérées sont construites
à l'aide d'un ensemble X qui ne sera pas explicité.

Définition 6 (Littéral)
Soit x une variable propositionnelle. Un littéral est la formule x ou la 
formule -x. Le littéral x (respec-
tivement --x) est un littéral positif (respectivement négatif).

Définition 7 (Clause disjonctive)

Soient ñn EUR N, x1,x2,...,x, des littéraux. La formule x; V x V ... V x, est 
appelée clause disjonctive à
n littéraux (ou de taille n). Par convention, () désigne la clause disjonctive 
vide, c'est-à-dire la clause
sans littéral.

Une clause de Horn est une clause disjonctive contenant au plus un littéral 
positif.
Une clause unitaire est une clause composée d'un unique littéral.

Définition 8 (Forme normale conjonctive)

Soit P une formule propositionnelle. On dit que P est une forme normale 
conjonctive s'il existe un
entier n EUR N, Ci, C2,...,C, des clauses disjonctives vérifiant P = C3 À C3 À 
... À C,. Par convention,
une forme normale conjonctive sans clause est représentée par Ü.

Définition 9 (formule de Horn)
Soit P une formule propositionnelle. On dit que P est une formule de Horn s'il 
existe n EUR N, Ci, C,...,C;
des clauses de Horn vérifiant P = CAC A...AC,.

Définition 10 (Interprétation)
Soient n EUR N et x1,X2,...x, des variables propositionnelles. Une 
interprétation est une application
L: {X1, X, . . . ; Xn} mn {V,F}.

Définition 11 (Évaluation)

Soient P une formule propositionnelle, x:,x2,...,2x, les variables 
propositionnelles apparaissant dans P
et / une interprétation sur {x1,x2,...,x,}. L'évaluation de P suivant 
l'interprétation 7 que l'on note [P];
est définie par récurrence de la façon suivante :

5/11
- S PE {V,F}, alors [P]; = P;

- SP E{X,,x2,...,Xx,}, alors [P]; = I(P);

- Si P = -Q où Q est une formule propositionnelle, alors [P]; = -[Q];;

- S P = A0 B où À,B sont des formules propositionnelles et o EUR {A, V}, alors 
[P]; = [A]; o [B;.
Par convention, [0]; = F et [Y]; = V.

Définition 12 (Satisfiable)
Soit P une formule propositionnelle. On dit que P est satisfiable s'il existe 
une interprétation J telle que
[P | I -- V.

Q10. Pour chacune des formules suivantes, montrer qu'elle est satisfñable ou 
qu'elle est non satisfable.

LP = (XV) AGXV=y) A (XV =), 2. P3 = (x) A (x V =y) A (y V2) A (2),
3. P3 =0(, 4. Pa =(XV-YV =) AVE V x V -y).

Q11. Parmi les fomules de la Q10, lesquelles sont des formules de Horn ? On ne 
justifiera pas la
réponse.

Définition 13 (Propagation unitaire)
Soit P une forme normale conjonctive contenant une clause unitaire (x). On 
construit une formule P" à
partir de P de la façon suivante :

1. supprimer de P toutes les clauses où x apparaît ;
2. enlever toutes les occurrences du littéral -x.
Cette procédure de simplification est appelée propagation unitaire.

Par exemple, si P = (x V -y V z) À (-x V y V z) A (x), on a alors P" = (y Vz). 
Si P = (x) A(-x),;ona
alors P" = ().

Dans la suite, on note II(P) une formule sans clause unitaire obtenue en 
itérant la propagation unitaire
sur P. On admet que si IT(P) ne contient pas de clause vide () alors IT(P) est 
unique et que s1 IT(P)
contient au moins une clause vide alors toute formule sans clause unitaire 
obtenue par itération de la
propagation unitaire sur P contient au moins une clause vide.

Q12. On pose :

P = (x) A (x V x V x) À (x V %3 V X4) À (x V 1%) À (=X2 V x] V %3)
À (2%3 V =Xxa V Xs) À (2x1 V X2 V Xs).

Calculer IT(P). On pourra donner le résultat directement sans détailler les 
calculs.

Q13. Soit P une formule de Horn. Montrer que II(P) est une formule de Horn.
Q14. Soit P une forme normale conjonctive. Montrer que P est satisfñable s1 et 
seulement si II(P) est
satisfable.

Q15. Soit P une forme normale conjonctive. Montrer que si () apparaît dans 
II(P), alors P n'est pas
satisfable.

Q16. Soit C une clause de Horn. Montrer que si C n'est n1 la clause vide n1 une 
clause unitaire positive,
alors C est satisfable.

Q17. Soit P une formule de Horn ne contenant ni de clause vide n1 de clause 
unitaire positive. Montrer
que P est satisfiable.

Q18. Soit P une formule de Horn. Montrer que P n'est pas satisfable si et 
seulement si () apparaît
dans II(P).

6/11
Partie III - Étude des classes sylvestres

Étant donné un arbre binaire de recherche T,, sa classe sylvestre est 
l'ensemble des mots qui donnent
l'arbre T' après insertion dans l'arbre vide. L'objectif de cette partie est de 
donner une caractérisation et
une description de cet ensemble. On commence par rappeler la structure des 
arbres binaires de recherche
ainsi que leurs propriétés usuelles. Puis, on introduit la notion de 
S-équivalence sur les mots qui permet
de caractériser la classe sylvestre d'un arbre T. Enfin, à l'aide du produit de 
mélange, on présente un
algorithme calculant la classe sylvestre d'un arbre donné.

Dans toute la suite, Z désigne un alphabet fini totalement ordonné. Le symbole 
& désigne le mot vide.

III. 1 - Algorithme d'insertion dans un arbre binaire

Définition 14 (Arbre binaire)
Un arbre binaire 7 (étiqueté par les éléments de Y) est récursivement soit :

- l'arbre vide que l'on note o;
- un triplet (7,,r, Ta) où r est un élément de », T, et 7, des arbres binaires. 
Les éléments 7, T, et Ta
sont respectivement appelés racine, sous-arbre gauche et sous-arbre droit de T.

Définition 15 (Arbre binaire de recherche)
Un Arbre Binaire de Recherche (abrégé en ABR) T est récursivement soit :

- l'arbre vide:

- un triplet (T,,,r, Ta) où r est un élément de », T, et T, des ABR. De plus, 
toute valeur apparaissant
dans 7, est strictement inférieure à r et toute valeur apparaissant dans T, est 
supérieure ou égale
à r.

Définition 16 (Insertion dans un arbre binaire)
L'insertion d'un élément a de Z dans un arbre binaire T est une opération que 
l'on note T + a définie
récursivement comme sui :

- ST =0,alors T -- a=(0,a,0);
- ST =(T,;r, Tyetr a, alosT -», als TT - char arbre -> char arbre

et telle que insertion_lettre a t est l'arbre binaire obtenu en insérant la 
lettre a dans
l'arbre binaire t.

Q21. Ecrire une fonction récursive en Ocamil de signature :
insertion _ mot : char list -> char arbre -> char arbre
et telle que insertion_mot w t est l'arbre binaire obtenu en insérant le mot w 
dans l'arbre

binaire t.

Définition 18 (Lecture préfixe)
Soit T un arbre binaire. La lecture préfixe de T que l'on note w7 est le mot 
défini récursivement par :

- si Î = o, alors wr = EUR;
- ST = (T,,r, Ta), alors wr = rw,wa où w, et w, sont les lectures préfixes 
respectives de T, et de
Ta.

8/11
Q22. Expliciter wr pour l'arbre binaire T représenté ci-dessous :
S
y TT
N V

7° \ /

O O

\

Ê

/\ À

/

O

4 MN,
\ \  /

Figure 4 - Représentation de T de Q22

Q23. Ecrire une fonction récursive en Ocamil de signature :
prefixe : char arbre -> char list

et telle que prefixe t est le mot qui correspond à la lecture préfixe de 
l'arbre t.

Q24. Soit T un ABR, soit w7 la lecture préfixe de T. Montrer que T est l'ABR 
associé à wr.
IIL.2 - Une relation d'équivalence sur les mots

Définition 19 (S-adjacence)
Soient u et v deux mots sur Z. On dit que u est S-adjacent à v (ou que u et v 
sont S-adjacents) s'il existe
trois lettres a < b < c de X et trois mots f., f), f; sur Z vérifiant : (u -- f.bfacf; et v = f.bf,caf;) ou (u -- f.bf,caf; et v = f.bf,acf;). Définition 20 (S-équivalence) Soient z et y deux mots sur Z. On dit que u est S-équivalent à v (ou que u et v sont S-équivalents) s'il existe nEN,(Wwp,W1,...,Wn) EUR OE*)" vérifiant : u = Wo,vV = Wy, VIE {0,1,...,n--1},w; est S-adjacent à w;,1. SL Q25. Montrer que la relation " être S-équivalent à " est bien une relation d'équivalence sur X*. Q26. Soient a, b,c trois lettres de Z vérifiant a < b < c. Montrer que pour tout arbre binaire de recherche T contenant au moins la lettre b, on a: T + ac =T + ca. On pourra raisonner par récurrence sur le nombre de noeuds de T. Q27. Montrer que si deux mots et v sont S-équivalents, alors les ABR (0 + u)et(o « y) sont égaux. 9/11 existe un mot w' = ruv où u (respectivement v) est un mot dont toutes les lettres sont plus petites strictement (respectivement plus grandes au sens large) que r et tels que w et w' sont S-équivalents. On note À l'ensemble des mots S-équivalents à w. Pour tout a = äpdi...4y_1 EUR À, on pose : Q28. Soit w un mot de longueur n > 1 sur », soit r la première lettre de w. On 
veut montrer qu'il

N(@a)= {Gi jefln-1fPli< ja; char list list -> char list list

et telle que ajout_lettre a liste est la liste de mots de la forme a: :w où w 
est un élément
de liste.

Écrire une fonction récursive en Ocaml de signature :
shuffle : char list-> char list -> char list list

et telle que shuffle u v est une liste contenant exactement tous les mots de w 
LL v avec
répétitions possibles d'un même mot. On devra utiliser la fonction auxihaire 
ajout_lettre et
l'opérateur de concaténation @.

Écrire une fonction récursive en Ocaml de signature :
shuffle_1l : char list list -> char list list -> char list list

et telle que shuffle_1l I m est une liste contenant exactement tous les mots de 
L 111 M où la
liste 1 (respectivement m) représente le langage L (respectivement M), avec 
répétitions possibles
d'un même mot. Seules les fonctions définies précédemment peuvent être 
utilisées en fonctions
auxiliaires.

Ecrire une fonction récursive en Ocaml de signature :
sylvestre _T : char arbre -> char list list

et telle que sylvestre_T t est une liste contenant exactement tous les éléments 
de la classe
sylvestre de t. Seules les fonctions définies précédemment peuvent être 
utilisées en fonctions
auxiliaires.

FIN

11/11