Utilisation des Structures Combinatoires pour le Test Statistique

Plan
Utilisation des
Contexte
Structures Combinatoires Structures combinatoires
Test statistique et qualité de testpour le Test Statistique
Nouvelle approche du test statistique
Tirer des chemins
Optimiser la qualité de test
Validation de l’approche
Le prototype AuGuSTeSandrine-Dominique GOURAUD
Résultats expérimentaux
Équipe “Programmation et Génie Logiciel”, L.R.I.
Bilan et Perspectives
Co-encadrants: M.-C. Gaudel et A. Denise
2
Les structures combinatoires décomposables
La spécification de structures combinatoires
consiste en un ensemble de règles de
production construites à partir:Contexte
d’objets de base: (de taille 0) et atome (de taille 1)
d’opérateurs: union(+), produit(x), sequence, etc.
de contraintes de cardinalité
Exemples:
Arbre binaire complet non vide: A= F+ AxA
où F est l’atome de base représentant une feuille
Séquence de 3 à 5 feuilles: S= Sequence(F,Card=3..5)
4
Les structures combinatoires décomposables Le test de logiciel
Résultats théoriques sur la génération aléatoire Objectif: trouver des fautes/erreurs dans
uniforme de telles structures [Flajolet,Zimmermann,VanCutsem,1994] les programmes
Complexité en n*log n pour des structures Comment? En exécutant le programme
combinatoires de taille n sur un ensemble de données qu’on
Complexité linéaire dans certains cas particuliers appelle jeu de test.
Outils disponibles pour l’environnement MuPAD: Les difficultés:
Le package CS [Corteel, Denise,Dutour,Sarron,Zimmermann] Trouver les bons jeux de ...