ENS Informatique Fondamentale (Maths Info) MP 2016Sujet et corrigé

Pas encore noté

Explorer les annales

BanqueX-ENS Année2016 FilièreMP MatièreMathématiques-Informatique

Annales X-ENS MP Mathématiques-Informatique X-ENS MP 2016 MP Mathématiques-Informatique Mathématiques-Informatique 2016

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Lire en ligne LaTeX Word

Rapport du jury : non disponible

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

COMPOSITION D'INFORMATIQUE-MATHÉMATIQUES - (ULCR)

(Durée : 4 heures)

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.

Langage d'une Chaîne de Markov

Soit

N

un entier positif. On appelle chaîne de Markov une matrice

M

ℝ^(N, N)

telle que :

pour toute entrée $i, j : 1 \leq i, j \leq N, M(i, j) \in [0, 1]$ et
pour toute colonne $1 \leq j \leq N, \sum_(i = 1)^N M(i, j) = 1$ .

Une distribution est un vecteur colonne

X \in [0, 1]^N

avec

\sum_(i = 1)^N X(i) = 1

, où

X(i)

est la ième coordonnée de

X

. On note Distrib l'ensemble des distributions.

Soit

X

une distribution. On s'intéresse à la première coordonnée

(M^k \cdot X)(1)

de l'application de

M^k

X

, et ce pour tout

k \in ℕ

. Etant donné un réel

τ

dans

[0, 1]

, on veut savoir si

(M^k \cdot X)(1) \leq τ

ou non. On notera

A

(Above) pour

(M^k \cdot X)(1) \geq τ

, et

B

(Below) pour

(M^k \cdot X)(1) < τ

, où

A, B

sont deux lettres distinctes.

Formellement, on définit la suite

(σ_k^(M, X, τ))_(k \in ℕ)

avec :

- σ_k^(M, X, τ) = Asi(M^k \cdot X)(1) \geq τ

, et

- σ_k^(M, X, τ) = Bsi(M^k \cdot X)(1) < τ

.
On appelle

(σ_k^(M, X, τ))_(k \in ℕ)

la trajectoire de

M

à partir de

X

. On peut voir

(σ_k^(M, X, τ))_(k \in ℕ)

comme un mot infini sur l'alphabet

{A, B}

Par exemple, prenant

τ = 1/2

, la trajectoire à partir de

X_0 = (1/0)

M_0 = (1/4, 3/4; 3/4, 1/4)

est

ABAB\dots

, c'est à dire

σ_k^(M, X_0, 1/2) = A

pour tout

k

pair, et

σ_k^(M, X_0, 1/2) = B

pour tout

k

impair. En effet,

(M^0 \cdot X)(1) = 1, (M^1 \cdot X)(1) = 1/4, (M^2 \cdot X)(1) = (10)/(16), \dots

Plus généralement, on s'intéressera au langage

L(M, τ)

d'une chaîne de Markov

M

, c'est à dire à l'ensemble des trajectoires

(σ_k^(M, X, τ))_(k \in ℕ)

à partir de toutes les distributions

X

possibles :

L(M, τ) = {(σ_k^(M, X, τ))_(k ∈ ℕ)|X

une distribution

}

Par exemple,

L(M_0, 1/2) = {w, w^′, w^(′′)}

avec :

la suite $w$ définie par $w = (a_k)_(k \in ℕ)$ avec $a_k = A$ pour $k$ pair et $a_k = B$ pour $k$ impair (c'est à dire $w = ABABAB\dots$ ).
la suite $w^'$ définie par $w^' = (b_k)_(k \in ℕ)$ avec $b_k = A$ pour $k$ impair et $b_k = B$ pour $k$ pair (c'est à dire $w = BABABA\dots$ ).
la suite $w^('')$ définie par $w^('') = (c_k)_(k \in ℕ)$ avec $c_k = A$ pour tout $k \in ℕ$ (c'est à dire $w = AA\dots$ ).

Ce sujet comprend 8 pages au total, 4 parties, et 13 questions. Les résultats d'une question pourront être admis dans la suite du sujet.

PARTIE I. Préliminaires.

Question 1 Montrer que pour toute chaîne de Markov

M

et toute distribution

X

M \cdot X

est une distribution.

On veut décrire un algorithme pour calculer l'ensemble

I

des indices

i

tel qu'il existe

ℓ

avec pour tout

n \geq ℓ

, pour toute distribution initiale

X_0

, on a

(M^n \cdot X_0)(i) =

0 . Pour cela, on va considérer le graphe orienté suivant :

G_M = (V, E)

avec l'ensemble de sommets

V = {1, \dots, N}

et l'ensemble des arêtes

(i, j) \in E

si et seulement si

M(i, j) \neq 0

Question 2 Soit

i \in V

un sommet du graphe

G_M

. Considérons les composantes fortement connexes de

G_M

.
a) Supposons que la composante fortement connexe à laquelle appartient

i

ait au moins un autre élément

j

. Montrer que

i \notin I

.
b) Supposons que la composante fortement connexe à laquelle appartient

i

est le singleton

{i}

et que

(i, i) \in E

. Montrer que

i \notin I

.
c) Caractériser

