X ENS Option Informatique MP 2019Sujet, corrigé et rapport du jury

Autour des sous-mots et des sur-mots

5,0(1 vote)

Faisable en Sup

Programmation dynamique
Analyse de complexité
Preuves par récurrence et invariants
Langages rationnels et expressions régulières
Programmation en OCaml

Explorer les annales

BanqueX-ENS Année2019 FilièreMP MatièreInformatique

Annales X-ENS MP Informatique X-ENS MP 2019 MP Informatique Informatique 2019

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Rapport du jury Lire en ligne LaTeX Word

Présentation du sujet

Difficile

Sous-mots et sur-mots : algorithmique des sous-suites et des expressions rationnelles

L'épreuve explore des algorithmes sur la notion de sous-mot (sous-suite extraite) d'un mot fini. Une première partie porte sur le dénombrement des sous-mots et le calcul du plus petit sur-mot commun à deux mots, avec passage d'algorithmes exponentiels à des algorithmes polynomiaux par programmation dynamique. Une seconde partie étend le problème aux langages rationnels décrits par des expressions régulières, via un calcul de résidus.

1Préliminaires : décider si un mot est sous-mot d'un autreDémonstration d'une propriété récursive et programme polynomial de test de sous-mot.
2I. Compter et construireDénombrement du nombre de plongements, du cardinal des sous-mots et calcul du plus petit sur-mot commun, par programmation dynamique.
3II. Sous-mots et expressions rationnellesTest d'appartenance d'un mot aux sous-mots du langage d'une expression rationnelle, par calcul de résidus puis par matrice des facteurs couverts.

Difficile. La moyenne s'établit à 9,55/20 sur 1112 copies et le rapport note que très peu de candidats sont parvenus à la dernière question, aucun n'ayant traité correctement l'intégralité du sujet.

L'épreuve en chiffres

Moyenne 9,55 / 20 · écart-type 3,3 · 1 112 copies · où vous situez-vous ?

Moyenne: 9,55/ 20
Écart-type: 3,3
Copies: 1 112

Deux tiers des copies environ (moyenne ± écart-type)

Où je me situe ?

Votre note sur 20 à ce sujet, en conditions de concours.

Source : rapport du jury. Notes publiées par le concours (après harmonisation le cas échéant). Courbe : estimation par une loi normale.

Ce qu'a observé le jury

5 erreurs relevées

Preuves de récurrence peu rigoureuses · Erreurs de bord classiques dans les programmes · Complexités affirmées sans justification

L'épreuve, centrée sur l'algorithmique des sous-mots puis leur lien avec les expressions rationnelles, a été peu traitée au-delà de la question 11. Les preuves de récurrence manquent souvent de rigueur et de nombreux programmes comportent des erreurs de bord classiques.

Les erreurs les plus sanctionnées

1
Preuves de récurrence peu rigoureusesQ3
Beaucoup de copies se contentent de paraphraser un algorithme en français au lieu de formuler une hypothèse de récurrence ou un invariant de boucle précis.
2
Erreurs de bord classiques dans les programmes
Une majorité de programmes présente des problèmes de bord : tableaux trop petits d'une unité, accès hors bornes ou boucles s'arrêtant un cran trop tôt.
« d'un tableau de taille n ensuite parcouru avec un indice allant de 0 »
3
Complexités affirmées sans justification
L'énoncé demandait de justifier les complexités en temps des algorithmes, mais beaucoup de candidats se contentent d'affirmer un résultat sans le démontrer.
4
Cas du langage vide oubliéQ10, Q11, Q12
Dans la partie sur les expressions rationnelles, le cas particulier d'un sous-langage vide est très souvent ignoré, ce qui met en défaut plusieurs égalités demandées.
5
Sujet peu terminéQ14, Q15, Q16
Très peu de candidats sont parvenus jusqu'à la dernière question et personne n'a traité l'ensemble du sujet correctement.
« aucun n'a su traiter toutes les questions correctement »

Ce qui a été bien réussi

