Inférence d'automates de Mealy sans ré-initialisation : Différence entre versions

De Ensiwiki
Aller à : navigation, rechercher
(Page créée avec « {{Sujet irl | labo = LIG | titre = Inférence d'automates de Mealy sans ré-initialisation | equipe = VASCO | encadrants = Catherine.Oriat@imag.fr }} Catégorie:IRL ==... »)
 
(Thème général)
Ligne 13 : Ligne 13 :
 
que l'on dispose de modèles du programme. Comme de tels modèles ne sont pas
 
que l'on dispose de modèles du programme. Comme de tels modèles ne sont pas
 
toujours disponibles, différentes méthodes d'inférence ont été proposées pour
 
toujours disponibles, différentes méthodes d'inférence ont été proposées pour
reconstruire ces modèles.  
+
reconstruire ces modèles.
 +
 
 +
On suppose que le système peut être représenté, à un certain niveau
 +
d'abstraction, par une machine à états finie ayant certaines entrées
 +
et sorties (automates de Mealy). L'équipe VASCO du LIG s'intéresse
 +
depuis plusieurs années aux techniques d'inférence "active", qui
 +
consistent construire cette machine à états en observant ses sorties
 +
en fonction de différentes entrées. Ces techniques d'apprentissage
 +
reposent sur des tests en boîte noire, ne supposent pas qu'on dispose
 +
du code source, ni même du code binaire du logiciel.
  
 
===  Contexte du travail ===  
 
===  Contexte du travail ===  

Version du 6 octobre 2015 à 14:28


Inférence d'automates de Mealy sans ré-initialisation

Labo LIG
Equipe VASCO
Encadrants Catherine.Oriat@imag.fr

Thème général

Le développement rigoureux de logiciel, basé sur des méthodes formelles, exige que l'on dispose de modèles du programme. Comme de tels modèles ne sont pas toujours disponibles, différentes méthodes d'inférence ont été proposées pour reconstruire ces modèles.

On suppose que le système peut être représenté, à un certain niveau d'abstraction, par une machine à états finie ayant certaines entrées et sorties (automates de Mealy). L'équipe VASCO du LIG s'intéresse depuis plusieurs années aux techniques d'inférence "active", qui consistent construire cette machine à états en observant ses sorties en fonction de différentes entrées. Ces techniques d'apprentissage reposent sur des tests en boîte noire, ne supposent pas qu'on dispose du code source, ni même du code binaire du logiciel.

Contexte du travail

On suppose que le système peut être représenté, à un certain niveau d'abstraction, par une machine à états finie ayant certaines entrées et sorties (automates de Mealy). L'équipe VASCO du LIG s'intéresse depuis plusieurs années aux techniques d'inférence "active", qui consistent construire cette machine à états en observant ses sorties en fonction de différentes entrées. Ces techniques d'apprentissage reposent sur des tests en boîte noire, ne supposent pas qu'on dispose du code source, ni même du code binaire du logiciel.

Sujet

La plupart des algorithmes d'inférence supposent qu'on peut à tout moment replacer le système dans son état initial (opération de ré-initialisation). Cette hypothèse n'est pas satisfaite par tous les systèmes ; parfois cette opération est possible, mais très coûteuse en temps.

L'objectif de ce travail consiste à formaliser et implémenter un algorithme combinatoire d'inférence de machine sans ré-initialisation. Cet algorithme pourra ensuite être comparé à un algorithme développé par Rivest et Schapire [RV89], qui pourra être implémenté dans la plateforme d'inférence SIMPA développée au sein de l'équipe VASCO.

[RS89] Ronald L. Rivest, Robert E. Schapire. Inference of finite automata using homing sequences. Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, 1989.

Résultats attendus

  • Formalisation d'un algorithme d'inférence combinatoire
  • Implantation de cet algorithme et de l'algoritme de Rivest et Schapire dans la plateforme d'inférence SIMPA
  • Comparaison expérimentale de la complexité des deux algorithmes

Compétences nécessaires

Connaissances en théorie des langages : automates