Version interactive avec LaTeX compilé

ENS Informatique Fondamentale (Maths Info) MP 2016

Notez ce sujet en cliquant sur l'étoile

0.0(0 votes)

🔗 Explorer

X-ENS MP X-ENS 2016 MP Maths Info Maths Info 2016

2025_08_29_94e1f5bff69bfd6ae15dg

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

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

telle que :

pour toute entrée et
pour toute colonne .

Une distribution est un vecteur colonne

avec

, où

est la ième coordonnée de

. On note Distrib l'ensemble des distributions.

Soit

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

de l'application de

, et ce pour tout

. Etant donné un réel

dans

, on veut savoir si

ou non. On notera

(Above) pour

, et

(Below) pour

, où

sont deux lettres distinctes.

Formellement, on définit la suite

avec :

, et

.
On appelle

la trajectoire de

à partir de

. On peut voir

comme un mot infini sur l'alphabet

Par exemple, prenant

, la trajectoire à partir de

est

, c'est à dire

pour tout

pair, et

pour tout

impair. En effet,

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

d'une chaîne de Markov

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

à partir de toutes les distributions

possibles :

une distribution

Par exemple,

avec :

la suite définie par avec pour pair et pour impair (c'est à dire ).
la suite définie par avec pour impair et pour pair (c'est à dire ).
la suite définie par avec pour tout (c'est à dire ).

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

et toute distribution

est une distribution.

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

des indices

tel qu'il existe

avec pour tout

, pour toute distribution initiale

, on a

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

avec l'ensemble de sommets

et l'ensemble des arêtes

si et seulement si

Question 2 Soit

un sommet du graphe

. Considérons les composantes fortement connexes de

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

ait au moins un autre élément

. Montrer que

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

est le singleton

et que

. Montrer que

.
c) Caractériser

grâce aux composantes fortement connexes de

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

de calculer la liste

des sommets accessibles à partir de

. 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

. 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

. Montrer que la complexité de cette approche pour calculer

à partir de (

) est un

pour un

que vous déterminerez. Notez que

pour

le nombre de sommets et

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

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

, l'entrée

mentionne si le sommet

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

présent sur la pile de recursion,

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

, l'entrée

donne le

minimal avec

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

. La valeur 0
est reservée pour les sommets

qui ne sont pas sur la pile. Les noms

des sommets sont des entiers de 1 à

. Enfin, on a une liste

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

à partir de (

) et en utilisant l'algorithme de Tarjan est un

pour un

que vous déterminerez.

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

Question 4 Calcul du langage de

.
Le cas de

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

?
b. Quel est le langage

?
c. Quel est le langage

Question 5 Calcul des valeurs propres de

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

. Fournir une famille de

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

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

. Fournir une famille de

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

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

. Fournir une famille de

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

.
d. Verifier que les trois valeurs propres de

sont :

avec

, avec des vecteurs propres associées

Question 6 Soit

une chaîne de Markov de

.
a. Montrer que toutes les valeurs propres

satisfont

On pourra considérer la matrice transposée de

.
b. Montrer que 1 est valeur propre de

PARTIE III. Base de vecteurs propres.

Soit

une chaîne de Markov de

. Supposons que

ait exactement

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

, avec

pour tout

. On classe les valeurs propres avec

. Soit

des vecteurs propres correspondants, i.e.

est non nul et

pour tout

avec

Question 7 Soit

une distribution de

. Montrer qu'il existe

tels que, pour tout

Question 8 Montrer que pour

donnée à la partie précedente,

, on a

si et seulement si :

On admettra pour la Question 9 que pour tout

entier non nul, l'ensemble

est dense dans

On dit qu'une suite

avec

pour tout

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

qu'on appellera la période et un indice

avec

pour tout

, et tout

Question 9 On considère la suite

de la partie précédente. Montrer que

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

suivante, associée à

Question 10

a. Calculer les valeur propres de

. Sont-elles réelles positives? On note

les 3 valeurs propres de

, avec

. Determiner des vecteurs propres

respectifs associés, avec

une distribution.
b. Soit

. Prenant

puis

, donner des valeurs explicites pour

Distrib

tels que

si et seulement si

pour tout

.
c. Quelles sont les trajectoires

associées à

Question 11 Soit

. On définit

.
a. Montrer que

.
b. Soit

(en particulier

). Montrer qu'il existe

tel que

est

pour tout

, puis

pour tout

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

pour les distributions initiales dans l'ensemble

Question 12

a. Montrer que pour tout

, il existe

avec

b. Montrer que pour tout

, il existe

avec

pour tout

.
c. Existe-t-il

tel que

pour tout

?
d. Décrire le langage de

pour les distributions initiales dans l'ensemble

, c'est à dire l'ensemble des suites

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

. Soit

une chaîne de Markov de

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

0 . Soit

une distribution, vecteur propre associé à

, et

deux vecteurs propres associés respectivement à

. Pour toute distribution

, on admettra qu'il existe

des réels tels que

si et seulement si

Soit

tel que

pour toute distribution

. C'est le cas dès que

. Soit

deux distributions avec

pour tout

. On pose

pour tout

Question 13 Quel est le langage

?
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.