MARDI 13 AVRIL 2021
14h00-18h00
FILIERE MP - Epreuve
I NFORMATI QUE A (XULCR)
Durée : 4 heures
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve
Cette composition ne concerne qu'une partie des candidats de la filière MP, les autres candidats effectuant simultanément la composition de Physique et Sciences de l'Ingénieur.
Pour la filière MP, il y a donc deux enveloppes de Sujets pour cette séance.
Facteurs dans les mots binaires
Ce sujet traite de mots sur un alphabet . On s'intéresse à leurs facteurs, notamment aux facteurs répétés dans un mot et aux mots ayant le maximum de facteurs distincts. L'algorithmique des facteurs est particulièrement utile dans le domaine de la bio-informatique, où l'analyse de mots très longs, à savoir les génomes, requiert des structures de données efficaces.
Mots. Un mot est une suite finie de lettres de l'alphabet . Sa longueur est notée et sa lettre d'indice est notée pour . Le mot vide, de longueur 0 , est noté . On note le mot de longueur formé de caractères .
Pour deux mots et , on définit leur concaténation comme le mot de longueur .
Pour , on note le mot , qui est appelé facteur de . On note que le mot vide est un facteur de n'importe quel mot, obtenu pour . Un préfixe (resp. suffixe) de est un facteur de la forme resp. et on le note (resp. . On note
l'ensemble des facteurs de ;
l'ensemble des préfixes de ;
l'ensemble des suffixes de .
Arbres binaires. Un arbre binaire est défini récursivement de la manière suivante :
soit comme l'arbre vide, noté , qui ne contient aucun nœud;
soit comme un nœud, noté et appelé racine, où est l'information stockée dans le nœud, est un arbre binaire appelé sous-arbre gauche et est un arbre binaire appelé sous-arbre droit.
On note le nombre de nœuds et la hauteur d'un arbre binaire , définis par et .
Langage OCaml. Ce sujet utilise les listes et les tableaux d'OCaml. Une liste est construite à partir de la liste vide [] et de la construction qui renvoie une nouvelle liste dont la tête est l'élément x et dont la queue est la liste 1 . L'appel de List.rev 1 renvoie une nouvelle liste, formée des éléments de la liste 1 en ordre inverse.
On peut créer des tableaux avec les deux fonctions Array.make et Array.of_list. L'appel de Array.make crée un tableau de taille n dont toutes les cases contiennent la valeur x . L'appel de Array. of_list 1 crée un tableau contenant, dans l'ordre, les éléments d'une liste 1. Les cases d'un tableau sont numérotées à partir de 0 . La fonction Array. length renvoie la taille d'un tableau. Pour un tableau tab, on accède à l'élément d'indice i avec tab. (i) et on le modifie avec tab. (i) <- v.
Dans tout le sujet, on représente un mot par un tableau d'entiers, ne contenant que des entiers 0 ou 1 . On se donne donc le type suivant :
type mot = int array (* ne contient que des 0/1 *)
Dans les fonctions demandées, on ne cherchera jamais à vérifier que les tableaux passés en arguments ne contiennent que des 0 et des 1 .
Complexité. Par complexité (en temps) d'un algorithme on entend le nombre d'opérations élémentaires (comparaison, addition, soustraction, multiplication, division, affectation, test, etc.) nécessaires à l'exécution de dans le cas le pire. Lorsque la complexité dépend d'un ou plusieurs paramètres , on dit que a une complexité en s'il existe une constante telle que, pour toutes les valeurs de suffisamment grandes (c'est-à-dire plus grandes qu'un certain seuil), pour toute instance du problème de paramètres , la complexité est au plus .
Dépendances. Ce sujet est conçu pour être traité linéairement. La partie I est nécessaire pour la partie II, et ces deux premières parties motivent la partie III, elle-même utilisée dans la question 22 de la partie IV. En revanche, les questions 20 et 21 de la partie IV ainsi que la partie V sont indépendantes du reste du sujet.
Partie I. Arbres de mots
Dans cette partie, on introduit une structure de données, appelée arbre de mots, qui représente un ensemble fini de mots. Un arbre de mots est un arbre binaire dont chaque nœud contient un booléen. Un arbre de mots a représente un ensemble fini de mots, noté , défini comme suit. Si l'arbre est vide, alors est l'ensemble vide. Si l'arbre est de la forme , alors est l'ensemble des mots suivants :
le mot vide si le booléen est true;
les mots de la forme pour ;
les mots de la forme pour .
Autrement dit, est l'ensemble des mots correspondant aux chemins menant de la racine à un nœud contenant true, en utilisant le caractère 0 quand on va à gauche et le caractère 1 quand
on va à droite. Ainsi, l'arbre de la figure 1 représente l'ensemble de mots . Dans tous les dessins, on utilise T (resp. F) pour le booléen true (resp. false).
Figure 1 - Des arbres de mots.
On note qu'un ensemble de mots peut être représenté par une infinité d'arbres de mots. En effet, il suffit de remplacer un arbre vide par un nœud pour obtenir un autre arbre de mots représentant le même ensemble de mots. Par exemple, l'arbre vide et l'arbre à un nœud false, représentent tous les deux l'ensemble vide. On dit qu'un arbre de mots est réduit dès lors que tout nœud dont les deux sous-arbres sont vides contient le booléen true. Dans toute la suite, on ne manipulera que des arbres de mots réduits.
Question 1. Donner l'ensemble de mots représenté par l'arbre de la figure 1. Dessiner un arbre de mots réduit représentant l'ensemble de mots .
Question 2. Montrer que, pour tout ensemble fini de mots, il existe un unique arbre de mots réduit qui le représente.
Dans la suite, on note l'arbre de mots réduit de l'ensemble fini de mots . On a donc pour tout ensemble fini de mots et inversement pour tout arbre de mots réduit .
Pour représenter un arbre de mots en OCaml, on se donne le type suivant
type am =
| V
| N of bool * am * am
où V représente l'arbre vide et N représente un nœud. Par exemple, l'arbre de la figure 1 est représenté par la valeur suivante :
N (true, V, N (false, N (true, V, V), N (true, V, V)))
Question 3. Écrire une fonction zeros_puis_uns: int am qui reçoit en argument un entier et qui renvoie l'arbre de mots réduit représentant tous les mots de la forme avec . L'arbre de la figure 1 donne un exemple d'un tel arbre pour .
Question 4. Écrire une fonction k_uns: int -> int -> am qui reçoit en arguments deux entiers et et qui renvoie l'arbre de mots réduit représentant tous les mots de
longueur au plus et contenant exactement caractères 1 . L'arbre de la figure 1 donne un exemple d'un tel arbre pour et .
Indication : Pour s'assurer que l'arbre renvoyé est bien réduit, on pourra se servir de la fonction suivante.
let sN = function
| (false, V, V) -> V
| (b, a0, a1) -> N (b, a0, a1)
Question 5. Écrire une fonction compter: am -> int qui reçoit en argument un arbre de mots et renvoie le cardinal de l'ensemble . La complexité en temps doit être linéaire en , mais il n'est pas demandé de la justifier.
Question 6. Écrire une fonction chercher: am -> mot -> bool qui reçoit en arguments un arbre de mots et un mot et détermine si appartient à l'ensemble . La complexité en temps doit être linéaire en , mais il n'est pas demandé de la justifier.
Question 7. Écrire une fonction enumerer: am -> mot list qui reçoit en argument un arbre de mots réduit et renvoie l'ensemble de mots sous la forme d'une liste. La complexité en temps doit être linéaire en la taille du résultat . On justifiera la complexité.
Indication : On pourra écrire une fonction récursive auxiliaire qui reçoit en arguments
une liste acc dans laquelle on accumule les mots déjà construits,
une liste pref contenant les lettres rencontrées le long du chemin menant du nœud courant à la racine,
le sous-arbre dont la racine est le nœud courant,
et qui renvoie la liste acc complétée avec tous les mots de auxquels on a ajouté le préfixe donné par la liste pref.
Question 8. Écrire une fonction ajouter: am -> mot -> am qui reçoit en arguments un arbre de mots réduit et un mot et renvoie l'arbre de mots réduit représentant l'ensemble de mots . La complexité en temps doit être linéaire en , mais il n'est pas demandé de la justifier.
Pour la suite, on remarque que les nœuds de l'arbre de mots correspondent à l'ensemble de mots et . En effet, les mots donnés par les chemins de la racine aux nœuds de (en utilisant 0 quand on va à gauche et 1 quand on va à droite) sont précisément les préfixes d'au moins un mot de .
Partie II. Arbre des suffixes
Dans cette partie, on considère un mot et on définit l'arbre des suffixes de , noté , comme l'arbre de mots réduit de tous les suffixes de , c'est-à-dire .
Question 9. Donner l'arbre pour le mot .
Question 10. Quelle est la hauteur de l'arbre ? En déduire une fonction retrouver_mot: am -> mot qui retrouve le mot à partir de l'arbre de ses suffixes. La complexité en temps doit être linéaire en , mais il n'est pas demandé de la justifier.
Question 11. Montrer que les nœuds de l'arbre correspondent aux facteurs distincts de . En déduire que le nombre de nœuds de l'arbre est au moins linéaire et au plus quadratique en . Montrer que ces bornes sont atteintes, c'est-à-dire que pour tout entier , il existe un mot de longueur tel que l'arbre a nœuds (resp. au moins nœuds où est une constante indépendante de que l'on explicitera).
Des bornes plus précises sur le nombre de facteurs distincts de seront étudiées dans la partie IV.
Partie III. Arbre des facteurs
Dans cette partie, on introduit une structure de données potentiellement plus compacte pour représenter l'arbre des suffixes d'un mot fixé, appelée arbre des facteurs. Cette structure est basée sur les deux idées suivantes:
dans l'arbre de suffixes , un chemin formé de nœuds dont le booléen est false et dont l'un des sous-arbres est vide peut être compacté dans le nœud suivant, quitte à se rappeler de la séquence de caractères correspondante ( 0 quand on va à gauche et 1 quand on va à droite) ;
une telle séquence de caractères se représente de façon compacte par une paire d'entiers qui désigne le facteur .
On considère donc un arbre binaire dont chaque nœud contient deux entiers et tels que et un booléen. Un tel arbre représente l'ensemble des mots défini comme suit. Si l'arbre est vide, alors est l'ensemble vide. Si l'arbre est de la forme , alors est l'ensemble des mots suivants :
le mot si le booléen est true;
les mots de la forme pour ;
les mots de la forme pour .
L'arbre est un arbre des facteurs du mot si l'ensemble est exactement l'ensemble de tous les suffixes de . On dit qu'un arbre des facteurs est réduit dès lors que tout nœud dont au moins un des sous-arbres est vide contient le booléen true. Ainsi, l'arbre de la figure 2 est un arbre des facteurs réduit du mot 10110100. Dans tous les dessins, on représente l'information contenue dans un nœud par si est true et si est false.
Figure 2 - Un arbre des facteurs réduit du mot 10110100.
Attention : Un arbre des facteurs du mot n'est pas un arbre de mots de tous les facteurs de , mais une représentation compacte de l'arbre des suffixes de . On parle d'arbre des facteurs car il permet de manipuler facilement tous les facteurs de , comme on le verra plus loin.
Question 12. Pour chaque arbre de la figure 3, donner l'ensemble et indiquer s'il s'agit d'un arbre des facteurs pour le mot , et s'il est réduit.
Figure 3 - Des arbres.
On peut se convaincre facilement qu'il existe toujours au moins un arbre des facteurs pour tout mot . En effet, il suffit de construire l'arbre des suffixes de de la partie II et d'ajouter dans chaque nœud la paire d'entiers . Pour obtenir un arbre des facteurs réduit, il suffit alors de réduire cet arbre comme expliqué au début de cette partie, en compactant tous les nœuds dont le booléen est false et dont un des sous-arbres est vide. On verra plus loin une procédure pour construire directement un arbre des facteurs réduit.
On montre maintenant qu'un arbre des facteurs réduit du mot est compact en comparaison de l'arbre des suffixes de la partie II qui pouvait être quadratique comme observé à la question 11.
Question 13. Soit un arbre des facteurs réduit d'un mot . On note que l'arbre a nœuds si est ou pour . En supposant que les deux lettres 0 et 1 apparaissent dans le mot ,
montrer que le nombre de nœuds de ayant au moins un sous-arbre vide est au plus ,
en déduire une borne supérieure du nombre de nœuds de en fonction de , et montrer que cette borne est atteinte (c'est-à-dire que pour tout , il existe un mot de longueur dont un arbre des facteurs a précisément ce nombre de nœuds).
Pour représenter un arbre des facteurs en OCaml, on se donne le type
type af =
| V
| N of int * int * bool * af * af
où V représente l'arbre vide et N représente un nœud. On rappelle que le mot est fixé dans cette partie. On pourra supposer qu'il est dans une variable globale m.
Question 14. Écrire une fonction nb_facteurs: af -> int qui reçoit en argument un arbre des facteurs du mot et renvoie le nombre de facteurs distincts de . La complexité en temps doit être linéaire en , mais il n'est pas demandé de la justifier.
Question 15. Écrire une fonction plpc: mot -> int -> int -> mot -> int -> int -> int (pour "plus long préfixe commun") qui prend en arguments un mot avec deux indices et un mot avec deux indices , et qui renvoie le plus grand tel que et et . La complexité en temps doit être linéaire en le résultat, mais il n'est pas demandé de la justifier.
Question 16. Écrire une fonction facteur: af -> mot -> bool qui reçoit en arguments un arbre des facteurs du mot et un mot et détermine si est un facteur de . La complexité en temps doit être linéaire en . On justifiera la complexité.
Question 17. Écrire une fonction facteurs: af -> mot list qui reçoit en argument un arbre des facteurs réduit du mot et renvoie l'ensemble des facteurs sous la forme d'une liste. Chaque facteur doit apparaître une fois et une seule dans cette liste. La complexité en temps doit être linéaire en la taille du résultat . On justifiera la complexité.
On montre maintenant comment construire un arbre des facteurs réduit pour le mot . Pour cela, on part de l'arbre vide et on ajoute successivement tous les suffixes du mot , dans un ordre arbitraire. Un suffixe est ajouté à l'arbre courant de la manière suivante :
si , on construit l'arbre , true, ,
si , on cherche le plus grand tel que et et tel que . On distingue alors deux cas :
si alors on construit l'arbre où
si , alors est false et et sont les arbres et , true, , placés dans le bon ordre;
si , alors est true et et sont les arbres et , placés dans le bon ordre;
si , alors
si , alors on ajoute récursivement le suffixe dans le bon sous-arbre de ;
si , alors on remplace le booléen par true.
Dans la suite, on admet que cette procédure construit un arbre des facteurs réduit pour le mot . On a représenté à la figure 4 les étapes successives de la construction de l'arbre des facteurs pour le mot , en insérant les suffixes dans deux ordres différents. On peut remarquer que la forme de l'arbre des facteurs construit par cette procédure ne dépend pas de l'ordre d'insertion (en revanche, les indices dans les nœuds dépendent de l'ordre d'insertion), mais cette propriété ne sera pas utilisée par la suite.
suffixe inséré
1010
010
10
0
arbre obtenu
0..4(T)
suffixe inséré
0
10
010
1010
arbre obtenu
4.. 4 (T)
4..4(T)
. }
Figure 4 - Étapes successives de la construction de l'arbre des facteurs pour le mot , en insérant les suffixes dans deux ordres différents.
Question 18. Représenter les étapes successives de la construction de l'arbre des facteurs pour le mot , en insérant successivement les suffixes dans l'ordre , et 01001.
Question 19. Compléter le code de la fonction ajouter_suffixe: int -> af -> af cidessous, qui reçoit en arguments une position et un arbre en cours de construction et renvoie l'arbre obtenu en ajoutant le suffixe à l'arbre en suivant la procédure décrite ci-dessus.
let rec ajouter_suffixe i a =
let n = Array.length m in
match a with
| V -> N (i, n, true, V, V)
|N(p, q, b, a0, a1) ->
let k = plpc m p q m i n in
if p + k < q then
(* CAS 1 *)
...
else
(* CAS 2 *)
...
On donnera uniquement dans la copie le code correspondant à (* CAS ) et ( CAS ). La fonction plpc est celle décrite à la question 15 .
Partie IV. Application : plus long facteur répété
Dans cette partie, on s'intéresse aux facteurs répétés du mot , c'est-à-dire aux triplets avec et tels que et . On cherche la longueur maximale d'un facteur répété dans . On commence par un algorithme naïf.
Question 20. Écrire une fonction plfr1: mot -> int (pour "plus long facteur répété") qui reçoit en argument un mot non vide et renvoie la longueur d'un plus long facteur répété dans . La complexité en temps doit être , mais il n'est pas demandé de la justifier.
Pour améliorer la complexité de ce calcul, on utilise maintenant un algorithme de programmation dynamique. Pour , on note la longueur du plus long suffixe commun de et . On rappelle qu'en OCaml, une matrice est un tableau de tableaux. L'appel de Array.make_matrix p q x crée une matrice de taille dont toutes les cases contiennent la valeur . Pour une matrice mat, on accède à l'élément avec mat. (i). (j) et on le modifie avec mat. (i). (j) <- v.
Question 21. Écrire une fonction plfr2: mot int qui reçoit en argument un mot non vide et renvoie la longueur d'un plus long facteur répété dans en construisant la table des . La complexité en temps doit être ), mais il n'est pas demandé de la justifier.
On suppose maintenant qu'on connaît un arbre des facteurs du mot . On observe que les plus longs facteurs répétés dans le mot correspondent aux nœuds internes de profondeur maximale de l'arbre des facteurs. La profondeur est ici considérée comme étant égale à la longueur du mot représenté par le chemin depuis la racine, c'est-à-dire que chaque nœud contribue à la profondeur.
Question 22. Écrire une fonction plfr3: af -> int qui reçoit en argument un arbre des facteurs réduit d'un mot non vide et renvoie la longueur d'un plus long facteur répété dans . La complexité en temps doit être en . On justifiera la complexité.
Partie V. Mot contenant un maximum de facteurs distincts
Dans cette partie, on cherche des mots ayant un maximum de facteurs distincts. Pour un mot et un entier , on note le nombre de facteurs distincts de de longueur , et le nombre de facteurs distincts de .
Question 23. Montrer que pour tout mot sur l'alphabet et tout entier , on a
Figure 5 - Le graphe .
On considère maintenant un entier fixé. On suppose qu'il existe un mot tel que chaque mot de longueur sur l'alphabet apparaisse exactement une fois comme facteur de . Par exemple, le mot 0001011100 a cette propriété pour . On montrera plus tard qu'il tel mot existe toujours.
Question 24. Déterminer la longueur d'un tel mot et que ce mot atteint le nombre maximum de facteurs distincts parmi les mots de longueur .
Il reste donc à montrer qu'il existe un mot tel que chaque mot de longueur apparaisse exactement une fois comme facteur de . Pour cela, on va considérer des cycles eulériens dans un graphe orienté particulier, appelé graphe de de Bruijn.
Un graphe orienté est dit fortement connexe si, pour toute paire de sommets et , il existe un chemin de à .
Un graphe orienté est dit eulérien si, pour tout sommet , le degré entrant de est égal au degré sortant de . Un cycle eulérien dans un graphe orienté est un cycle passant une et une seule fois par chaque arête de .
Question 25. Montrer que tout graphe eulérien ayant au moins une arête admet un cycle , et que le graphe privé des arêtes du cycle est encore eulérien.
Question 26. En déduire qu'un graphe orienté fortement connexe est eulérien si et seulement s'il contient un cycle eulérien.
Finalement, on considère le graphe orienté dont
les sommets sont tous les mots à lettres sur l'alphabet ,
les arêtes sont les couples ( ) pour tous les mots à lettres sur l'alphabet .
Par exemple, le graphe orienté est représenté à la figure 5 .
Question 27. Montrer que le graphe admet un cycle eulérien. En déduire qu'il existe un mot tel que chaque mot de longueur apparaisse exactement une fois comme facteur de .
X ENS Option Informatique MP 2021 - Version Web LaTeX | WikiPrépa | WikiPrépa
