CCINP Option Informatique MP 2023Sujet et rapport du jury

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

INFORMATIQUE

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.

Partie I - Programmation en OCaml : sélection du (k + 1)^e plus petit élément

1.1 - Fonctions utiles

• paquets_de_cinq [] est égal à [],
• paquets_de_cinq [2; 1; 2; 1; 3] est égal à [[2; 1; 2; 1; 3]],
• paquets_de_cinq [ 3; 4; 2; 1; 5; 6; 3 ] est égal à [ [3; 4; 2; 1; 5]; [6; 3] ].

medians : 'a list list -> 'a list

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

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

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

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

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

1. G_1 = (S, A_1) avec A_1 = {(1, 2), (1, 3), (1, 5), (2, 6)}.
2. G_2 = (S, A_2) avec

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

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

III. 1 - Définitions

• Q un ensemble fini non vide appelé ensemble des états,
• Σ est un ensemble fini appelé alphabet,
• δ : Q × Σ → Q une application appelée application de transition,
• q_0 un élément de Q appelé état initial,
• F une partie de Q appelée ensemble des états finaux.

• Σ = {0, 1},
  − ∀(c, e) ∈ Q, δ((c, e), 0) = ((c + 1)modp, e),
  − ∀(c, e,) ∈ Q, δ((c, e), 1) = {((c + 1), modp, 1 − e), si c = kmodp,; ((c + 1), modp, e), sinon.
• q_0 = (0, 0),
  − F = {0, 1, …, p − 1} × {1}.
  On note L_(k, p) la fonction indicatrice de l'ensemble des mots reconnus par A_(k, p). Soit autrement:

III. 2 - Exemples et propriétés élémentaires des A_(k, p)