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

Version interactive avec LaTeX compilé

Télécharger PDF

ENS Informatique MP PC 2003

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Logo ens
🔗 Explorer
Banque
X-ENS
Année
2003
Filière
MP/PC
Matière
Info
X-ENS MP/PCX-ENS 2003MP/PC InfoInfo 2003
2025_08_29_4cc5505c9cc91e551321g
SESSION 2003

Filière MP (groupes MPI/MI)

Épreuve commune aux ENS de Paris et Cachan
Filière MP (groupe I)
Épreuve commune aux ENS de Paris, Lyon et Cachan

Filière PC (groupe I)

Épreuve commune aux ENS de Paris et Lyon

INFORMATIQUE

Durée : 4 heures
L'usage de calculatrices électroniques de poche à alimentation autonome, non imprimantes et sans document d'accompagnement, est autorisé. Cependant, une seule calculatrice à la fois est admise sur la table ou le poste de travail, et aucun échange n'est autorisé entre les candidats.
m

Tournez la page S.V.P.

Préambule

Le sujet comporte 4 parties.
La partie 1 introduit différents problèmes d'algorithmique sur les mots et étudie la complexité des algorithmes naïfs.
La partie 2 propose un algorithme optimal pour le problème de la recherche de motifs.
La partie 3 introduit une structure de données importante dans de nombreux problèmes d'algorithmique des mots, l'arbre des suffixes, et montre comment le calculer en temps linéaire en la taille de l'entrée.
La partie 4 est destinée à l'étude de quelques applications de l'arbre des suffixes.
Les parties 1, 2, 3 sont indépendantes. La partie 4 dépend de la partie 3, mais peut être traitée indépendamment en admettant les résultats qui y sont établis.
Le soin apporté à la rédaction et à la présentation sera apprécié par les correcteurs.
A. Notations et primitives de manipulation des mots. Dans tout le problème, est un alphabet fini, de cardinal fixé. On supposera que la comparaison de deux éléments de (caractères) s'effectue en temps constant. La i-ème lettre d'un mot sera notée . Le sous-mot constitué des caractères d'indice sera noté . On conviendra que est le mot vide si . La longueur d'un mot sera notée . La concaténation de deux mots u et sera notée u.v; il s'agit du mot de longueur tel que si sinon.
On supposera que toutes ces primitives de manipulation des mots peuvent être effectuées en temps constant.
Si les entrées d'un problème ont pour taille , on supposera que toutes les opérations arithmétiques (addition, soustraction, multiplication, comparaison) sur des entiers inférieurs à se font en temps 1 .
B. Avertissement. Cette épreuve est une épreuve d'informatique. À ce titre, la résolution des questions d'algorithmique du sujet sera prise en compte de façon importante dans l'évaluation de la copie. On attire tout particulièrement l'attention des candidats sur le fait que dans l'écriture d'algorithmes sur les mots, il convient d'être attentifs aux dépassements d'indice; c'est-à-dire que si est un mot de taille , il n'est pas licite d'appeler pour ou au cours d'un algorithme.
Sauf mention expresse du contraire, on ne demande pas de justifier formellement les algorithmes écrits.
Outre les structures de contrôle habituelles, les structures de données du programme et les primitives les manipulant, les candidats pourront utiliser dans l'écriture de leurs algorithmes les primitives définies au paragraphe .

1. Quelques problèmes D'Algorithmique des mots

  1. Écrire un algorithme COMPARE_SOUS_CHAÎNE qui prend en argument deux mots de et trois entiers positifs ou nuls, et qui renvoie faux si ou , vrai sinon. Quelle en est la complexité?
