Универсальные автоматы как модели функционального восстановления поведения дискретных систем

• Автор: Вагарина, Наталия Сергеевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Саратов
• Количество страниц: 115 с.

ГЛАВА 1. Математические модели функционального
восстановления поведения дискретных систем
1Л. Основные положения и обозначения
1.2. Постановка задачи функционального восстановления поведения сложных систем
1.3. Универсальные автоматы как математические модели функционального восстановления поведения
ГЛАВА 2. Универсальность в классах групповых автоматов
ф 2.1. Критерии универсальности для класса групповых
автоматов
2.2. Теорема о существовании универсального перечислителя
для класса групповых автоматов
2.3. Метод синтеза универсального перечислителя для класса групповых автоматов
ГЛАВА 3. Полнота и анализ универсальных автоматов
ГЛАВА 4. Применение модели универсального автомата для
решения задач технической диагностики
ЗАКЛЮЧЕНИЕ
® Список литературы
Практическое и теоретическое значение автоматных моделей в решении задач проектирования и технического диагностирования, изучении процессов формирования и передачи сигналов в сложных системах стало причиной интенсивных исследований теории автоматов как математической модели сложных систем. В настоящее время практически в любой сфере человеческой деятельности мы встречаемся с понятием "система". Это объясняется постоянным усложнением технологических объектов, конструкций, устройств, технологий. Термин "система" служит обозначением таких общих понятий, как "целое, составленное из частей", "совокупность элементов, образующих некий порядок". Таким образом, категория "быть системой" присуща как объектам материальной природы (материальные системы), так и объектам, порожденным умозрительным рассуждением (концептуальные системы). Среди концептуальных систем выделяется класс абстрактных систем, являющихся математическими моделями материальных систем. Особый интерес представляют системы, обладающие поведением или законом функционирования. В системном анализе под поведением понимается "совокупность причинно-следственных связей, реализуемых системой при своей работе".
В процессе эксплуатации сложных систем с течением времени может происходить трансформация их первоначального поведения. Это обусловлено самим характером материальной природы систем. Дж. фон Нейман в своей работе указывал, что "...неисправности компонент... существенная и неотъемлемая часть их работы" [20]. В широком смысле восстановление поведения означает возврат объекта к реализации заданного функционирования после возникновения, обнаружения и локализации неисправности без физического устранения дефекта. Организация восстановления поведения сложной системы включает в себя комплекс следующих задач:
- обеспечение восстанавливаемости поведения объекта на этапе его проектирования;
- самодиагностирование и самовосстановление объекта в процессе функционирования;
- применение спектра восстановительных процедур и приемов физического устранения последствий возникшего дефекта.
Наиболее часто для модификации поведения используются два основных вида избыточности — структурная и временная. Однако выход из строя структурного резервирования порождает вопрос: "Можно ли использовать свойства текущего закона функционирования автомата для формирования на выходах требуемой совокупности реакций?". Ответ на него предполагает изучение имеющейся в данный момент времени функциональной избыточности системы, а также возможных вариантов её целенаправленного создания на этапе проектирования. Восстановление поведения, осуществляемое на указанных принципах, называют функциональным. Функциональное восстановление опирается на принцип обучения Я.З. Цыпкина [30]. В случае функционального восстановления поведения текущий закон функционирования выступает как "обучающаяся" система, которая после приложения специальных "обучающих" последовательностей должна генерировать сигналы, эквивалентные реакциям исправного поведения. Формальная постановка задачи функционального восстановления поведения была сделана A.A. Сытником.
В данной работе исследуется восстановление поведения дискретных систем и в качестве математической модели системы выбран конечный детерминированный автомат. Исследованию общей теории автоматов и возможностей ее прикладного использования посвящены работы таких специалистов как М.А. Айзерман, М. Арбиб, Я.М. Барздинь, Б.А. Трахтенброт,
A.М. Богомолов, Д.В. Сперанский, В.И. Варшавский, М.А. Гаврилов,
B.М. Глушков, А. Гилл, И.Е. Кобринский, В.Б. Кудрявцев, О.П. Кузнецов, В.Г. Лазарев, М. Минский, К. Шеннон, Дж. фон Нейман, A.A. Сытник, В.А. Тверохлебов, Дж. Ульман, М.Л. Цетлин, С.В. Яблонский и другие
автоматные подстановки
и 8к всегда реализуют функцию переходов
универсального автомата для класса 3' то есть порождают группу МЗп ■ Пусть 1>3. Выберем обозначения таким образом, чтобы было / > / > / > 1. Четная
автоматная подстановка
4 • • • 4-і 4+1 • • ■ 4 ч4 ...4+1 4+2 ••■51)
принадлежит группе МЗп и вместе
с 8к в силу следствия теоремы 2.1.3. реализует функцию переходов универсального автомата для класса 3^ _ то есть порождает знакопеременную группу автоматных преобразований соответствующих элементов. Эта группа
содержит автоматные подстановки
4-і 4 4+і
, г-3 4 где 4+7 означает
состояние из подстановки 8к, не принадлежащее последовательности (*)
другой стороны, подстановка
принадлежит группе мз и
множество подстановок
4+1
V 4 4+і 4-і
, г-2,..Щ в силу леммы 2.1.2 порождает
группу МЗп. Следовательно, это верно и для подстановок 8,, 1=1,...к. Лемма
доказана Лемма 2Л.6.
Пусть дан универсальный перечислитель М=(3,Х, 8) для автоматов из класса Зи (3^) с множеством состояний 5-(0,...я-1), п>2 и множеством
входных символов Х=(хо хр). Тогда автомат М' = (3',Х',8'), такой что 5" = 5,и+?„, 8'= 81)8,, где 8автоматная подстановка степени п+1, содержащая состояние п в цикле порядка больше 1, является универсальным перечислителем для автоматов из класса 3 +1 ( 3^ +1).
Доказательство
Пусть г (0