Mines Option Informatique MP 2018Sujet, corrigé et rapport du jury

ÉCOLE DES PONTS PARISTECH, ISAE-SUPAERO, ENSTA PARISTECH, TELECOM PARISTECH, MINES PARISTECH, MINES SAINT-ÉTIENNE, MINES NANCY, IMT Atlantique, ENSAE PARISTECH.
Concours Centrale-Supélec (Cycle International), Concours Mines-Télécom, Concours Commun TPE/EIVP.

CONCOURS 2018

ÉPREUVE D'INFORMATIQUE MP

Durée de l'épreuve : 3 heures

INFORMATIQUE - MP

L'énoncé de cette épreuve comporte 8 pages de texte.

Préliminaire concernant la programmation

Définitions générales

1 Recherche naïve d'un motif

• 3
• 6
• 12
• 16

2 Automates finis déterministes à repli

• F ⊆ Q_A est un ensemble d'états, appelés finals.
• δ : Q_A × Σ → Q_A est une fonction partielle de transition (c'est-à-dire, une fonction dont le domaine de définition est un sous-ensemble de Q_A × Σ ); on impose que δ(0, α) soit défini pour tout α ∈ Σ.
• ρ : Q_A∖{0} → Q_A est une application (c'est-à-dire, une fonction totale), appelée fonction de repli, telle que pour tout q ∈ Q_A avec q ≠ 0, ρ(q) < q. On prolonge ρ en convenant ρ(0) = 0.
  Un AFDR est représenté en Caml par le type enregistrement suivant :

type afdr = {
    final : bool vect;
    transition : int vect vect;
    repli: int vect;
};;;
où :

• final est un tableau de taille k de booléens tel que si q ∈ Q_A, final. (q) contient true si et seulement si q ∈ F;
• transition est un tableau de taille k de tableaux de taille λ d'entiers, tel que si q ∈ Q_A et α_i ∈ Σ de code i, transition. (q). (i) contient -1 si δ(q, α_i) n'est pas défini, et contient δ(q, α_i) sinon;
• repli est un tableau de taille k d'entiers tel que repli. (0) contient 0 et repli. (q) pour q ∈ Q_A∖{0} contient ρ(q).
  On observe que le type afdr ne code pas explicitement la valeur de k, mais k est par exemple la longueur du tableau final.

A_1 peut être dessiné comme suit :

◻7 - Soit A = (k, F, δ, ρ) un AFDR. Pour tout q ∈ Q_A, on note ρ^j(q) pour j ∈ ℕ l'application répétée j fois de la fonction ρ à q, c'est-à-dire
Montrer que pour tout q ∈ Q_A, pour tout α ∈ Σ, il existe j ⩾ 0 tel que δ(ρ^j(q), α) est défini.
On dit qu'un AFDR A = (k, F, δ, ρ) accepte un mot u = u_1…u_p ∈ Σ^∗ s'il existe une suite finie q_0, q_1^′, q_1, q_2^′, q_2, …, q_(p − 1)^′, q_(p − 1), q_p^′, q_p d'états de A avec :

• q_0 = 0;
• pour tout 1 ⩽ i ⩽ p, q_i^′ = ρ^j(q_(i − 1)) avec j ⩾ 0 le plus petit entier tel que δ(ρ^j(q_(i − 1)), u_i) est défini ;
• pour tout 1 ⩽ i ⩽ p, q_i = δ(q_i^′, u_i);
• q_p ∈ F.

3 Automate de Knuth-Morris-Pratt

• F = {k}.
• Pour tout 1 ⩽ i ⩽ k, δ(i − 1, u_i) = i et, pour tout α ∈ Σ∖{u_1}, δ(0, α) = 0; aucune autre transition n'est définie.
• Pour tout 1 ⩽ i ⩽ k, ρ(i) est le plus grand entier 0 ⩽ j < i tel que u_1…u_j est un suffixe de u_1…u_i.
  On peut ainsi vérifier que l'automate A_1 de la question précédente est l'automate KMP associé à « aba »sur l'alphabet Σ = {a, b}.

4 Ensemble de motifs et automates à repli arborescents

On considère maintenant l'AFDR A_2 suivant, sur l'alphabet Σ = {a, b} :

◻21 - Donner (sans justification) une description concise du langage reconnu par l'AFDR A_2.
◻22 - On considère l'alphabet Σ = {a, b, c}. Construire (sans justification) un AFDR dont le langage reconnu est l'ensemble des mots dont un suffixe est « baa », « bab » ou « bc ». Indication : on cherchera un AFDR tel que si δ(q, α) est défini et q est non nul, alors δ(q, α) > q.

Fin de l'épreuve