J-0
00m
00j
00h
00min
00s

Version interactive avec LaTeX compilé

Télécharger PDF

X ENS Option Informatique MP 2019

Autour des sous-mots et des sur-mots

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Logo x-ens
🔗 Explorer
Banque
X-ENS
Année
2019
Filière
MP
Matière
Info
X-ENS MPX-ENS 2019MP InfoInfo 2019
2025_08_29_b66ebc423098428826b6g

CONCOURS D’ADMISSION 2019

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

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 tirées d'un alphabet fini . On utilisera pour dénoter les éléments de , c.-à-d. les mots sur . On note pour le mot vide et pour la longueur de , de sorte que .
Si un mot se décompose sous la forme , alors est un facteur de , et même un préfixe (ou un suffixe) si (ou si ) dans cette décomposition. Dans le cas d'un mot on écrit , sous la condition , pour désigner le facteur . Cette notation s'étend à et pour désigner, respectivement, et .
Ce que l'on appelle sous-mot de correspond à la notion classique de sous-suite, ou de suite extraite, et ne doit pas être confondu avec un facteur. Pour , on dira qu'un mot de longueur est un sous-mot de , ce que l'on notera , s'il existe une suite strictement croissante telle que . Par exemple, caml bechamel. Formellement, pour tout , nous noterons [ ] pour l'ensemble , de sorte que la suite peut être vue comme une application strictement croissante . Pour une telle application, on note pour dire que est le sous-mot extrait de via et on dit que est un plongement de dans , noté . Notons qu'il peut exister plusieurs façons différentes de plonger dans .
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 on entend le nombre d'opérations élémentaires (comparaison, addition, soustraction, multiplication, division, affectation, test, etc.) nécessaires à l'exécution de dans le cas le pire. Par complexité en espace d'un algorithme on entend l'espace mémoire minimal nécessaire à l'exécution de dans le cas le pire. Lorsque la complexité en temps ou en espace dépend d'un ou plusieurs paramètres , on dit que a une complexité en s'il existe une constante telle que, pour toutes les valeurs de suffisamment grandes (c'est-à-dire plus grandes qu'un certain seuil), pour toute instance du problème de paramètres , la complexité est au plus .
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 val construit une matrice de lignes et 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 et et deux lettres et , on a l'équivalence suivante :
b. Programmez une fonction OCaml teste_sous_mot : string -> string -> bool décidant en temps polynomial si un mot est sous-mot d'un mot . Détaillez et justifiez votre analyse de complexité.

I. Compter et construire

