Version interactive avec LaTeX compilé

CCINP Option Informatique MP 2023

Notez ce sujet en cliquant sur l'étoile

0.0(0 votes)

🔗 Explorer

CCINP MP CCINP 2023 MP Info Info 2023

2025_08_29_782502ef78d0203317d9g

É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.

Partie I - Programmation en OCaml : sélection du plus petit élément

La sélection du

plus petit élément d'une liste d'entiers

, non nécessairement triée, consiste à trouver le

élément de la liste obtenue en triant

dans l'ordre croissant.

Par exemple, si

plus petit élément de

est 4 . On pourra remarquer que si la liste

est triée dans l'ordre croissant, le

plus petit élément est l'élément de rang

dans

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

, on note

le plus grand entier inférieur ou égal à

1.1 - Fonctions utiles

Dans cette section, on écrit des fonctions auxiliaires qui sont utiles pour la fonction principale.
Q1. Écrire une fonction récursive de signature:
longueur : 'a list -> int
et telle que longueur 1 est la longueur de la liste 1.
Q2. Écrire une fonction récursive de signature :
insertion : 'a list -> 'a -> 'a list
et telle que insertion l a est la liste triée dans l'ordre croissant obtenue en ajoutant l'élément

dans la liste croissante 1 .

Q3. En déduire une fonction récursive de signature :
tri_insertion : 'a list -> 'a list
et telle que tri_insertion l est la liste obtenue en triant l dans l'ordre croissant.
Q4. É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 [

] 3 est égal à 4 .

Q5. Écrire une fonction récursive de signature :
paquets_de_cinq : 'a list -> 'a list list
et telle que paquets_de_cinq l 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 est égal à ,
paquets_de_cinq [ ] est égal à [ ].

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

, l'élément médian désigne

.
Dans le cas où la liste

n'est pas triée, l'élément médian désigne l'élément médian de la liste obtenue en triant

par ordre croissant. Par exemple :

medians [[3;1;5;3;2];[4;3;1];[1;3];[5;1;2;4]] est égal à [3;3;1;2].

Q7. Écrire une fonction de signature :

partage : 'a -> 'a list -> 'a list * 'a list * int * int

telle que partage p 1 est un quadruplet

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 l kest le

plus petit élément de la liste l. L'écriture de la fonction sera une traduction en OCaml 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

, on note

le nombre maximum de comparaisons entre éléments lors d'une sélection d'un élément quelconque dans des listes

sans répétition de taille

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

Q9. En admettant la proposition (I), montrer que pour tout entier

supérieur à 1 , on a :

Pour l'initialisation, on pourra remarquer que

est une fonction croissante.

Algorithme 1 - Sélection du $(k+1)^{\mathrm{e}}$ plus petit élément
SELECTION L K :
/* L est une liste, k est un entier positif */
début
    $n \leftarrow$ LONGUEUR L
    si $n \leq 5$ alors
        $\mathrm{M} \leftarrow$ (TRI_INSERTION $L)$
        retourner l'élément de rang $k$ de $M$
    fin
    sinon
        L_Cinq $\leftarrow$ PAQUETS_DE_CINQ L
        $\mathrm{M} \leftarrow$ medians L_Cinq
        pivot $\leftarrow$ selection $\mathrm{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$ */
        $L_{1}, L_{2}, n_{1}, n_{2} \leftarrow$ PARTAGE pivot L
        si $k<n_{1}$ alors
            retourner selection $L_{1} k$
        fin
        sinon
            retourner selection $L_{2}\left(k-n_{1}\right)$
        fin
    fin
fin

Partie II - Recherche d'une clique de célébrités

II. 1 - Définitions et propriétés

Définition 1 (Graphe). On appelle graphe un couple

où

est un ensemble fini appelé ensemble des sommets et

est une partie de

, appelée ensemble des arêtes.

On pourra remarquer que, dans cette définition de graphe, les éléments de la forme (

) où

sont des arêtes possibles.

Définition 2 (Clique). Soit

un graphe. Soit

une partie de

. On dit que

est une clique si :

Définition 3 (Clique de célébrités, célébrité). Soient

un graphe et

une partie de

. On dit que

est une clique de célébrités si

est une clique et :

Un élément de l'ensemble

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 (

) représente le fait que

connaît

. Ainsi, une célébrité est connue de tous et elle connaît uniquement les autres célébrités.

Q10. Dans cette question, on pose

. 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.

avec .
avec

Q11. Soit

un graphe quelconque. Montrer que s'il existe une clique de célébrités non vide

dans

, alors celle-ci est unique.

Dans la suite, on note

l'unique clique de célébrités non vide du graphe

. Dans le cas où celle-ci n'existe pas,

désigne alors l'ensemble vide qui est noté

Q12. Soient

un graphe et

un sommet de

. On note

. Montrer les propositions suivantes :
a) Montrer que si

est égal à l'ensemble vide, alors

