X/ENS Informatique A MP 2021

Thème de l'épreuve Facteurs dans les mots binaires
Principaux outils utilisés programmation OCaml, fonctions récursives, arbres, chaînes de caractères, programmation dynamique, graphes, complexité
Mots clefs de Bruijn, suffixe, facteur, bio-informatique, peigne, arbre binaire, mots, accumulateur, graphe eulérien

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                                

Rapport du jury

(télécharger le PDF)
              

Énoncé obtenu par reconnaissance optique des caractères


ECOLE POLYTECHNIQUE
ECOLES NORMALES SUPERIEURES
CONCOURS D'ADMISSION 2021

MARDI 13 AVRIL 2021
14h00 - 18h00
FILIERE MP

-

Epreuve n° 4

INFORMATIQUE 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

{0, 1}. 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 ecaces.

Mots.

mot m est une suite nie m0 m1 . . . m`-1 de lettres de l'alphabet {0, 1}. Sa longueur `
`(m) et sa lettre d'indice i est notée mi pour 0  i  `(m)-1. Le mot vide, de longueur 0,
. On note c` le mot de longueur ` formé de ` caractères c.
Un

est notée
est noté

m = m0 m1 . . . m`(m)-1
0 =
leur concaténation comme le mot mm
0
0
gueur `(mm ) = `(m) + `(m ).
Pour

Pour

deux

mots

0  i  j  `(m),

on note

