MIAGE Master 1: Recherche Opérationnelle I TD2: le 26/09/2007

Ecrire et tester un programme en C qui lit des informations sur une chaîne de Markov et affiche des conclusions sur la classification des états.

Les entrées

Un entier n (inférieur ou égal à 100); une matrice stochastique de taille n par n.

Le programme doit lire ces informations d’un fichier; il n’y aura pas de ponctuation entre les valeurs. Des exemples du format d’un

fichier sont disponibles en ~jrobson/RO/[jeu|livraison|grand].dat

Les sorties

Plusieurs niveaux de programme sont à essayer dans l’ordre:

1. La division des états en classes

2. Pour chaque classe si elle est finale ou de passage

3. Si la chaîne a une seule classe finale

(a) si la classe finale est périodique ou non.

(b) si elle est périodique, la période, et la division en sousclasses.

4. si vous avez assez de temps Calculer les matrices des probabilités P^{m} et observer le nombre d’itérations nécessaires avant qu’elles convergent vers leur comportement asymptotique (à 5 chiffres près).

Squelette

Un programme squelette est disponible en ~jrobson/RO/squelette.c qui effectue la lecture du fichier et qui contient des procédures pour le calcul des puissances d’une matrice par la méthode des carrés.