I

grâce aux composantes fortement connexes de

G_M

On va donc maintenant s'interresser à un algorithme pour calculer les composantes fortement connexes d'un graphe orienté.

Question 3 La première méthode considérée est assez naïve. Il s'agit pour chaque sommet

v \in V

de calculer la liste

L_v

des sommets accessibles à partir de

v

. Pour les algorithmes, on demande une explication claire de leur fonctionnement, permettant de se convaincre que les programmes que vous écrirez sont corrects.
a) Donner un algorithme pour obtenir l'ensemble des composantes fortement connexes à partir de

(L_v)_(v \in V)

. On attend en sortie de l'algorithme une liste de listes, listant les composantes connexes, chaque composante connexe étant représentée par la liste de ses éléments (dans un ordre quelconque).
b) En déduire un algorithme pour calculer l'ensemble

I

. Montrer que la complexité de cette approche pour calculer

I

à partir de (

E, V

) est un

O(|E|^k)

pour un

k

que vous déterminerez. Notez que

|V| = N \leq |E|

pour

|V|

le nombre de sommets et

|E|

le nombre d'arêtes.

Afin d'optimiser la complexité de recherche des composantes fortement connexes, on va s'appuyer sur l'algorithme de Tarjan donné ci-dessous, basé sur la recherche en profondeur. Il y a 3 tableaux globaux

b, p, q

indexés par les sommets. D'abord, pour chaque sommet

v

, l'entrée

b(v) \in {0, 1}

mentionne si le sommet

v

a été vu (entrée 1) ou non (entrée 0 ) par la recherche auparavant. Ensuite, pour chaque sommet

v

présent sur la pile de recursion,

p(v) \in ℕ

donne explicitement sa hauteur de pile (hauteur 1 pour le premier sommet de la pile, les sommets qui ne sont pas sur la pile ont hauteur 0

)

. Enfin, pour chaque sommet

v

, l'entrée

q(v)

donne le

q(v) = p(w) > 0

minimal avec

w

un sommet sur la pile visité par Profondeur à partir de

v

. La valeur 0
est reservée pour les sommets

v

qui ne sont pas sur la pile. Les noms

v

des sommets sont des entiers de 1 à

N

. Enfin, on a une liste

cc

globale qui contient les sommets courants de la prochaine composante connexe qui va être affichée. L'algorithme est le suivant. On admettra qu'il affiche, une par une, les composantes fortement connexes (ligne 14) :

SousFonction Profondeur (v)
    Pour tout successeur $w$ de $v$
        Si $(p(w) \neq 0) \quad \%$ c'est à dire $w$ est sur la pile
            $q(v):=\min (q(v), p(w))$
        FinSi
        Si $(b(w)=0) \% \% w$ n'a pas encore été visité
            $p(w):=p(v)+1$ et $q(w):=p(w)$
            Appel Profondeur ( $w$ )
            $q(v):=\min (q(v), q(w))$
        FinSi
    FinPourTout
    Ajouter $v$ à $c c$
    $\mathrm{Si} \quad(q(v)=p(v))$
        Afficher $c c$
        $c c:=$ liste_vide
    FinSi
    $p(v):=0, \% \% v$ n'est plus sur la pile
EndSousFonction Profondeur
Fonction Tarjan ()
    $c c$ la liste vide, $b, p, q$ tableaux de 0
        $v:=1$, \% \% on initialise au premier sommet
        TantQue ( $\mathrm{b}(\mathrm{v})=0$ )
            $b(v):=1, \quad p(v):=1$ et $q(v):=1$
            Call Profondeur (v)
            TantQue $(b(v)=1$ et $v<N)$
                $v:=v+1$
            FinTantQue $\% \% v$ est le plus petit avec $b(v)=0$ ou $v=N$
        FinTantQue
EndFonction Tarjan

c) Montrer que la complexité pour calculer

I

à partir de (

E, V

) et en utilisant l'algorithme de Tarjan est un

