Projet Java TTT 2009-2010

Générateur aléatoire par chaîne de Markov


Date de rendu : 15 février 2010


I. Présentation

Le but du projet est de faire un programme qui prend une séquence de valeurs comme modèle, et produit un générateur aléatoire de séquences qui ressemblent au modèle.

Soit O un ensemble d'objets du même type.
Le modèle est une séquence d'objets S=[o1,o2,...,on], avec n grand. Si P=[p1,...,pm] est une séquence de m ≤ n objets, on note n(P,S) le nombre de fois qu'apparaît P dans S. Par exemple, n([a,a,b,a], [c,a,a,b,a,a,b,a,b,b]) = 2.

La chaîne de Markov CM d'ordre k ≥ 2 de S donne, pour chaque séquence P=[p1,...,p{k-1}], une loi de probabilité sur l'ensemble des objets O. Ainsi, CM(P,o) est la probabilité que l'objet o apparaisse à la suite de la séquence P.
Celle-ci est donc obtenue à partir du modèle S par

CM(P,o)=n([p1,...,p{k-1},o],S)
n(P,S)

Le projet consiste à calculer à partir d'une séquence d'objets une représentation de la fonction CM, puis de s'en servir pour générer aléatoirement des séquences d'objets.

II. Un ensemble probabilisé

Dans un premier temps, réalisez une classe ProbaSet<O> qui représente une ensemble d'objets pondéré dans N (chaque objet o de l'ensemble a un poids entier p(o)). La classe possède obligatoirement les méthodes suivantes :

III. Un k-buffer

Réalisez une classe KBuffer<O> qui permet de parcourir les blocs de k objets d'une séquence d'objets de type O. Elle doit posséder les méthodes suivantes :

IV. Une chaîne de Markov

Réalisez une classe MarkovChain<O> qui simule l'application CM de la partie I. En fait, on associe à chaque séquence P=[p1,...,p{k-1}] un objet de la classe ProbaSet<O> contenant, pour chaque objet o qui peut suivre P dans S, l'objet o avec le poids n([p1,...,p{k-1},o],S). Par exemple si S est une séquence de caractères S="aabaabbaaba" et que k=4, l'objet MarkovChain<Character> associe à la séquence "aab" le ProbaSet<Character> {(a,2),(b,1)} puisque a suit deux fois "aab" dans S et b une fois.

Elle doit posséder les méthodes suivantes :

V. Un constructeur de chaîne de Markov

Réalisez une classe MarkovChainBuilder qui contient des méthodes static pour générer des chaînes de markov :

VI. Rendu du projet

Le rendu du projet consiste en une archive zip contenant les sources du projet et des fichiers permettant de tester le projet, ainsi qu'un rapport en pdf. L'archive doit être nommée JavaTTT_XXXX_YYYY.zipXXXX et YYYY sont les noms des auteurs du projet; le désarchivage doit créer un répertoire de même nom JavaTTT_XXXX_YYYY dans lequel se trouvent tous les fichiers rendus.

Dans votre rapport :


Annexe : un exemple détaillé

On considère pour cet exemple une séquence S contenant n=10 objets représentés par des images :

S=

Fabrication de la chaîne de Markov :

On prend k=3. Il s'agit donc dans un premier temps, de fabriquer une simulation c de la CM en associant à tout couple (k-1=2) d'images (o1,o2) une liste probabilisée d'images. Elle est calculée, pour chaque couple (o1,o2) qui a une image, en regardant quels sont les images qui suivent (o1,o2) dans S. Par exemple, la séquence apparaît 3 fois dans S; une fois suivie par et deux fois suivie par . En procédant ainsi pour tous les couples possibles, on a au final :
c() = {  (,1), (,2)  }
c() = {  (,1)   }
c() = {  (,1)   }
c() = {  (,1), (,2)   }
c()= {  (FIN,1)   }


Utilisation de la chaîne de Markov :

Une fois la CM calculée, on peut générer aléatoirement des séquences. Pour cela on se donne un paramètre size, ici size=6, qui correspond au nombre maximum d'objets générés, et d'un début start qui est une séquence de taille k-1. Ici il s'agit donc d'un couple, et on prend start= pour l'exemple.

La génération se déroule de la façon suivante, au début P=start et évolue au fur et à mesure. Le résultat est une séquence R qui est vide au début :