La question 1b (programme de test de sous-mot) a été plutôt bien traitée, avec peu de candidats proposant un code exponentiel.
Les questions 2 et 6, portant sur des propriétés de dénombrement, ont été plutôt bien traitées.

Conseils du jury

Rédiger des preuves rigoureuses avec une hypothèse de récurrence ou un invariant de boucle clairement identifié.
Toujours justifier les complexités annoncées plutôt que de les affirmer.
Découper un programme long en fonctions nommées explicitement plutôt qu'en aux, aux2, aux3.
Soigner l'indentation du code et l'usage de couleurs, appréciés des correcteurs.
Vérifier systématiquement les cas limites : mot vide, tableaux de taille nulle, bornes d'indices.

Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

CONCOURS D’ADMISSION 2019

VENDREDI 19 AVRIL 2019-14h00-18h00 FILIERE MP (Spécialité Informatique) Epreuve $n^\circ4$

INFORMATIQUE A (XULCR)

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation sera obligatoirement OCaml.

Autour des sous-mots et des sur-mots

Préliminaires

Un mot est une suite de lettres

a_0\dotsa_(n - 1)

tirées d'un alphabet fini

A = {a, b, \dots}

. On utilisera

u, v, u^', u^(''), u_1, u_2, \dots

pour dénoter les éléments de

A^*

, c.-à-d. les mots sur

A

. On note

ε

pour le mot vide et

|u|

pour la longueur de

u

, de sorte que

|ε| = 0

Si un mot

u

se décompose sous la forme

u = u_1 vu_2

, alors

v

est un facteur de

u

, et même un préfixe (ou un suffixe) si

u_1 = ε

(ou si

u_2 = ε

) dans cette décomposition. Dans le cas d'un mot

u = a_0\dotsa_(n - 1)

on écrit

