Peupler un vecteur de chiffres pour exposer une erreur dans une exécution de la fonction

Question

Alors disons que j'écris un algorithme qui prend un vecteur comme entrée. Je veux savoir que j'écris cet algorithme correctement correctement, donc je sais bien sûr des tests pour voir si la sortie est égale à ce que j'attends sur des intrants spécifiques. En fait, je pourrais le faire pour toutes les tailles de vecteur sous une certaine taille, mais je n'éumérerais jamais toutes les valeurs possibles, toutes les tailles de vecteur possibles.

Cela me survient cependant qu'il pourrait être possible de remplir les valeurs du vecteur de telle sorte que je puisse toujours vérifier tous les vecteurs possibles sous une certaine taille tant que je prends une certaine hypothèse sur la mise en œuvre de la fonction à tester.

dire que j'ai une fonction $ f: \ mathbb {n} ^ n \ to \ mathbb {n} $ telle que $ f (x)=sum_ {i= 1} ^ nc_i \ prod_ {j= 1} ^ n x_j ^ {e_ {ij ^ {e_ {ij ^ {e_ {ij}} $ pour certains $ E $ et $ C $ tel que $ e_ {ij} \ in \ {0,1 \} $ et $ C_I \ in \ {0, 1 \} $ . Je veux voir si cela est égal à une fonction dorée connue $ g $ mais je vais devoir travailler manuellement $ g $ pour des intrants spécifiques. Je crois qu'il est vrai qu'il existe une entrée $ r $ tel que $ f (r) $ Détermine de manière unique $ F $ . Cela fait des tests pour voir si une implémentation particulièrement de $ f $ est celle que nous attendions de manière triviale facile.

pour $ n= 2 $ Les valeurs possibles de $ f (3, 7) $ sont ce qui suit: 0, 1, x= 3, y= 7, xy= 21, 2, 1 + x= 4, 1 + y= 8, 1 + xy= 22, x + x= 6, x + y= 10, x + xy= 24, xy + xy= 42

Donc, si je fais en supposant qu'une fonction partitruclar que je teste a ce qui précède est caractérisée par $ C $ C $ et $ E $ Puis, je n'ai besoin que d'une entrée pour tester complètement une implémentation de $ F $

.

.

Une bonne heuristique pour générer ces entrées consiste à démarrer avec le premier prime plus élevé que le nombre de termes que vous avez, puis essayez des nombres premiers successivement plus élevés pour chaque entrée suivante jusqu'à ce que vous éliminiez les quelques kinks qui restent. L'intuition est qu'aucun produit ne sera identique parce que vous avez choisi des nombres premiers et que chaque produit unique sera espacé de sorte que les sommes éventuellement toutes seules aussi.

Y a-t-il un algorithme pour générer une entrée à une telle fonction qui rend toutes les fonctions de telles fonctions entraîne des valeurs uniques? Et si nous sommes prêts à être probabilistes dans un sens comme "la sortie attendue est probablement unique pour cette entrée"? Y a-t-il d'autres formes de fonctions pour lesquelles cette question a été étudiée?

Answer 1

polynômes multilinéaires

Si vous êtes prêt à utiliser des méthodes probabilistes, je suggère d'utiliser un algorithme randomisé pour les tests d'identité polynomiale.

Vous voulez tester si $ f (x)= g (x) $ est content pour tous $ x $ < / span>, où $ f, g $ sont des oolynomiales multilignes. Ceci est une instance de Test d'identité polynomiale problème. Il existe des algorithmes randomisés efficaces pour les tests d'identité polynomiale.

Pour faire cette réponse autonome, je vais vous donner un bref aperçu d'un algorithme raisonnable. Premièrement, choisissez au hasard une grande classe principale $ P $ . Suivant, choisissez aléatoirement $ x= (x_1, \ dots, x_n) $ , avec chaque élément $ x_i $ Choisissez uniformément à Random Modulo $ P $ . Enfin, vérifiez si $ p (x) \ equiv g (x) \ pmod p $ . Si non, vous savez que votre mise en œuvre est défectueuse. Si oui, alors votre mise en œuvre a de bonnes chances d'être bon. (En particulier, une implémentation défectueuse qui calcule un autre polynôme multilinéaire a une faible probabilité d'aller non détectée, grâce au SCHWartz-ZIpple Lemma .) Vous pouvez répéter cette procédure plusieurs fois pour des garanties plus fortes.

Cette procédure suppose que vous pouvez inspecter le code de l'algorithme et vérifier qu'il calcule un polynôme multilinéaire, ce qui semble être quelque chose que votre question propose de pouvoir assumer. Si vous avez une boîte noire complète et que vous n'avez aucune connaissance, qu'il s'agisse d'un polynôme multilinéaire ou non, vous ne pouvez pas obtenir de fortes garanties que $ f $ sera correct partout partout partout : Par exemple, votre implémentation $ F $ peut être correcte sur toutes les entrées sauf une sauf une fois qu'elle est spéciale à émettre la mauvaise réponse.

cas plus généraux

Vous pourriez être intéressé par la théorie des auto-tests, pionnier de Blum, Luby, Rubinfeld et développé par d'autres personnes. Voir, par exemple, le papier seminal suivant:

Auto-tester / corriger avec des applications aux problèmes numériques . Blum manuel, Michael Luby, Ronitt Rubinfeld. Journal of Computer et System Sciences, 47 (3), 549-595.

Ils généralisent votre idée en considérant des testeurs qui invoquent plusieurs fois le programme-test multiple; En permettant des tests probabilistes, où il est possible de remarquer des problèmes, mais cette probabilité peut être contrôlée ou bornée; et en permettant à l'auto-correction, où nous utilisons le programme éventuellement défectueux en tant que sous-programme pour construire une sortie qui sera correcte avec une probabilité élevée. Néanmoins, malgré ces généralisations, la classe de fonctions que nous savons construire des auto-testeurs efficaces est assez limitée et nous ne savons pas comment le faire pour des fonctions arbitraires.