Recherche de motifs. Soit un mot fixé de longueur (le motif), et de longueur (le texte). Le problème de la recherche du motif dans le texte consiste à trouver l'ensemble des indices tels que . Dans les algorithmes, cet ensemble pourra être représenté comme une liste sans répétitions.
2. Montrer que l'ensemble des mots tels que card est un langage rationnel. L'ensemble des mots tels que est-il un langage rationnel?
3. Écrire un algorithme prenant en entrée les deux mots et et résolvant le problème de la recherche de motifs en temps .
Plus longue sous-chaîne commune. Soient et deux mots de de longueurs respectives et .
Une sous-chaîne commune est un mot de de longueur tel qu'il existe et avec .
Une plus longue sous-chaîne commune est une sous-chaîne commune de longueur maximale.
4. Proposer un algorithme de complexité trouvant une plus longue sous-chaîne commune de deux mots et .
Répétitions maximales. Soit un mot de de longueur . Un triplet de répétition de s est un triplet ( ) tel que et .
Un triplet de répétition est dit maximal si ni , ni ne sont des triplets de répétition. On dit alors que est une répétition maximale.
5. Proposer un algorithme calculant toutes les répétitions maximales d'un mot . Quelle est sa complexité? On pourra, cette fois, représenter l'ensemble des répétitions comme une liste pouvant contenir plusieurs fois le même élément. Comment détecter les répétitions intervenant plusieurs fois dans la liste?

2. Algorithme avancé pour la recherche de motifs

Pour tout élément de , on appelera préfixe de un mot de longueur au plus tel que . Soit un mot de longueur . Pour , on note la longueur du plus long préfixe de s[i..n] qui est aussi un préfixe de s. On pose
on note le plus petit indice atteignant le maximum. Si pour tout , on pose .
Le mot est donc le préfixe de commençant à gauche de et se terminant le plus à droite possible.
  1. Calculer les pour .
  2. On suppose . Soit le plus petit entier tel que . Exprimer en fonction de . On pourra distinguer le cas et le cas .
  3. Soit un entier. On suppose que .
    a. Montrer que .
    b. En déduire que si , alors , .
    c. Dans le cas contraire, soit . Exprimer et en fonction de et de .
  4. Déduire de 2. et 3. un algorithme calculant les et effectuant comparaisons de caractères.
  5. Soit . En considérant , montrer que l'on peut trouver un algorithme trouvant le motif dans le texte en temps .

3. Arbre des suffixes

On définit un type de données arbre étiqueté comme étant un triplet formé de deux entiers et d'une liste d'arbres étiquetés. Une feuille est un arbre étiqueté pour lequel la liste est vide; la liste vide sera notée []. L'ajout d'un élément en tête d'une liste sera noté .
On supposera données les fonctions :
Intuitivement, les deux entiers associés à un noeud de l'arbre correspondent au mot . Ce mot sera appelé l'étiquette du nœud.
L'étiquette depuis la racine d'un nœud est l'étiquette du chemin qui mène de la racine à ce nœud, ce dernier non compris dans le chemin. En particulier, l'étiquette depuis la racine de la racine elle-même est .
On dira qu'il existe un chemin d'étiquette dans l'arbre s'il existe un noeud , ) tel que l'étiquette de depuis la racine soit un préfixe de , et que soit un préfixe de . On dira que le chemin d'étiquette se termine en position du nœud si . Dans le cas particulier , on dira le chemin d'étiquette se termine en position 0 de la racine.
On suppose donnée une fonction trouve qui prend en argument un arbre étiqueté, un mot de et deux entiers et , et renvoie un triplet ( ) constitué d'un nœud interne , d'un booléen et d'un entier tels que
  • faux s'il existe un chemin issu de la racine d'étiquette ; dans ce cas, ce chemin se termine en position du nœud .
  • vrai sinon; dans ce cas, s'il existe un chemin issu de la racine d'étiquette , le chemin se termine en position du nœud . Sinon, et .
    Dans le cas où plusieurs chemins conviennent, on supposera que trouve détecte l'un quelconque d'entre eux. On établira à la question 3 que ce n'est jamais le cas dans ce problème.
