Upload
nassim-khorchi
View
85
Download
4
Embed Size (px)
Citation preview
Un outil d’analyse pour les
chaînes de Markov à temps discret
République Algérienne Démocratique et Populaire
Ministère de l’Enseignement Supérieur et de la Recherche Scientifique
Université des Sciences et de la Technologie Houari Boumediene
Faculté d’Electronique et d’Informatique
Département Informatique
Mémoire de Licence
Domaine Mathématiques et Informatique
Spécialité
Ingénierie des Systèmes d’Information et du Logiciel
Thème
Présenté par : Proposé par :
Mr KHORCHI Nassim Mme GHARBI Nawel
Mr ZAHARIOU Youcef
Devant le jury
Mr BOUKALA (président)
Mme OUROUA (membre)
Projet N° : 070/2016
Dédicace
Nous dédions ce travail ;
A nos parents les plus chers à nos cœurs, qui nous ont encouragé à
poursuivre nos rêves et soutenu dans chaque étape de nos vies, qui ont fait
de nous ce que nous sommes aujourd’hui, et font tout pour nous rendre
heureux. Que dieu le tout puissant veille sur eux et les protège ;
A nos frères, aucun mot ne pourra exprimer notre gratitude envers eux. Que
Dieu nous unisse à jamais ;
A toute la famille KHORCHI de la part de Nassim
et à toute la famille ZAHARIOU et la famille SERIR de la part de Youcef
Merci pour l’aide que vous nous aviez apportée durant toutes ces années ;
A nos amis les étudiants ;
A nos amis d’ailleurs ;
A celui que nous considérons toujours comme un frère, il se reconnaitra.
Remerciement
Nous Remercions Dieu tout puissant de nous avoir donné la volonté et le
courage d’entreprendre ce travail.
Nous tenons à remercier particulièrement notre promotrice, professeur
Nawel GHARBI pour le sujet proposé et qui nous a encadré tout au long de
ce travail avec ses conseils et critiques qui ont contribués à sa réalisation.
Nous remercions Monsieur le professeur Mohand Cherif BOUKALA
pour l’honneur qu’il nous fait en présidant le jury de notre projet de fin
d’études. La participation de Madame OUROUA comme membre du jury
nous honore, qu’elle trouve ici l’expression de notre profond respect.
Nous remercions tous les membres de nos familles pour leurs soutiens
moraux et leurs aide précieuse. Plus particulièrement nos parents, nos frère
et sœurs qui ont en plus fait preuve de beaucoup de patience.
A tous nos enseignants qui nous ont permis d’atteindre ce niveau, nous
leur serons toujours reconnaissants.
Nos sincères remerciements pour tous ceux qui, de près ou de loin nous
ont aidés à la réalisation de ce travail.
Table des matières
Introduction Générale ........................................................................................... 1
Chapitre 1 Processus stochastiques et chaînes de Markov .............................. 2
1.1 Introduction .................................................................................................... 2
1.2 Notions de base .............................................................................................. 3
1.2.1 Expérience aléatoire ......................................................................................... 3
1.2.2 Evènement ........................................................................................................ 3
1.2.3 Probabilité ........................................................................................................ 3
1.2.4 Espace probabilisé ............................................................................................ 3
1.2.5 Espace des états ................................................................................................ 4
1.2.6 Espace de temps ............................................................................................... 4
1.2.7 Variable aléatoire ............................................................................................. 4
1.3 Processus stochastiques .................................................................................. 5
1.4 Chaînes de Markov à temps discret ............................................................... 7
1.4.1 Représentation des chaînes de Markov ............................................................ 8
1.5 Propriétés élémentaires d’une CMTD ......................................................... 11
1.5.1 Homogénéité .................................................................................................. 11
1.5.2 Irréductibilité .................................................................................................. 11
1.5.3 Absorbance ..................................................................................................... 12
1.5.4 Périodicité, apériodicité .................................................................................. 12
1.5.5 Récurrent, transitoire ...................................................................................... 13
1.5.6 Théorème de solidarité ................................................................................... 14
1.6 Analyse d’une CMTD .................................................................................. 15
1.6.1 Distribution d’état initial ................................................................................ 15
1.6.2 Premier temps de passage .............................................................................. 15
1.6.3 Probabilité de transition en n étape ................................................................ 15
1.6.4 Analyse transitoire.......................................................................................... 16
1.6.5 Analyse stationnaire ....................................................................................... 17
1.6.6 Ergodicité ....................................................................................................... 17
1.7 Conclusion .................................................................................................... 18
Chapitre 2 Réalisation d’un logiciel de manipulation des chaînes de Markov
................................................................................................................................ 19
2.1 Introduction .................................................................................................. 19
2.1 Les cas d’utilisation de l’application ........................................................... 20
2.2 Description de l’outil .................................................................................... 21
2.2.1 Environnement de développement ................................................................. 21
2.2.2 Présentation des interfaces ............................................................................. 22
2.2.3 Exemple applicatif.......................................................................................... 40
2.2.4 Discussion des résultats obtenus .................................................................... 42
2.3 Conclusion .................................................................................................... 44
Conclusion Générale ............................................................................................ 45
Bibliographie ........................................................................................................ 46
Table des figures
Figure 1.1 : Comportement d’un processus stochastiques. ..................................... 6
Figure 1.2 : Processus Markovien dérivé de processus stochastiques. ................... 8
Figure 1.3 : Exemple d’un graphe d’état d’une CMTD. ......................................... 9
Figure 1.4 : Exemple d’une matrice stochastique d’une CMTD. ......................... 10
Figure 1.5 : Exemple d’une CMTD irréductible. .................................................. 12
Figure 1.6 : Exemple d’une CMTD apériodique. ................................................. 13
Figure 2.1 : Cas d'utilisation de l'application. ....................................................... 20
Figure 2.2 : Fenêtre principal de l’application. ..................................................... 23
Figure 2.3 : Menu fichier, élément nouveau projet. .............................................. 24
Figure 2.4 : Message d'alerte nouveau projet. ....................................................... 24
Figure 2.5 : Boite de dialogue ouverture d'un projet............................................. 25
Figure 2.6 : Menu fichier, élément ouvrir un projet. ............................................. 25
Figure 2.7 : Menu fichier, élément enregistrer. ..................................................... 26
Figure 2.8 : Menu fichier, élément fermer, message d'alerte de fermeture de
l'application. ........................................................................................................... 26
Figure 2.9 : Menu projet, élément irréductibilité, message de résultat :
irréductibilité. ......................................................................................................... 27
Figure 2.10 : Message de résultat : circuit. ........................................................... 28
Figure 2.11 : Message de résultat : absorbant. ...................................................... 30
Figure 2.12 : Message de résultat : ergodique. ...................................................... 30
Figure 2.13 : Menu projet, élément calculer la période. ....................................... 31
Figure 2.14 : Message de résultat : période de la chaîne. ..................................... 31
Figure 2.15 : Message de résultat période d'un état. ............................................. 31
Figure 2.16 : Effet de l’élément centrer la chaîne. ................................................ 32
Figure 2.17 : Menu outils, élément afficher la matrice. ........................................ 32
Figure 2.18 : Fenêtre d’affichage de la matrice. ................................................... 33
Figure 2.19 : Fenêtre d'affichage du vecteur de distribution. ............................... 33
Figure 2.20 : Fenêtre paramètres : tabulation analyse, tabulation chaîne............. 34
Figure 2.21 : Menu outils, élément affichage de la chaîne, exemples. ................. 35
Figure 2.22 : Page d’aide d’utilisation de l’application. ....................................... 36
Figure 2.23 : Barre d'outils, élément ajouter un état. ............................................ 37
Figure 2.24 : Barre d'outils. ................................................................................... 37
Figure 2.25 : Espace de travail, exemple d'ajout, suppression et modification
d'états et transitions. ............................................................................................... 38
Figure 2.26 : Message d'affichage de matrice espace insuffisant. ........................ 39
Figure 2.27 : Espace d'affichage de la matrice. ..................................................... 39
Figure 2.28 Barre d'état, exemples des messages, état et transition. .................... 39
Figure 2.29 : Barre d'état, exemples des messages, analyse. ................................ 40
Figure 2.30 : Analyser une chaîne, choisir le type d'analyse. ............................... 40
Figure 2.31 : Fenêtre analyse transitoire. .............................................................. 41
Figure 2.32 : Résultat du calcul après l'analyse transitoire d'une CMTD. ........... 42
1
Introduction Générale
La modélisation joue un rôle important dans la conception et l’analyse des systèmes.
C’est clairement vrai aux étapes préliminaires de réalisation, quand on doit procéder à
l’étude de fiabilité et la certitude des résultats réaliser par le système et ce face au temps
qui passe.
Cependant, une implémentation réelle est le meilleur moyen pour déduire des résultats
et effectuer des études plus concrètement et beaucoup plus réaliste, mais il est souvent
prohibitif. Donc des modèles mathématiques ont été utilisés pour contourner ce problème,
parmi eux les processus stochastiques que nous allons aborder dans notre mémoire et
découvrir une de ses particularités qui sont les chaînes de Markov.
Le processus stochastique plus particulièrement markovien est un modèle attrayant
surtout pour analyser le comportement au fil du temps concernant le changement des
systèmes. Les principaux avantages de ce modèle sont la précision et la stabilité
numérique qui nous permettra de prévoir le futur.
Notre convivial, un outil graphique basé sur le résout, la représentation des chaînes de
Markov en dessinant et en résolvant l'espace état.
Pour être pratique, l'outil doit être capable de tirer grand nombre d’états des espaces
en insertion et permet aussi l’ajout de transition et l’analyse du comportement des chaînes
à travers le temps.
Ce mémoire comprend deux chapitres où le premier est consacré à la présentation des
processus stochastiques et chaînes de Markov avec les propriétés essentielles, ainsi
quelques notions fondamentales, puis nous allons plonger dans l’étude des méthodes
d’analyse appropriées aux chaînes de Markov à temps discret.
Dans le deuxième chapitre, nous donnons des détails de l’implémentation de ces
méthodes dans notre application avec présentation des différentes fonctionnalités.
Nous terminons ce mémoire par une conclusion générale de notre travail.
Chapitre 1
Processus stochastiques et chaînes de Markov
1.1 Introduction
La théorie des processus stochastiques concerne l’étude mathématique des
phénomènes physiques, biologiques ou économiques évoluant dans le temps, et dont
l’évolution est de caractère aléatoire, c’est-à-dire non prévisible avec certitude. Ainsi les
chaînes de Markov sont un cas particulier des processus stochastiques dans des conditions
bien définies et des objectifs précis.
En général les processus stochastiques sont des objets plus généraux, comprenant des
suites de variables aléatoires qui ne sont pas indépendantes. En effet, on interprète l'indice
numérotant ces variables comme le temps. Un cas important est celui des processus
markoviens, pour lesquels chaque variable aléatoire de la suite ne dépend que de la
précédente. Les chaînes de Markov sont des exemples de processus stochastiques
markoviens, que nous allons étudier plus en détail.
Dans ce chapitre nous allons d’abord définir le vocabulaire utilisé ie des généralités
sur les probabilités et des notions de bases, puis on donnera des définitions formelles et
des exemples montrant l’application des processus stochastiques. L’exploration des
processus stochastiques et la compréhension détaillée nous permettra de définir les
conditions qui devront être vérifiées pour qu’un processus stochastique sera appelé une
chaîne de Markov. Cela va aussi nous promouvoir l’étude des chaînes de Markov et
d’introduire leurs particularités tout en restant dans notre objectif.
1 Notions de base 3
1.2 Notions de base
Pour comprendre ce qu’un processus stochastique il faut d’abord définir les termes qui
suivent.
1.2.1 Expérience aléatoire
On appelle une expérience aléatoire l’expérience dont on ne peut pas prévoir avec
certitude le résultat ie produit des résultats différents dans des conditions apparemment
identiques. [1]
Exemple : le lancer d’un dé.
Ω : Ensemble des résultats possibles = {0, 1,2, 3, 4, 5,6}.
1.2.2 Evènement
L’évènement est un sous-ensemble observable de Ω et qui correspond à une assertion
logique vérifiable relative au résultat d’une expérience. [1]
Exemple : le nombre obtenu quand on lance un dé est supérieur à 2.
1.2.3 Probabilité
C’est la mesure de l’importance de l’évènement, associée à un évènement un nombre
qui représente le degré de certitude de sa réalisation.
Les probabilités permettent de modéliser des incertitudes. [1]
Exemple : la probabilité que demain il fera beau est à 70% d’après le centre de
recherche météorologique.
1.2.4 Espace probabilisé
On appelle espace probabilisé le triplé (Ω, ε, P(.)), où :
Ω : Ensemble des résultats possibles d’une expérience aléatoire.
ε : Ensemble de sous-ensembles de (les événements).
1 Notions de base 4
P(.) : loi (ou mesure) de probabilité, associant à chaque A ϵ ε un nombre
ϵ [0, 1]. [1]
1.2.5 Espace des états
C’est un ensemble E qui peut être :
• discret : c’est-à-dire fini ou dénombrable. Il sera, dans ce cas, souvent pratique
d’identifier E avec une partie de ℕ ou de ℤ.
• non discret : par exemple E = IR ou E ⊂ IR2 (partie du plan) ou E ⊂ IR3 (partie
de l’espace). [1]
1.2.6 Espace de temps
C’est un ensemble T, nous citons les deux espaces de temps les plus utilisés :
T= IN : le processus est dit discret ; on regarde ce qu’il se passe à chaque
unité de temps, ou bien on fait une suite d’opérations et on regarde ce qu’il se passe
à chaque opération (ex : lancer d’une pièce).
T= 𝐼𝑅+ : le processus est dit continu ; on garde les yeux fixe sur un système
qui évolue dans le temps et à partir d’un instant 𝑡0 et que l’on prend pour origine
des temps (t=0). [1]
1.2.7 Variable aléatoire
Soit une expérience aléatoire dont l’ensemble des résultats possibles est noté Ω.
On appelle variable aléatoire, l’application X allant de Ω dans IR, qui associe à toute
élément de Ω un nombre réel :
𝑋 : Ω → IR
𝜔 → 𝑋 (𝜔)
L’espace d’états de X (E) est définie comme l’ensemble des valeurs que peut prendre la
variable aléatoire X. [1]
1 Processus stochastiques 5
1.3 Processus stochastiques
Les processus stochastiques sont des modèles mathématiques utiles pour la description
des systèmes comportant des phénomènes de nature probabiliste (qui dépendent du
hasard) en fonction d’un paramètre qui est généralement le temps.
Nous citons à titre d’exemple le processus markovien.
Dans cette section nous allons expliquer ce qu’un processus stochastique et ce qu’on
entend par la propriété de Markov.
Définition :
Un processus stochastique {𝑋𝑡}𝑡𝜖𝑇 , est une famille de variables aléatoires indexées par
le temps 𝑡 et définies sur un espace de probabilité Ω.
Les mots processus et stochastique signifient respectivement fonction et aléatoire. La
spécificité d’un processus stochastique réside dans cette structure en fonction de deux
variables 𝑋(𝑡, 𝜔) que nous écrivons souvent 𝑋𝑡(𝜔), alors qu’une variable aléatoire X
associe à chaque 𝜔 𝜖 𝛺 une réalisation 𝑋(𝜔), un processus stochastique {𝑋𝑡}𝑡𝜖𝑇 associe
à chaque ω une fonction (ou trajectoire) :
{𝑋𝑡(𝜔)}𝑡𝜖𝑇 ∶ 𝑇 → 𝐸
𝑡 → 𝑋𝑡(𝜔)
Où E est l’espace des arrivées des variables aléatoires (𝑋𝑡).
Un processus stochastique est dit à temps discret, lorsque T est dénombrable, nous
supposerons alors 𝑇 = ℤ et le processus sera noté :{𝑋𝑥, 𝑥 = 0,1,2, … , }.
Un processus stochastique est dit à temps continu lorsque l’ensemble T est non
dénombrable, le plus souvent sera égale à ℝ . Le processus sera alors noté {𝑋𝑡}, 𝑡 ≥ 0.
Un processus stochastique est markovien, si conditionnellement à sa valeur
présente au temps t, son évolution future est indépendante de son passé.
Plusieurs processus stochastiques utilisé lors de la modélisation dans les biens
financiers et d’autres systèmes d’ingénierie sont markoviens.
De nombreux phénomènes ne peuvent pas être décrits par une simple variable
aléatoire :
1 Processus stochastiques 6
– Débit d’une rivière au cours de l’année.
– Evolution d’un stock de produit.
Mais par des suites de variables aléatoires interdépendantes (Processus stochastiques).
Nous restreindrons notre étude aux processus stochastiques à événements discrets,
nous étudierons donc les chaînes de Markov à temps discret. [2]
(Voir figure 1.1)
Figure 1.1 : Comportement d’un processus stochastiques.
1 Chaînes de Markov à temps discret 7
1.4 Chaînes de Markov à temps discret
Les travaux d’Andreï A. Markov (1856-1922), un mathématicien Russe sur la théorie
des probabilités l’ont amené à mettre au point les chaînes de Markov qui l'ont rendu
célèbre. Ceux-ci peuvent représenter les prémices de la théorie du calcul stochastique. [5]
Une chaîne de Markov est une suite de variables aléatoires {𝑋𝑛, 𝑛 ∈ ℕ } qui permet de
modéliser l’évolution dynamique d’un système aléatoire, 𝑋𝑛 représente l’état du système
à l’instant n.
La propriété fondamentale des chaînes de Markov, dite propriété de Markov, est que
son évolution future ne dépend du passé qu’au travers de sa valeur actuelle.
Les applications des chaînes de Markov sont très nombreuses, un intérêt particulier
concerne la modélisation des systèmes informatiques (réseaux, génétique des
populations, mathématiques financières, gestion de stocks, algorithmes stochastiques
d’optimisation, simulation, . . .).
Nous donnons dans cette section des définitions et des propriétés élémentaires des
chaînes de Markov, et plus précisément nous caractérisons les propriétés des états d’une
chaîne de Markov.
Définition :
Un processus stochastique {𝑋𝑛}𝑛𝜖ℕ à espace d’état discret et à temps discret, est une
chaîne de Markov à temps discret (CMTD) si et seulement si la propriété de Markov
suivante est vérifiée :
𝑃[𝑋𝑛 = 𝑗|𝑋𝑛−1 = 𝑖𝑛−1, 𝑋𝑛−2 = 𝑖𝑛−2, … . . , 𝑋0 = 𝑖0]
= 𝑃[𝑋𝑛 = 𝑗|𝑋𝑛−1 = 𝑖𝑛−1]
Où : 𝑋𝑛 représente l’état du système à l’instant n.
Ainsi, la probabilité pour que la chaîne soit dans un certain état à la n ième étape du
processus ne dépend que de l’état du processus à l’étape précédente (la n-1 ième étape)
et pas des états dans lesquels il se trouvait aux étapes antérieurs (les étapes j pour j=0, 1,
2, 3… n-2).
1 Chaînes de Markov à temps discret 8
Cette propriété facilite donc la mise en œuvre informatique d’un tel processus. En
particulier, il n’est pas nécessaire de conserver en mémoire tout le passé du processus
pour effectuer des calculs de performance (perte de mémoire, voire figure 1.2). [3]
La probabilité 𝑃𝑖𝑗(𝑛) = 𝑃[𝑋𝑛 = 𝑗|𝑋𝑛−1 = 𝑖 ] représente la probabilité de transition, qui
est la probabilité de passer de l’état i à l’état j en une étape à l’instant n. Lorsque cette
dernière ne dépend pas de n, la chaîne est dite homogène dans le temps.
1.4.1 Représentation des chaînes de Markov
Il s'agit de modéliser une CMTD à l'aide de représentations synthétiques afin de
connaître l'évolution des états du système. On utilisera les matrices et les graphes, les
matrices pour contenir les probabilités des transitions envisageables par la CMTD, et les
graphes qui nous permettront de déduire les propriétés qualitatives.
Processus
stochastique
Evènements
discrets
Temps
discret
Sans
mémoire
Evènements
continus
Temps
continus
Figure 1.2 : Processus Markovien dérivé de processus stochastiques.
1 Chaînes de Markov à temps discret 9
1.4.1.1 Graphe d’état
Appelé aussi automate, on l’utilise souvent comme méthode générique de conception,
il est utilisé surtout dans la théorie des graphes.
Définition :
Un graphe orienté (ou automate fini) où chaque état (de la chaîne ou de l’automate
correspondant) est un sommet (ou nœud). Les transitions sont représentées par des arcs
(flèches) étiquetées par les probabilités de transition correspondantes entre les deux états.
Exemple :
La figure 1.3 est une représentation d’une CMTD à 4 états et avec les transitions
démontrées par les flèches.
Chemin :
Dans un graphe, on appelle chemin la suite (𝑋, 𝑋1, … . 𝑋𝑛−1, 𝑋𝑛) de sommets (dans
notre cas les états) tel que deux sommets consécutifs quelconques 𝑋𝑖 et 𝑋𝑗 sont reliés par
un arc.
Les sommets 𝑋0 et 𝑋𝑛 sont respectivement l’origine et l’extrémité du chemin.
Le nombre d’arc qui compose le chemin est la longueur de ce chemin. [4]
Figure 1.3 : Exemple d’un graphe d’état d’une CMTD.
1 Chaînes de Markov à temps discret 10
Exemple :
Dans la Figure 1.3, la suite E1, E2 et E3 construit un chemin, dont l’origine est E1 et
l’extrémité est E3.
Circuit :
Dans un graphe, un circuit est un chemin de longueur non nulle et dont l’origine et
l’extrémité sont identiques. [4]
Exemple :
Dans la Figure 1.3, la suite E1, E2, E4, E1 construit un circuit, de longueur 3 dont
l’origine et l’extrémité est égale à E1.
Remarque : on appelle un circuit de longueur 1 une boucle.
1.4.1.2 Matrice de transition
Appelé aussi matrice stochastique, cette matrice est carrée, de dimension égale au
nombre d’états possibles. Tous les termes sont positifs ou nuls et inférieurs ou égaux à 1
(puisqu’elle ne contient que des probabilités). La somme des termes de chaque ligne est
1 (puisqu’il y a toujours un état de destination).
Exemple :
Figure 1.4 : Exemple d’une matrice stochastique d’une CMTD.
Soit Pi,j(n) la probabilité d′aller de i à j en n etapes.
Alors la matrice de Pi,j(n) est justement la matrice Pn (Puisance n ieme de la
Matrice P) .
1 Propriétés élémentaires d’une CMTD 11
Nous discuterons plus de détails concernant cette proposition ci-dessus plus tard
dans 1.6 dans les probabilités de transition en n étapes.
1.5 Propriétés élémentaires d’une CMTD
Une chaîne de Markov à temps discret est caractérisée par des propriétés, parmi eux
les propriétés qui suivent.
1.5.1 Homogénéité
Une chaîne de Markov (𝑋𝑛)𝑛𝜖ℕ est dite homogène (dans le temps) si :
𝑃𝑖𝑗(𝑛)= {𝑋𝑛+1 = 𝑗|𝑋𝑛 = 𝑖 } ne dépend pas de n et on note :
𝑃𝑖𝑗 = 𝑃{𝑋𝑛+1 = 𝑗|𝑋𝑛 = 𝑖 }
Alors la chaîne de Markov est dite homogène ie la probabilité d’aller de i en j reste la
même au cours du temps. Elle permet de regrouper en une matrice (indépendante de n) la
probabilité de transition entre deux états quelconques. [6]
1.5.2 Irréductibilité
L’idée générale est de regarder le graphe d’état et à partir d’un état donné trouver quel
sont les états que l’on peut atteindre, si on peut atteindre n’importe quel autre état dans le
graphe donc la CMTD correspondante est irréductible sinon elle est réductible.
Définition :
Nous dirons qu’on peut atteindre un état j à partir d’un état i s’il existe un chemin
menant de i vers j, autrement dit il existe un entier n tel que 𝑃𝑖𝑗(𝑛)
> 0 et nous dirons que
les états i et j communiquent si on a à la fois 𝑃𝑖𝑗(𝑛)
> 0 𝑒𝑡 𝑃𝑗𝑖(𝑛) > 0 .
Une chaîne de Markov est appelée irréductible si et seulement si tous les états
communiquent entre eux, son graphe est fortement connexe.
Pour deux état quelconque s, s’ϵ S avec s≠ s’on a :
𝑃𝑛(𝑋𝑡 = s’|𝑋0 = s) > 0
1 Propriétés élémentaires d’une CMTD 12
Exemple :
1.5.3 Absorbance
Un état s ϵ S d’une chaîne de Markov est appelé absorbant si pour un t ϵ T quelconque
et s, s’ϵ S avec s’≠ s on a 𝑃 (𝑋𝑡 = s’|𝑋0 = s) = 0 .
Autrement dit, un état absorbant est un état dont sa probabilité de transition vers lui-
même est égale à 1 et nulle pour le reste des états. [6]
Remarque : Une chaîne de Markov est absorbante si et seulement si elle contient au
moins un état absorbant.
1.5.4 Périodicité, apériodicité
La période d’un état j est : D(𝑗) = PGCD{𝑘 ≥ 1/𝑃𝑗,𝑗(𝑘)> 0} . C’est le plus grand
commun diviseur des longueurs des circuits allants de j à j. [5]
Définition :
La période d’une CMTD est égale au PGCD des périodes de chacun de ses états.
Elle est égale au PGCD de la longueur de tous les circuits du graphe correspondant à la
CMTD.
Figure 1.5 : Exemple d’une CMTD irréductible.
1 Propriétés élémentaires d’une CMTD 13
Une CMTD est dite périodique si sa période est supérieure à 1 (et apériodique
si sa période est égale à 1).
Une condition nécessaire et suffisante pour qu’une CMTD irréductible soit
apériodique est de contenir au moins une boucle.
Exemple :
Dans la CMTD de la Figure 1.6, la période de chaque état donné est comme suit :
D(E1) =1 car PGCD (1,3)
D(E2) =1 car PGCD (3,2)
D(E3) =1 car PGCD (3 ,2)
Et comme le PGCD (1, 1,1) = 1, donc la période de la CMTD est 1 ce qu’il fait que la
CMTD correspondante est apériodique.
1.5.5 Récurrent, transitoire
Un état 𝑠 ϵ S tel que, lorsque la chaîne est issue de cet état, elle y retourne en un temps
fini avec une probabilité strictement positive, s’appelle un état récurrent (sinon l’état est
dit transitoire). Cette distinction entre état récurrents et transitoires est nettement plus
délicate à déduire du graphe des états. [2]
Figure 1.6 : Exemple d’une CMTD apériodique.
1 Propriétés élémentaires d’une CMTD 14
Définition :
Une CMTD est dite récurrente si et seulement si tous ses états sont récurrents.
Notons simplement que lorsqu’une CMTD est irréductible, ses états sont tous
récurrents. On parle alors de chaîne récurrente.
Un cas particulier intéressant de chaîne récurrente est celui d’une chaîne
périodique.
1.5.6 Théorème de solidarité
Les états d’une chaîne de Markov irréductible sont de même nature :
Si un des états est récurrent, alors tous les états sont récurrents.
Si un des états est périodique, alors tous les états sont périodiques et de même
période.
1 Analyse d’une CMTD 15
1.6 Analyse d’une CMTD
Maintenant avec les définitions introduites, on peut facilement procéder aux méthodes
de calcul des probabilités dans le cas transitoire et stationnaire afin d’évaluer le système
c’est-à-dire calculer son évolution à travers le temps.
Au début nous déterminons quelques notions.
1.6.1 Distribution d’état initial
Soit v un vecteur linéaire représentant la distribution de l’état initial de la chaîne de
Markov à temps discrets i.e v dénote la probabilité d’être initialement à l’état s avec s ε
S, donc l’état initial d’un système est défini par le vecteur des probabilités v tel que :
𝑣 = [𝑣1 , 𝑣2, … . ]
Où : 𝑣𝑖 = P {𝑋0= i} = la probabilité que la chaîne se trouve à l’instant initial à l’état i,
dire qu’initialement le système est dans l’état j signifie que 𝑣𝑗 = 1 et 𝑣𝑖 = 0 quel que soit
i ≠ j.
1.6.2 Premier temps de passage
On appelle premier temps de passage de l’état i à l’état j le nombre de transitions
effectués par le processus en allant de l’état i à l’état j pour la première fois.
Cela nous permet de calculer la performance de notre système, ou même tester sa
fiabilité.
1.6.3 Probabilité de transition en n étape
On note par 𝑃𝑖,𝑗(𝑛)
la probabilité pour qu’une CMTD passe d’un état i à un état j en n
étapes.
𝑃𝑖,𝑗(𝑛) = 𝑃(𝑋𝑛 = 𝑗|𝑋0 = 𝑖) = 𝑃(𝑋𝑡 = 𝑗|𝑋𝑡−𝑛 = 𝑖)
𝑒𝑡 𝑃𝑖,𝑗(1)= 𝑃𝑖,𝑗
Dans le cas où n=2, nous avons :
𝑃𝑖,𝑗(2) = 𝑃(𝑋𝑡 = 𝑗|𝑋𝑡−2 = 𝑖)
1 Analyse d’une CMTD 16
𝑃𝑖,𝑗(2) =∑𝑃(𝑋𝑡 = 𝑗 , 𝑋𝑡−1 = 𝑘|𝑋𝑡−2 = 𝑖)
𝑘
𝑃𝑖,𝑗(2) =∑𝑃(𝑋𝑡 = 𝑗|𝑋𝑡−1 = 𝑘, 𝑋𝑡−2 = 𝑖)𝑃(𝑋𝑡−1 = 𝑘|𝑋𝑡−2)
𝑘
𝑃𝑖,𝑗(2) =∑𝑃(𝑋𝑡 = 𝑗|𝑋𝑡−1 = 𝑘)𝑃(𝑋𝑡−1 = 𝑘|𝑋𝑡−2)
𝑘
𝑃𝑖,𝑗(2) =∑𝑃𝑖𝑘𝑃𝑘𝑗
𝑘
Multiplication matricielle, d’où :
𝑃(2) = 𝑃2
De manière générale (Chapman Kolmogorov)
𝑃𝑖,𝑗(𝑚+𝑛)
= ∑ 𝑃𝑖𝑘(𝑚)
𝑘 𝑃𝑘𝑗(𝑛) (1)
𝑃𝑖,𝑗(𝑚+𝑛) = 𝑃(𝑚)𝑃
(𝑛) (2)
En appliquant l’équation de Chapman Kolmogorov, nous déduisons que la matrice de
probabilité de transition en n étapes est la puissance n ième de la matrice des probabilités
de transition : 𝑃(𝑛) = 𝑃𝑛.
Cette relation exprime le fait que pour aller de l’état i à j en n étapes, on peut aller de
l’état i à l’état k en m étapes, puis aller de cet état k à l’état j en n-m étapes.
1.6.4 Analyse transitoire
L’analyse d’une CMTD au régime transitoire consiste à déterminer le vecteur des
probabilités d’état 𝑣(𝑛) = [𝑃𝑖(𝑛), 𝑖 ∈ 𝐸] où :
𝑣𝑖(𝑛)= 𝑃[𝑋𝑛 = 𝑖] est la probabilité que la chaîne se trouve à l’instant n (à la nième
étape du processus) dans l’état i.
Ce vecteur des probabilités 𝑣(𝑛) dépend :
- De la matrice de transition P.
- Du vecteur des probabilités d’état initiales 𝑣(0).
1 Analyse d’une CMTD 17
La matrice 𝑃 comprend les probabilités de transition 𝑃𝑖𝑗 en une seule étape, tandis que
la matrice 𝑃𝑛 comprend les probabilités de transition en n étapes.
1.6.5 Analyse stationnaire
Lorsque le système aura fonctionné suffisamment longtemps (𝑛 → ∞) , il atteint le
régime stationnaire défini par le vecteur limite ou le vecteur des probabilités stationnaires.
[5]
Nous nous intéressons à la limite lorsque n tend vers l'infini du vecteur des
probabilités 𝑣(𝑛).
Cette limite existe-t-elle et si oui, comment la calculer ?
Dans une CMTD finie, irréductible et apériodique, le vecteur 𝑣 = [𝑣1, 𝑣2, … , 𝑣𝑛]
des probabilités limites 𝑣𝑗 = lim𝑛→∞
𝑣𝑗(𝑛) existe toujours, est indépendant de la
distribution des probabilités initiales 𝑣(0), et est solution du système :
{
𝑣 = 𝑣 𝑃
∑𝑣𝑖 = 1
𝑖∈𝐸
↔
{
𝑣𝑗 =∑𝑣𝑖𝑃𝑖𝑗
𝑖∈𝐸
𝑝𝑜𝑢𝑟 𝑡𝑜𝑢𝑡 𝑗 ∈ 𝐸
∑𝑣𝑖 = 1𝑖∈𝐸
1.6.6 Ergodicité
Une chaîne de Markov à temps discret finie, apériodique et irréductible est ergodique.
Définition :
Une chaîne de Markov admet une distribution stationnaire sur ses états si elle est
ergodique.
Ainsi, si la CMTD est ergodique, le système qu’elle modélise se stabilise après
l’écoulement d’un temps infini et il existe toujours une seule distribution des probabilités
stationnaires 𝑣. [5]
1 Conclusion 18
1.7 Conclusion
L’objet de ce chapitre a été la présentation des processus stochastiques et leur
particularité les chaînes de Markov qui étaient notre sujet, au début nous avons fait un
rappel des notions fondamentaux liés à ces derniers, tel que les variables aléatoires, les
probabilités, les évènements, la matrice stochastique, etc.
Les chaînes de Markov occupent une grande importance dans l’étude des phénomènes
qui ne se focalisent pas sur le passé or qu’à l’état présent, et bien qu’ils permettent de
prévoir d’une manière assez cohérente le futur, en revanche analyser le comportement
des systèmes en question d’étude et mettre en évidence leur performance est une de ses
résultats.
Dans le chapitre prochain qui consistera dans la présentation de notre application, nous
implémentons toutes les méthodes d’analyse que nous avons expliquées et les propriétés
élémentaires à tester comme des fonctionnalités dans notre application.
Chapitre 2
Réalisation d’un logiciel de manipulation des chaînes
de Markov
2.1 Introduction
Les chaînes de Markov sont des modèles analytiques, idéaux pour l’étude dans le
domaine de modélisation. Le développement des outils informatiques qui permettent de
les utiliser de manière efficace, interactive et rapide est important afin de faciliter
l’analyse et automatiser les calculs en implémentant les algorithmes correspondants.
Dans ce chapitre nous allons présenter le contexte expérimental de notre travail et les
différents outils utilisés pour le développement de notre application. Le résultat sera une
application à une interface graphique (GUI) interagissant avec l’utilisateur et qui lui
donne la possibilité de dessiner les chaînes de Markov tout en insérant des états et des
transitions, faire le calcul d’analyse transitoire et stationnaire, en offrant la possibilité de
modification, suppression. L’outil doit aussi garantir la sauvegarde du travail compléter
par l’utilisateur ainsi que l’ouverture d’un travail existant, tous ces fonctionnalités devront
respecter les qualités suivantes : la facilité d’utilisation, l’efficacité, la portabilité et la
maintenabilité. Le développement est basé sur les algorithmes mathématiques des
différentes méthodes d’analyse présentées dans le chapitre précédent.
2 Les cas d’utilisation de l’application 20
2.1 Les cas d’utilisation de l’application
Le diagramme de cas d’utilisation est le point de départ de notre conception, il va
nous permettre de représenter les interactions entre le système et son utilisateur.
Figure 2.1 : Cas d'utilisation de l'application.
2 Description de l’outil 21
2.2 Description de l’outil
2.2.1 Environnement de développement
Java :
Notre application est développée avec le langage de
programmation orienté objet Java avec l’EDI Eclipse
Environnement de Développement Intégré, sur la
plateforme WINDOWS 10 à processeur 64bits.
Le Java Development Kit (JDK) version 1.8 est l’environnement dans lequel le code
Java est compilé pour être transformé en bytecode afin que la machine virtuelle
Java(JVM) puisse l’interpréter.
Les composants primaires du JDK sont une sélection
d’outils de programmation incluant : javac : le
compilateur qui convertit le code source en fichier
binaire (.class). jar : l’archiveur, qui met sous forme d’un paquetage unique l’ensemble
des fichiers class dans un seul fichier JAR. javadoc : le générateur de documentation, qui
génère automatiquement de la documentation à partir des commentaires du code source.
jdb : le débogueur qui permet de tester le programme compilé afin de récupérer des
bogues.
Ainsi, il dispose de fonctionnalités graphiques
permettant de concevoir des interfaces graphiques :
GUI, d’AWT et de Swing, il peut même contenir
plusieurs processus qui s’exécutent en parallèle
indépendamment et continuellement (appelé threads).
Pourquoi a-t-on choisi Java ?
A cause de la richesse de l’API Java (Application Program Interface), Le haut niveau
d'abstraction, l’orienté objet et l’excellente portabilité ainsi que la documentation offerte
sur internet, nous avons décidé de choisir Java parmi d’autres langage pour développer
notre application.
2 Description de l’outil 22
Photoshop : c’est un logiciel de retouche, de
traitement et de dessin assisté par ordinateur édité par
Adobe. Il nous a principalement servit pour dessiner
et animer les différents curseurs et icones utilisés dans notre application.
Configuration recommandée de la machine
La machine ou le PC exécutant cette application doit préférablement posséder les
caractéristiques suivantes :
Système
d’exploitation
RAM Processeur Espace disque
libre
Windows Xp, 7, 8, 10
(x86, x64)
Linux
Mac OS
1 Giga octet
DualCore 1.5
MHZ
100 Méga octets
En plus de de ces caractéristiques citées dessus, le PC doit aussi préinstaller le JRE
(Java Runtime Environment) pour que l’application puisse s’exécuter dans la machine
virtuelle java (JVM). Le JRE est disponible pour tous les systèmes d’exploitation et
machines sur le lien suivant : https://java.com/download
2.2.2 Présentation des interfaces
L’interface graphique de notre application nous assure une communication complète
entre l’utilisateur et l’outil au niveau d’accéder aux commandes, en cliquant avec la souris
ou le clavier et en interagissant avec les messages dialogues envoyés par l’application
vers l’écran de l’utilisateur, cela nous garantit une simplicité d’utilisation et meilleure
exploitation au niveau des fonctionnalités de notre outil. Grace aux fenêtres inclut dans
notre interface graphique, et les différents boutons et menu, l’utilisateur n’aura pas besoin
d’écrire la moindre ligne de code ou soucier de comprendre les algorithmes implémentées
dans l’application, ce qui induit une large facilité d’utilisation.
2 Description de l’outil 23
1) Fenêtre principale
Une fois l’application lancée, une fenêtre comme sur la figure 2.2 sera affichée, c’est
notre première et principale fenêtre. Elle comprend les éléments suivants : une barre de
menue (1), une barre d’outils (2), un espace de travail (3), un espace d’affichage de la
matrice de transition en temps réel (4), une barre d’état (5).
Nous allons dans ce qui suit présenter les éléments cités ci-dessus ainsi que d’autres
fenêtres.
2) Barre de menus
La barre de menus offre à l’utilisateur la possibilité d’accéder à un ensemble de menus
organiser comme suit : Fichier, Projet, Outils, Aide.
Figure 2.2 : Fenêtre principal de l’application.
2 Description de l’outil 24
Fichier : Le menu Fichier contient les éléments suivants :
- Nouveau Projet : qui permet de créer un nouvel espace de travail tout en alertant
l’utilisateur et prenant en considération que s’il y a un travail en cours, ce dernier sera
interrompu et risque d’être perdu s’il n’a pas été sauvegardé.
- Ouvrir un projet : ouvre une boite de dialogue qui donne la possibilité de choisir un
fichier de travail qui a déjà été sauvegarder par l’utilisateur afin d’éviter de le refaire
depuis le début et continuer l’édition si besoin. Le fichier doit porter l’extension
(.Markov) pour être sure que c’est un fichier valide et a été conçu par notre application.
Figure 2.3 : Menu fichier, élément nouveau projet.
Figure 2.4 : Message d'alerte nouveau projet.
2 Description de l’outil 25
- Enregistrer sous : un sous menu qui contient lui-même deux sous éléments :
Enregistrer en format projet Markovien celui-là permet de sauvegarder le travail
courant réaliser à n’importe quel moment dans un fichier d’extension
(. Markov) associé avec notre application et contenant le travail effectué avec ses
différents paramètres en donnant le choix à l’utilisateur de choisir le chemin
d’enregistrement et le nom du fichier.
Enregistrer en format Image PNG cet option en effet permet de prendre une capture
de l’espace de travail et l’enregistrer dans un répertoire qui sera choisis par l’utilisateur.
Figure 2.5 : Boite de dialogue ouverture d'un projet.
Figure 2.6 : Menu fichier, élément ouvrir un projet.
2 Description de l’outil 26
- Fermer : permet de quitter l’application tout en proposant à l’utilisateur de vérifier s’il
existe un travail en cours non enregistrer car il risque de le perdre, dans le cas contraire
il peut ignorer ce message et fermer l’application.
Figure 2.7 : Menu fichier, élément enregistrer.
Figure 2.8 : Menu fichier, élément fermer, message d'alerte de fermeture de
l'application.
2 Description de l’outil 27
Projet : on trouve dans le menu projet les fonctionnalités suivantes :
Le menu projet contient des fonctions à appliquer sur la CMTD, ces fonctions
permettent de faire des calculs et afficher des résultats :
- Vérifier si la chaîne est irréductible : affiche dans un message si la chaîne présenter
dans l’espace de travail est irréductible ou pas avec justification.
L’algorithme utilisé pour vérifier l’irréductibilité :
function isIrreductible( LinkedList[] listAdjacence,LinkedList listEtat ){
/* Nous modifions la liste d'adjacence telle que
chaque état va contenir les etats qu'il atteint indirectement aussi*/
for (int i = 0; i < listAdjacence.length; i++) {
for (int j = 0; j < listEtat.size(); j++) {
if (!listAdjacence[i].contains(listEtat.get(j))) {
for (int h = 0; h < listAdjacence[i].size(); h++) {
int p = listAdjacence[i].get(h);
if (listAdjacence[p].contains(listEtat.get(j))) {
if (!listAdjacence[i].contains(listEtat.get(j))) {
listAdjacence[i].add(listEtat.get(j));
break;
}
}
}
}
}
}
Figure 2.9 : Menu projet, élément irréductibilité, message de
résultat : irréductibilité.
2 Description de l’outil 28
/*si chaque etat contient tout les etats de la chaine alors elle'est
irreductible*/
for (int i = 0; i < listAdjacence.length; i++)
if (listAdjacence[i].size() != listEtat.size())
return false;
else
return true;
}
- Vérifier s’il existe des circuits dans la chaîne : affiche dans un message les différents
états et les circuits appropriés.
L’algorithme utilisé pour trouver les circuits :
Nous avons utilisé l’algorithme de Johnson en le modifiant pour qu’il marche avec nos
données disponibles : [7]
/** Noeuds blockés utilisés par l'algorithme de Johnson */
boolean[] blocked = null;
/** B-Lists, utilisés par l'algorithme de Johnson */
Vector[] B = null;
/** Pile pour noeuds, utilisé par l'algorithme de Johnson */
LinkedList<Integer> stack = null;
/**la liste des cycles qu'on veut obtenir**/
LinkedList<LinkedList> cycles = new LinkedList<>();
Figure 2.10 : Message de résultat : circuit.
2 Description de l’outil 29
public boolean findCycles(int v, int s, LinkedList<Integer>[] graph) {
boolean f = false;
this.stack.add(v);
this.blocked[v] = true;
for (int i = 0; i < graph[v].size(); i++) {
int w = graph[v].get(i);
// cycle trouvé, on l’ajoute dans la liste par depiler la pile
qui a enregistré le chemin
if (w == s) {
LinkedList cycle = new LinkedList<>();
for (int j = 0; j < this.stack.size(); j++) {
cycle.add(this.stack.get(j));
}
this.cycles.add(cycle);
f = true;
}
// si on a pas trouvé un cycle on continue a faire le parcous
de la chaine par récursivité
else if (w < this.blocked.length && !this.blocked[w]) {
if (this.findCycles(w, s, graph)) {
f = true;
}
}
}
if (f) {
this.unblock(v);
} else {
for (int i = 0; i < graph[v].size(); i++) {
int w = graph[v].get(i);
if (!this.B[w].contains(v)) {
this.B[w].add(v);
}
}
}
this.stack.remove(new Integer(v));
return f;
}
private void unblock(int node) {
this.blocked[node] = false;
Vector Bnode = this.B[node];
while (Bnode.size() > 0) {
Integer w = (Integer) Bnode.get(0);
Bnode.remove(0);
if (this.blocked[w]) {
this.unblock(w);
}
}
}
2 Description de l’outil 30
- Vérifier s’il existe des états absorbants : vérifie et affiche dans un message si la chaîne
contient des états absorbants ou non et spécifie ces derniers.
- Vérifier si la chaîne est ergodique : vérifie et affiche dans un message si la chaîne est
ergodique ou pas avec justification.
Figure 2.11 : Message de résultat : absorbant.
Figure 2.12 : Message de résultat : ergodique.
2 Description de l’outil 31
- Calculer la période : contient elle-même deux sous fonctions, la première calcule et
affiche la période de la chaîne, la deuxième est pour un seul état choisi depuis une liste
par l’utilisateur.
Figure 2.13 : Menu projet, élément calculer la période.
Figure 2.14 : Message de résultat : période de la
chaîne.
Figure 2.15 : Message de résultat période d'un état.
2 Description de l’outil 32
Outils : Le menu outils se compose des éléments suivants :
- Centrer la chaîne : permet de positionner la chaîne au milieu de l’espace de travail.
Figure 2.16 : Effet de l’élément centrer la chaîne.
- Afficher la matrice de transition : permet d’afficher la matrice de transition dans une
nouvelle fenêtre et l’enregistrer en dehors de l’application.
Figure 2.17 : Menu outils, élément afficher la matrice.
2 Description de l’outil 33
- Affichage du vecteur de distribution à l’instant n : affiche dans une nouvelle fenêtre le
vecteur de distribution correspondant à chaque instant.
Figure 2.18 : Fenêtre d’affichage de la matrice.
Figure 2.19 : Fenêtre d'affichage du vecteur de
distribution.
2 Description de l’outil 34
- Paramètres du projet : servent à personnaliser la chaîne de Markov en spécifiant les
différentes options disponibles comme la forme, la couleur et la taille des états et des
arcs et aussi la précision des calculs (le nombre après la virgule) dans l’analyse.
Figure 2.20 : Fenêtre paramètres : tabulation analyse, tabulation chaîne.
2 Description de l’outil 35
- Affichage de la chaîne : sert à organiser les éléments de la chaîne en trois différents
styles d’affichages qui sont circulaire, organique et arbre (voir figure 2.21).
Figure 2.21 : Menu outils, élément affichage de la chaîne, exemples.
Aide : Le menu aide contient essentiellement les éléments :
- Aide d’utilisation : Ouvre une page web qui explique les chaines de Markov et donne
des exemples d’utilisation de chaque fonctionnalité de notre application par des vidéos
de courte durées.
2 Description de l’outil 36
Figure 2.22 : Page d’aide d’utilisation de l’application.
- À-propos : affiche dans une nouvelle fenêtre des informations concernant
l’application, nos noms, la date de création…etc.
3) Barre d’outils
La barre d’outils est un élément de base des interfaces graphiques (un widget) qui
regroupe en une barre plusieurs boutons. Il s'agit donc d'une rangée d'icônes regroupées
en un bloc.
2 Description de l’outil 37
Quand l’utilisateur fait passer le curseur de la souris sur un bouton, ce dernier va
afficher un texte explicatif qui permet de savoir le rôle du bouton. Les boutons sont
partagés en 3 groupes, le premier et le deuxième groupe sont composer de trois boutons
et respectivement dédier pour les états et les arcs de transition, le troisième contient un
seul bouton permettant de lancer l’analyse de la CMTD, qui donnera lieu à deux types
d’analyse qui sont l’analyse transitoire et l’analyse stationnaire.
4) Espace de travail
L’espace de travail est représenté par une feuille de dessin blanche où l’utilisateur va
dessiner la chaîne de Markov grâce aux boutons de la barre d’outils.
Figure 2.23 : Barre d'outils, élément
ajouter un état.
Figure 2.24 : Barre d'outils.
2 Description de l’outil 38
Figure 2.25 : Espace de travail, exemple d'ajout, suppression et modification d'états et
transitions.
4) Espace d’affichage de la matrice de transition
La matrice à afficher est d’ordre 9, si elle le dépasse un message comme sur la figure
2.26 apparait. La matrice change à chaque fois que l’utilisateur modifie des états ou des
transitions.
2 Description de l’outil 39
5) Barre d’état
En informatique, c’est la partie d'une fenêtre où est affiché l'état de l’application
associé à la fenêtre. Elle consiste en une barre horizontale qui est affichée en bas.
Dans la suite on va présenter des exemples sur les différentes instructions à suivre et
les erreurs qui peuvent être affichées :
- Des messages avec la manipulation des états et des arcs. (Voir figure 2.27)
- Des messages lors de lancement de l’analyse. (Voir figure 2.28)
Figure 2.28 Barre d'état, exemples des messages, état et transition.
Figure 2.26 : Message d'affichage de matrice espace
insuffisant. Figure 2.27 : Espace d'affichage de la
matrice.
2 Description de l’outil 40
Figure 2.29 : Barre d'état, exemples des messages, analyse.
2.2.3 Exemple applicatif
Nous mettons dans cette partie, un exemple d’une CMTD qu’on va analyser avec
l’application.
On construit la CMTD présenté sur la figure 2.30, et on commence l’analyse en
cliquant sur le bouton rouge ‘Analyser’ on choisit le type d’analyse, dans cet exemple
c’est transitoire, une fois valider, une fenêtre comme sur la figure 2.31 s’affiche. Nous
allons expliquer la fonction de chaque bouton de la barre d’outils dans la suite.
Figure 2.30 : Analyser une chaîne, choisir le type d'analyse.
2 Description de l’outil 41
1 Faire une animation du calcul : permet d’avancer dans le calcul en affichant les
différentes étapes une par une, et d’une certaine vitesse spécifiée dans le Slider. Et permet
aussi d’arrêter l’animation du calcul si elle est en cours.
2 Calcul par étape +1 : permet d’avancer d’une seule étape dans le calcul.
3 Calcul direct : permet de donner le calcul à l’instant n spécifié dans le Combobox
par l’utilisateur.
4 Réinitialiser le calcul : avec ce bouton on revient à l’instant 0 et nous pouvons
même refaire le choix de l’état initial.
5 Revenir au dessin du graphe : comme le titre l’indique ce bouton nous permet de
revenir vers l’interface qui nous permet l’édition de la chaîne.
Remarque : l’état initial est représenté avec la couleur vert, une fois dans l’analyse
transitoire l’utilisateur pourra le changer en cliquant sur le nouvel état désirer.
Figure 2.31 : Fenêtre analyse transitoire.
2 Description de l’outil 42
2.2.4 Discussion des résultats obtenus
Chaque ligne du tableau représente la probabilité que le système se trouve à l’instant
n dans l’état i.
Les résultats en vert qui sont affichés sous les états de la chaîne sont ceux de l’instant
en cours, dans notre exemple c’est 10.
Figure 2.32 : Résultat du calcul après l'analyse transitoire d'une CMTD.
2 Description de l’outil 43
Nous remarquons qu’avec notre application, nous pouvons atteindre une précision de
18 chiffres après la virgule et on peut aller jusqu’à un million d’instants dans des fractions
de seconde, ce qui est infaisable avec des calculatrices classiques.
L’utilisateur peut également sauvegarder ces résultats dans un fichier Excel à afin de
les comparer ou d’effectuer d’autres opérations.
2 Conclusion 44
2.3 Conclusion
Nous avons présenté dans ce chapitre, l’application que nous avons implémentée et
avec ces différentes fonctionnalités. En premier lieu nous avons donné le diagramme qui
décrit les cas d’utilisations de l’application, puis l’environnement que nous avons choisi
et ensuite nous avons décrit l’interface de notre application en donnant des détails
concernant les différentes fenêtres, messages et fonctionnalités. Enfin nous avons étudier
un exemple de chaîne de Markov et appliquer l’analyse transitoire pour tester
l’application en notons les résultats obtenus.
En effet, il ressort de ce chapitre l’utilité et l’importance de notre application et la
réalisation des méthodes d’analyse des chaînes de Markov à temps discret sur un outil
informatique.
Conclusion Générale
L’objectif principal de notre travail était de concevoir un outil informatique qui permet
d’analyser les chaînes de Markov à temps discret.
Afin d’atteindre cet objectif, nous nous sommes penchés, dans un premier temps, à
découvrir les processus stochastiques et étudier les chaînes de Markov et leurs essentielles
propriétés qui vont être indispensables pour l’implémentation. Après avoir compris les
chaînes de Markov nous avons implémenter des algorithmes qui permettent de
représenter, modifier, supprimer, enregistrer et calculer avec les deux méthodes d’analyse
dans une application en utilisant des interfaces graphiques. Nous nous sommes basés sur
trois critères de qualité : l’efficacité, la simplicité et la portabilité.
Ce projet a été très bénéfique pour nous, car il nous a permis de renforcer et enrichir
nos connaissances théoriques dans le domaine des probabilités et la modélisation et
évaluation des systèmes, ainsi qu’à nos connaissances pratiques en mettant notre
expérience acquise le long de nos études. Il nous a encore donné l’occasion de mieux
maitriser le langage de programmation Java et l’orienter objet, en plus ce projet était une
bonne occasion pour réaliser un travail très concret, avec des objectifs intéressants et bien
définis et de se familiariser avec l’environnement du travail professionnelle.
Enfin, et comme perspective, nous pouvons améliorer notre application en ajoutant
d’autres cas d’utilisations comme le cas de chaînes de Markov à temps continue, la
manipulation de plusieurs projets dans la même fenêtre, et l’optimisation des algorithmes
de calculs.
Bibliographie
[1] F. Schnitzler, L. Wehenkel. Introduction aux processus
stochastiques, support de cours rappel de probabilités, Université de
Liège, Février 2010.
[2] M. Diener. Chapitre 2 Chaînes de Markov compléments de cours,
Université de Nice - Sophia Antipolis, 2007.
[3] G. Montcouquiol. Théorie des graphes, support de cours, IUT
Orsay, 2006-2007.
[4] D. Flipo. Chaînes de Markov, Thèse de Doctorat, EUSTL, 2007.
[5] N. Gharbi. Chaînes de Markov, Support de cours, chapitre 2,
USTHB, 2011.
[6] B. de Werra. T. M. Liebling and J. F. Heche. Recherche
opérationnelle pour les ingénieurs II. Paris, 2003.
[7] Johnson's Algorithm, Find All simple cycles in a directed graph,
https://github.com/mission-peace/interview/blob/master/src/com/
interview /graph/AllCyclesInDirectedGraphJohnson.java, 06/2016.
Résumé
Les besoins et les exigences des utilisateurs des systèmes actuels ne cessent de s’accroitre.
Pour cela, des efforts considérables sont réalisés afin d’améliorer la qualité du service offert,
ce qui nécessite une évolution permanente. Cette évolution rend la construction, la gestion et
la maintenance de ces systèmes de plus en plus complexe. D’où la nécessité d’une approche
formelle rigoureuse permettant l’analyse des performances de ces systèmes pour en contrôler
le développement avant leur construction.
Parmi les modèles formels les plus utilisés dans le domaine de l’évaluation des performances,
nous trouvons les chaînes de Markov et plus particulièrement les chaînes de Markov à temps
discret. Ces processus stochastiques caractérisés par la propriété markovienne (perte de
mémoire) et par la prise en compte des probabilités de transition entre états, sont très adaptés
à la modélisation ainsi que l’évaluation des performances de divers types de systèmes dont
les états possibles sont dénombrables et ce en régime transitoire ou encore stationnaire.
Le but de ce projet de licence, est la conception ainsi l’implémentation d’un outil permettant
l’édition (saisi, modification ou suppression) de modèles basés sur le formalisme des chaînes
de Markov à temps discret décrivant tout type de système. Cet outil doit aussi permettre à
l’utilisateur de calculer les indices de performance choisis par ce dernier.
Mot clés : Chaîne de Markov - Processus stochastique – Java - Matrice stochastique – GUI
- Graphe – Modélisation - Analyse transitoire