Nombre minimum de tests pour identifier le sous-ensemble de modules qui déclenchent un bogue?
-
31-10-2019 - |
Question
J'ai un ensemble commandé de modules logiciels $ M $ compilés ensemble. L'interaction de quelque $ n $ -tuple de ces modules provoque un bogue lorsque le programme est exécuté.
Je peux exécuter le programme avec n'importe quel sous-ensemble souhaité des modules activés / désactivés, afin que je puisse tester le programme en l'exécutant avec un certain sous-ensemble de modules activés et en voyant s'il se bloque ou non (appelez cela "un test"). Je voudrais identifier les modules $ n $ qui causent ce problème avec le nombre minimal de tests. Supposons qu'un test particulier entraînera un accident si et seulement s'il inclut tous les modules problématiques $ N $ (et peut-être d'autres; mais au moins ces $ N $).
$ N $ est connu à l'avance.
Pour $ n = 1 $, je peux identifier efficacement le coupable dans $ log_2 (m) $ tests par recherche binaire.
Pour d'autres valeurs de $ n $, quelle approche puis-je adopter pour identifier les coupables $ n $?
Pas de solution correcte