La complexité de la fonction trouve sera supposée proportionnelle au nombre de nœuds se trouvant sur le chemin.
On suppose enfin que le fait de modifier un nœud interne d'un arbre en modifie également l'arbre en remplaçant dans ce dernier par .
On donne alors les deux fonctions suivantes:
. Si flag alors si alors fils fils sinon fils , fin , fils 
        $\operatorname{fin}(B) \leftarrow z$.
    finsi
finsi.
Arbre_suffixe(s) =

Pour de 2 à faire
Pour de 1 à faire
ajoute
finpour.
finpour.
Renvoyer .
  1. Que vaut Arbre_suffixe(mississipi)? On pourra donner les arbres sous forme de représentation arborescente usuelle.
  2. Montrer que pour , avant l'appel à ajoute( ) il existe dans un chemin d'étiquette .
  3. Montrer que les arbres successifs construits par les appels à ajoute vérifient :
    si est un nœud interne de , alors pour tout . En déduire que pour tout mot , il existe au plus un nœud interne d'étiquette depuis la racine tel que est un préfixe de et est un préfixe de e.s[debut ..fin ].
  4. Montrer que la fonction Arbre_suffixe effectue opérations.
Dans la fonction Arbre_suffixe, on dira qu'on est au stade de l'étape si et . Dans la fonction ajoute, on dira qu'on est dans le cas 2 si flag vaut vrai; qu'on est dans le cas 1 s'il est faux, que fils et ; qu'on est dans le cas 3 sinon.
5. Montrer que si l'on est dans le cas 1 au stade de l'étape , alors on sera dans le cas 1 au stade de toutes les étapes ultérieures.
6. Montrer que si on est dans le cas 3 au stade de l'étape , alors on sera dans le cas 3 dans les stades ultérieurs de l'étape .
7. Comment modifier Arbre_suffixe pour qu'il effectue seulement itérations?
L'objectif est maintenant de modifier la structure de données pour permettre à la fonction trouve de s'exécuter en temps constant.
8. On suppose qu'on est dans le cas 2 au stade de l'étape , résultant en la création d'un nœud interne d'étiquette depuis la racine . Montrer qu'au plus tard à la fin du stade il existe un nœud interne d'étiquette depuis la racine .
On modifie la définition d'un arbre, en ajoutant un champ supplémentaire contenant un arbre; ce champ est utilisé pour stocker un lien suffixe : le nœud , dont l'étiquette depuis la racine est a un lien suffixe vers l'éventuel nœud d'étiquette depuis la racine .
Étant donné un nœud , on note le nombre de nœuds sur le chemin menant de la racine à .
9. Montrer que s'il existe un lien suffixe allant d'un nœud à un nœud , alors .
10. Expliquer comment on peut modifier Arbre_suffixe pour qu'il opère en opérations. On pourra construire et utiliser les liens suffixes pour passer d'un chemin d'étiquette à un chemin d'étiquette . On pourra en outre rajouter dans la structure d'arbre étiqueté un arbre permettant de remonter d'un nœud interne à son père.
11. Soit . Montrer que l'arbre associé au mot a exactement feuilles correspondant aux suffixes de et à #.
Cet arbre est l'arbre des suffixes du mot .

4. Applications de l'arbre des suffixes

  1. Comment utiliser l'arbre des suffixes pour obtenir la liste des suffixes d'un mot triés par ordre lexicographique en temps linéaire?
  2. Soit un mot de longueur . Montrer que le calcul d'un arbre de suffixes de permet ensuite de trouver les occurrences d'un mot dans en temps . Comparer avec la méthode de la partie 2.
  3. Montrer que si ( ) est un triplet de répétition maximal alors est l'étiquette depuis la racine de deux nœuds distincts de l'arbre des suffixes.
En déduire qu'il y a au plus répétitions maximales dans .
4. Montrer que l'arbre des suffixes permet de déterminer l'ensemble des répétitions maximales en temps linéaire.
5. Expliquer comment une structure de données généralisant l'arbre des suffixes permet de résoudre le problème de la plus longue sous-chaîne commune en temps linéaire.
ENS Informatique MP PC 2003 - Version Web LaTeX | WikiPrépa | WikiPrépa