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

De Ensiwiki
Aller à : navigation, rechercher
(Contexte du travail)
(Sujet)
Ligne 38 : Ligne 38 :
  
 
=== Sujet ===
 
=== Sujet ===
 
+
L'objectif de ce travail de recherche consiste à étudier une optimisation
La plupart des algorithmes d'inférence supposent qu'on peut à tout moment
+
de l'algorithme ICTSS2015
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 ===
 
=== Résultats attendus ===

Version du 6 octobre 2015 à 14:30


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

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.

Plusieurs algorithmes ont été proposés pour inférer des automates de Mealy sans ré-initialisation, en particulier l'algorithme ICTSS2015 [GS2015]. Un certain nombre des ces algorithmes sont implémentés dans la plateforme SIMPA.

Sujet

L'objectif de ce travail de recherche consiste à étudier une optimisation de l'algorithme ICTSS2015

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