Оценки длин тестов для функциональных элементов при большом числе допустимых неисправностей

Рассматриваются задачи проверки исправности и диагностики состояний $N$ функциональных элементов, реализующих в исправном состоянии заданную булеву функцию $f(x_1,\dots,x_n)$, путём составления из них схем с одним выходом и наблюдения выдаваемых этими схемами значений на любых входных наборах значений переменных. Допускаются произвольные константные неисправности на выходах функциональных элементов; при этом предполагается, что не более $k$ элементов неисправны, где $k$ – заданное натуральное число, не превосходящее $N$. Требуется минимизировать число схем, необходимых для проверки исправности и определения состояний всех элементов. Получена нижняя оценка на число указанных схем в случае, когда $k$ близко к $N$. В качестве следствия из этой оценки установлено, что при выполнении некоторого условия на $N$ и принадлежности $k$ некоторому отрезку число таких схем не может быть меньше $ck$, где $c>1$ – константа, не зависящая от выбора числа $k$ из этого отрезка. Библиогр. 15.