Содержание к диссертации
Введение
ГЛАВА 1. Математические модели функционального восстановления поведения дискретных систем 11
1.1. Основные положения и обозначения 12
1.2. Постановка задачи функционального восстановления поведения сложных систем 15
1.3. Универсальные автоматы как математические модели функционального восстановления поведения 19
ГЛАВА 2. Универсальность в классах групповых автоматов 40
2.1. Критерии универсальности для класса групповых автоматов 41
2.2. Теорема о существовании универсального перечислителя для класса групповых автоматов 68
2.3. Метод синтеза универсального перечислителя для класса групповых автоматов 83
ГЛАВА 3. Полнота и анализ универсальных автоматов 89
ГЛАВА 4. Применение модели универсального автомата для решения задач технической диагностики 100
Заключение 111
Список литературы 113
- Постановка задачи функционального восстановления поведения сложных систем
- Универсальные автоматы как математические модели функционального восстановления поведения
- Теорема о существовании универсального перечислителя для класса групповых автоматов
- Метод синтеза универсального перечислителя для класса групповых автоматов
Введение к работе
Практическое и теоретическое значение автоматных моделей в решении задач проектирования и технического диагностирования, изучении процессов формирования и передачи сигналов в сложных системах стало причиной интенсивных исследований теории автоматов как математической модели сложных систем. В настоящее время практически в любой сфере человеческой деятельности мы встречаемся с понятием "система". Это объясняется постоянным усложнением технологических объектов, конструкций, устройств, технологий. Термин "система" служит обозначением таких общих понятий, как "целое, составленное из частей", "совокупность элементов, образующих некий порядок". Таким образом, категория "быть системой" присуща как объектам материальной природы (материальные системы), так и объектам, порожденным умозрительным рассуждением (концептуальные системы). Среди концептуальных систем выделяется класс абстрактных систем, являющихся математическими моделями материальных систем. Особый интерес представляют системы, обладающие поведением или законом функционирования. В системном анализе под поведением понимается "совокупность причинно-следственных связей, реализуемых системой при своей работе".
В процессе эксплуатации сложных систем с течением времени может происходить трансформация их первоначального поведения. Это обусловлено самим характером материальной природы систем. Дж. фон Нейман в своей работе указывал, что ".. .неисправности компонент... существенная и неотъемлемая часть их работы" [20]. В широком смысле восстановление поведения означает возврат объекта к реализации заданного функционирования после возникновения, обнаружения и локализации неисправности без физического устранения дефекта. Организация восстановления поведения сложной системы включает в себя комплекс следующих задач:
обеспечение восстанавливаемости поведения объекта на этапе его проектирования;
самодиагностирование и самовосстановление объекта в процессе функционирования;
применение спектра восстановительных процедур и приемов физического устранения последствий возникшего дефекта.
Наиболее часто для модификации поведения используются два основных вида избыточности - структурная и временная. Однако выход из строя структурного резервирования порождает вопрос: "Можно ли использовать свойства текущего закона функционирования автомата для формирования на выходах требуемой совокупности реакций?". Ответ на него предполагает изучение имеющейся в данный момент времени функциональной избыточности системы, а также возможных вариантов её целенаправленного создания на этапе проектирования. Восстановление поведения, осуществляемое на указанных принципах, называют функциональным. Функциональное восстановление опирается на принцип обучения ЯЗ. Цыпкина [30]. В случае функционального восстановления поведения текущий закон функционирования выступает как "обучающаяся" система, которая после приложения специальных "обучающих" последовательностей должна генерировать сигналы, эквивалентные реакциям исправного поведения. Формальная постановка задачи функционального восстановления поведения была сделана А.А. Сытником.
В данной работе исследуется восстановление поведения дискретных систем и в качестве математической модели системы выбран конечный детерминированный автомат. Исследованию общей теории автоматов и возможностей ее прикладного использования посвящены работы таких специалистов как М.А. Айзерман, М. Арбиб, Я.М. Барздинь, Б.А. Трахтенброт, A.M. Богомолов, Д.В. Сперанский, В.И. Варшавский, М.А. Гаврилов, В.М. Глушков, А. Гилл, И.Е. Кобринский, В.Б. Кудрявцев, О.П. Кузнецов, В.Г.Лазарев, М. Минский, К.Шеннон, Дж. фон Нейман, А.А. Сытник, В.А. Тверохлебов, Дж. Ульман, М.Л. Цетлин, СВ. Яблонский и другие. При
построении математических моделей законов функционирования рассматриваются различные типы отношений между входной и выходной информацией, что определяет различные виды поведения. Так, поведение конечных детерминированных автоматов может рассматриваться в преобразовательной и перечислительной формах. В первом случае анализируется процесс реализации заданного отображения между множествами последовательностей входных и выходных сигналов. Во втором акцент переносится на результаты преобразования входных сигналов. То есть в центре внимания находится вопрос об определении по заданной выходной реакции совокупности последовательностей входных сигналов, ее индуцирующих. Необходимость рассмотрения перечислительной формы поведения обусловлена тем, что возникновение неисправности в системе приводит к нарушению преобразовательного способа переработки информации.
Способность математической модели поведения к имитации функционирования некоторого заданного множества объектов рассматриваются в рамках теории универсальных автоматов. Ее возникновение связано с работами К.Шеннона, М. Минского, Дж. фон Неймана, наметивших основные направления исследования. Существует два подхода к понятию «универсальность».
Первый из них связан с понятием функциональной полноты и однородной структуры, В 1956 году М. Минский в работе [1, стр.163] поставил задачу о построении универсального автомата как базового объекта для создания некоторой однородной структуры, реализующей поведение любого из заданного множества элементов - "определенная категория множеств элементов "универсальна" в том смысле, что из таких элементов можно собрать машины, реализующие произвольные...функции". В той же работе [1, стр.177] элемент назван универсальным, если некоторое, достаточно большое множество объектов "обладает некоторыми подобными свойствами этого элемента или отличающимися лишь в количественном отношении". В 1960 году в [4] впервые дано формальное определение универсального объекта как
математической модели, образующей функционально полную систему. Исследование данного подхода на множестве ограниченно-детерминированных функций проведено В.Б. Кудрявцевым и В.А. Буевичем [10, стр.65].
Изучение второго подхода к понятию универсальность связано с ответом на вопрос - «существует ли конечный детерминированный автомат, моделирующий поведение любого из заданного множества автомата только за счет изменения соответствующих входных воздействий?». Одновременно с исследованиями М.Минского, в работе К. Шеннона [1, стр.214] показана возможность построения универсальной машины Тьюринга, имитирующей функционирование произвольной машины Тьюринга при помощи настройки соответствующими входными воздействиями. А. Тьюринг [1, стр.230] показал возможность построения некоторой вычислительной машины универсальной в том смысле, что на ней путем подходящего кодирования можно выполнять любое вычисление, которое могла бы выполнить любая заданная машина Тьюринга. Затем М. Дэвис [1] и Р. Петер [1] получили ряд условий, определяющих в явном виде метод построения команд универсальной машины Тьюринга. Дальнейшие исследования понятия "универсальность" были посвящены уточнению и конкретизации указанных походов на множествах булевых функций и конечных детерминированных автоматов. К их числу следует отнести работы Э.В. Евреинова и И.В. Прангишвили [15], В.И. Варшавского [9], В.А. Мищенко и др. [19], Я.М. Барздиня [5], В.М. Глушкова [13] и др.
Итак, универсальный автомат должен иметь способность моделировать, порождать, воспроизводить (соответственно по Шеннону, Минскому и фон Нейману) заданный спектр поведений или объектов. То есть понятия «восстановление поведения» и «универсальный автомат» взаимосвязаны. Таким образом, теория универсальных автоматов служит фундаментальной основой для решения задачи функционального восстановления поведения и универсальный автомат является математической конструкцией, на основании свойств которой решается задача восстановления поведения.
Как показано А.А. Сытником [24] задача построения универсального автомата относительно произвольного семейства КДА алгоритмически не разрешима, так же как и задача восстановления поведения для произвольной сложной системы. Однако, задача построения универсального конечного детерминированного автомата относительно конечного семейства конечных детерминированных автоматов алгоритмически разрешима. В настоящее время предпринимаются попытки выделить классы, для которых это задача имеет решение. Например, Т.Э. Шульгой [32] проведена работа по исследованию числовой модели конечного детерминированного автомата, в частности, описан класс автоматов, допускающих моделирование семействами степенных многочленов, и для него решена задача функционального восстановления поведения.
Таким образом, возможность восстановления поведения относительно заданного класса неисправностей предполагает синтез универсального автомата для заданного класса. Решение задачи синтеза - универсальный автомат - с содержательной точки зрения способен заменить любой автомат заданного класса при возникновении неисправностей. С другой стороны, интерес представляет решение задачи анализа универсального автомата, которая может быть сформулирована следующим образом: для произвольного конечного детерминированного автомата М определить класс конечных автоматов, для каждого из которых М есть универсальный.
Итак, данная работа посвящена исследованию моделей функционального восстановления поведения сложных систем дискретного типа. Цель работы состоит в выделении класса конечных детерминированных автоматов, разрешимого относительно задачи функционального восстановления поведения. Для этого были поставлены и решены следующие задачи:
задача синтеза универсальных автоматов в классе групповых автоматов;
задача анализа универсальных автоматов классе (л,2);
- задача построения отказоустойчивых систем дискретного типа с
использованием модели универсального автомата.
Методологическую основу работы составляют теоретико-автоматные и алгебраические методы.
К новым результатам, полученным в данной работе можно отнести следующее:
разработана и исследована модель универсального автомата-перечислителя для класса групповых автоматов;
разработан и исследован метод применения модели универсального автомата-перечислителя для решения задачи функционального восстановления поведения в классе групповых автоматов;
найдены критерии универсальности конечного детерминированного автомата для класса групповых автоматов;
доказано существование универсального перечислителя вида М - (S, X, {Sx, 5К }) для класса групповых автоматов;
найден метод синтеза универсального перечислителя для класса групповых автоматов;
решена задача функционального восстановления поведения в классе групповых автоматов;
найден критерий решения задачи анализа произвольного универсального автомата из класса (w,2);
решена задача функционального восстановления поведения в классе автоматов (п,2);
предложена схема построения отказоустойчивых систем дискретного типа с использованием модели универсального автомата.
Работа выполнена на 115 страницах машинописного текста, состоит из оглавления, введения, 4 глав, заключения и списка литературы.
Во введении формулируются цели и задачи работы, дается краткий обзор по исследуемой теме, излагаются основные результаты и описывается структура диссертации.
В первой главе вводятся основные положения и обозначения, используемые в работе, дается содержательная постановка задачи функционального восстановления поведения сложных систем, вводятся основные понятия и определения теории универсальных автоматов, дается формальная постановка задачи функционального восстановления поведения в терминах универсальных автоматов.
Вторая глава посвящена решению задачи синтеза универсального автомата в классе групповых автоматов. В ней разработана и исследована модель универсального автомата-перечислителя для класса групповых автоматов, разработан и исследован метод применения модели универсального автомата-перечислителя для решения задачи функционального восстановления поведения в классе групповых автоматов, найдены критерии универсальности КДА для класса групповых автоматов (теоремы 2.1.4 и 2.1.5), доказано существование универсального перечислителя для класса групповых автоматов вида М' = (S,X,{5х, д^}) (теорема 2.2.1), найден метод синтеза универсального
перечислителя для класса групповых автоматов (параграф 2.3), решена задача восстановления поведения в классе групповых автоматов (теорема 2.2.3).
В третьей главе рассматривается задача анализа относительно произвольного универсального автомата из класса (и,2). Найден критерий решения задачи анализа произвольного универсального автомата. Показано, что решением задачи анализа является множество автоматов, пересечение (Х,5)-гомоморфных образов которых содержит заданный универсальный автомат (теорема 3.2), решена задача восстановления поведения в классе автоматов (и,2) (теорема 3.3).
В четвертой главе рассматривается возможность прикладных применений универсального автомата для решения задач технической диагностики. А именно рассматривается применение универсальных автоматов для построения отказоустойчивых систем дискретного типа, основанное на способности универсального автомата моделировать поведение заданного класса объектов.
Показано, что сложность получаемой схемы контроля не зависит от роста сложности рассматриваемой системы (теорема 4.5).
В заключении диссертации суммируются полученные результаты.
Основные результаты докладывались и обсуждались на пятом международном конгрессе по математическому моделированию (Россия, Дубна, 2002), на международной научно-технической конференции "Искусственный интеллект. Интеллектуальные и многопроцессорные системы» (Таганрог, 2004), на V международной конференции «Автоматизация проектирования дискретных систем» (Минск, 2004), на XIV Международной конференции «Проблемы теоретической кибернетики» (Пенза, 2005 г.), на семинарах Института проблем точной механики и управления РАН, Саратовского государственного университета, Саратовского государственного социально-экономического университета, на внутривузовских конференциях Саратовского социально-экономического университета.
Основные результаты работы содержатся в 7 статьях автора.
Постановка задачи функционального восстановления поведения сложных систем
Как показано А.А. Сытником [24] задача построения универсального автомата относительно произвольного семейства КДА алгоритмически не разрешима, так же как и задача восстановления поведения для произвольной сложной системы. Однако, задача построения универсального конечного детерминированного автомата относительно конечного семейства конечных детерминированных автоматов алгоритмически разрешима. В настоящее время предпринимаются попытки выделить классы, для которых это задача имеет решение. Например, Т.Э. Шульгой [32] проведена работа по исследованию числовой модели конечного детерминированного автомата, в частности, описан класс автоматов, допускающих моделирование семействами степенных многочленов, и для него решена задача функционального восстановления поведения.
Таким образом, возможность восстановления поведения относительно заданного класса неисправностей предполагает синтез универсального автомата для заданного класса. Решение задачи синтеза - универсальный автомат - с содержательной точки зрения способен заменить любой автомат заданного класса при возникновении неисправностей. С другой стороны, интерес представляет решение задачи анализа универсального автомата, которая может быть сформулирована следующим образом: для произвольного конечного детерминированного автомата М определить класс конечных автоматов, для каждого из которых М есть универсальный.
Итак, данная работа посвящена исследованию моделей функционального восстановления поведения сложных систем дискретного типа. Цель работы состоит в выделении класса конечных детерминированных автоматов, разрешимого относительно задачи функционального восстановления поведения. Для этого были поставлены и решены следующие задачи: - задача синтеза универсальных автоматов в классе групповых автоматов; - задача анализа универсальных автоматов классе (л,2); - задача построения отказоустойчивых систем дискретного типа с использованием модели универсального автомата. Методологическую основу работы составляют теоретико-автоматные и алгебраические методы. К новым результатам, полученным в данной работе можно отнести следующее: - разработана и исследована модель универсального автомата-перечислителя для класса групповых автоматов; - разработан и исследован метод применения модели универсального автомата-перечислителя для решения задачи функционального восстановления поведения в классе групповых автоматов; - найдены критерии универсальности конечного детерминированного автомата для класса групповых автоматов; - доказано существование универсального перечислителя вида М - (S, X, {Sx, 5К }) для класса групповых автоматов; - найден метод синтеза универсального перечислителя для класса групповых автоматов; - решена задача функционального восстановления поведения в классе групповых автоматов; - найден критерий решения задачи анализа произвольного универсального автомата из класса (w,2); - решена задача функционального восстановления поведения в классе автоматов (п,2); - предложена схема построения отказоустойчивых систем дискретного типа с использованием модели универсального автомата. Работа выполнена на 115 страницах машинописного текста, состоит из оглавления, введения, 4 глав, заключения и списка литературы. Во введении формулируются цели и задачи работы, дается краткий обзор по исследуемой теме, излагаются основные результаты и описывается структура диссертации. В первой главе вводятся основные положения и обозначения, используемые в работе, дается содержательная постановка задачи функционального восстановления поведения сложных систем, вводятся основные понятия и определения теории универсальных автоматов, дается формальная постановка задачи функционального восстановления поведения в терминах универсальных автоматов. Вторая глава посвящена решению задачи синтеза универсального автомата в классе групповых автоматов. В ней разработана и исследована модель универсального автомата-перечислителя для класса групповых автоматов, разработан и исследован метод применения модели универсального автомата-перечислителя для решения задачи функционального восстановления поведения в классе групповых автоматов, найдены критерии универсальности КДА для класса групповых автоматов (теоремы 2.1.4 и 2.1.5), доказано существование универсального перечислителя для класса групповых автоматов вида М = (S,X,{5х, д }) (теорема 2.2.1), найден метод синтеза универсального перечислителя для класса групповых автоматов (параграф 2.3), решена задача восстановления поведения в классе групповых автоматов (теорема 2.2.3).
В третьей главе рассматривается задача анализа относительно произвольного универсального автомата из класса (и,2). Найден критерий решения задачи анализа произвольного универсального автомата. Показано, что решением задачи анализа является множество автоматов, пересечение (Х,5)-гомоморфных образов которых содержит заданный универсальный автомат (теорема 3.2), решена задача восстановления поведения в классе автоматов (и,2) (теорема 3.3).
В четвертой главе рассматривается возможность прикладных применений универсального автомата для решения задач технической диагностики. А именно рассматривается применение универсальных автоматов для построения отказоустойчивых систем дискретного типа, основанное на способности универсального автомата моделировать поведение заданного класса объектов. Показано, что сложность получаемой схемы контроля не зависит от роста сложности рассматриваемой системы (теорема 4.5). В заключении диссертации суммируются полученные результаты.
Основные результаты докладывались и обсуждались на пятом международном конгрессе по математическому моделированию (Россия, Дубна, 2002), на международной научно-технической конференции "Искусственный интеллект. Интеллектуальные и многопроцессорные системы» (Таганрог, 2004), на V международной конференции «Автоматизация проектирования дискретных систем» (Минск, 2004), на XIV Международной конференции «Проблемы теоретической кибернетики» (Пенза, 2005 г.), на семинарах Института проблем точной механики и управления РАН, Саратовского государственного университета, Саратовского государственного социально-экономического университета, на внутривузовских конференциях Саратовского социально-экономического университета.
Универсальные автоматы как математические модели функционального восстановления поведения
Существует широкий спектр определений понятия "система" [24, стр.7], отражающих различные подходы при исследовании выделенного множества свойств и характеристик заданной области приложений. В 1955 году была дана формулировка, явившаяся исходной, в современном толковании систем: "Система есть комплекс элементов, находящихся во взаимодействии". Одним из видов систем являются системы, порожденные умозрительным рассуждением (концептуальные системы). Среди концептуальных систем выделяется класс абстрактных систем, являющихся математическими моделями материальных систем.
Цель моделирования - исследование объектов, процессов, явлений в различных областях. Результаты этих исследований служат для определения и улучшения характеристик реальных объектов и процессов; для понимания сути явлений и их прогнозирования; выработки умения приспосабливаться или управлять ими; для конструирования новых объектов или модернизации старых. Моделирование выступает как метод познания, состоящий в создании и исследовании моделей.
В процессе эксплуатации сложных систем с течением времени может происходить трансформация их первоначального поведения. Это обусловлено самим характером материальной природы систем. В современных условиях развития и становления информационного общества все большее значение приобретает поиск новых способов восстановления поведения сложных систем. Интуитивное понятие термина "восстановление поведения" является многогранным и допускает толкование в широких пределах - от устранения причины изменения закона функционирования до организации сложного взаимодействия между исследователем и объектом восстановления с конструированием в процессе восстановления и стратегии проведения восстановления заданного поведения. Термин "восстановление поведения" может рассматриваться в таких контекстах как: - метод изучения функциональных возможностей системы; - специфический метод преобразования текущего поведения к некоторому заданному; - один из вариантов организации действий исследователя для достижения в системе требуемой формы функционирования. В качестве метода изучения восстановление поведения может применяться: - при исследовании свойств взаимосвязи и взаимодействия различных режимов работы системы; - для определения устойчивости закона функционирования и структуры системы относительно произвольного типа неисправностей; - для выработки на стадии проектирования обоснованного прогноза и соответствующих рекомендаций по отказоустойчивости и восстанавливаемости будущего поведения системы на стадии проектирования. Организация восстановления поведения сложной системы включает в себя комплекс следующих задач: - обеспечение восстанавливаемости поведения объекта на этапе его проектирования; - самодиагностирование и самовосстановление объекта в процессе функционирования; - применение спектра восстановительных процедур и приемов физического устранения последствий возникшего дефекта. Традиционным подходом к решению данных задач является предположение о наличии структурной или временной избыточности в рассматриваемых технических системах. В этом случае задача реализации заданного функционирования возлагается на имеющийся структурный или временной резерв. Выход из строя структурного резервирования порождает вопрос о возможности использования свойств текущего закона функционирования системы для формирования на выходах требуемой совокупности реакций. То есть предполагается изучение функциональной избыточности системы, а также возможных вариантов её целенаправленного создания на этапе проектирования. Эти вопросы изучаются в рамках альтернативного подхода, заключающегося в попытке восстановить правильное функционирование за счет использования только поведенческих свойств и особенностей объекта. Восстановление поведения, осуществляемое на указанных принципах, называют функциональным. Содержательная постановка задачи восстановления поведения дискретных систем с памятью выглядит следующим образом: реальное поведение системы отличается от заданного, определено текущее поведение, требуется: 1. Определить возможность восстановления исходного поведения 2. Найти совокупность преобразований системы, позволяющих восстановить исходное поведение Формальная постановка задачи восстановления поведения сложной системы выглядит следующим образом: Пусть рассматриваемое множество / вариантов поведения сложной системы представлено множеством математических моделей поведения r v/}/e/. Множество Q. средств преобразования поведения сложной системы определено как множество отображений № х вида гиг для некоторых дополнительных вариантов поведения Г\ порожденных действиями средств преобразования поведения на Г. Правила F расшифровки преобразованных вариантов поведения сложной системы заданы отображением ВИДаЯ (Г )- Гі Для заданных эталонного (требуемого) варианта поведения У и подмножества вариантов поведения г« (го порождается учитываемым классом неисправностей сложной системы) требуется найти такое преобразование , для которого выполняется условие: SF((Г0)) - {їй} _ Обшую постановку задачи (в терминах задачи функционального восстановления поведения) можно интерпретировать следующим образом: некоторый рассматриваемый класс неисправностей сложной системы порождает множество вариантов ее поведения . При ограничениях на средства восстановления поведения, определяемых О. и правилах расшифровки новых вариантов поведения F находится такое преобразование со сложной системы, которое позволяет изменить любой вариант поведения из ffl(ro) в эталонный вариант поведения . Возникновение неисправностей в условиях отсутствия резервирования приводит к нарушению преобразовательного принципа, так как для некоторого входного символа наблюдаемая реакция отличается от заданной, а значит восстановление поведения в преобразовательной форме невозможно. Таким образом, в случае функционального восстановления поведения происходит переход от преобразовательной формы описания закона функционирования к перечислительной. Выражение "восстановить правильное функционирование" в этой терминологии равносильно замене "неисправного" входного сигнала (при подаче которого происходит нарушение работы системы) на "исправное" входное воздействие (возможно набор входных сигналов), вызывающих требуемую выходную реакцию.
Теорема о существовании универсального перечислителя для класса групповых автоматов
Группа подстановок из п символов называется симметрической группой Sn степени п. Утверяедение 1.3.5.
Все четные подстановки из п символов с определенной операцией умножения подстановок в качестве групповой операции составляют группу. Нечетные подстановки степени п группы не составляют. Определение 1.3.15. Группа всех взаимно однозначных отображений некоторого множества М на самого себя с последовательным выполнением отображений в качестве их умножения называется группой преобразований. Если множество V конечно и состоит из п элементов, то группа преобразований превращается в симметрическую группу степени п. Определение 1.3.16.
Пусть дано некоторое множество М. Назовем всякое взаимно однозначное отображение множества М на себя по аналогии с подстановками конечных множеств подстановкой в множестве М, а всякую подгруппу группы всех взаимно однозначных отображений М на себя группой подстановок над М. Если М конечно и состоит из п элементов, то группы подстановок над М (подгруппы симметрической группы и-ой степени), будут называться группами подстановок степени п. Определение 1.3.17.
Группа подстановок над множеством М называется транзитивной, если всякий элемент множества Af может быть переведен некоторой подстановкой из этой группы в любой другой элемент этого множества. Определение 1.3.18.
Транзитивная группа подстановок над множеством М называется непримитивной, если множество М можно так разложить на непересекающиеся истинные подмножества Ми хотя бы одно из которых содержит не менее двух элементов (Mi называются системами импримитивности группы), чтобы выполнялось следующее требование: если элемент а из любой системы импримитивности Mi переводится некоторой подстановкой в элемент Ъ, содержащийся в системе импримитивности Мг , то всякий элемент ИЗ М/ переводится этой подстановкой в некоторый элементт из Л 2- Если такое разложение невозможно, то группа называется примитивной.
Одним из подходов к решению задачи функционального восстановления поведения является алгебраический. А именно, с алгебраической точки зрения проблема организации целенаправленного поведения может быть сформулирована следующим образом: приложение каждого входного символа индуцирует на множестве внутренних состояний - выходных реакций преобразование, которое относительно операции умножения (суть переход от подачи входных символов к последовательностям входных символов) образует полугруппу преобразований. Множество всех преобразований, индуцируемых всеми входными символами, в этом случае выступает порождающим множеством данной полугруппы. Таким образом, в этих терминах возникновение неисправности приводит к удалению или изменению соответствующего преобразования из порождающего множества. Самовосстановление в этом случае означает возможность его построения из оставшихся элементов при помощи операции умножения. То есть вопрос об изменении поведения сводится к вопросу конструктивного поиска механизма построения необходимой полугруппы (новое поведение) из имеющегося порождающего множества. Таким образом, все основные свойства КДА могут быть найдены через инициируемые ими полугруппы, исследуемые традиционными алгебраическими методами.
В данной работе рассматривается случай, когда полугруппа является группой. В следующем разделе приведены результаты, определяющие условия универсальности автомата для класса групповых автоматов. В частности, в них определяется явный вид функции переходов универсального конечного детерминированного автомата. Доказательство полученных результатов основывается на свойствах симметрической группы перестановок. На основе вспомогательных лемм и теорем доказаны критерии, определяющие вид пары автоматных подстановок, образующих функцию переходов автомата, универсального для класса групповых конечных детерминированных автоматов.
Метод синтеза универсального перечислителя для класса групповых автоматов
Целью данной главы является продолжение изучения свойств модели универсального автомата, начатого в предыдущих главах. Основное внимание уделяется вопросам применения универсальных автоматов как математической модели перенастраиваемых технических объектов для решения задач технической диагностики.
Непрерывный рост сложности реальных технических систем приводит к необходимости создания методов контроля и диагностирования максимально независимых от исследуемого объекта. Разработка методов такого рода может быть представлена как решение совокупности следующих задач:
Создание методов построения тестов с использованием "минимально возможного" количества информации о технической системе, и, в то же время, применимого для достаточно широкого класса схем.
Создание математической модели, содержащей некоторый заданный класс (например, множество неисправностей) объектов, и реализующий их при определенном входном воздействии. Модель универсального автомата может быть предложена в качестве такого объекта. Поэтому, для создания "универсальных" средств контроля и диагностирования необходимо решить первую задачу. Данная глава посвящена исследованию возможности применения универсального автомата, как математической модели перенастраиваемых технических объектов, для решения задач технической диагностики. Рассмотрим некоторую систему R , состоящую из компонент Пусть {Аи...Ак}-1 - конечные детерминированные автоматы, описывающие законы функционирования соответственно модулей Rl,...Rk Согласно методу, приведенному при доказательстве теоремы 1.З.З., построим А/ - автомат универсальный относительно класса /, то есть Предположим, что множество отображений # = (/ ,.../} реализуется некоторой комбинационной схемой, называемой блоком управления (БУ). Причем, эта схема функционирует как соответствующее отображение h: є И при подаче на управляющий вход кода числа і . Блок управления имеет два типа входов и выходов: к первому типу входа присоединяются все входные каналы модулей Rv...Rk системы R; ко второму типу входов соответствующие выходные каналы. Входные каналы первого типа соединены структурными входами универсального автомата А; (множество входных символов X,Z, V), выходные каналы второго типа подсоединены вместе с выходом модуля, реализующего А/ к схеме сравнения С. Подробно описанная структура изображена на рис.1. Таким образом, функционирование построенной схемы встроенного контроля состоит в следующем: при подаче на управляющий вход кода і , данная схема, то есть блок управления и универсальный автомат, реализуют (по равенству 4.1.) закон функционирования А модуля Rt. Пусть на Rt поступило некоторое слово р є XRl. Тогда по построению FA, (Р) = Я (4.2) При подаче на управляющий вход кода і реакция модуля выдается по выходу 2 и поступает совместно с реакцией Aj на схему сравнения, то есть по коду і пропускаются только соответствующие входные сигналы по і -м входным каналам типов 1 и 2. Если Rt исправен, то выполняется равенство: Следовательно, построенная стандартная схема встроенного контроля при подаче на управляющий вход кода / осуществляет функциональный контроль модуля R{. . Исследуемую систему Rj вместе с соответствующей стандартной схемой встроенного контроля обозначим как RB. Очевидно ,что для полного функционального контроля системы Rs, то есть всех компонент Rlt...Rk, необходимо проведение эксперимента кратности к (к переключений универсального автомата Л/). В то же время, для проведения указанного контрольного эксперимента необходимо вначале, установить универсальный автомат в одно из состояний соответствующих начальному множеству состояний контролируемого модуля Л;. С этой целью рассмотрим задачу управления для произвольного конечного автомата A = (S J.SJ.). Пусть S0 с S,Sf с S подмножества множества состояний, интерпретируемые соответственно как множество начальных и конечных состояний. Под управлением понимается процесс перевода произвольного состояния s є S0 в некоторое s є Sf. Решением задачи управления является такое слово р є X , удовлетворяющее условию.
