Введение к работе
Актуальность темы. В работе изучаются возможности эффективного решения задачи диагностики неисправностей схем иэ функциональных элементов (СЮ) с помощью условных тестов.
Начало математической теории контроля было положено работами С.В.Яблонского и И. А. Чегис". В частности, в этих работах на примере контактных схем и схем из функциональных элементов даются описания основных задач теории контроля и способов их решения.
Проблемы контроля и диагностики являются одними из основных в математической кибернетике и теоретической информатике. Рассматриваемые в диссертации СФЭ представляют собой математическую модель дискретных устройств, в которых время преобразования входных сигналов в выходные существенно мало по сравнению с длительностью сигналов (устройства комбинационного типа или устройства без памяти). Такие устройства широко используются в *ычислительной технике. Для СФЭ в настоящей работе определяется большое семейство типов неисправностей. В частности это семейство включает в себя такие хорошо известные типы неисправностей, как константные неисправности, неисправности типа "отрицание", 'V- и "v''-замыкания и всевозможные их комбинации.
Цель работы. Для всевозможных базисов СФЭ (конечных непустых множеств булевых функция, существенно зависящих от всех своих переменных) и типов неисправностей исследование
"Яблонский СВ. , Чегис И. А. О тестах для электрических схем // УМН. - 1955. - 10, вып. 4(56). - С. 182 - 184.
Чегис И. А., Яблонский С.В. Логические способы контроля электрических схем// Тр. МИ АН СССР.- 1958.- 51.- С. 270-360.
-/-
минимальной глубины условных тестов, диагностирующих неисправности, в зависимости от сложности СФЭ в худшем случае (исследование соответствующей функции Шеннона).
Научная новизна. Основные результаты работы состоят в следующем. Для всевозможных базисов СФЭ и типов неисправностей получены верхние и нижние оценки функции Шеннона. Показано, что для любого базиса СФЭ и типа неисправностей из рассматриваемого семейства функция Шеннона с ростом сложности СФЭ или ограничена сверху, константой, или растет линейно, или растет быстрее любого наперед заданного полинома. Отметим, что в первых двух случаях условные тесты, диагностирующие неисправности, имеют эффективное описание.
Все основные результата являются оригинальными.
Теоретическая и практическая ценность. Работа имеет теоретическую направленность. Полученные результаты могут быть использованы в дальнейших исследованиях возможностей условных тестов для решения задач контроля и диагностики неисправностей СФЭ, а также при обучении студентов по специальности прикладная математика.
Апробация работы. Результаты, представленные в диссертации, докладывались на Всесоюзных конференциях по проблемам теоретической кибернетики (Иркутск, 1985, Горький, 1988, Волгоград, 1990), на Всесоюзных семинарах по дискретной математике и ее приложениям (Москва,1989,1991,1993), на семинаре Научного Совета АН УССР по проблеме "Кибернетика" (Донецк, 1990), на Международных конференциях "Интеллектуальные системы" (Москва, 1992,1993), на Межгосударственных школах-семинарах по синтезу и сложности управляющих систем (Н.Новгород, 1992, 1994, Минск, 1993), на
Международной конференции по грубым множествам и компьютерным вычислениям ССША, Сан-Хосе, 1994), на Международной научной конференции "Математические модели в теории управлявших систем" СМосква, 1995), на семинарах в Нижегородском и Московском университетах.
Публикации. Результаты по теме диссертации опубликованы в работах С1 - 111.
Структура и обьем работы. Диссертация изложена на 149 страницах машиннописного текста. Состоит из введения, четырех глав и списка литературы, содержащего 44 наименования.