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

Version interactive avec LaTeX compilé

Télécharger PDF

Centrale Option Informatique MP 2008

Mots de Lukasiewicz, recherche de motif

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Logo centrale
🔗 Explorer
Banque
Centrale
Année
2008
Filière
MP
Matière
Info
Centrale MPCentrale 2008MP InfoInfo 2008
2025_08_29_274612522ce1a26ab503g
Les deux parties sont indépendantes. Le candidat indiquera en tête de sa copie le langage choisi : Caml ou Pascal.

Partie I-Mots de Lukasiewicz

Dans cette partie, les mots considérés sont pris sur l'alphabet .
On appelle mots de Lukasiewicz les mots sur cet alphabet qui vérifient les deux propriétés suivantes :
On note avec un point la concaténation de deux mots, par exemple .
  • En Caml, un mot de Lukasiewicz sera représenté par une liste d'entiers (int list).
  • En Pascal, un mot de Lukasiewicz sera représenté par une chaîne de caractères (string) composée de symboles '+' (pour +1) et '-' (pour -1). On rappelle les opérations suivantes:
  • accéder au caractère numéro de la chaîne : c [i] (la numérotation commence à 1);
  • obtenir la longueur d'une chaîne length(c);
  • extraire une chaîne d'une sous-chaîne: copy(chaîne, position, longueur). Par exemple, copy('abcdef', 2, 3) retourne 'bcd';
  • concaténer deux chaînes ou caractères et pour obtenir une nouvelle chaîne : .
    On demande d'indiquer le type de toutes les fonctions écrites, que ce soit en Caml ou en Pascal.

I.A - Quelques propriétés

I.A.1) Donner tous les mots de Lukasiewicz de longueur 1, 2 et 3, puis tous ceux de longueur paire.
I.A.2) Écrire une fonction qui indique si un mot est de Lukasiewicz. Cette fonction renverra une valeur booléenne. La fonction proposée devra impérativement avoir une complexité (en termes d'opérations élémentaires) en , avec la longueur du mot d'entrée.
I.A.3) Montrer que si et sont des mots de Lukasiewicz, alors est un mot de Lukasiewicz.
I.A.4) Réciproquement, montrer que tout mot de Lukasiewicz de longueur supérieure ou égale à 3 admet une décomposition unique de la forme , où et sont des mots de Lukasiewicz.
I.A.5) Écrire une fonction décompose qui associe ce couple ( ) à un mot de Lukasiewicz de longueur supérieure ou égale à 3. En Pascal, on pourra écrire une procédure qui modifie deux de ses paramètres et passés par référence. On ne demande pas de traiter les cas où le mot fourni en entrée ne serait pas de Lukasiewicz.
I.A.6) On souhaite calculer tous les mots de Lukasiewicz d'une longueur donnée. Comparer les avantages d'une solution récursive appliquant le principe de la décomposition suggéré par la question A.4), et celle d'une solution appliquant le même principe, mais pour laquelle on tabulerait les résultats intermédiaires.
I.A.7) Écrire une fonction obtenirLukasiewicz qui calcule la liste des mots de Lukasiewicz de taille inférieure ou égale à un entier donné.
En Pascal, on dispose des types et fonction :
type
    ptliste=^liste;
    liste=record
            valeur : string;
            suivant:ptliste
        end;
function adjonction(x:string; pt:ptliste):ptliste;
Cette dernière fonction adjonction réalise l'adjonction d'une nouvelle cellule en tête de liste (et retournant un pointeur sur ladite cellule). On ne demande pas de l'écrire.
I.B - Dénombrement
I.B.1) Soit un mot tel que . Démontrer qu'il existe un unique entier , tel que ( ) soit un mot de Lukasiewicz. Ce mot est appelé conjugué de .
I.B.2) Écrire une fonction conjugue qui calcule le conjugué d'un mot vérifiant .
I.B.3) En utilisant les résultats précédents, déterminer le nombre de mots de Lukasiewicz de longueur .
On pourra utiliser ce résultat admis : et sont deux mots non vides, les deux propositions suivantes sont équivalentes :
  • il existe un mot non vide et deux entiers tels que et
    I.C - Régularité
    I.C.1) Montrer que le langage n'est pas reconnaissable (implicitement dans la suite : «par un automate fini »).
    I.C.2) Montrer que l'intersection de deux langages reconnaissables est un langage reconnaissable.
    I.C.3) Prouver le caractère reconnaissable ou non du langage constitué des mots de Lukasiewicz.

I.D - Capsules

On appelle capsule d'un mot tout facteur de de la forme . On définit sur une fonction dite de décapsulage :
è
I.D.1) Justifier le fait que la suite est constante au delà d'un certain rang. La valeur limite de la suite est notée .
I.D.2) Écrire une fonction rho qui calcule .
I.D.3) Écrire une fonction rhoLim qui calcule .
I.D.4) Démontrer que est un mot de Lukasiewicz si et seulement si .

