CCINP Option Informatique MP 2018Sujet et corrigé

ÉPREUVE SPÉCIFIQUE - FILIÈRE MP

INFORMATIQUE

Les calculatrices sont interdites

Partie I - Logique et calcul des propositions

I. 1 - Première épreuve

• sur la boîte 1, il est écrit : "Une au moins des deux boîtes contient une clé verte" ;
• sur la boîte 2, il est écrit : "Il y a une clé rouge dans l'autre boîte".

I. 2 - Deuxième épreuve

• sur la boîte 1, il est écrit : "Il y a une clé rouge dans cette boîte, ou bien il y a une clé verte dans la boîte 2";
• sur la boîte 2, il est écrit : "Il y a une clé verte dans la boîte 1 ".

I. 3 - Troisième épreuve

• sur la boîte 1, il est écrit : "La boîte 3 est vide" ;
• sur la boîte 2, il est écrit : "La clé rouge est dans la boîte 1" ;
  — sur la boîte 3, il est écrit : "Cette boîte est vide".
  L'animateur affirme que l'inscription portée sur la boîte contenant la clé verte est vraie, celle portée par la boîte contenant la clé rouge est fausse. L'inscription affichée sur la boîte vide est aussi vraie.

Partie II - Automates

II. 1 - Définitions

• Q un ensemble d'états,
  − Σ un alphabet,
• q_0 l'état initial,
• F ⊆ Q un ensemble d'états finaux,
• δ : Q × Σ → Q une application de transition définie sur Q × Σ tout entier.

• ∀a ∈ Σ, ∀m ∈ Σ^∗, ∀q ∈ Q δ^∗(q, m.a) = δ(δ^∗(q, m), a).

• Q_L = {u^(− 1)L, u ∈ Σ^∗},
• q_(L_0) = Λ^(− 1)L = L,
• F_L = {u^(− 1)L, u ∈ L} = {q ∈ Q_L, Λ ∈ q},
  − ∀q ∈ Q_L, ∀a ∈ Σ δ_L(q, a) = a^(− 1)q.
  On admettra qu'un automate minimal définit bien un automate.
  Q14. Montrer que l'automate minimal d'un langage régulier L ⊆ Σ^∗ est un automate fini, c'est-à-dire un automate possédant un nombre fini d'états.

II. 2 - Construction de l'automate minimal

Algorithme 1: Algorithme de recherche des états équivalents
Entrée : un automate déterministe $A=\left(Q, \Sigma, q_{0}, F, \delta\right)$
Sortie : les ensembles d'états équivalents
$k \leftarrow 0$
************ Initialisation ************
$N_{0} \leftarrow \emptyset$
pour tous $p \in F$ et $q \in Q \backslash F$ faire
    ***La paire (p,q) est distinguée.***
    $N_{0} \leftarrow N_{0} \cup\{(p, q)\}$
tant que $N_{k} \neq \emptyset$ faire
    ****Construction de $N_{k+1}{ }^{* * * *}$
    $N_{k+1} \leftarrow \emptyset$
    pour chaque paire $(p, q) \in N_{k}$ faire
        pour chaque a $\in \Sigma$ faire
            pour chaque $(r, s) \in Q^{2}$ tel que $\delta(r, a)=p, \delta(s, a)=q$ faire
                si $(r, s) \notin \bigcup_{i=0}^{k} N_{i}$ alors
                    i
                    $N_{k+1} \leftarrow N_{k+1} \cup\{(r, s),(s, r)\}$
    $k \leftarrow k+1$

• les états sont des cercles, le nom de l'état est écrit à l'intérieur du cercle ;
• les transitions sont représentées par des flèches partant de l'état de départ et pointant sur l'état d'arrivée. Le symbole définissant la transition est indiqué au milieu de la flèche ;
• l'état initial est signalé par une flèche sans étiquette pointant sur cet état;
• les états finaux sont entourés d'un deuxième cercle, externe au premier.

Partie III - Algorithmique et programmation

III. 1 - Transformation de Burrows-Wheeler (BWT)

- Phase de codage -

- Phase de décodage -

III. 2 - Codage par plages RLE [Informatique pour tous]

－Phase de codage－

－Phase de décodage－

III． 3 －Codage de Huffman［Informatique pour tous］

Algorithme 2: Codage de Huffman
Entrée : $\mu$ un mot de taille $|\mu|$
Sortie : $\operatorname{Huffman}(\mu)$ le codage de Huffman de $\mu$
pour $a \in \Sigma$ faire
    si $|\mu|_{a}>0$ alors
        créer un noeud $\left(a,|\mu|_{a}\right)$
$\mathcal{L} \leftarrow$ liste des noeuds dans l'ordre croissant des poids
$\mathcal{A} \leftarrow$ liste vide
tant que $($ longueur $(\mathcal{L})+$ longueur $(\mathcal{A})>1)$ faire
    $(g, d) \leftarrow$ deux noeuds de plus faible poids parmi les 2 premiers noeuds de $\mathcal{L}$ et les 2 premiers
    noeuds de $\mathcal{A}$
    Créer un noeud $t$
    $n_{t} \leftarrow n_{g}+n_{d}$
    gauche $(t) \leftarrow g$
    Coder la branche de $t$ à $g$ par 0
    droite $(t) \leftarrow d$
    Coder la branche de $t$ à $d$ par 1
    Insérer $t$ à la fin de $\mathcal{A}$
    Retirer $g$ et $d$ de $\mathcal{L}$ ou de $\mathcal{A}$
$\underline{\operatorname{Huffman}}(\mu) \leftarrow \mathcal{A}$

FIN