L'usage de la calculatrice et de tout dispositif électronique est interdit.

Cette épreuve concerne uniquement les candidats de la filière MP.
Les candidats sont priés de mentionner de façon apparente sur la première page de la copie :

L'épreuve est composée d'un unique problème, comportant 24 questions. Après un préliminaire et des définitions générales, ce problème est divisé en 4 parties; la partie 2 est indépendante de la partie 1 .

Le but du problème est d'étudier des algorithmes permettant de rechercher efficacement des occurrences d'une ou plusieurs chaînes de caractères (appelées motifs) à l'intérieur d'une longue chaîne de caractères.

Il faudra coder des fonctions à l'aide du langage de programmation Caml, tout autre langage étant exclu. Lorsque le candidat écrira une fonction, il pourra faire appel à d'autres fonctions définies dans les questions précédentes; il pourra aussi définir des fonctions auxiliaires. Quand l'énoncé demande de coder une fonction, il n'est pas nécessaire de justifier que celle-ci est correcte, sauf si l'énoncé le demande explicitement. Enfin, si les paramètres d'une fonction à coder sont supposés vérifier certaines hypothèses, il ne sera pas utile dans l'écriture de cette fonction de tester si les hypothèses sont bien vérifiées.

Dans les questions du problème, un même identificateur écrit dans deux polices de caractères différentes désignera la même entité, mais du point de vue mathématique pour la police en italique (par exemple ) et du point de vue informatique pour celle en romain avec espacement fixe (par exemple ).

On fixe un alphabet , c'est-à-dire un ensemble fini, dont les éléments sont appelés symboles. On note le nombre d'éléments de cet alphabet, et on suppose que cette taille est disponible depuis les fonctions Caml à implémenter sous la forme d'une constante globale lambda. Par exemple :
let lambda ; ;
On supposera que les éléments de sont ordonnés, par exemple par ordre alphabétique, et on les note dans l'ordre . On dit que le code d'un symbole de l'alphabet est l'entier tel que .

Une chaîne de caractères est une suite finie non vide de symboles de . La longueur de est son nombre de symboles, c'est-à-dire, ici, . On représentera en Caml les chaînes de caractères par des listes d'entiers (int list), chaque entier étant le code d'un symbole. Ainsi, si l'alphabet est , dans cet ordre, la chaîne de caractères « » sera représentée par la liste [0; 1; 0; 2]. En particulier, on n'utilisera jamais le type string de Caml.

Une occurrence d'une chaîne de caractères (aussi appelée un motif) dans une autre chaîne de caractères est un entier naturel avec tel que, pour tout entier tel que . En d'autres termes, l'occurrence indique la position du dernier caractère du motif au sein de la chaîne de caractères (les positions commençant à 1 ).

Par exemple, si est le motif « » et la chaîne de caractères «abcabcdababcdabcdabde», il y a quatre occurrences de dans , à savoir :

1 - Soit deux chaînes de caractères. Est-il possible d'avoir deux occurrences et de dans avec et ? Si oui, donner un exemple ; sinon, le prouver.
- Quel est le nombre maximal d'occurrences d'un motif de longueur dans une chaîne de caractères de longueur ? Prouver que cette borne est toujours respectée, et que cette borne est atteinte.
- Programmer en Caml une fonction longueur : 'a list -> int qui prend en entrée une liste et qui renvoie la longueur de cette liste. Quelle est la complexité de cette fonction, en terme du nombre d'éléments de la liste?
- Programmer en Caml une fonction int list -> int list -> bool prenant en entrée deux listes d'entiers et codant des chaînes de caractères et testant si est un préfixe de . Quelle est la complexité de cette fonction, en terme des longueurs et de et ?
- À l'aide des fonctions longueur et prefixe, programmer une fonction recherche_naive : string -> string -> int list, la plus directe possible, telle que si est un motif et une chaîne de caractères, recherche_naive s t renvoie la liste des entiers qui sont des occurrences de dans , triés par ordre croissant.
- Quelle est la complexité de la fonction recherche_naive, en terme des longueurs et de ses deux paramètres et ?

Un automate fini déterministe à repli (ou ) sur l'alphabet est un quadruplet tel que :
est un entier strictement positif représentant le nombre d'états de ; l'ensemble des états de est et 0 est appelé l'état initial.

type afdr = {
    final : bool vect;
    transition : int vect vect;
    repli: int vect;
};;;
où :

On dessine un AFDR de manière similaire au dessin d'un automate fini déterministe classique, en faisant figurer en pointillés une flèche indiquant les replis d'un état vers un autre. Les états finals sont figurés par un double cercle.

Considérons par exemple l'automate sur l'alphabet défini par , et les fonctions et suivantes:

peut être dessiné comme suit :

- Soit un AFDR. Pour tout , on note pour l'application répétée fois de la fonction à , c'est-à-dire
Montrer que pour tout , pour tout , il existe tel que est défini.
On dit qu'un AFDR accepte un mot s'il existe une suite finie d'états de avec :

Le langage accepté par un AFDR est l'ensemble des mots acceptés.
Ainsi, accepte le mot «ababa», comme le montre la suite d'états parcourus

