CCINP Informatique optionnelle MP 2023

SESSION 2023 © MP7IN
CONCOURS
C COMMUN

É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 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 indépendantes. 1/8 Partie | - Programmation en OCami : sélection du (k + 1}° plus petit élément La sélection du (k + 1}° plus petit élément d'une liste d'entiers L, non nécessairement triée, consiste a trouver le (k + 1° élément de la liste obtenue en triant ZL dans l'ordre croissant. Par exemple, si L = [9;1;2;4;7;8] le 3° plus petit élément de Z est 4. On pourra remarquer que si la liste L est triée dans l'ordre croissant, le (k + 1)° plus petit élément est l'élément de rang k dans L. On présente un algorithme permettant de résoudre ce problème de sélection avec une complexité temporelle linéaire dans le pire cas. Celui-ci est basé sur le principe de "diviser pour régner" et sur le choix d'un bon pivot pour partager la liste en deux sous-listes. Dans cette partie, les fonctions demandées sont à écrire en OCaml et ne doivent faire intervenir aucun trait impératif du langage (références, tableaux ou autres champs mutables ou exception par exemple). Étant donné un réel a, on note |a] le plus grand entier inférieur ou égal à a. 1.1 - Fonctions utiles Dans cette section, on écrit des fonctions auxiliaires qui sont utiles pour la fonction principale. Q1. Q2. QS. Q4. Écrire une fonction récursive de signature : longueur : 'a list -> int
et telle que longueur 1 est la longueur de la liste 1.
Écrire une fonction récursive de signature :
insertion : l'a list -> 'a -> 'a list

et telle que insertion 1 a est la liste triée dans l'ordre croissant obtenue en 
ajoutant l'élé-
ment a dans la liste croissante 1.

En déduire une fonction récursive de signature :

tri insertion : 'a list -> 'a list
et telle que tri_insertion 1 est la liste obtenue en triant 1 dans l'ordre 
croissant.
Écrire une fonction récursive de signature :

selection n : 'a list -> int -> 'a

et telle que selection _n 1 n est l'élément de rang n de la liste 1.
Par exemple, selection_n [4;2;:6;4;1;15] 3 est égal à 4.

218
Q5. Écrire une fonction récursive de signature :
paquets _de_ cinq : 'a list -> 'a list list

et telle que paquets _de_ cinq 1 est une liste de listes obtenue en regroupant 
les éléments de
la liste 1 par paquets de cinq sauf éventuellement le dernier paquet qui est 
non vide et qui
contient au plus cinq éléments. Par exemple :

- paquets de cinq [] est égal à [],

- paquets de cinq [2;1;2;1;3] est égal à [[2;1;2;1;31],

- paquets _de_ cinq [3;4;:2;1;5;6;3] est égal à [f[3;4;2;1;51;[6;3]].

Q6. Écrire une fonction récursive de signature :
medians : 'a list list -> 'a list

et telle que medians 1 est la liste m obtenue en prenant dans chaque liste /; 
apparaissant dans
la liste de listes 1 l'élément médian de /;. On convient que pour une liste À 
dont les éléments
sont exactement ao < ai <... < an_1, l'élément médian désigne a »1. 2 Dans le cas où la liste L n'est pas triée, l'élément médian désigne l'élément médian de la liste obtenue en triant L par ordre croissant. Par exemple : medians [[3;1;5;3;2];14;3;1]1;11;3];[5;1;2;4]] est égal à [3;3;1;21]. Q7. Écrire une fonction de signature : partage : 'a -> 'a list -> l'a list * 'a list * int * int

telle que partage p 1 est un quadruplet 11,12,n1,n2 où 11 est la liste des 
éléments de 1
plus petit que p, 12 est la liste des éléments de 1 strictement plus grand que 
p, n1 et n2 sont
respectivement les longueurs de 11 et 12.

1.2 - La fonction de sélection et sa complexité

