Les candidats indiqueront en tête de leur copie le langage de programmation choisi (Pascal ou Caml). Les candidats ayant choisi Caml devront donner le type de chaque fonction écrite. Les candidats travaillant en Pascal pourront écrire des fonctions ou des procédures.
Les deux parties sont indépendantes.
I Identification de sous-mots répétés dans un mot
Cette partie traite de l'identification de sous-mots répétés dans un mot formé sur un alphabet donné. Ce problème est particulièrement prégnant en génétique où il s'agit de repérer des répétitions dans des brins d'ADN, ce qui permet de comprendre sa structure. Dans ce cas, on prend simplement .
Soit un alphabet et soit un mot de longueur formé sur ( pour tout ).
Un mot sera représenté par une chaîne de caractères. Aussi bien en Caml qu'en Pascal, on extraira d'un mot le caractère de rang à l'aide d'une fonction caractère , supposée fournie. Le rang du premier caractère est 0 .
I.A - Une famille de relations d'équivalence
Soit et soient . Les rangs et sont dits -équivalents si
c'est-à-dire si les sous-mots de longueur commençant aux indices et sont identiques.
Ce fait est noté .
I.A.1) Montrer que peut se déduire de deux expressions simples construites sur et .
I.A.2) Montrer que peut se déduire de deux expressions simples construites sur , lorsque . Ce résultat sera utilisé dans la suite.
I.B - Manipulation de piles
En Caml, on définit le type pile (d'entiers) par :
type pile = {
mutable elements: int list;
};;;
En Pascal, le type pile est défini par :
type
pmaillon = ^maillon;
pile = pmaillon;
maillon = record
valeur: integer;
suivant: pmaillon;
end;
Le type pile possède trois opérations :
empile, qui ajoute un élément au sommet de la pile;
depile, qui rend l'élément situé au sommet de la pile et le retire de la pile;
vide, qui rend vrai si et seulement si la pile est vide.
Écrire les fonctions empile, depile et vide.
I. - Calcul des classes d'équivalence de
On considère à partir de maintenant que est composé des 26 lettres de l'alphabet. On suppose que l'on dispose d'une fonction numero_lettre qui à chaque lettre (caractère) associe son rang, compris entre 0 et 25.
On rappelle que si , la classe d'équivalence de pour est le sous-ensemble des entiers tels que . Une classe d'équivalence de est une partie de pour laquelle il existe tel que .
I.C.1) Pour , que signifie ?
I.C.2) On note le nombre de classes d'équivalence de ; les classes d'équivalence de seront numérotées par des entiers entre 0 et . Elles seront représentées par un vecteur (Caml) ou tableau (Pascal) d'entiers, de longueur (indices numérotés de 0 à ), dans lequel l'élément de rang sera le numéro de la classe d'équivalence de .
Dans la suite, on utilisera le terme vecteur pour désigner aussi bien les vecteurs de Caml que les tableaux de Pascal.
Exemple : pour le mot «abracadabra», le vecteur [ ] donne les classes d'équivalence de .
Écrire une fonction construit_E1 qui pour un mot donné en argument, construit le vecteur représentant les classes d'équivalence de ; cette fonction utilisera un seul vecteur de longueur et aucune autre structure annexe de type liste ou pile.
I.C.3) Donner la complexité de cette fonction en termes du nombre de lectures et d'écritures dans un vecteur.
I.C.4) On autorise maintenant la fonction construit_E1 à utiliser un vecteur supplémentaire. Réécrire construit_E1 de sorte qu'elle ait une complexité en .
I.D - Classes d'équivalence des
On cherche dans cette section à construire les classes d'équivalence de , connaissant les classes d'équivalence de et sachant que .
Comme précédemment, les classes d'équivalence de sont numérotées de 0 à .
Soit le vecteur donnant les numéros des classes d'équivalence de ; on rappelle que est un vecteur à composantes. Le but de cette section est de construire le vecteur à composantes donnant les numéros des classes d'équivalence de .
Pour construire les classes d'équivalence de , on commence par regrouper les indices des lettres de en sous-ensembles, de façon que deux éléments , e quelconques d'un tel sous-ensemble vérifient . On remarque que seuls sont concernés les indices vérifiant .
I.D.1) Combien y aura-t-il de sous-ensembles au maximum ?
I.D.2) On souhaite construire ces différents sous-ensembles. On utilisera pour cela un vecteur de piles, chaque pile correspondant à un sous-ensemble. Expliquer comment on peut simplement construire ce vecteur de piles. On ne demande pas d'écrire de programme en Caml ou Pascal à ce stade. Certaines piles peuvent être vides.
I.D.3) Une pile donnée contient donc des indices tels que deux valeurs successives et vérifient . Si de plus ces deux valeurs successives vérifient , que peut-on en déduire d'utile pour construire les classes de ?
I.D.4) Cependant, a priori la méthode de construction des piles de la question I.D. 2 ne garantit pas que tous les éléments d'une pile qui appartiennent à une même classe d'équivalence de seront placés successivement. On cherche donc à modifier la solution de la question I.D. 2 pour ajouter cette propriété.
Nous allons commencer par créer un premier vecteur de piles (intermédiaire), contenant tous les éléments de , et tel que si deux éléments appartiennent à la même pile, alors . Ecrire une fonction empileClassesEa qui fournit ce résultat, en fonction du vecteur et du nombre de classes d'équivalence de .
I.D.5) À partir de ce vecteur de piles intermédiaire, modifier la méthode proposée à la question I.D. 2 de façon à obtenir un vecteur de piles final dans lequel les éléments d'une pile qui appartiennent à une même classe d'équivalence de sont placés successivement. La solution sera réalisée sous forme d'une fonction sousEnsembles prenant en paramètre le vecteur , vecteur de piles intermédiaire, et la valeur .
I.D.6) En utilisant la propriété remarquée dans la question I.D.3, écrire une fonction classesAplusB qui calcule les classes d'équivalence de . Cette fonction rendra le vecteur et prendra en paramètre le vecteur , le vecteur (final) de piles issu de la fonction de la question précédente et la valeur .
I.D.7) Écrire finalement la fonction classesAversAplusB qui calcule le vecteur à partir du vecteur .
I.E - Construction des classes d'équivalence des
I.E.1) Soit un entier naturel tel que soit inférieur ou égal à . Montrer que l'on peut construire les classes d'équivalence de en appliquant fois classesAversAplusB.
I.E.2) Écrire une fonction classesEq qui, à un mot de longueur et à un entier quelconque , associe les classes d'équivalence de .
I.F - Sous-mots répétés
I.F.1) Expliquer comment classesEq permet d'obtenir la liste des sous-mots répétés d'une certaine longueur .
On cherche maintenant à trouver l'entier maximum pour lequel il y a des sous-mots répétés.
I.F.2) Quel test simple sur le résultat de classesEq permet de savoir si un mot contient des sous-mots répétés de longueur ?
I.F.3) Nous avons vu en I.E. 1 que peut être construit avec appels à classesAversAplusB. En vertu de ce résultat et de la question précédente, on doit donc pouvoir déterminer le plus petit entier tel qu'il n'existe pas de sous-mots répétés de longueur dans .
Comment alors déterminer en un minimum d'opérations le plus grand entier tel que contienne des sous-mots répétés de longueur ?
On ne demande pas de programmer cette opération.
II Langages et automates
II.A - Ensembles dénombrables
Notation - Pour tout ensemble , on note l'ensemble des sous-ensembles de . En particulier, .
Définitions - Deux ensembles et sont dits équipotents, s'il existe une bijection de vers . Un ensemble est dit dénombrable si et sont équipotents ( désigne l'ensemble des entiers naturels).
II.A.1) Si est un ensemble fini, montrer que et ne sont pas équipotents.
II.A.2) Si est un ensemble quelconque, montrer que et ne sont pas équipotents.
Indication. On peut raisonner par l'absurde en supposant qu'il existe une bijection ; on considérera et tel que , puis on examinera la véracité de .
II.A.3) Soit .
Montrer que n'est pas dénombrable.
II.A.4) On peut montrer que l'ensemble des langages rationnels est dénombrable. Cela implique qu'il existe des langages sur qui ne sont pas rationnels. En voici un :
Soit est premier . Montrer que n'est pas rationnel.
II.B - Lemme d'Arden
Le lemme d'Arden permet de résoudre des équations du type : où et sont des langages. Soit un alphabet.
Définition Soit deux langages sur . Le langage est défini par
Le langage est défini comme l'union avec :
II.B.1) Soit un ensemble non vide et, pour chaque , soit un langage sur . Soit un langage sur . Montrer les propositions suivantes :
II.B.2) On désigne par ( ) l'équation
où et .
Démontrer que est une solution de .
II.B.3) Démontrer que, pour l'inclusion, est la plus petite solution de ( ).
II.B.4) Donner un exemple de valeurs de et pour lesquelles l'équation ( ) admet plusieurs solutions.
II.B.5) Démontrer que si alors est l'unique solution de ( ).
II.B.6) Un automate fini déterministe est décrit par une structure ( ) avec :
l'ensemble fini non-vide des états de ;
l'alphabet;
la fonction de transition;
l'état initial;
l'ensemble des états terminaux.
À chaque état on associe l'équation :
Le système d'équations associé à est l'ensemble qui contient les équations pour .
On considère, et on représente ci-dessous, l'automate avec , et .
Écrire le système d'équations associé à .
II.B.7) Calculer une solution de .
II.B.8) Que représente le langage associé à par la solution de ?
Centrale Option Informatique MP 2011 - Version Web LaTeX | WikiPrépa | WikiPrépa