On note le nombre de plongements de dans , de sorte que si et seulement si . Notons en particulier que pour tout mot car il n'existe qu'une injection de , c.-à-d. , dans et cette injection est bien un plongement.
Question 2. a. Montrez que .
b. Que vaut quand est une lettre?
On rappelle que est le mot constitué de occurrences de la lettre .
c. Montrez que pour tous mots et toute lettre .
Question 3. Pour calculer 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 le nombre de fois où la fonction aux est appelée lors du calcul de nb_plongements .
Question 4. a. Montrez qu'il existe une constante telle que .
b. Montrez que l'on ne peut pas majorer par une fonction polynomiale de .
c. Montrez qu'il existe une constante telle que .
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 de ses arguments. De meilleurs algorithmes existent...
Question 5. Programmez en OCaml une nouvelle fonction nb_plongements_rapide : string -> string -> int qui calcule en temps polynomial en . 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 . On note pour . Il s'agit d'un langage fini. Par exemple de sorte que abab a 12 sous-mots distincts, ce que l'on note .
Les langages étant des ensembles (des parties de ), on utilisera les notations , , etc. avec leur signification ensembliste habituelle. On utilise aussi la notation pour désigner le produit de concaténation de deux langages : . Dans le cas d'un singleton , on écrit souvent au lieu de .
Question 6. a. Montrez que, pour tous mots et toute lettre , on a
b. Montrer que l'union est disjointe si et seulement si le mot ne contient pas la lettre .
Quand l'union est disjointe dans l'équation , on peut obtenir , pour wava, en combinant et . Cette approche se généralise au cas d'un mot quelconque.
Question 7. a. Donnez des équations récursives permettant de calculer en se ramenant à des préfixes de . On pourra considérer par exemple les diverses occurrences de la dernière lettre de quand elle existe.
b. En se basant sur vos équations, programmez une fonction OCaml nb_sousmots : string -> int qui, pour un mot donné, calcule en temps polynomial en . Justifiez votre analyse de complexité.
Un sur-mot commun à et est un mot tel que et . Il existe une infinité de tels mots. Parmi tous ces sur-mots communs à et , 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 et par exemple pcsmc(informatique, difficile) difnficormatilque.
Question 8. a. Soient deux lettres distinctes. Montrez que si pcsmc alors , ceci pour tous mots .
b. Généralisez la propriété précédente en donnant des équations qui permettent de caractériser pcsmc dans le cas général, y compris quand .
c. Programmez une fonction OCaml calculant pcsmc en temps polynomial en pour des mots et 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 , ainsi que les lettres , que l'on peut combiner au moyen des opérateurs binaires et (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 est défini inductivement par et enfin
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 et 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 , est le nombre de constructeurs apparaissant dans l'expression. On pourrait calculer 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 et 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 et , 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 et une lettre , si contient un mot commençant par .
Pour un langage , on définit . On s'intéresse maintenant à la question de savoir, pour un mot et une expression rationnelle , si est dans , c.-à-d. si est sous-mot d'un des mots définis par . Une solution possible passe par des calculs de résidus de langages. Formellement, pour un langage et un mot , on définit le résidu de par comme
Ainsi, est sous-mot d'un mot de si et seulement si . Notons d'ailleurs que ssi .
Question 11. Pour chacune des égalités suivantes, dites lesquelles sont valides pour tous mots et , lettre , et langages . Justifiez vos réponses négatives par un contre-exemple.
(1) ,
(2) ,
(3) ,
(4) .
Question 12. a. Programmez une fonction OCaml eps_residu_ratexp : ratexp -> ratexp qui à partir d'une expression rationnelle construit une expression rationnelle telle que .
b. Donnez (et justifiez) un majorant, en fonction de , de la taille de l'expression construite par votre programme.
Question 13. a. Programmez une fonction OCaml char_residu_ratexp : char -> ratexp -> ratexp qui, à partir de et , construit une expression telle que . b. Donnez (et justifiez) un majorant, en fonction de , de la taille de l'expression construite par votre programme.
Question 14. a. Programmez une fonction OCaml sousmot_de_ratexp : string -> ratexp -> bool décidant si pour un mot et une expression rationnelle .
Indication : on pourra utiliser la fonction char_residu_ratexp.
b. Votre programme s'exécute-t-il en temps polynomial en ? Justifiez brièvement votre réponse.
On développe maintenant une autre approche pour décider si . Pour un mot et un langage , on définit comme étant l'ensemble des couples ( ) tels que et . Quand on dit que « couvre le facteur de . On écrit aussi au lieu de quand est une expression rationnelle.
Pour représenter un ensemble de couples tel que , on utilisera une matrice booléenne de dimension telle que true ssi . Notons qu'en particulier false pour .
Question 15. Programmez une fonction facteurs_couverts : string -> ratexp -> bool array array qui, pour un mot et une expression , calcule . 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 à partir des matrices associées aux sous-expressions de .
Question 16. En utilisant la fonction facteurs_couverts, programmez une nouvelle version de la fonction sousmot_de_ratexp décidant si pour un mot et une expression rationnelle (cf. question 14). Indiquez la complexité de la nouvelle version.
X ENS Option Informatique MP 2019 - Version Web LaTeX | WikiPrépa | WikiPrépa