CCINP Option Informatique MP 2021Sujet, corrigé 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 - Étude des partitions non croisées

1. ∀P ∈ P, P ≠ ∅;
2. ∀(P, Q) ∈ P^2, (P ≠ Q) ⟹ (P ∩ Q = ∅);
3. ⋃_(P ∈ P)P = A.

Figure 1 - Représentations picturales de P, Q, R

I. 1 - Exemples et fonctions élémentaires (Informatique Pour Tous)

1. P_1 = {{1, 3}, {2, 4, 5}},
2. P_2 = {{1, 3}, {1, 2}, {4, 5}},
3. P_3 = {{1, 3}{2, 4}},
4. P_4 = {{1, 4, 5}, {2, 3}}.

def mystere(P) :
    L = [False for _ in range(len(A))]
    for i in range(len(P)) :
        if P[i] == [] :
            return False
        else :
            for j in range(len(P[i])) :
                if P[i][j] not in A :
                    return False
                else :
                    # A.index(a) renvoie l'indice de a dans A
                    k = A.index(P[i][j])
                    if L[k] :
                        return False
                    else:
                        L[k] = True
    return not (False in L)

1. mystere([[1,3],[1,5],[2,4]]) 2. mystere([[1,3,4],[2]])
3. mystere([[1,3,5],[2,4]]) 4. mystere([[],[1,2,3,4,5]]).

def est_nc(P) :
    # On rappelle que A est une liste triée dans l'ordre croissant
    N = len(A)
    for i in range(N) :
        for j in range ( }\textrm{i}+1,\textrm{N}\mathrm{ ) :
            for k in range( j + 1,N) :
                for l in range ( }\textrm{k}+1,\textrm{N}\mathrm{ ) :

I. 2 - Nombre de partitions non croisées

Figure 2 - Représentations picturale de S

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

• 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 ∧ Q), (P ∨ Q) sont des formules propositionnelles.

• si P ∈ { V, F}, alors [P]_I = P;
• si P ∈ {x_1, x_2, …, x_n}, alors [P]_I = I(P);
• si P = ¬Q où Q est une formule propositionnelle, alors [P]_I = ¬[Q]_I;
• si P = A ∘ B où A, B sont des formules propositionnelles et ∘ ∈ { ∧, ∨ }, alors [P]_I = [A]_I ∘ [B]_I.

1. P_1 = (x ∨ y) ∧ (¬x ∨ ¬y) ∧ (x ∨ ¬y),
2. P_2 = (x) ∧ (¬x ∨ ¬y) ∧ (¬y ∨ z) ∧ (z),
3. P_3 = (),
4. P_4 = (x ∨ ¬y ∨ ¬t) ∧ (z ∨ ¬t ∨ ¬x ∨ ¬y).

1. supprimer de P toutes les clauses où x apparaît;
2. enlever toutes les occurrences du littéral ¬x.

Partie III - Étude des classes sylvestres

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

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

• l'arbre vide;
• un triplet ( T_g, r, T_d ) où r est un élément de Σ, T_g et T_d des ABR. De plus, toute valeur apparaissant dans T_g est strictement inférieure à r et toute valeur apparaissant dans T_d est supérieure ou égale à r.

• si T = ∘, alors T ← a = (∘, a, ∘);
• si T = (T_g, r, T_d) et r ≤ a, alors T ← a = (T_g, r, T_d ← a);
• si T = (T_g, r, T_d) et r > a, alors T ← a = (T_g ← a, r, T_d).

• si w = ε, alors T ← w = T;
• si w = av avec a ∈ Σ, alors T ← w = (T ← a) ← v.

Figure 3 - Représentation de T

type 'a arbre = Vide | Noeud of ('a arbre) * 'a * ('a arbre).

Noeud(Vide, 'a', Noeud(Vide, 'b', Vide)).

insertion_lettre : char -> char arbre -> char arbre

insertion_mot : char list -> char arbre -> char arbre

• si T = ∘, alors w_T = ε;
• si T = (T_g, r, T_d), alors w_T = rw_g w_d où w_g et w_d sont les lectures préfixes respectives de T_g et de T_d.

Figure 4 - Représentation de T de Q22

prefixe : char arbre -> char list

III. 2 - Une relation d'équivalence sur les mots

III. 3 - Construction de classes sylvestres

Définition 21 (Mélange)

• si v = ε, alors u⊔v = {u};
• si u = ε, alors u⊔v = {v};
• si u = au^′ et v = bv^′ où a et b sont des lettres, u^′ et v^′ des mots, alors :