Partie II-Recherche de motif

Dans ce problème, nous allons étudier deux algorithmes de recherche de motif (en général noté ) dans un mot (en général noté ). Par exemple, le motif bra apparaît deux fois dans le mot m0=abracadabra. Les programmes de recherche de motif devront retourner la liste (éventuellement vide) des positions (au sens de Caml/Pascal) du motif dans le mot. Dans l'exemple précédent, les programmes devront retourner une liste contenant les positions 1 et 8 en Caml; 2 et 9 en Pascal. C'est la position de la première lettre qui est prise en compte. Plus formellement, si
, on dit que apparaît en position dans lorsque , avec la longueur de .

II.A - Algorithme naïf

II.A.1) Écrire une fonction coincide prenant en entrée deux chaînes de caractères p et , une position pos, et retournant true si apparait en position pos dans m (et false sinon). Cette fonction devra uniquement utiliser des comparaisons de caractères, sans utiliser sub_string (Caml) ou copy (Pascal). De plus, en cas de réponse false, elle devra arrêter les tests dès que possible.
II.A.2) Écrire une fonction recherche prenant en entrée deux chaînes de caractères p et m , et retournant la liste (dans n'importe quel ordre, et éventuellement vide) des positions de p dans m.
En Pascal, on dispose comme dans la première partie des types ptliste, liste et de la fonction adjonction, avec cette fois le champ valeur de type integer.
II.A.3) Évaluer la complexité (en termes de comparaisons de caractères, et en fonction de et de la fonction précédente dans le pire des cas. On exhibera un cas défavorable (en terme de complexité), avec et arbitrairement grands.

II.B - Algorithme de Rabin-Karp

La présentation de l'algorithme de Rabin-Karp est faite dans le cas de l'alphabet .
Un mot peut être vu naturellement comme un entier ( est dans mais aussi dans ).
II.B.1) La première idée de l'algorithme de Rabin-Karp est que si on cherche dans , on va regarder les lettres de par groupes de 3 , en initialisant un compteur à , et en «avançant» dans en ajoutant à chaque fois une nouvelle lettre, et en effaçant la première de . Dans notre exemple, passe d'abord à 746 puis 463 . Plus formellement, lire la lettre dans en effaçant change en . Si , cela signifie que le motif est présent en position dans .
On suppose dans cette première version de l'algorithme de Rabin-Karp que est de très petite longueur, de sorte que le compteur ne dépassera jamais la valeur du plus grand entier autorisé par Caml ou Pascal.
On considère définie une fonction appelée numeral prenant comme entrée un caractère de l'alphabet et retournant la valeur entière correspondante (par exemple on associe l'entier 0 au caractère ' 0 ') :
  • En Caml, numeral : char -> int = <fun>
  • En Pascal, function numeral(a : char) : integer ;
    a) Écrire une fonction prenant en entrée un mot , une longueur , et retournant la valeur initiale du compteur, calculée en lisant les premières lettres de . Dans l'exemple donné plus haut, sur l'entrée ( ), la fonction doit retourner 974.
    b) Écrire enfin une fonction prenant en entrée un motif, un mot (supposé de taille supérieure au motif), et calculant la liste des positions dans où le motif est présent.
    II.B.2) L'hypothèse quant à la longueur << faible >> de étant très restrictive, on modifie l'algorithme précédent en choisissant un entier modulo lequel on calculera c. En lisant la lettre et en effaçant , le nouveau compteur devient donc .
    Lorsque , on a . Mais réciproquement, lorsque , on n'est pas assuré d'avoir . On regarde alors (avec l'algorithme naïf) si le facteur de correspondant au compteur calculé est égal à . Si mais , on parle de << fausse-position >>.
    a) Donner les valeurs successives de lors de la recherche de dans , avec .
    b) Écrire une fonction recherchant les positions d'un motif dans un mot, en appliquant l'algorithme de Rabin-Karp, avec un entier donné en paramètre.
    c) Lors de la recherche de dans avec , combien de cas de fausse-position va-t-on rencontrer?
    d) Majorer le temps de calcul de la liste des positions de dans , en fonction de et avec l'algorithme de Rabin-Karp.
    est supposé tel que les calculs arithmétiques modulo sont d'un coût constant. Le temps de calcul pendra donc en compte ces opérations arithmétiques, et les comparaisons de caractères, du type .
    e) Comparer les complexités dans le pire des cas de l'algorithme de Rabin-Karp et de l'algorithme naïf.
    f) En pratique, aura-t-on intérêt à prendre plutôt petit ou plutôt grand? Que peut-on alors espérer pour le temps de calcul de la recherche des occurrences de dans ?
    On demande une justification informelle, le choix de l'entier q et l'évaluation de temps moyen de calcul étant deux choses très délicates ...
Centrale Option Informatique MP 2008 - Version Web LaTeX | WikiPrépa | WikiPrépa