Abstract FR:

Cette thèse traite de la résolution de modèles markoviens pour l'évaluation des performances de systèmes complexes. L'approche adoptée est l'étude des propriétés structurelles de la chaîne de Markov. Dans une première partie, nous nous plaçons dans le cas général des chaînes de Markov qui n'ont pas, à priori, de structure particulière. En utilisant la méthode de réduction pour la résolution de la distribution stationnaire et des techniques de la théorie des graphes, nous recherchons une structure particulère dans la chîne permettant la diminution du temps de calcul. Cette structure particulière dans la chîne permettant la diminution du temps de calcul. Cette structure particulière revient à chercher un FVS (Feedback Vertex Set) de taille minimum (problème NP-dur) sur le graphe associé à la chaîne de Markov. Une généralisation de ces techniques est proposée. Elle utilise des permutations sur la matrice associée ou des échanges successifs de prédécesseurs ou des successeurs entre sommets du graphe. Dans une deuxième partie, nous abordons deux structures de chaînes de Markov particulières pour lesquelles nous proposons des méthodes de résolution directes adaptées à ces structures. Les chaînes de Markov étudiées sont des QBD (Quasi Birth and Death process). La première structure particulière est issue d'un modèle de réseau UMTS où le QBD a un espace d'états fini. Nous montrons qu'un algorithme simple, utilisant les techniques proposées dans la première partie, permet de calculer efficacement différents indices de performances (taux de perte,. . . ) La seconde structure particulière que nous étudions correspond aux QBD à un espace d'états infini ayant des propriétés particulières, notés LG (Level Geometric). Nous définissons et caractérisons cette propriété. Nous montrons qu'n utilisant cette propriété, il est possible de calculer la distribution stationnaire plus simplement.