O(|E|^(k^'))

pour un

k^'

que vous déterminerez.

PARTIE II. Exemples de chaînes de Markov.
Considérons les chaînes de Markov suivantes :

M_1 = (1, 0; 0, 1), M_2 = (0, 1; 1, 0), M_3 = (0, 6, 0, 6; 0, 4, 0, 4) et M_4 = (0, 6, 0, 1, 0, 3; 0, 3, 0, 6, 0, 1; 0, 1, 0, 3, 0, 6)

Question 4 Calcul du langage de

M_1, M_2, M_3

.
Le cas de

M_4

est repoussé à la partie III.
a. Quel est le langage

L(M_1, 1/2)

?
b. Quel est le langage

L(M_2, 1/2)

?
c. Quel est le langage

L(M_3, 1/2)

Question 5 Calcul des valeurs propres de

M_1, M_2, M_3, M_4

.
a. Donner les valeurs propres ainsi que leur multiplicité pour

M_1

. Fournir une famille de

k

vecteurs propres indépendants pour chaque valeur propre de multiplicité

k

.
b. Donner les valeurs propres ainsi que leur multiplicité pour

M_2

. Fournir une famille de

k

vecteurs propres indépendants pour chaque valeur propre de multiplicité

k

.
c. Donner les valeurs propres ainsi que leur multiplicité pour

M_3

. Fournir une famille de

k

vecteurs propres indépendants pour chaque valeur propre de multiplicité

k

.
d. Verifier que les trois valeurs propres de

M_4

sont :

1, ρ_0 e^(iθ_0), ρ_0 e^(- iθ_0)

avec

ρ_0 = \sqrt(19)/10

θ_0 = arccos(4/\sqrt(19))

, avec des vecteurs propres associées

(1/3; 1/3; 1/3), (- 1 - \sqrt3i; - 1 + \sqrt3i; 2), (- 1 + \sqrt3i; - 1 - \sqrt3i; 2)

Question 6 Soit

M

une chaîne de Markov de

ℝ^(N, N)

.
a. Montrer que toutes les valeurs propres

v

M

satisfont

|v| \in [0, 1]

On pourra considérer la matrice transposée de

M

.
b. Montrer que 1 est valeur propre de

M

PARTIE III. Base de vecteurs propres.

Soit

M

une chaîne de Markov de

ℝ^(N, N)

. Supposons que

M

ait exactement

N

valeurs propres distinctes que l'on décrira sous forme de coordonnées polaires :

ρ_1 e^(iθ_1), \dots, ρ_N e^(iθ_N)

, avec

ρ_j \in [0, 1]

pour tout

j \leq N

. On classe les valeurs propres avec

ρ_1 \geq \dots \geq ρ_N \geq 0

. Soit

V_1, \dots, V_N

des vecteurs propres correspondants, i.e.

V_j

est non nul et

M \cdot V_j = ρ_j e^(iθ_j)V_j

pour tout

j

avec

1 \leq j \leq N

Question 7 Soit

X

une distribution de

ℝ^N

τ \in [0, 1]

. Montrer qu'il existe

α_0, \dots, α_N \in ℂ^(N + 1)

tels que, pour tout

k \in ℕ

σ_k^(M, X, τ) = A si et seulement si α_0 + \sum_(j = 1)^N α_j ρ_j^k e^(ikθ_j) \in ℝ^+

Question 8 Montrer que pour

M_4

donnée à la partie précedente,

τ_4 = 1/3

X_4 = (1/4; 1/4; 1/2)

, on a

(M_4^k \cdot X_4)(1) \geq τ_4

si et seulement si :

(\sqrt3sin(kθ_0) - cos(kθ_0)) \geq 0, avec θ_0 = arccos(4/\sqrt(19))

On admettra pour la Question 9 que pour tout

ℓ

entier non nul, l'ensemble

{rℓθ_0 mod2π|r ∈ ℕ}

est dense dans

[0, 2π[

On dit qu'une suite

(σ_n)_(n \in ℕ)

avec

σ_n ∈ {A, B}

pour tout

n \in ℕ

, est ultimement périodique si il existe un entier non nul

P \in ℕ∖{0}

qu'on appellera la période et un indice

ℓ \in ℕ

avec

σ_(ℓ + r + Pk) = σ_(ℓ + r)

pour tout

r \in {0, \dots, P - 1}

, et tout

k \in ℕ

Question 9 On considère la suite

(σ_k^(M_4, X_4, τ_4))_(k \in ℕ)

de la partie précédente. Montrer que

(σ_k^(M_4, X_4, τ_4))_(k \in ℕ)

n'est pas ultimement périodique.

Il est donc difficile de décrire explicitement même une trajectoire de la chaîne de Markov. On va s'intéresser dans la suite à un cas où on peut décrire explicitement non seulement chaque trajectoire, mais aussi l'ensemble de ces trajectoires.

PARTIE IV. Chaîne de Markov avec des valeurs propres dans

ℝ^+

On veut maintenant calculer le language de la chaîne de Markov

M_5

suivante, associée à

τ_5 = 5/(12)

M_5 = (0, 8, 0, 1, 0, 2; 0, 1, 0, 8, 0, 1; 0, 1, 0, 1, 0, 7)

Question 10

a. Calculer les valeur propres de

M_5

. Sont-elles réelles positives? On note

ρ_1, ρ_2, ρ_3

les 3 valeurs propres de

M_5

, avec

ρ_1 = 1

ρ_2 > ρ_3

. Determiner des vecteurs propres

V_1, V_2, V_3

respectifs associés, avec

V_1

une distribution.
b. Soit

X_0 = (1; 0; 0)

X_1 = (1/3; 1/3; 1/3)

. Prenant

X = X_0

puis

X = X_1

, donner des valeurs explicites pour

α_1(X), \dots, α_3(X) :

Distrib

\mapsto ℝ^N

tels que

σ_k^(X, τ_5) = A

si et seulement si

\sum_(j = 1)^3 α_j(X)ρ_j^k \geq 0

pour tout

k \in ℕ

.
c. Quelles sont les trajectoires

(σ_k^(M_5, X_0, τ_5))_(k \in ℕ)

(σ_k^(M_5, X_1, τ_5))_(k \in ℕ)

associées à

X_0

X_1

Question 11 Soit

λ \in [0, 1]

. On définit

X_λ = λX_1 + (1 - λ)X_0

.
a. Montrer que

α_i(X_λ) = λα_i(X_1) + (1 - λ)α_i(X_2)

.
b. Soit

λ \in [0, 1[

(en particulier

X_λ \neq X_1

). Montrer qu'il existe

ℓ_λ \in ℕ

tel que

(σ_k^(X_λ, τ_5))_(k \in ℕ)

est

B

pour tout

0 \leq k < ℓ_λ

, puis

A

pour tout

k \geq ℓ_λ

Maintenant que nous avons démontré que chaque trajectoire était explicitement descriptible de manière finie, on va s'intéresser au langage de

M_5

pour les distributions initiales dans l'ensemble

{X_λ|λ ∈ [0, 1]}

Question 12

a. Montrer que pour tout

x \in [1, + \infty[

, il existe

μ_x \in ]0, 1[

avec

μ_x\sum_(j = 1)^N α_j(X_0)ρ_j^x + (1 - μ_x)\sum_(j = 1)^N α_j(X_1)ρ_j^x = 0

b. Montrer que pour tout

ℓ^' \in ℕ

, il existe

λ \in [0, 1]

avec

σ_k^(M_5, X_λ, τ_5) = B

pour tout

k \leq ℓ^'

σ_k^(M_5, X_λ, τ_5) = A

pour tout

k > ℓ^'

.
c. Existe-t-il

ℓ \in ℝ

tel que

ℓ_λ < ℓ

pour tout

λ \in [0, 1]

?
d. Décrire le langage de

M_5

pour les distributions initiales dans l'ensemble

{X_λ|λ ∈ [0, 1]}

, c'est à dire l'ensemble des suites

{(σ_k^(M_5, X_λ, τ_5))_(k ∈ ℕ)|λ ∈ [0, 1]}

On propose maintenant de traiter un cas plus général.
On prend

N = 3

. Soit

M

une chaîne de Markov de

ℝ^3

ayant des valeurs propres toutes réelles positives et distinctes deux à deux :

1 = ρ_1 > ρ_2 > ρ_3 \geq

0 . Soit

V_1

une distribution, vecteur propre associé à

ρ_1

, et

V_2, V_3

deux vecteurs propres associés respectivement à

ρ_2, ρ_3

. Pour toute distribution

X

, on admettra qu'il existe

α_0(X), α_1(X), α_2(X), α_3(X)

des réels tels que

α_0(X) + α_1(X)ρ_1^k + α_2(X)ρ_2^k + α_3(X)ρ_3^k \geq 0

si et seulement si

σ_k^(M, X, τ) = A

Soit

τ

tel que

α_0(X) = α_1(X) = 0

pour toute distribution

X

. C'est le cas dès que

τ = V_1(1)

. Soit

X_0, X_1

deux distributions avec

σ_k^(M, X_0, τ) = A

σ_k^(M, X_1, τ) = B

pour tout

k \geq 0

. On pose

X_λ = λX_1 + (1 - λ)X_0

pour tout

λ \in [0, 1]

Question 13 Quel est le langage

{(σ_k^(M, X_λ, τ))_(k ∈ ℕ)|λ ∈ [0, 1]}

?
On peut caractériser le langage de toute chaîne de Markov ayant des valeurs propres distinctes deux à deux et réelles positives, mais cela ne sera pas demandé ici.

Pas de description pour le moment

Commentaires• ENS Informatique Fondamentale (Maths Info) MP 2016

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...