⟨u[i, j[≫

, sous la condition

0 \leq i \leq j \leq n

, pour désigner le facteur

a_i\dotsa_(j - 1)

. Cette notation s'étend à

u[i\dots[

u[i]

pour désigner, respectivement,

u[i, n[

u[i, i + 1[

Ce que l'on appelle sous-mot de

u

correspond à la notion classique de sous-suite, ou de suite extraite, et ne doit pas être confondu avec un facteur. Pour

u = a_0\dotsa_(n - 1)

, on dira qu'un mot

v

de longueur

m

est un sous-mot de

u

, ce que l'on notera

v≼u

, s'il existe une suite strictement croissante

0 \leq p_0 < p_1 < \dots < p_(m - 1) < n

telle que

v = a_(p_0)a_(p_1)\dotsa_(p_(m - 1))

. Par exemple, caml

≼

bechamel. Formellement, pour tout

n \in ℕ

, nous noterons [

n

] pour l'ensemble

{0, 1, 2, \dots, n - 1}

, de sorte que la suite

p_0, p_1, \dots, p_(m - 1)

peut être vue comme une application strictement croissante

p : [m] \to [n]

. Pour une telle application, on note

v = u \circ p

pour dire que

v

est le sous-mot extrait de

u

via

p

et on dit que

p

est un plongement de

v

dans

u

, noté

p : v≼u

. Notons qu'il peut exister plusieurs façons différentes de plonger

v

dans

u

Notre objectif ici est de développer des algorithmes impliquant à divers titres la notion de sous-mot : recherche d'un sous-mot à l'intérieur d'un texte, dénombrement des sous-mots, raisonnement sur l'ensemble des sous-mots d'un texte ou d'un langage.

Complexité. Par complexité en temps d'un algorithme

A

on entend le nombre d'opérations élémentaires (comparaison, addition, soustraction, multiplication, division, affectation, test, etc.) nécessaires à l'exécution de

A

dans le cas le pire. Par complexité en espace d'un algorithme

A

on entend l'espace mémoire minimal nécessaire à l'exécution de

A

dans le cas le pire. Lorsque la complexité en temps ou en espace dépend d'un ou plusieurs paramètres

κ_0, \dots, κ_(r - 1)

, on dit que

A

a une complexité en

O(f(κ_0, \dots, κ_(r - 1)))

s'il existe une constante

C > 0

telle que, pour toutes les valeurs de

κ_0, \dots, κ_(r - 1)

suffisamment grandes (c'est-à-dire plus grandes qu'un certain seuil), pour toute instance du problème de paramètres

κ_0, \dots, κ_(r - 1)

, la complexité est au plus

Cf(κ_0, \dots, κ_(r - 1))

OCaml. On rappelle quelques éléments du langage OCaml qui peuvent être utiles. Une chaîne de caractères s a le type string, sa longueur est obtenue avec String.length s et son i-ième caractère avec s . [i], les caractères étant indexés à partir de 0 . Un tableau t a le type

τ

array, où

τ

est le type des éléments, et sa longueur est obtenue avec Array.length t . Son i-ième élément est obtenu avec t . (i) et modifié avec t . (i) <- val, les éléments étant indexés à partir de 0 . L'expression Array.make n val construit un tableau de taille n dont les éléments sont initialisés avec la valeur val. En OCaml, une matrice est un tableau de tableaux de même taille. L'expression Array.make_matrix

nm

val construit une matrice de

n

lignes et

m

colonnes, dont les éléments sont tous initialisés avec la valeur val. Le candidat est libre d'utiliser tout autre élément du langage OCaml et de sa bibliothèque standard.

Question 1. a. Montrez que pour deux mots

u

u^'

et deux lettres

a

a^'

, on a l'équivalence suivante :

ua≼u^' a^' ⟺ ua≼u^' ou (a = a^' et u≼u^').

b. Programmez une fonction OCaml teste_sous_mot : string -> string -> bool décidant en temps polynomial si un mot

v

est sous-mot d'un mot

u

. Détaillez et justifiez votre analyse de complexité.

I. Compter et construire

On note

(u/v)

le nombre de plongements de

v

dans

u

, de sorte que

v≼u

si et seulement si

(u/v) > 0

. Notons en particulier que

(u/ε) = 1

pour tout mot

u \in A^*

car il n'existe qu'une injection de

[0]

, c.-à-d.

\emptyset

, dans

{0, 1, \dots, |u| - 1}

et cette injection est bien un plongement.

Question 2. a. Montrez que

((abab)/(ab)) = 3

.
b. Que vaut

((a^n)/(a^m))

quand

a \in A

est une lettre?

On rappelle que

a^n

est le mot constitué de

n

occurrences de la lettre

a

.
c. Montrez que

((ua)/(va)) = (u/(va)) + (u/v)

pour tous mots

u, v \in A^*

et toute lettre

a \in A

Question 3. Pour calculer

(u/v)

on considère la fonction OCaml suivante.

let nb_plongements (v:string) (u:string) =
    let rec aux i j =
        if i = 0 then 1
        else if j = 0 then 0
        else if v.[i-1] = u.[j-1] then (aux (i - 1) (j - 1)) + (aux i (j - 1))
        else aux i (j - 1)
    in
    aux (String.length v) (String.length u)
a. Prouvez sa terminaison.
b. Justifiez sa correction, c.-à-d., expliquez pourquoi elle renvoie bien la valeur (\begin{array}{l}{u}\\{v}\end{array}).

On note

T(v, u)

le nombre de fois où la fonction aux est appelée lors du calcul de nb_plongements

vu

Question 4. a. Montrez qu'il existe une constante

C_1

telle que

T(v, u) < 2^(|u|) \cdot C_1

.
b. Montrez que l'on ne peut pas majorer

T(v, u)

par une fonction polynomiale de

(u/v)

.
c. Montrez qu'il existe une constante

C_2

telle que

T(v, u) \geq 2(u/v) + C_2

La question précédente a montré que la fonction nb_plongements proposée dans le sujet demande un temps de calcul parfois exponentiel en la taille

|u| + |v|

de ses arguments. De meilleurs algorithmes existent...

Question 5. Programmez en OCaml une nouvelle fonction nb_plongements_rapide : string -> string -> int qui calcule

(u/v)

en temps polynomial en

|u| + |v|

. Détaillez votre analyse de complexité en temps et en espace.
Indication : on pourra utiliser la programmation dynamique.
On cherche maintenant à dénombrer les sous-mots d'un mot

u

. On note

↓u

pour

{v|v≼u}

. Il s'agit d'un langage fini. Par exemple

↓abab = {ε, a, b, ab, aa, ba, bb, aab, aba, abb, bab, abab}

de sorte que abab a 12 sous-mots distincts, ce que l'on note

Card(↓abab) = 12

Les langages étant des ensembles (des parties

L, L^', \dots

A^*

), on utilisera les notations

L \cup L^'

L∖L^'

, etc. avec leur signification ensembliste habituelle. On utilise aussi la notation

L \cdot L^'

pour désigner le produit de concaténation de deux langages :

L ⋅ L^′ = {uv|u ∈ L, v ∈ L^′}

. Dans le cas d'un singleton

L = {u}

, on écrit souvent

u \cdot L^'

au lieu de

{u} ⋅ L^′

Question 6. a. Montrez que, pour tous mots

v, w

et toute lettre

a

, on a

↓wava=↓wav \cup (↓wav∖↓w) \cdot a.

b. Montrer que l'union

↓wav \cup (↓wav∖↓w) \cdot a

est disjointe si et seulement si le mot

v

ne contient pas la lettre

a

Quand l'union est disjointe dans l'équation

(‡)

, on peut obtenir

Card(↓u)

, pour

u =

wava, en combinant

Card(↓wav)

Card(↓w)

. Cette approche se généralise au cas d'un mot

u

quelconque.

Question 7. a. Donnez des équations récursives permettant de calculer

Card(↓u)

en se ramenant à des préfixes de

u

. On pourra considérer par exemple les diverses occurrences de la dernière lettre de

u

quand elle existe.
b. En se basant sur vos équations, programmez une fonction OCaml nb_sousmots : string -> int qui, pour un mot

u

donné, calcule

Card(↓u)

en temps polynomial en

|u|

. Justifiez votre analyse de complexité.

Un sur-mot commun à

u

v

est un mot

w

tel que

u≼w

v≼w

. Il existe une infinité de tels mots. Parmi tous ces sur-mots communs à

u

v

, on s'intéresse à celui qui est le plus court, et qui est le premier dans l'ordre lexicographique pour départager les sur-mots communs de même longueur. Ce mot est noté pcsmc

(u, v)

et par exemple pcsmc(informatique, difficile)

=

difnficormatilque.

Question 8. a. Soient

a, b

deux lettres distinctes. Montrez que si pcsmc

(ua, vb) = wa

alors

w = pcsmc(u, vb)

, ceci pour tous mots

u, v, w

.
b. Généralisez la propriété précédente en donnant des équations qui permettent de caractériser pcsmc

(ua, vb)

dans le cas général, y compris quand

a = b

.
c. Programmez une fonction OCaml calculant pcsmc

(u, v)

en temps polynomial en

|u| + |v|

pour des mots

u

v

arbitraires. Détaillez votre analyse de complexité.

II. Sous-mots et expressions rationnelles

On rappelle que les expressions rationnelles sont écrites à partir des expressions de base

⟨ε⟩⟩, ⟨\emptyset⟩

, ainsi que les lettres

⟨a⟩⟩, ⟨b⟩⟩, \dots

, que l'on peut combiner au moyen des opérateurs binaires

≪ + >

< \cdot ≫

(désignant l'union et la concaténation de langages) ainsi que de l'«étoile de Kleene », un opérateur unaire « * » noté en exposant.

Le langage représenté par une expression rationnelle

e

est défini inductivement par

L(ε) = {ε}, L(∅) = ∅, L(a) = {a}, …, L(e + e^′) = L(e) ∪ L(e^′), L(e ⋅ e^′) = L(e) ⋅ L(e^′)

et enfin

L(e^∗) = L(e)^∗ = {ε} ∪ L(e) ∪ L(e) ⋅ L(e) ∪ ⋯ = ⋃_(i ∈ ℕ)L(e) ⋅ L(e)⋯L(e)^()^i.

Pour manipuler des expressions rationnelles, on utilisera la définition OCaml suivante :

type ratexp =
    | Epsilon
    | Empty
    | Letter of char
    | Sum of ratexp * ratexp
    | Product of ratexp * ratexp
    | Star of ratexp

Par exemple, les expressions rationnelles

a \cdot (b + c)^*

((\emptyset + ε)^*)^*

seront représentées par

let e_exmp1 = Product (Letter 'a', Star (Sum (Letter 'b', Letter 'c')))
let e_exmp2 = Star (Star (Sum (Empty, Epsilon)))

La taille d'une expression rationnelle, notée

|e|

, est le nombre de constructeurs apparaissant dans l'expression. On pourrait calculer

|e|

en OCaml au moyen du code suivant :

let rec taille_ratexp (e : ratexp) =
    match e with
    | Empty -> 1 | Epsilon -> 1 | Letter _ -> 1
    | Sum (e1,e2) -> 1 + taille_ratexp(e1) + taille_ratexp(e2)
    | Product (e1,e2) -> 1 + taille_ratexp(e1) + taille_ratexp(e2)
    | Star (e1) -> 1 + taille_ratexp(e1)

Question 9. On définit les expressions rationnelles

e_1

e_2

par

let e1 = Product (Star (Product (Sum (Letter 'a', Empty), Letter 'c')),
    Product (Letter 'b',
        Product (Empty,
            Star (Product (Letter 'c', Letter 'c')))))
let e2 = Product (Star(Product(Letter 'b', Letter 'a')),
    Product (Sum (Epsilon, Letter 'a'), Star(Letter 'c')))

Pour chacun des langages

L(e_1)

L(e_2)

, dites s'il contient un mot commençant par a; par b; par c.

Question 10. Programmez une fonction OCaml peut_debuter_par : ratexp -> char -> bool testant, pour une expression rationnelle

e

et une lettre

a

, si

L(e)

contient un mot commençant par

a

Pour un langage

L

, on définit

↓L = ⋃_(w \in L)↓w

. On s'intéresse maintenant à la question de savoir, pour un mot

u

et une expression rationnelle

e

, si

u

est dans

↓L(e)

, c.-à-d. si

u

est sous-mot d'un des mots définis par

e

. Une solution possible passe par des calculs de résidus de langages. Formellement, pour un langage

L \subseteq A^*

et un mot

u \in A^*

, on définit le résidu de

L

par

u

comme

⟨u⟩L = {v ∈ A^∗|∃w tel que u≼w et wv ∈ L}.

Ainsi,

u

est sous-mot d'un mot de

L

si et seulement si

ε \in ⟨u⟩L

. Notons d'ailleurs que

ε \in ⟨u⟩L

ssi

⟨u⟩L \neq \emptyset

Question 11. Pour chacune des égalités suivantes, dites lesquelles sont valides pour tous mots

u

v

, lettre

a

, et langages

L, L_1, L_2

. Justifiez vos réponses négatives par un contre-exemple.
(1)

⟨ε⟩L = L

,
(2)

⟨a⟩(L_1 \cdot L_2) = (⟨a⟩L_1) \cdot L_2 \cup ⟨a⟩L_2

,
(3)

⟨uv⟩L = ⟨u⟩(⟨v⟩L)

,
(4)

⟨u⟩(L^*) = (⟨u⟩L) \cdot L^*

Question 12. a. Programmez une fonction OCaml eps_residu_ratexp : ratexp -> ratexp qui à partir d'une expression rationnelle

e

construit une expression rationnelle

e^'

telle que

L(e^') = ⟨ε⟩L(e)

.
b. Donnez (et justifiez) un majorant, en fonction de

|e|

, de la taille

|e^'|

de l'expression construite par votre programme.

Question 13. a. Programmez une fonction OCaml char_residu_ratexp : char -> ratexp -> ratexp qui, à partir de

a \in A

e

, construit une expression

e^('')

telle que

L(e^('')) = ⟨a⟩L(e)

. b. Donnez (et justifiez) un majorant, en fonction de

|e|

, de la taille

|e^('')|

de l'expression construite par votre programme.

Question 14. a. Programmez une fonction OCaml sousmot_de_ratexp : string -> ratexp -> bool décidant si

u\in↓L(e)

pour un mot

u

et une expression rationnelle

e

.
Indication : on pourra utiliser la fonction char_residu_ratexp.
b. Votre programme s'exécute-t-il en temps polynomial en

|u| + |e|

? Justifiez brièvement votre réponse.

On développe maintenant une autre approche pour décider si

u\in↓L(e)

. Pour un mot

u = a_0 a_1\dotsa_(n - 1)

et un langage

L \subseteq A^*

, on définit

FC(u, L)

comme étant l'ensemble des couples (

i, j

) tels que

0 \leq i \leq j \leq |u|

u[i, j[\in↓L

. Quand

(i, j) \in FC(u, L)

on dit que

« «L

couvre le facteur

[i, j[

u≫

. On écrit aussi

FC(u, e)

au lieu de

FC(u, L(e))

quand

e

est une expression rationnelle.

Pour représenter un ensemble de couples tel que

FC(u, e)

, on utilisera une matrice booléenne

M

de dimension

(n + 1) \times (n + 1)

telle que

M[i, j] =

true ssi

(i, j) \in FC(u, e)

. Notons qu'en particulier

M[i, j] =

false pour

j < i

Question 15. Programmez une fonction facteurs_couverts : string -> ratexp -> bool array array qui, pour un mot

u

et une expression

e

, calcule

FC(u, e)

. Indiquez et justifiez brièvement la complexité de votre fonction.
Pour ce code, il est suggéré de construire la matrice associée à une expression complexe

e

à partir des matrices associées aux sous-expressions de

e

Question 16. En utilisant la fonction facteurs_couverts, programmez une nouvelle version de la fonction sousmot_de_ratexp décidant si

u\in↓L(e)

pour un mot

u

et une expression rationnelle

e

(cf. question 14). Indiquez la complexité de la nouvelle version.

Questions fréquentes

4 questions

Sur quels chapitres porte l'épreuve Informatique A X-ENS MP option info 2019 ?

Le sujet porte sur les algorithmes de dénombrement de sous-mots, la programmation dynamique et le lien entre sous-mots et langages rationnels.

Quelle est la moyenne à l'épreuve Informatique A X-ENS MP 2019 ?

La moyenne est de 9,55/20 sur 1112 copies, avec un écart-type de 3,3.

Quelles erreurs le jury a-t-il le plus relevées sur ce sujet ?

Des preuves de récurrence trop informelles, des complexités affirmées sans justification et des erreurs de bord classiques dans les programmes.

Le sujet Informatique A X-ENS MP 2019 est-il faisable en entier ?

Non, le rapport indique que très peu de candidats sont parvenus à la dernière question et qu'aucun n'a traité l'ensemble du sujet correctement.

Pas de description pour le moment

Commentaires• X ENS Option Informatique MP 2019

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...

Explorer les annales

Téléchargements

Présentation du sujet

L'épreuve en chiffres

Ce qu'a observé le jury

Les erreurs les plus sanctionnées

Ce qui a été bien réussi

Conseils du jury

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

CONCOURS D’ADMISSION 2019

VENDREDI 19 AVRIL 2019-14h00-18h00 FILIERE MP (Spécialité Informatique) Epreuve n^∘4

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve. Le langage de programmation sera obligatoirement OCaml.

Autour des sous-mots et des sur-mots

Préliminaires

I. Compter et construire

II. Sous-mots et expressions rationnelles

Questions fréquentes

Sur quels chapitres porte l'épreuve Informatique A X-ENS MP option info 2019 ?

Quelle est la moyenne à l'épreuve Informatique A X-ENS MP 2019 ?

Quelles erreurs le jury a-t-il le plus relevées sur ce sujet ?

Le sujet Informatique A X-ENS MP 2019 est-il faisable en entier ?

Commentaires• X ENS Option Informatique MP 2019

Commentaires• X ENS Option Informatique MP 2019

VENDREDI 19 AVRIL 2019-14h00-18h00 FILIERE MP (Spécialité Informatique) Epreuve $n^\circ4$

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation sera obligatoirement OCaml.