.
b) Montrer que si

, alors

.
c) On suppose que

n'est pas l'ensemble vide et on fixe

un élément de

.
i) Montrer que si (

) n'est pas un élément de

, alors

.
ii) Montrer que si (

) n'est pas un élément de

, alors

.
iii) Montrer que si (

) et (

) sont des éléments de

, alors

II. 2 - Algorithmique et programmation en Python (Informatique Commune)

Dans la suite, l'ensemble des sommets est de la forme

où

est un entier supérieur à 1 et un graphe

est représenté en Python par sa liste d'adjacence que l'on note

et qui est définie par:

Par exemple, si

, alors

.
On pourra remarquer que si l'ensemble des sommets d'un graphe

est égal à

, alors la longueur de la liste

est égale à

Q13. Écrire une fonction Python est_clique(

) prenant en argument une liste

qui est une liste d'adjacence d'un graphe

et une liste

sans répétition d'éléments de

et qui renvoie True si l'ensemble des éléments de

constitue une clique de

et False sinon.

Q14. On considère le graphe

ayant comme liste d'adjacence :

Décrire l'évolution de la variable

à 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

représentant un graphe et qui renvoie la liste

construite à l'aide de l'Algorithme 2 .

Q16. Montrer par récurrence sur le nombre de sommets que si

est un graphe où

est non vide, alors Clique_possible_C(G) est égale à

Algorithme 2 - Construction d'une clique de célébrités possibles
Clique_possible_C G :
début
    $C \leftarrow[]$
    $S \leftarrow[0,1, \ldots, n-1]$
    $/ * \mathrm{n}$ est le nombre de sommet de $G \quad * /$
    pour chaque $s$ élément de $S$ faire
        si $C$ est vide alors
            Ajouter s dans C
        fin
        sinon
            $c \leftarrow$ premier élément de $C$
            $t \leftarrow$ FAUX
            /* t permet de vérifier si on a effectué certaines instructions */
            si ( $s, c$ ) n'est pas une arête de $G$ alors
                $C \leftarrow[s]$
                $t \leftarrow$ VRAI
            fin
            si ( $c, s$ ) n'est pas une arête de $G$ alors
                $C \leftarrow C$
                $t \leftarrow$ VRAI
            fin
            si $t=F A U X$ alors
                Ajouter $s$ à la fin de liste $C$
            fin
        fin
    fin
fin
retourner $C$

Partie III - Étude d'une famille d'automates

Dans cette partie, l'alphabet

désigne l'ensemble

, le symbole

désigne le mot vide et on rappelle que

désigne l'ensemble des mots sur l'alphabet

Étant donné un mot

, on rappelle que

désigne la longueur du mot

et l'indexation des lettres de

commence par 0 . La première lettre de

est donc

La notation Card (

) désigne le cardinal d'un ensemble

.
Étant donnés un entier

et un entier non nul

, la notation

désigne le reste de la division euclidienne de

par

III. 1 - Définitions

Définition 4 (Automate déterministe). Un Automate déterministe est un quintuplet

avec :

un ensemble fini non vide appelé ensemble des états,
est un ensemble fini appelé alphabet,
une application appelée application de transition,
un élément de appelé état initial,
une partie de appelée ensemble des états finaux.

Définition 5 (Application de transition étendue aux mots). Soit

un automate déterministe.

On définit de manière récursive

par :

Définition 6 (Reconnaissance d'un mot par un automate). Soient

un mot sur un alphabet

. On dit que

est reconnu par l'automate

Définition 7 (Automate

, fonction indicatrice

). Soient

deux entiers vérifiant

. L'automate

est défini par :

,
,
,
.
On note la fonction indicatrice de l'ensemble des mots reconnus par . Soit autrement:

î

III. 2 - Exemples et propriétés élémentaires des

Q17. Soit

. Expliciter sans démonstration l'état

, la lecture du mot étant effectuée dans l'automate

. On pourra s'aider d'une représentation graphique de l'automate.

Dans les questions Q18 à Q22,

désignent des entiers tels que

.
Q18. Soit

. Expliciter l'état

, la lecture du mot étant effectuée dans l'automate

. 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

est égal à :

Dans la suite du problème, on admet ce résultat.
Q19. Soit

un mot reconnu par un automate

. Montrer que

est reconnu par au moins un autre automate parmi

avec

Définition 8 (Ou exclusif étendu aux mots binaires). On rappelle que le

exclusif qu'on note

est une opération définie sur

par :

Soient

deux éléments de

. On définit le Ou exclusif de

, noté

, le mot de longueur

défini par :

Q20. Soient

deux mots de

de même longueur. Montrer que :

Q21. Soit

un mot binaire vérifiant :

a) Montrer que

.
b) En déduire que pour tout mot

, on a :

Q22. Montrer que pour tout

, on a

.
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

peuvent être séparés par un automate de la forme

ayant

états.