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

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top