X/ENS Informatique A MP 2019

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                    

Extrait du corrigé obtenu par reconnaissance optique des caractères



X/ENS Informatique A MP 2019 -- Corrigé
Ce corrigé est proposé par Benjamin Monmege (enseignant-chercheur à 
l'université) ; il a été relu par William Aufort (professeur en CPGE).

Ce sujet de théorie des langages s'intéresse aux notions de sous-mot et de 
surmot. Un sous-mot correspond à la notion classique de suite extraite : par 
exemple,
bar est un sous-mot d'abracadabra. L'objectif est de développer des 
algorithmes, en
particulier de programmation dynamique, pour rechercher un sous-mot à 
l'intérieur
d'un texte, pour dénombrer les sous-mots ou encore décider si un mot est 
sous-mot
de l'un des mots d'un langage rationnel. Après une question préliminaire 
permettant
de tester si un mot est un sous-mot d'un texte, l'énoncé est découpé en deux 
parties.
· Dans une première partie, on compte tout d'abord le nombre de façon de plonger
un mot u dans un mot v dont u est un sous-mot : on dit que v est un sur-mot
de u dans ce cas. Il existe par exemple 3 façons de plonger le mot bar dans le
mot abracadabra. On cherche ensuite à compter le nombre de sous-mots d'un
texte donné, ainsi qu'à construire le plus court sur-mot commun à deux mots.
· La seconde partie s'intéresse aux expressions rationnelles, afin de savoir 
tester s'il existe un mot, décrit par une expression, qui contient un sous-mot u
donné. Deux méthodes sont étudiées en détail, l'une de complexité 
exponentielle, l'autre de complexité polynomiale.
Ce sujet est particulièrement difficile à traiter parfaitement dans le temps 
imparti,
du fait des programmes nombreux, difficiles et longs à écrire de façon 
entièrement
correcte. En condition de concours, sur ce type de sujet, il faut sans doute 
réussir à
aller suffisamment vite (quitte à oublier certains détails) puisqu'il est 
probable que
les correcteurs se seront montrés cléments vu le nombre de programmes à écrire.
Plus de la moitié d'entre eux utilisent la programmation dynamique, ce qui fait 
de
cet énoncé un sujet idéal pour réviser ce paradigme algorithmique. Bien 
qu'utilisant
la notion de langage rationnel, aucune connaissance préalable sur les automates 
finis
n'est requise pour traiter ce sujet.

Indications
Préliminaires
1.a Raisonner par double implication, en distinguant à chaque fois deux cas 
selon
l'endroit où peut se plonger la lettre a dans u a .
1.b Utiliser la formule de la question 1.a pour obtenir un algorithme récursif. 
Majorer le nombre d'appels récursifs pour montrer qu'il est de complexité 
polynomiale.
Partie I
2.b Lorsque m 6 n, il suffit de compter le nombre d'applications strictement 
croissantes de [m] dans [n].
2.c Partitionner les plongements de va dans ua selon le plongement de la 
dernière
lettre.
3.b Prouver par récurrence sur j  [m + 1] que, pour tout i  [n + 1], l'appel à 
la

fonction aux i j renvoie u[0,j[
. On utilisera le résultat de la question 2.c.
v[0,i[
4.a Majorer le nombre C(i, j) d'appels récursifs lors de l'appel aux i j.

4.b Raisonner par l'absurde en supposant que T(v, u) peut être borné par f uv
pour une certaine fonction polynomiale f , et obtenir une contradiction en 
considérant u = v = an pour un entier naturel n assez grand.

4.c Donner une définition par récurrence du nombre C(i, j) d'appels récursifs 
lors
de l'appel aux i j, pour i 6 m et j 6 n, et l'utiliser pour minorer C(i, j) par

u[0, j[
C(i, j) > 2
-2
v[0, i[
5 Employer une méthode de programmation dynamique en définissant une matrice de 
taille (|v| + 1) × (|u| + 1) dont le coefficient (i, j) contiendra u[0,j[
v[0,i[ .

6.a Raisonner par double inclusion.

7.a Pour un mot non vide u = u a (avec a  A), traiter différemment le cas
où u  (A r {a}) du cas général où on s'inspirera de la question 6.
7.b Procéder à nouveau par programmation dynamique en stockant dans un vecteur
de longueur |u|+1 les différentes valeurs de Card (u[0, i[). On pourra 
introduire
une fonction auxiliaire pour calculer la dernière occurrence d'une lettre a dans
un préfixe u[0, i[ du mot u.
8.b Dans le cas où a et b sont des lettres distinctes, montrer que pcsmc(ua, 
vb) peut
s'obtenir à partir de pcsmc(u, vb)a et pcsmc(ua, v)b.
8.c Utiliser encore un algorithme de programmation dynamique pour stocker dans
une matrice de taille (|u|+1)×(|v|+1) les mots pcsmc(u[0, i[, v[0, j[) pour i 6 
|u|
et j 6 |v|.
Partie II
10 Montrer que la propriété « contient un mot commençant par la lettre a » peut
être définie par induction sur la forme des expressions rationnelles. Dans le
cas d'un produit e = e1 · e2 , veiller à bien considérer les cas où   L(e1 ) ou
bien L(e2 ) = .

11 Montrer que les 4 égalités sont fausses.
12.a Noter que v  hiL si et seulement si v est un suffixe d'un mot de L. En 
déduire une définition inductive de hiL(e) en fonction de la forme de 
l'expression
rationnelle e.
12.b La taille de l'expression obtenue par la fonction eps_residu_ratexp doit 
être
quadratique en la taille de l'expression e de départ.
13.a Noter que haiL est l'ensemble des mots de L desquels on a supprimé un 
préfixe
contenant la lettre a. Trouver à nouveau une définition de haiL(e) par induction
sur la forme de e. Dans le cas où e = e1 · e2 , distinguer les cas où L(e1 ) =  
et
haiL(e1 ) = . Dans le cas restant, montrer que
haiL(e) = (haiL(e1 )) · L(e2 )  hiL(e2 )
Dans le cas où e = e1  , distinguer le cas où haiL = . Dans l'autre cas, 
montrer que
haiL = hiL
14.a Montrer que, pour tout mot u  A , toute lettre a  A et tout langage L on a
hauiL = hui(haiL)
En déduire un calcul de huiL(e) par récurrence sur la longueur du mot u. 
Utiliser
finalement le fait, rappelé par l'énoncé, que u est un sous-mot de L(e) si et
seulement si   huiL(e).
15 Pour un mot u  A fixé, trouver une définition de FC(u, e) par induction sur 
la
forme de l'expression rationnelle e. Faire le lien entre la somme d'expressions 
et
la somme des matrices correspondantes, le produit d'expressions avec le produit
matriciel correspondant, et l'étoile de Kleene e avec la clôture transitive du
graphe dont la matrice d'adjacence est la matrice booléenne FC(u, e).

Préliminaires
1.a Soient u = a0 · · · an-1 et u = a0 · · · an -1 deux mots de longueurs 
respectives n
et n . Soient a et a deux lettres, qu'on notera également an = a et an = a . 
Montrons
l'équivalence (1) par double implication.
Supposons d'abord que ua 4 u a . Il existe donc un plongement p : [n+1]  [n +1]
tel que pour tout i  [n+1], ai = api . En particulier, a = apn . Deux cas sont 
possibles :
· 1er cas : si pn < n alors, puisque p est une application strictement 
croissante,
elle est d'image incluse dans [n ] et c'est donc un plongement de ua dans u ,
c'est-à-dire ua 4 u .
· 2e cas : sinon, pn = n . Ainsi, a = apn = an = a . De plus, la restriction de 
p
à [n] est une application strictement croissante de [n] dans [n ], c'est-à-dire 
un
plongement de u dans u , donc u 4 u .
On a donc

ua 4 u

ou (a = a

et

u 4 u )

Réciproquement, supposons que ua 4 u ou (a = a et u 4 u ). Distinguons à
nouveau deux cas :
· 1er cas : si ua 4 u , alors il existe un plongement p : [n + 1]  [n ] de ua
dans u . L'application p peut aussi être vue comme une application strictement
croissante de [n + 1] dans [n + 1], c'est-à-dire comme un plongement de ua
dans u a .
· 2e cas : si a = a et u 4 u , alors il existe un plongement p : [n]  [n ] de u
dans u . Étendons cette application en posant pn+1 = n + 1. L'application p
prolongée est donc toujours strictement croissante et on a bien
apn+1 = a = a = an +1
On obtient ainsi un plongement de ua dans u a .
Dans les deux cas, on a donc construit un plongement p : ua 4 u a . Finalement,
Pour tous mots u et u et lettres a et a , on a l'équivalence
ua 4 u a

ua 4 u

ou (a = a et u 4 u )

1.b Afin de vérifier si v de longueur m est un sous-mot de u de longueur n, 
utilisons
une fonction auxiliaire récursive prenant en argument deux entiers j et i et 
qui teste
si v[j · · · [ 4 u[i · · · [. On peut alors tester si u 4 u en appelant la 
fonction auxiliaire
avec i = j = 0.
Les cas de base de la fonction récursive correspondent aux cas où j = m ou i = 
n.
Si j = m, on renvoie true puisque v[j · · · [ est alors le mot vide. Sinon, si 
i = n, alors
on renvoie false puisque v[j · · · [ est alors non vide et ne peut donc pas 
être plongé
dans le mot vide u[i · · · [.
Dans les cas où j < m et i < n, on distingue deux cas : si les lettres u[i]
et v[j] sont identiques, alors on continue en cherchant un plongement de v[j + 
1 · · · [
dans u[i+1 · · · [. Dans le cas contraire, la lettre u[i] n'est pas utilisée 
dans un éventuel
plongement et on poursuit en cherchant un plongement de v[j · · · [ dans u[i + 
1 · · · [.