Изучается временная сложность алгоритмов диагностики схем из функциональных элементов в зависимости от числа входов в схеме. Возможные неисправности в схемах представляют собой различные комбинации ∧- и ∨-замыканий между собой и в совокупности или с константными неисправностями, или с неисправностями типа «отрицание». Для диагностики таких неисправностей используются деревья решений (условные тесты). Показано, что для диагностики произвольно заданной схемы с n, n ≥ 4, входами в зависимости от типа элементов в схеме и вида неисправностей нужно подать самое меньшее C(n) входных наборов, а самое большее – 2n, где C(n) – сумма чисел сочетаний из n - 1 по [(n - 1) / 2] и из n - 1 по [(n - 1) / 2] + 1.

схема из функциональных элементов, неисправность, сложность диагностики, условный тест

Математические вопросы и теория численных методов