Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья в сборнике "Математические вопросы кибернетики" №10, Москва, 2001
Авторы: Шевченко В.И.
О сложности диагностики неэлементарных замыканий в схемах из функциональных элементов
Аннотация:
Изучается временная сложность алгоритмов диагностики схем из функциональных элементов в зависимости от числа входов в схеме. Возможные неисправности в схемах представляют собой различные комбинации ∧- и ∨-замыканий между собой и в совокупности или с константными неисправностями, или с неисправностями типа «отрицание». Для диагностики таких неисправностей используются деревья решений (условные тесты). Показано, что для диагностики произвольно заданной схемы с n, n ≥ 4, входами в зависимости от типа элементов в схеме и вида неисправностей нужно подать самое меньшее C(n) входных наборов, а самое большее – 2n, где C(n) – сумма чисел сочетаний из n - 1 по [(n - 1) / 2] и из n - 1 по [(n - 1) / 2] + 1.
Ключевые слова:
схема из функциональных элементов, неисправность, сложность диагностики, условный тест
Язык публикации: русский, страниц: 36 (с. 103-138)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст: Сведения об авторах:
  • Шевченко Владимир Иванович,  ,  Институт информационных технологий, математики и механики, ННГУ им. Н.И.Лобачевского