X/ENS Informatique A MP 2019

Thème de l'épreuve Autour des sous-mots et des sur-mots
Principaux outils utilisés combinatoire, programmation dynamique, complexité, terminaison, correction, expressions rationnelles, langages rationnels
Mots clefs sur-mot, sous-mot, facteurs, plongement, ordre lexicographique, résidu

Corrigé

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

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                    

Rapport du jury

(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 · · · [.