On remarque qu'un AFDR dont la fonction de transition est définie partout peut être vu comme un automate fini déterministe classique, et que cet automate fini déterministe est complet (ce qui signifie précisément que sa fonction de transition est définie partout). En effet, les puissances non nulles de la fonction de repli ne sont utilisées que si la fonction de transition n'est pas définie. On appellera un tel automate fini déterministe complet un .
- Construire (sans justification) un AFDC sur l'alphabet reconnaissant le même langage que et ayant le même nombre d'états que .
- Donner (sans justification) une description concise du langage reconnu par l'AFDR .
- Programmer en Caml une fonction copie_afdr : afdr -> afdr qui renvoie un nouvel AFDR identique à l'AFDR fourni en entrée, mais ne partageant aucune donnée avec lui. On pourra utiliser la fonction standard copie_vect : 'a vect -> 'a vect qui renvoie un nouveau tableau contenant les mêmes éléments que les éléments d'entrée et s'exécute en un temps proportionnel au nombre d'éléments du tableau d'entrée.
- En s'inspirant de la réponse aux questions 7 et 8 , et en utilisant la fonction copie_afdr, programmer une fonction enleve_repli : afdr -> afdr telle que, si est un AFDR , enleve_repli A renvoie un AFDC reconnaissant le même langage. On souhaite que cette fonction s'exécute en temps , où est le nombre d'états de et est la taille de l'alphabet. Montrer que la fonction proposée a bien cette complexité.
- Étant donné un AFDC et un mot sur , proposer un algorithme (pas un programme Caml) en pour calculer la liste triée des entiers avec tels que le préfixe de est accepté par .
- Implémenter en Caml l'algorithme de la question précédente : programmer une fonction occurrences : afdr -> int list -> int list telle que, si est un AFDC et liste une liste d'entiers codant des symboles de l'alphabet , occurrences A liste renvoie la liste des entiers avec tels que le mot est reconnu par . Quelle est la complexité de cette fonction en terme de la longueur de la liste d'entiers, du nombre d'états de l'automate et de ?

L'automate de Knuth-Morris-Pratt (ou automate KMP) associé à un motif sur l'alphabet est un AFDR sur avec :
.

14 - Construire (sans justification) l'automate KMP associé à «ababc»sur l'alphabet .
- Donner (sans justification) une description concise du langage reconnu par l'AFDR pour un motif arbitraire.
- Montrer que si est un motif et ( ) l'automate KMP associé à , alors pour tout , si est le plus petit entier tel que est défini (qui existe d'après la question 7), alors .
- En utilisant la caractérisation de la question 16, programmer une fonction automate_kmp : int list -> afdr qui prend en entrée une liste d'entiers s codant une chaîne de caractères et qui renvoie l'AFDR .
- Pour un motif et pour tout , on note le plus petit entier tel que est défini, comme à la question 16. Montrer que pour tout et en déduire que est en .
- Quelle est la complexité de la fonction automate_kmp en terme de la longueur du motif passé en argument et de ? Prouver cette affirmation.
- En s'appuyant sur les fonctions Caml automate_kmp, enleve_repli et occurrences, programmer une fonction Caml recherche_kmp : string -> string -> int list telle que, si est un motif de longueur et une chaîne de caractères, recherche_kmp s t renvoie la liste des occurrences de dans , triés par ordre croissant.
Quelle est la complexité de cette fonction en terme des longueurs et de et et de ? Comparer avec la complexité de la fonction recherche_naive obtenue en question 6.

On considère maintenant l'AFDR suivant, sur l'alphabet :

- Donner (sans justification) une description concise du langage reconnu par l'AFDR .
- On considère l'alphabet . Construire (sans justification) un AFDR dont le langage reconnu est l'ensemble des mots dont un suffixe est « », « » ou « ». Indication : on cherchera un AFDR tel que si est défini et est non nul, alors .

On fixe maintenant un ensemble fini de motifs. L'ensemble des occurrences de dans une chaîne de caractères est l'ensemble des occurrences de chacun des motifs de dans .
- En utilisant la fonction recherche_kmp, programmer une fonction recherche_dictionnaire_kmp : int list list -> int list -> int list qui est telle que, si est un ensemble fini de motifs codé comme une liste de motifs, et une chaîne de caractères, recherche_dictionnaire_kmp S t renvoie la liste des occurrences d'un motif dans . On n'impose pas d'ordre particulier sur cette liste, et on autorise les doublons.
Quelle est la complexité de cette fonction, en terme du nombre de motifs, de la longueur maximale d'un motif, de et de la longueur de ?
- En s'inspirant de l'automate , de la réponse à la question 22 et de la partie 3, proposer une approche pour calculer efficacement les occurrences d'un ensemble fini de motifs dans une chaîne de caractères . On ne demande
ni une formalisation complète de cette approche, ni une implémentation, mais une stratégie générale et les grandes étapes nécessaires à la résolution du problème. On pourra faire l'hypothèse, pour simplifier, que l'ensemble ne contient pas deux mots qui sont préfixes l'un de l'autre.
Quelles difficultés sont à prévoir dans l'implémentation? Quelle complexité peut-on espérer avec une telle approche, en terme du nombre de motifs, de la longueur maximale d'un motif, de et de la longueur de ? Comparer avec la complexité obtenue en réponse à la question précédente.