On détaille la fonction de sélection :
Q8. Écrire une fonction récursive de signature :
selection : 'a list -> int -> 'a

telle que selection 1 kestle (k + 1)° plus petit élément de la liste 1. 
L'écriture de la fonction
sera une traduction en OCami de l'Algorithme 1 présenté en page 4.

On cherche à déterminer la complexité en nombre de comparaisons de la fonction 
selection. Pour
tout n e N, on note T'(n) le nombre maximum de comparaisons entre éléments lors 
d'une sélection
d'un élément quelconque dans des listes Z sans répétition de taille n.

En analysant l'Algorithme 1,il est possible de démontrer que :

masse cr(et]} er (8) an e

Q9. En admettant la proposition (|), montrer que pour tout entier n supérieur à 
1, on a :
T (n) < (200 + T (55))n. Pour l'initialisation, on pourra remarquer que T est une fonction croissante. 318 1 2 12 13 14 15 16 17 18 19 20 Algorithme 1 - Sélection du (k + 1}° plus petit élément SELECTION L K: /* L est une liste, k est un entier positif * / début n LONGUEUR L si n < 5 alors M <- (TRI_INSERTION L) retourner l'élément de rang k de M fin sinon L_ Cinq + PAQUETS_DE_CINQ L M < mep1ians L Cinq pivot < SELECTION M ((n+4)//5)//2 /* L'opérateur // désigne le quotient d'entiers. Le rang ((n+4)//5)//2 correspond au rang du médian de la liste M * / Li, L,ni,n2 + PARTAGE Pivot L Si k < n, alors | retourner SELECTION L, k fin sinon | retourner SELECTION L) (k--n:;) fin fin fin Partie Il - Recherche d'une clique de célébrités 11.1 - Définitions et propriétés Définition 1 (Graphe). On appelle graphe un couple G = (S,A) où S est un ensemble fini appelé ensemble des sommets et À est une partie de S x S, appelée ensemble des arêtes. On pourra remarquer que, dans cette définition de graphe, les éléments de la forme (s,5)ousesS sont des arêtes possibles. Définition 2 (Clique). Soit G = (S,A) un graphe. Soit S' une partie de S. On dit que S'" est une clique SI : V(s1,5) ES XS",(51, 52) EUR À. Définition 3 (Clique de célébrités, célébrité). Soient G = (S,A) un graphe et C une partie de S. On dit que C est une clique de célébrités si C est une clique et : V(csECXS,((s,c)E A)A((C SEA = sEC). Un élément de l'ensemble C est alors appelé célébrité. Le terme célébrité" provient de l'interprétation suivante : l'ensemble des sommets correspond à un ensemble de personnes et une arête (s,c) représente le fait que s connaît c. Ainsi, une célébrité est connue de tous et elle connaît uniquement les autres célébrités. 418 Q10. Dans cette question, on pose S = {0,1,2,...,6}. Pour chacun des graphes suivants, préciser S'ils contiennent une clique de célébrités non vide. Dans le cas où il y en a une, l'expliciter. 1. Gi =(S,A,) avec À, = {(1,2),(1,3).,(1,5),(2,6)!}. 2. G2 = (S,A)) avec A) -- (0,3),(0,5),(1,2),(1,3),(2,2),(2,3),(3,3), 27 | (4,1),(4,3),(4,5),(5,1),(5,3),(6,1),(6,3) Q11. Soit G = (S,A) un graphe quelconque. Montrer que s'il existe une clique de célébrités non vide C dans G, alors celle-ci est unique. Dans la suite, on note CG l'unique clique de célébrités non vide du graphe G. Dans le cas où celle-ci n'existe pas, C& désigne alors l'ensemble vide qui est noté 0. Q12. Soient G = (S,A) un graphe et p un sommet de G. On note G" = (S\{p},AN(S\{p} xS \{p})). Montrer les propositions suivantes : a) Montrer que si C; est égal à l'ensemble vide, alors CG EUR {0,{p}}. b) Montrer que si CG\{p} 4 0, alors C& = CG\{p}. c) On suppose que C;: n'est pas l'ensemble vide et on fixe c" un élément de Cc. 1) Montrer que si (p, c') n'est pas un élément de 4, alors CG EUR {0,{p}}. i) Montrer que si (c', p) n'est pas un élément de 4, alors CG EUR {0, Ca}. ii) Montrer que si (p, c') et (c', p) sont des éléments de 4, alors CG EUR {0, {p} U Co}. 11.2 - Algorithmique et programmation en Python (Informatique Commune) Dans la suite, l'ensemble des sommets est de la forme {0, 1,...,n-- 1} où n est un entier supérieur à 1 et un graphe G = (S, À) est représenté en Python par sa liste d'adjacence que l'on note Z; et qui est définie par : [Ej | JES et G, je A J'iesS]. Par exemple, si G = ({0,1,2,3},{(0,1),(3,2),(3,1),(1,2)}), alors LG = [[1], [2], [}, [1,2]]. On pourra remarquer que si l'ensemble des sommets d'un graphe G est égal à {0,1,...,n -- 1}, alors la longueur de la liste Z; est égale à n. Q13. Écrire une fonction Python est_clique(L,R) prenant en argument une liste L qui est une liste d'adjacence d'un graphe G = (S,A) et une liste R sans répétition d'éléments de S et qui renvoie True si l'ensemble des éléments de RÀ constitue une clique de G et False sinon. Q14. On considère le graphe G ayant comme liste d'adjacence : LG = [[1,3,5], 10,21, [4, 67, 2,4, 5, 61, [2T, [2, 3, 4], (2, 4, 61]. Décrire l'évolution de la variable C à chaque étape de l'Algorithme 2 décrit en page 6. Q15. Écrire une fonction Python Clique_possible_C(G) prenant en argument une liste G représen- tant un graphe et qui renvoie la liste C construite à l'aide de l'Algorithme 2. Q16. Montrer par récurrence sur le nombre de sommets que si G est un graphe où CG est non vide, alors Clique_possible C(G) est égale à CG. 9/8 Algorithme 2 - Construction d'une clique de célébrités possibles 1 CLIQUE_POSSIBLE C G: 2 début 3 CI 4 S -- [0,1,...,n-1] /* n est le nombre de sommet de G 5 pour chaque s élément de S faire 6 si C est vide alors 7 | Ajouter s dans C 8 fin 9 sinon 10 c-- premier élément de C 11 t-- FAUX /* t permet de vérifier si on a effectué certaines instructions 12 si (S,c) n'est pas une arête de G alors 13 Cfs] 14 t-- VRAI 15 fin 16 si (c,s) n'est pas une arête de G alors 17 CC 18 t-- VRAI 19 fin 20 si : = FAUX alors 21 | Ajouter s à la fin de liste C 22 fin 23 fin 24 fin 25 fin 26 retourner C 6/8 Partie III - Etude d'une famille d'automates Dans cette partie, l'alphabet > désigne l'ensemble {0,1}, le symbole & désigne 
le mot vide et on rap-
pelle que Z* désigne l'ensemble des mots sur l'alphabet x.

Étant donné un mot w, on rappelle que |w| désigne la longueur du mot w et 
l'indexation des lettres de
w commence par 0. La première lettre de w est donc wo.

La notation Card (£E) désigne le cardinal d'un ensemble E.

Étant donnés un entier n et un entier non nul m, la notation n mod m désigne le 
reste de la division
euclidienne de n par m.

1.1 - Définitions

Définition 4 (Automate déterministe ). Un Automate déterministe est un 
quintuplet A = (Q, X, 6, go, F)
avec :

Q un ensemble fini non vide appelé ensemble des états,

> est un ensemble fini appelé alphabet,

- 6: Q XX -- Q une application appelée application de transition,
go Un élément de Q appelé état initial,

F une partie de Q appelée ensemble des états finaux.

Définition 5 (Application de transition étendue aux mots). Soit A = (Q,X, 6, 
qo, F) un automate déter-
ministe.

On définit de manière récursive 6* : Q x Z* -- Q par:

Ve Q, 6*(q,E=) = aq,
VaeQ,VaeX,YweX*, 6*(q,aw) = 6*(6(q,a),w).

Définition 6 (Reconnaissance d'un mot par un automate). Soient w = wowi...w, Un 
mot sur un
alphabet x et À = (Q, 5,6, go, F). On dit que w est reconnu par l'automate À si 
6* (go, w) EUR F.

Définition 7 (Automate 4;,, fonction indicatrice Z;,). Soient p et k deux 
entiers vérifiant 0 < k < p--1. L'automate A; est défini par : - Q=1{0,1,...,p--1}X {0,1}, - 2 = {0,1}, V(c,e) EUR Q,6((c,e),0)=((c+1) mod p,e), _ f ((c+1) mod p,l-e) sic=k mod p, V(ce,)EUR gé((ce), 1) = { ((c+1) mod p,e) sinon. go = (0,0), - F={0,1,...,p---1}x{1}. On note /,, la fonction indicatrice de l'ensemble des mots reconnus par 4;,. Soit autrement : 1 si A;, reconnaît u k _ Vue 2", Lx pu) = { O sinon. 11.2 - Exemples et propriétés élémentaires des A;, Q17. Soit w e X*. Expliciter sans démonstration l'état 5* (go, w), la lecture du mot étant effectuée dans l'automate 4, ;. On pourra s'aider d'une représentation graphique de l'automate. 718 Dans les questions Q18 à Q22, p et k désignent des entiers tels que p>2etke{0,1,...,p-1}.

Q18. Soit w EUR Z*. Expliciter l'état 6* (go, w), la lecture du mot étant 
effectuée dans l''automate 4;..
On ne demande pas de démonstration.

Un corollaire direct du résultat de la question Q18 est que l'ensemble des mots 
reconnu par l'automate
Ar, eSt égal à :

{we Z*

Card ({m EN | pm+k< [wl-1etw,n4x = 1}) est impair}. Dans la suite du problème, on admet ce résultat. Q19. Soit w un mot reconnu par un automate 4;,. Montrer que w est reconnu par au moins un autre automate parmi A62, A1 2, Ar,p aVeC l # k. Définition 8 (Ou exclusif étendu aux mots binaires). On rappelle que le Ou exclusif qu'on note & est une opération définie sur {0, 1} par : 080=1681=0et0æ1=160=lI. Soient n EUR N, u et y deux éléments de {0, 1}". On définit le Ou exclusif de z et v, noté " & v, le mot de longueur n défini par : Vie{0,1,...,n-1},(u@v); = u;@ v.;. Q20. Soient et v deux mots de Z* de même longueur. Montrer que : Le,p (Qu  v) = Le p (u) © Le,p (v). Q21. Soit w un mot binaire vérifiant : Lo2 (w) = Li2 (w)=0etVke{1,2,... >» P -- 1}, Lep (w) = 0.

a) Montrer que Lo, (w) = 0.

b) En déduire que pour tout mot w' EUR 0* -w, on a:
Lo2 (w') = Li2 (w') <= 0etVrke!{l,2,... >» P -- 1}, Lep (w') = (À.
Q22. Montrer que pour tout w e Z* et w' EUR w - 0*, on a L4,, (w) = Lx.p (Ww').
Remarque. Ces égalités permettent la construction d'une relation d'équivalence 
sur les mots qui est

utilisée pour montrer que deux mots de longueur N peuvent être séparés par un 
automate de la forme
Ax,p ayant O( VN In (N)) états.

FIN

8/8

NATIONALE - 231130 - D'après documents fournis

IMPRIMERIE