m[i..j[

m0 = m00 m01 . . . m0`(m0 )-1 , on dénit
m0 m1 . . . m`(m)-1 m00 m01 . . . m0`(m0 )-1 de lon-

et

le mot

mi mi+1 . . . mj-1 ,

facteur de m.
0  i = j  `(m).
m[i..`(m)[) et on le

qui est appelé

On note que le mot vide est un facteur de n'importe quel mot, obtenu pour
Un

préxe

(resp.

suxe )

m[..j[

(resp.

m[i..[).

note

de

m

est un facteur de la forme

· F(m) = {m[i..j[ | 0  i  j  `(m)}
· P(m) = {m[..j[ | 0  j  `(m)}
· S(m) = {m[i..[ | 0  i  `(m)}

Arbres binaires.

Un

m[0..j[

(resp.

On note

soit comme l'arbre vide, noté

·

soit comme un

l'ensemble des préxes de

l'ensemble des suxes de

arbre binaire

·

l'ensemble des facteurs de

m;

m;

m.

est déni récursivement de la manière suivante :

V,

qui ne contient aucun n÷ud ;

n÷ud, noté N (x, g, d) et appelé racine, où x est l'information stockée dans
sous-arbre gauche et d est un arbre binaire appelé
sous-arbre droit.
le n÷ud,

On note

g

n(a)

est un arbre binaire appelé

le nombre de n÷uds et

n(V ) = h(V ) = 0,

Langage OCaml.
partir de la liste vide
est l'élément

x

h(a)

la hauteur d'un arbre binaire

n(N (x, g, d)) = 1 + n(g) + n(d)

et

a,

dénis par

h(N (x, g, d)) = 1 + max(h(g), h(d)).

Ce sujet utilise les listes et les tableaux d'OCaml. Une liste est construite à

[]

et de la construction

et dont la queue est la liste

formée des éléments de la liste

l

l.

x :: l

qui renvoie une nouvelle liste dont la tête

L'appel de

en ordre inverse.

1

List.rev l

renvoie une nouvelle liste,

On peut créer des tableaux avec les deux fonctions
de

Array.make n x crée un tableau
Array.of_list l crée un

L'appel de

de taille

n

Array.make

et

Array.of_list.

L'appel

dont toutes les cases contiennent la valeur

tableau contenant, dans l'ordre, les éléments d'une liste

x.
l.

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 modie
avec tab.(i) <- v. Les cases d'un tableau sont numérotées à partir de 0. La fonction 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érier que les tableaux passés en arguments ne contiennent que des 0 et des 1. Complexité. Par complexité (en temps) d'un algorithme A on entend le nombre d'opérations élémentaires (comparaison, addition, soustraction, multiplication, division, aectation, test, etc.) A dans le cas le pire. Lorsque la complexité dépend d'un ou plu0 , · · · , r-1 , on dit que A a une complexité en O(f (0 , · · · , r-1 )) s'il existe C > 0 telle que, pour toutes les valeurs de 0 , · · · , r-1 susamment grandes

nécessaires à l'exécution de
sieurs paramètres
une constante

(c'est-à-dire plus grandes qu'un certain seuil), pour toute instance du problème de paramètres

0 , · · · , r-1 ,

la complexité est au plus

Dépendances.

C · f (0 , · · · , r-1 ).

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 ni de mots. Un arbre de mots est un arbre binaire dont chaque n÷ud contient un

a représente un ensemble ni de mots, noté M(a), déni comme suit.
a est vide, alors M(a) est l'ensemble vide. Si l'arbre a est de la forme N (b, a0 , a1 ),
M(a) est l'ensemble des mots suivants :

booléen. Un arbre de mots
Si l'arbre
alors

true ;

·

le mot vide

·

les mots de la forme

0m

pour

m  M(a0 ) ;

·

les mots de la forme

1m

pour

m  M(a1 ).

si le booléen

b

est

Autrement dit,

M(a) 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
2

on va à droite. Ainsi, l'arbre

a1

T

Dans tous les dessins, on utilise

T

(resp.

F)

pour le booléen

F

T

F

F

F
T

T

a1

(resp.

F

F

T

T

T

true

F

F

F

M(a1 ) = {, 10, 11}.
false).

de la gure 1 représente l'ensemble de mots

F

F
T

F
F

T

T

a2

F
F
T

T
T

a3

T

a4

Figure 1  Des arbres de mots.
On note qu'un ensemble de mots peut être représenté par une innité d'arbres de mots. En
eet, il sut de remplacer un arbre vide par un n÷ud

N (false, V, V )

pour obtenir un autre

arbre de mots représentant le même ensemble de mots. Par exemple, l'arbre vide
un n÷ud

réduit

est

N (false, V, V )

V

et l'arbre à

représentent tous les deux l'ensemble vide. On dit qu'un arbre de mots

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.
Question 2.

a2 de la gure
{, 00, 010, 1, 110, 111}.

Donner l'ensemble de mots représenté par l'arbre

arbre de mots réduit représentant l'ensemble de mots

1. Dessiner un

Montrer que, pour tout ensemble ni de mots, il existe un unique arbre de mots

réduit qui le représente.

Dans la suite, on note

M(A(M )) = M
de mots réduit

A(M )

l'arbre de mots réduit de l'ensemble ni de mots

pour tout ensemble ni de mots

M

et inversement

M.

On a donc

A(M(a)) = a pour tout arbre

a.

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

a1

de la gure 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 enn  0 et qui renvoie l'arbre de mots réduit représentant tous les mots de la forme 0p 1q avec
p + q = n. L'arbre a3 de la gure 1 donne un exemple d'un tel arbre pour n = 3.
tier

Question 4.
entiers

k  0

Écrire une fonction
et

n  0

k_uns: int -> int -> am

qui reçoit en arguments deux

et qui renvoie l'arbre de mots réduit représentant tous les mots de

3

longueur au plus

n

et contenant exactement

exemple d'un tel arbre pour

k=2

et

k

caractères 1. L'arbre

a4

de la gure 1 donne un

n = 3.

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

a et renvoie le
n(a), mais il n'est

compter: am -> int qui reçoit en argument
M(a). La complexité en temps doit

mots

cardinal de l'ensemble

en

pas demandé de la justier.

Question 6.

chercher: am -> mot -> bool qui reçoit
détermine si m appartient à l'ensemble M(a).

Écrire une fonction

arbre de mots

a

et un mot

temps doit être linéaire en

Question 7.

m et
`(m),

un arbre de
être linéaire

en arguments un
La complexité en

mais il n'est pas demandé de la justier.

enumerer: am -> mot list qui reçoit en argument un arbre
M(a) sous la forme d'une liste. La complexité en
P
taille du résultat
mM(a) `(m). On justiera la complexité.

Écrire une fonction

de mots réduit

a

et renvoie l'ensemble de mots

temps doit être linéaire en la

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 t dont la racine est le n÷ud courant,

et qui renvoie la liste acc complétée avec tous les mots de M(t) auxquels on a ajouté le préxe
donné par la liste pref.

Question 8.

Écrire une fonction

de mots réduit

M(a)  {m}.

a

et un mot

m

ajouter: am -> mot -> am qui reçoit en arguments un arbre

et renvoie l'arbre de mots réduit représentant l'ensemble de mots

La complexité en temps doit être linéaire en

`(m),

mais il n'est pas demandé de la

justier.

A(M ) correspondent à l'ensemble
{m[..i[ | m  M et 0  i  `(m)}. En eet, les mots donnés par les chemins de la racine
aux n÷uds de A(M ) (en utilisant 0 quand on va à gauche et 1 quand on va à droite) sont
précisément les préxes d'au moins un mot de M .
Pour la suite, on remarque que les n÷uds de l'arbre de mots

de mots

Partie II. Arbre des suxes
m et on dénit l'arbre des suxes de m, noté AS(m),
suxes de m, c'est-à-dire AS(m) = A(S(m)).

Dans cette partie, on considère un mot
comme l'arbre de mots réduit de tous les

4

Question 9.

Donner l'arbre

Question 10.

am -> mot

pour le mot

AS(m)

AS(m) ? En déduire une fonction retrouver_mot:
de l'arbre AS(m) de ses suxes. La complexité en

Quelle est la hauteur de l'arbre

m à partir
n(AS(m)), mais il

qui retrouve le mot

temps doit être linéaire en

Question 11.

m = 1011.

n'est pas demandé de la justier.

AS(m) correspondent aux facteurs distincts
AS(m) est au moins linéaire et au plus
quadratique en `(m). Montrer que ces bornes sont atteintes, c'est-à-dire que pour tout entier `,
2
il existe un mot m de longueur ` tel que l'arbre AS(m) a ` + 1 n÷uds (resp. au moins C` n÷uds
où C est une constante indépendante de ` que l'on explicitera).
de

m.

Montrer que les n÷uds de l'arbre

En déduire que le nombre de n÷uds de l'arbre

Des bornes plus précises sur le nombre de facteurs distincts de

m

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 suxes d'un mot

m

xé, appelée

arbre des facteurs.

Cette structure est

basée sur les deux idées suivantes :

·

dans l'arbre de suxes

AS(m),

false

un chemin formé de n÷uds dont le booléen est

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

(p, q)

qui désigne le facteur

m[p..q[.

On considère donc un arbre binaire dont chaque n÷ud contient deux entiers

0  p  q  `(m)

a
M(a)

et un booléen. Un tel arbre

a est vide, alors
N (p, q, b, a0 , a1 ), alors M(a) est l'ensemble

ni comme suit. Si l'arbre
forme

les mots de la forme

m[p..q[0f

pour

f  M(a0 ) ;

·

les mots de la forme

m[p..q[1f

pour

f  M(a1 ).

L'arbre

a

est

est un arbre des facteurs du mot

de tous les suxes de

m.

m

si l'ensemble

On dit qu'un arbre des facteurs est

au moins un des sous-arbres est vide contient le booléen

dé-

est de la

M(a)

réduit

true.

est exactement l'ensemble

dès lors que tout n÷ud dont

Ainsi, l'arbre de la gure 2 est

10110100. Dans tous les dessins, on représente l'information
N (p, q, b, a0 , a1 ) par p..q(T) si b est true et p..q(F) si b est false.

un arbre des facteurs réduit du mot
contenue dans un n÷ud

que

true ;

·

b

a

q tels
M(a)

des mots suivants :

le mot

si le booléen

et

est l'ensemble vide. Si l'arbre

·

m[p..q[

p

représente l'ensemble des mots

5

8..8(T)
8..8(T)
8..8(T)

6..6(F)
6..6(F)

7..8(T)

7..7(F)

4..8(T)

8..8(T)

4..8(T)
6..6(F)

7..8(T)

4..8(T)

Figure 2  Un arbre des facteurs réduit du mot 10110100.
Attention : Un arbre des facteurs du mot m n'est pas un arbre de mots de tous les facteurs de m,
mais une représentation compacte de l'arbre des suxes de m. On parle d' arbre des facteurs car
il permet de manipuler facilement tous les facteurs de m, comme on le verra plus loin.

Question 12.

Pour chaque arbre

a

de la gure 3, donner l'ensemble

m = 01001,

d'un arbre des facteurs pour le mot

5..5(T)
5..5(T)

2..5(T)

et indiquer s'il s'agit

5..5(T)

4..4(F)
4..5(T)

M(a)

et s'il est réduit.

3..5(T)

4..4(F)
4..5(T)

5..5(T)
5..5(T)

5..5(T)

4..4(F)

3..5(T)

4..5(T)

3..5(T)

a5

5..5(T)

5..5(T)
3..5(T)

a6

3..5(F)
4..5(T)

a7

Figure 3  Des arbres.
On peut se convaincre facilement qu'il existe toujours au moins un arbre des facteurs pour

m.

tout mot

En eet, il sut de construire l'arbre des suxes

d'ajouter dans chaque n÷ud la paire d'entiers

(0, 0).

AS(m)

de

m

de la partie II et

Pour obtenir un arbre des facteurs réduit,

il sut 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

m est compact en comparaison

de l'arbre des suxes de la partie II qui pouvait être quadratique comme observé à la question 11.

Question 13.
n÷uds si
le mot

m

est

Soit

0`

a

ou

un arbre des facteurs réduit d'un mot

1`

pour

`  0.

m.

On note que l'arbre

En supposant que les deux lettres

0

et

1

a

a

`+1

apparaissent dans

m,

1. montrer que le nombre de n÷uds de

a

ayant au moins un sous-arbre vide est au plus

a en fonction de `(m), et montrer
` > 0, il existe un mot de longueur `

2. en déduire une borne supérieure du nombre de n÷uds de
que cette borne est atteinte (c'est-à-dire que pour tout

dont un arbre des facteurs a précisément ce nombre de n÷uds).

6

`(m),

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

cette partie. On pourra supposer qu'il est dans une variable globale

m

est xé dans

m.

Question 14.

Écrire une fonction nb_facteurs: af -> int qui reçoit en argument un arbre
a du mot m et renvoie le nombre de facteurs distincts de m. La complexité en temps
linéaire en n(a), mais il n'est pas demandé de la justier.

des facteurs
doit être

Question 15. Écrire une fonction plpc: mot -> int -> int -> mot -> int -> int -> int
plus long préxe commun) qui prend en arguments un mot m1 avec deux in0  p  q  `(m1 ) et un mot m2 avec deux indices 0  i  j  `(m2 ), et qui renvoie
plus grand k tel que p + k  q et i + k  j et m1 [p..p + k[ = m2 [i..i + k[. La complexité en

(pour
dices
le

temps doit être linéaire en le résultat, mais il n'est pas demandé de la justier.

Question 16.

facteur: af -> mot -> bool qui reçoit en arguments un
arbre des facteurs a du mot m et un mot f et détermine si f est un facteur de m. La complexité
en temps doit être linéaire en `(f ). On justiera la complexité.

Question 17.

Écrire une fonction

facteurs: af -> mot list qui reçoit en argument un arbre
a du mot m et renvoie l'ensemble des facteurs F(m) sous la forme d'une liste.

Écrire une fonction

des facteurs réduit

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

P

f F(m) `(f ). On justiera la complexité.

On montre maintenant comment construire un arbre des facteurs réduit pour le mot

m. Pour

m,

dans un

cela, on part de l'arbre vide et on ajoute successivement tous les suxes du mot
ordre arbitraire. Un suxe

m[i..[

est ajouté à l'arbre courant

a

de la manière suivante :

N (i, `(m), true, V, V ),

·

si

a=V,

·

si

a = N (p, q, b, a0 , a1 ), on cherche le plus grand k tel que p + k  q
m[p..p + k[ = m[i..i + k[. On distingue alors deux cas :

on construit l'arbre

et

i + k  `(m)

et tel

que

si

p+k  af -> af ci0  i  `(m) et un arbre a en cours de construction
suxe m[i..[ à l'arbre a en suivant la procédure décrite

Compléter le code de la fonction

dessous, qui reçoit en arguments une position
et renvoie l'arbre obtenu en ajoutant le
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 *) ... 8 On donnera uniquement dans la copie le code correspondant à fonction plpc (* CAS 1 *) et (* CAS 2 *). La est celle décrite à la question 15. Partie IV. Application : plus long facteur répété facteurs répétés du mot m, c'est-à-dire aux tri(i, j, k) avec 0  i  i + k  `(m) et 0  j  j + k  `(m) tels que i 6= j et m[i..i + k[ = m[j..j + k[. On cherche la longueur maximale d'un facteur répété dans m. On Dans cette partie, on s'intéresse aux plets commence par un algorithme naïf. Question 20. dans m. plfr1: mot -> int

Écrire une fonction

reçoit en argument un mot

m

(pour plus long facteur répété) qui

non vide et renvoie la longueur d'un plus long facteur répété

La complexité en temps doit être

O(`(m)3 ),

mais il n'est pas demandé de la justier.

Pour améliorer la complexité de ce calcul, on utilise maintenant un algorithme de program-

0  i, j  `(m), on note c(i, j) la longueur du plus long suxe commun
m[0..i[ et m[0..j[. 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 p × q dont toutes les cases contiennent
la valeur x. Pour une matrice mat, on accède à l'élément (i, j) avec mat.(i).(j) et on le modie
avec mat.(i).(j) <- v. mation dynamique. Pour de Question 21. Écrire une fonction plfr2: mot -> int

La complexité en temps doit être

O(`(m)2 ),

m non
m en construisant la table des c(i, j).

qui reçoit en argument un mot

vide et renvoie la longueur d'un plus long facteur répété dans

mais il n'est pas demandé de la justier.

On suppose maintenant qu'on connaît un arbre des facteurs
les plus longs facteurs répétés dans le mot

m

a

du mot

m.

On observe que

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

q-p+1

Question 22.
facteurs réduit
dans

m.

Écrire une fonction

a

N (p, q, b, a0 , a1 )

à la profondeur.

d'un mot

m

plfr3: af -> int

qui reçoit en argument un arbre des

non vide et renvoie la longueur d'un plus long facteur répété

La complexité en temps doit être en

O(`(m)).

On justiera 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

m

0  k  `(m), on note fk (m) le nombre de facteurs
P`(m)
f (m) = k=0 fk (m) le nombre de facteurs distincts de m.

et un entier

longueur

k,

et

Question 23.

Montrer que pour tout mot

m

sur l'alphabet

{0, 1}

on a

fk (m)  min(2k , `(m) - k + 1).

9

distincts de

et tout entier

m

de

0  k  `(m),

100

110

000

010

101

001

111
011

Figure 5  Le graphe G4 .
On considère maintenant un entier
mot de longueur
exemple, le mot

k

xé. On suppose qu'il existe un mot

m

tel que chaque

k sur l'alphabet {0, 1} apparaisse exactement une fois comme facteur de m. Par
0001011100 a cette propriété pour k = 3. 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
exactement une fois comme facteur de
un graphe orienté particulier, appelé

G est
v à w.

Un graphe orienté
existe un chemin de

Un graphe orienté
au degré sortant de

v.

G

dit

eulérien
cycle eulérien

Question 26.

G

k

si, pour toute paire de sommets

si, pour tout sommet

v,

dans un graphe orienté

apparaisse

le degré entrant de

G

v

et

w,

v

est égal

il

est un cycle passant une et

G.

Montrer que tout graphe eulérien

et que le graphe

tel que chaque mot de longueur

fortement connexe

une seule fois par chaque arête de

Question 25.

m

Pour cela, on va considérer des cycles eulériens dans

graphe de de Bruijn.

est dit

Un

m.

`(m).

privé des arêtes du cycle

C

G ayant au moins une arête admet un cycle C ,

est encore eulérien.

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é

·

les sommets sont tous les mots à

·

les arêtes sont les couples
sur l'alphabet

mot

m

dont

lettres sur l'alphabet

{0, 1},

(m1 . . . mk-1 , m2 . . . mk ) pour tous les mots m1 . . . mk

à

k

lettres

{0, 1}.

Par exemple, le graphe orienté

Question 27.

k-1

Gk

G4

est représenté à la gure 5.

Montrer que le graphe

tel que chaque mot de longueur

Gk admet un cycle eulérien.
k apparaisse exactement une

10

En déduire qu'il existe un
fois comme facteur de

m.



Extrait du corrigé obtenu par reconnaissance optique des caractères



X/ENS Informatique optionnelle MP 2021
Corrigé
Ce corrigé est proposé par Benjamin Monmege (enseignant-chercheur à 
l'université) ; il a été relu par William Aufort (professeur en CPGE).

Ce sujet s'intéresse aux facteurs contenus dans des mots sur l'alphabet {0, 1},
surtout par le prisme algorithmique, pour calculer et stocker cet ensemble de 
facteurs
de manière concise et efficace, mais aussi d'un point de vue combinatoire pour 
exhiber
des mots maximisant le nombre de facteurs distincts. Cette étude des facteurs 
est
cruciale en bio-informatique avec l'étude du génome, qui est assimilable à de 
longs
mots sur un alphabet à quatre lettres ; les facteurs représentent alors des 
gènes. Une
autre application du même domaine consiste à rechercher des zones particulières 
de
molécules représentées par une suite d'acides aminés. Le sujet est composé de 
cinq
parties à traiter linéairement, même si le début de la partie IV et la partie V 
sont
indépendantes du reste.
· Dans la partie I, on introduit une structure de données arborescente 
permettant
de stocker un ensemble fini de mots. De nombreuses questions classiques de
programmation permettent de se familiariser avec cette structure.
· Cette structure est alors utilisée dans la partie II, plutôt courte, pour 
stocker
l'ensemble des suffixes d'un mot. On comprend alors que les noeuds de l'arbre
représentent les facteurs distincts contenus dans le mot m.
· La partie III introduit une nouvelle structure arborescente plus compacte,
l'arbre des facteurs. Pour cela, les noeuds de l'arbre contiennent désormais 
davantage d'informations (à savoir des facteurs du mot m). Il s'agit d'une 
partie
longue et plutôt délicate où il est important de bien comprendre les exemples
de l'énoncé.
· La partie IV s'intéresse au calcul de la longueur maximale d'un facteur 
apparaissant au moins en deux occurrences dans un mot fixé. Elle se compose
de trois questions proposant respectivement l'implémentation d'une méthode
naïve de complexité cubique, puis un algorithme de programmation dynamique
de complexité quadratique, et enfin une méthode linéaire une fois connu l'arbre
des facteurs du mot.
· Enfin, la partie V, davantage combinatoire, s'intéresse à produire un mot 
contenant un maximum de facteurs distincts. Pour cela, des graphes de de Bruijn
sont utilisés ainsi que la notion fort classique de cycle eulérien. Il s'agit 
d'une
partie sans programmation et tout à fait indépendante, qu'il fallait sans doute
prendre le temps de traiter le jour J.
Le sujet est plutôt progressif et bien écrit, avec beaucoup de programmation,
mais aussi un peu de combinatoire et de nombreuses questions où des exemples 
sont
demandés. Cela en fait un sujet varié pour travailler les chapitres 
d'algorithmes de
chaînes de caractères, et surtout d'arbres, et même de graphes dans la dernière 
partie.

Indications
Partie I
2 Se forger une intuition à l'aide du paragraphe précédant la question 1, puis 
réaliser une preuve plus formelle de l'existence et de l'unicité, par 
récurrence sur la
longueur maximale des mots de l'ensemble considéré.
3 Après avoir dessiné l'arbre demandé au brouillon, remarquer qu'il est composé 
de
« peignes droits » représentant l'ensemble singleton {1n }. En déduire une 
fonction
auxiliaire récursive qui construit l'arbre demandé ainsi que ces peignes.
4 Procéder par récurrence en distinguant le cas où l'un des arguments (ou les 
deux)
est nul.
5 Relier le cardinal de l'ensemble de mots représenté par un arbre de mots avec 
le
nombre de noeuds étiquetés par true.
6 S'inspirer des algorithmes de recherche dans un arbre binaire de recherche : 
il s'agit
de descendre le long d'une branche de l'arbre, guidé par le mot à rechercher.
Pour cela, utiliser une fonction auxiliaire récursive pour cela.
7 Pour justifier la complexité, procéder par récurrence pour la fonction 
auxiliaire
suggérée par l'énoncé et montrer que celle-ci est de l'ordre de

P
O 1 + (k + 1) ×
`(m)
mM(t)

où k est la longueur du préfixe.
8 Utiliser une méthode similaire à celle utilisée en question 6. Attention au 
cas où
la position correspondant au mot à insérer n'existe pas encore dans l'arbre.
Partie II
10 Relier la hauteur de l'arbre AS(m) et la longueur `(m) du mot m. En déduire
qu'on peut retrouver le mot m à partir de son arbre réduit en cherchant le noeud
le plus profond dans l'arbre, ce qu'on peut faire à l'aide d'une fonction 
auxiliaire récursive. Pour n'avoir à parcourir qu'une seule fois l'arbre et 
obtenir une
complexité linéaire, cette fonction auxiliaire peut renvoyer une paire composée
de la profondeur maximale et d'une liste représentant le mot associé au noeud
correspondant.
11 Utiliser la remarque de l'énoncé en fin de partie I. Pour montrer que les 
bornes
sont atteintes, considérer les mots 0` et 0` 1` .
Partie III
13 Pour la seconde partie de la question, montrer par récurrence forte que tout 
arbre
binaire possédant k > 0 feuilles possède au plus k -1 autres noeuds. Pour 
montrer
que la borne obtenue est atteinte, considérer le mot 1`-1 0.
14 Procéder de façon similaire à la fonction compter de la question 5.
15 Il est sans doute plus simple d'utiliser une boucle while qu'une fonction 
récursive.

16 Suivre le même principe qu'en question 6, en utilisant la fonction plpc de la
question 15. Pour la complexité, on peut utiliser, sans le prouver, le fait que 
la
fonction plpc est de complexité linéaire en son résultat.
17 Appliquer la méthode de la question 7 avec une fonction récursive auxiliaire 
similaire. Il pourra être utile de programmer par ailleurs une seconde fonction 
auxiliaire prenant en arguments l'accumulateur, la liste préfixe et deux 
positions p
et q du mot m et renvoyant l'accumulateur et le préfixe mis à jour à l'aide du
facteur m[p..q[.
19 Dans l'algorithme décrit dans l'énoncé, choisir « le bon ordre » ou « le bon 
sousarbre » se fait en regardant la première lettre du suffixe à insérer.
Partie IV
20 Procéder à l'aide de deux boucles imbriquées, en utilisant la fonction plpc 
de la
question 15.
21 Après avoir rempli la matrice des (c(i, j))06i,j6`(m) à l'aide d'une 
relation de
récurrence simple, noter que le résultat attendu peut en être extrait, puisque 
le
plus long facteur répété est le plus long suffixe commun à deux préfixes 
différents.
22 Utiliser une fonction auxiliaire récursive calculant la profondeur de 
l'arbre donné
en argument, dans le sens précisé par l'énoncé, et avec la convention que la 
profondeur d'un arbre vide ou d'une feuille vaut -1.
Partie V
24 Montrer que `(m) = 2k + k - 1. Pour la seconde partie de la question, il 
faut montrer que pour tout j  [[ 0 ; `(m) ]], le mot m maximise fj (m) parmi 
les mots de longueur `(m). Utiliser la formule de la question 23 en distinguant 
les cas j < k, j = k et j > k.
25 Produire un chemin partant du sommet source de l'arc dont on suppose 
l'existence, en montrant qu'on ne tombe jamais dans un cul-de-sac avant de 
finir par
revisiter un sommet déjà vu précédemment. Ce chemin contient un cycle (qui
emprunte au plus une fois chaque sommet du graphe).
26 En supposant que les graphes sont non vides dans cette question, montrer 
l'implication directe par récurrence forte sur le nombre d'arcs du graphe 
supposé
fortement connexe. Pour l'implication réciproque, exhiber une bijection entre 
les
arcs entrants et sortants d'un sommet fixé.
27 Utiliser la caractérisation de la question 26. À partir du cycle eulérien, 
construire
un mot m de longueur 2k + k - 1, conformément au résultat de la question 24.
Il s'agit ensuite de montrer que ce mot convient.

I. Arbres de mots
1 L'arbre a2 abrite trois noeuds étiquetés par T, ce qui implique que M(a2 ) 
contient
trois mots. Le mot codé par la feuille la plus à gauche est 00 puisqu'on 
emprunte
deux fois le sous-arbre gauche. La racine du sous-arbre droit code pour 1 et la 
feuille
la plus profonde représente le mot 101. Ainsi,
L'ensemble des mots représenté par l'arbre a2 est M(a2 ) = {00, 1, 101}.
Un arbre de mots réduit représentant l'ensemble de mots {, 00, 010, 1, 110, 111}
est le suivant :
T
F

T

T

F

F

T
2

T

T

On se forge une intuition avec le paragraphe précédant la question 1 :
deux arbres pour un même ensemble diffèrent par l'ajout successif de
noeuds N(false, V, V) représentant l'ensemble vide. On donne ci-dessous une
démonstration plus formelle de l'unicité, une telle preuve plus formelle 
utilisant une récurrence étant sans aucun doute attendue par les correcteurs, en
ce début de sujet.
Montrons par récurrence que la propriété
P(n) :

« Tout ensemble de mots, tous de longueur strictement inférieure à n, est 
représenté par un unique arbre de mots réduit. »

est vraie pour tout entier n  N.
· P(0) : le seul ensemble de mots, tous de longueur strictement inférieure à 0,
est l'ensemble vide. L'arbre V est un arbre réduit représentant cet ensemble.
Montrons par l'absurde que c'est le seul. En effet, si a est un arbre non vide
représentant l'ensemble vide, il possède au moins un noeud et tous ses noeuds
sont étiquetés par le booléen false, puisqu'un booléen true traduit la présence
d'un mot (vide ou non) dans l'ensemble. Ainsi, l'un des noeuds les plus profonds
(qui existe puisque l'arbre possède au moins un noeud et est fini) est étiqueté 
par
false et possède deux sous-arbre vides (sinon ce ne serait pas le plus profond) 
:
l'arbre a n'est donc pas réduit.
· P(n) = P(n + 1) : soit E un ensemble de mots, tous de longueur strictement
inférieure à n + 1. Par P(n), seul le cas d'un ensemble possédant au moins
un mot de longueur n + 1 reste à considérer. En particulier, l'ensemble E est
non vide. L'étiquette b de la racine d'un arbre représentant E est entièrement
déterminé par la présence, ou non, du mot vide  dans E. Notons ensuite
E0 = {m  {0, 1} | 0m  E}

et

E1 = {m  {0, 1} | 1m  E}

Par définition, tout arbre a représentant E est donc de la forme N(b, a0 , a1 )
avec a0 un arbre représentant E0 et a1 un arbre représentant E1 . Par P(n),
les ensembles E0 et E1 contenant des mots de longueur strictement inférieure
à n, il existe des uniques arbres de mots réduits a0 et a1 représentant 
respectivement E0 et E1 . Si E0 ou E1 est non vide, alors l'arbre a0 ou a1 est 
différent
de V et l'arbre N(b, a0 , a1 ) est donc également réduit, et c'est l'unique 
arbre