Мы применяем методы, первоначально развитые в теории информации и кодирования, для решения некоторых задач тестирования. Эффективность двухуровнего группового тестирования n объектов характеризуется минимальным математическим ожиданием числа E(n,p) тестов для Бернулли p-схемы, где минимум берется по всем матрицам, которые определяют тесты первого уровня. Теоретико-информационная граница показывает, что естественное желание достичь E(n,p)=o(n) при n → ∞ может быть осуществимо только если p(n) → 0. Используя случайный выбор и линейное программирование мы оцениваем некоторые параметры двоичных матриц, чтобы определить, с точностью до положительных констант, каким образом асимптотическое поведение E(n,p) при n → ∞ зависит от степени стремления p(n) → 0. В частности, показано, что при p(n)=n-β+o(1), где 0<β<1, асимптотическая эффективность двухуровневого метода не может быть улучшена переходом к многоуровнему адаптивному тестированию.
Ключевые слова:
коды свободные от покрытий, дизъюнктивное
тестирование, линейное программирование, групповое тестирование, случайный выбор, алгоритмы восстановления, отбор.
