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

Практическое и теоретическое значение автоматных моделей в решении задач проектирования и технического диагностирования, изучении процессов формирования и передачи сигналов в сложных системах стало причиной интенсивных исследований теории автоматов как математической модели сложных систем. В настоящее время практически в любой сфере человеческой деятельности мы встречаемся с понятием «система». Это объясняется постоянным усложнением технологических объектов, конструкций, устройств, технологий. Термин «система» служит обозначением таких общих понятий, как «целое, составленное из частей», «совокупность элементов, образующих некий порядок». Таким образом, категория «быть системой» присуща как объектам материальной природы (материальные системы), так и объектам, порожденным умозрительным рассуждением (концептуальные системы). Среди концептуальных систем выделяется класс абстрактных систем, являющихся математическими моделями материальных систем. Особый интерес представляют системы, обладающие поведением или законом функционирования. В системном анализе под поведением понимается «совокупность причинно-следственных связей, реализуемых системой при своей работе» .

В процессе эксплуатации сложных систем с течением времени может происходить трансформация их первоначального поведения. Это обусловлено самим характером материальной природы систем. Дж. фон Нейман в своей работе указывал, что «.неисправности компонент. существенная и неотъемлемая часть их работы» [20]. В широком смысле восстановление поведения означает возврат объекта к реализации заданного функционирования после возникновения, обнаружения и локализации неисправности без физического устранения дефекта. Организация восстановления поведения сложной системы включает в себя комплекс следующих задач:

— обеспечение восстанавливаемости поведения объекта на этапе его проектирования;

— самодиагностирование и самовосстановление объекта в процессе функционирования;

— применение спектра восстановительных процедур и приемов физического устранения последствий возникшего дефекта.

Наиболее часто для модификации поведения используются два основных вида избыточности — структурная и временная. Однако выход из строя структурного резервирования порождает вопрос: «Можно ли использовать свойства текущего закона функционирования автомата для формирования на выходах требуемой совокупности реакций?». Ответ на него предполагает изучение имеющейся в данный момент времени функциональной избыточности системы, а также возможных вариантов её целенаправленного создания на этапе проектирования. Восстановление поведения, осуществляемое на указанных принципах, называют функциональным. Функциональное восстановление опирается на принцип обучения Я. З. Цыпкина [30]. В случае функционального восстановления поведения текущий закон функционирования выступает как «обучающаяся» система, которая после приложения специальных «обучающих» последовательностей должна генерировать сигналы, эквивалентные реакциям исправного поведения. Формальная постановка задачи функционального восстановления поведения была сделана A.A. Сытником.

В данной работе исследуется восстановление поведения дискретных систем и в качестве математической модели системы выбран конечный детерминированный автомат. Исследованию общей теории автоматов и возможностей ее прикладного использования посвящены работы таких специалистов как М. А. Айзерман, М. Арбиб, Я. М. Барздинь, Б. А. Трахтенброт,.

A.M. Богомолов, Д. В. Сперанский, В. И. Варшавский, М. А. Гаврилов,.

B.М. Глушков, А. Гилл, И. Е. Кобринский, В. Б. Кудрявцев, О. П. Кузнецов, В. Г. Лазарев, М. Минский, К. Шеннон, Дж. фон Нейман, A.A. Сытник, В. А. Тверохлебов, Дж. Ульман, M. J1. Цетлин, C.B. Яблонский и другие. При построении математических моделей законов функционирования рассматриваются различные типы отношений между входной и выходной информацией, что определяет различные виды поведения. Так, поведение конечных детерминированных автоматов может рассматриваться в преобразовательной и перечислительной формах. В первом случае анализируется процесс реализации заданного отображения между множествами последовательностей входных и выходных сигналов. Во втором акцент переносится на результаты преобразования входных сигналов. То есть в центре внимания находится вопрос об определении по заданной выходной реакции совокупности последовательностей входных сигналов, ее индуцирующих. Необходимость рассмотрения перечислительной формы поведения обусловлена тем, что возникновение неисправности в системе приводит к нарушению преобразовательного способа переработки информации.

Способность математической модели поведения к имитации функционирования некоторого заданного множества объектов рассматриваются в рамках теории универсальных автоматов. Ее возникновение связано с работами К. Шеннона, М. Минского, Дж. фон Неймана, наметивших основные направления исследования. Существует два подхода к понятию «универсальность».

Первый из них связан с понятием функциональной полноты и однородной структуры. В 1956 году М. Минский в работе [1, стр.163] поставил задачу о построении универсального автомата как базового объекта для создания некоторой однородной структуры, реализующей поведение любого из заданного множества элементов — «определенная категория множеств элементов „универсальна“ в том смысле, что из таких элементов можно собрать машины, реализующие произвольные. функции». В той же работе [1, стр.177] элемент назван универсальным, если некоторое, достаточно большое множество объектов «обладает некоторыми подобными свойствами этого элемента или отличающимися лишь в количественном отношении». В 1960 году в [4] впервые дано формальное определение универсального объекта как математической модели, образующей функционально полную систему. Исследование данного подхода на множестве ограниченно-детерминированных функций проведено В. Б. Кудрявцевым и В. А. Буевичем [10, стр.65].

Изучение второго подхода к понятию универсальность связано с ответом на вопрос — «существует ли конечный детерминированный автомат, моделирующий поведение любого из заданного множества автомата только за счет изменения соответствующих входных воздействий?». Одновременно с исследованиями М. Минского, в работе К. Шеннона [1, стр.214] показана возможность построения универсальной машины Тьюринга, имитирующей функционирование произвольной машины Тьюринга при помощи настройки соответствующими входными воздействиями. А. Тьюринг [1, стр.230] показал возможность построения некоторой вычислительной машины универсальной в том смысле, что на ней путем подходящего кодирования можно выполнять любое вычисление, которое могла бы выполнить любая заданная машина Тьюринга. Затем М. Дэвис [1] и Р. Петер [1] получили ряд условий, определяющих в явном виде метод построения команд универсальной машины Тьюринга. Дальнейшие исследования понятия «универсальность» были посвящены уточнению и конкретизации указанных походов на множествах булевых функций и конечных детерминированных автоматов. К их числу следует отнести работы Э. В. Евреинова и И. В. Прангишвили [15], В. И. Варшавского [9], В. А. Мищенко и др. [19], Я. М. Барздиня [5], В. М. Глушкова [13] и др.

Итак, универсальный автомат должен иметь способность моделировать, порождать, воспроизводить (соответственно по Шеннону, Минскому и фон Нейману) заданный спектр поведений или объектов. То есть понятия «восстановление поведения» и «универсальный автомат» взаимосвязаны. Таким образом, теория универсальных автоматов служит фундаментальной основой для решения задачи функционального восстановления поведения и универсальный автомат является математической конструкцией, на основании свойств которой решается задача восстановления поведения.

Как показано A.A. Сытником [24] задача построения универсального автомата относительно произвольного семейства КДА алгоритмически не разрешима, так же как и задача восстановления поведения для произвольной сложной системы. Однако, задача построения универсального конечного детерминированного автомата относительно конечного семейства конечных детерминированных автоматов алгоритмически разрешима. В настоящее время предпринимаются попытки выделить классы, для которых это задача имеет решение. Например, Т. Э. Шульгой [32] проведена работа по исследованию числовой модели конечного детерминированного автомата, в частности, описан класс автоматов, допускающих моделирование семействами степенных многочленов, и для него решена задача функционального восстановления поведения.

Таким образом, возможность восстановления поведения относительно заданного класса неисправностей предполагает синтез универсального автомата для заданного класса. Решение задачи синтеза — универсальный автомат — с содержательной точки зрения способен заменить любой автомат заданного класса при возникновении неисправностей. С другой стороны, интерес представляет решение задачи анализа универсального автомата, которая может быть сформулирована следующим образом: для произвольного конечного детерминированного автомата М определить класс конечных автоматов, для каждого из которых Месть универсальный.

Итак, данная работа посвящена исследованию моделей функционального восстановления поведения сложных систем дискретного типа. Цель работы состоит в выделении класса конечных детерминированных автоматов, разрешимого относительно задачи функционального восстановления поведения. Для этого были поставлены и решены следующие задачи:

— задача синтеза универсальных автоматов в классе групповых автоматов;

— задача анализа универсальных автоматов классе (п, 2);

— задача построения отказоустойчивых систем дискретного типа с использованием модели универсального автомата.

Методологическую основу работы составляют теоретико-автоматные и алгебраические методы.

К новым результатам, полученным в данной работе можно отнести следующее:

— разработана и исследована модель универсального автомата-перечислителя для класса групповых автоматов;

— разработан и исследован метод применения модели универсального автомата-перечислителя для решения задачи функционального восстановления поведения в классе групповых автоматов;

— найдены критерии универсальности конечного детерминированного автомата для класса групповых автоматов;

— доказано существование универсального перечислителя вида М = (8,Х,{Зх, 3 }) для класса групповых автоматов;

— найден метод синтеза универсального перечислителя для класса групповых автоматов;

— решена задача функционального восстановления поведения в классе групповых автоматов;

— найден критерий решения задачи анализа произвольного универсального автомата из класса (п, 2);

— решена задача функционального восстановления поведения в классе автоматов (п, 2);

— предложена схема построения отказоустойчивых систем дискретного типа с использованием модели универсального автомата.

Работа выполнена на 115 страницах машинописного текста, состоит из оглавления, введения, 4 глав, заключения и списка литературы.

Во введении формулируются цели и задачи работы, дается краткий обзор по исследуемой теме, излагаются основные результаты и описывается структура диссертации.

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

Вторая глава посвящена решению задачи синтеза универсального автомата в классе групповых автоматов. В ней разработана и исследована модель универсального автомата-перечислителя для класса групповых автоматов, разработан и исследован метод применения модели универсального автомата-перечислителя для решения задачи функционального восстановления поведения в классе групповых автоматов, найдены критерии универсальности КДА для класса групповых автоматов (теоремы 2.1.4 и 2.1.5), доказано существование универсального перечислителя для класса групповых автоматов вида М' = (8,Х,{3Х, 8Х1})(теорема 2.2.1), найден метод синтеза универсального перечислителя для класса групповых автоматов (параграф 2.3), решена задача восстановления поведения в классе групповых автоматов (теорема 2.2.3).

В третьей главе рассматривается задача анализа относительно произвольного универсального автомата из класса (п, 2). Найден критерий решения задачи анализа произвольного универсального автомата. Показано, что решением задачи анализа является множество автоматов, пересечение (X,^-гомоморфных образов которых содержит заданный универсальный автомат (теорема 3.2), решена задача восстановления поведения в классе автоматов (п, 2) (теорема 3.3).

В четвертой главе рассматривается возможность прикладных применений универсального автомата для решения задач технической диагностики. А именно рассматривается применение универсальных автоматов для построения отказоустойчивых систем дискретного типа, основанное на способности универсального автомата моделировать поведение заданного класса объектов.

Показано, что сложность получаемой схемы контроля не зависит от роста сложности рассматриваемой системы (теорема 4.5).

В заключении диссертации суммируются полученные результаты.

Основные результаты докладывались и обсуждались на пятом международном конгрессе по математическому моделированию (Россия, Дубна, 2002), на международной научно-технической конференции «Искусственный интеллект. Интеллектуальные и многопроцессорные системы» (Таганрог, 2004), на V международной конференции «Автоматизация проектирования дискретных систем» (Минск, 2004), на XIV Международной конференции «Проблемы теоретической кибернетики» (Пенза, 2005 г.), на семинарах Института проблем точной механики и управления РАН, Саратовского государственного университета, Саратовского государственного социально-экономического университета, на внутривузовских конференциях Саратовского социально-экономического университета.

Основные результаты работы содержатся в 7 статьях автора. и.

выход.

Рис. 1. Стандартная схема встроенного контроля системы 7?={7?ь. .Як} yseS) S (s, p) eSf (4.6.).

По определению первичной спецификации:

J= ' «'^л» • • • ¦ ¦ ¦ S" «и ах +а2 + .ап = п.

Без ограничений на общность рассуждений предположим, что а, ф 0 то есть существует, по крайней мере, одно состояние s' е S для которого справедливо:

4.7.).

Но Sf и следовательно, (4.7.) противоречит предположению (4.6.). Пусть, теперь, существует такой индекс j е I, что aj = 0. Это означает:

V* 6 (4−8.).

Так как SjeSf, то (4.8.) показывает, что слово р не является решением исходной задачи управления. Таким образом:

Уs е S)(S (s, p) (((V/ е /)(ау ^ 0)) & ((Vy е Т){а} = 0)) (4.9.).

Обратно, пусть для первичной спецификации преобразования ар справедливо условие (4.5.). Покажем, что р является решением задачи управления. Действительно, поскольку для всех s е. S результат cxp (s) есть вектор, содержащий элементы только из множества Sf, то по определению р решение задачи управления с множеством конечных состояний Sf. Теорема доказана. Следствие 4.1.

Если р решение задачи управления, то.

1. Yuai=n j=i где: ajй показатель первичной спецификации преобразования где Д, — нулевой показатель вторичной спецификации преобразования сгр, к — мощность множества конечных состояний автомата, п — мощность состояний автомата.

3. Если Sj=S, то множество всех решений задачи управления совпадает с группой перестановок Ап полугруппы преобразований конечного автомата. Определение 4.1.

Назовем решение задачи управления р автомата, А = (S, X, Y, S, X).

1. тупиковым, если:

-.3 qx, q2 g X*){р = q, q2)& ((Vj e S)(S (s, qx) zSf)8c (O (s, q2) e S f)).

2. минимальным:

-, 3q e X')0/s e S)(o (q, s) e Sf) & < p).

Обозначим через число тупиковых решений произвольного автомата из класса (п, к) с множеством конечных состояний мощности к. Теорема 4.2.

Если для автомата из класса (п, 2) с множеством конечных состояний мощности к задача управления имеет решение, то.

Доказательство.

Рассмотрим произвольный автомат Ае 0,2). По условию теорема 4.1. преобразование сгр, индуцируемое решением задачи управления р, удовлетворяет (4.1). Из определения вторичной спецификации:

Д — уй показатель вторичной спецификации преобразования ар. Используя утверждение следствия 4.1., получаем:

4.10.).

До +—Р"=п.

4.11) п-к + Д + .Д, =п или.

Д±.Д, =к.

4.12.).

Поскольку принимают свои значения только на множестве натуральных чисел ТУ, то (4.12.) примет вид:

А (4.13) Также по определению вторичной спецификации /?,+. Д,. являются решениями уравнения.

Д+2 рг+.пр"=п (4.14.).

Из левой и правой частей (4.14.) вычтем соответствующие части (4.12.): р1+2ръ+.{п-)р11=п-к (4.15.).

Аналогично (4.12.), (4.15.) примет вид:

32+2&+.(п-к-т, к=п-к (4.16.).

Таким образом, показатели вторичной спецификации преобразования должны удовлетворять уравнениям системы:

Г р1+р2+. + рк=к р2+2р3+.(п-к-т1к=п-к.

Из комбинаторного анализа известно [33], что Г таких решений равно числу разбиений целого п с числом частей точно к. Применяя соотношение Рамануджана-Радамахера, получаем:

Для доказательства теоремы необходимо показать, что Т < Тп к, то есть, что между множеством тупиковых решений задачи управления и множеством решений (4.17) существует однозначное соответствие. Проведенные выше рассуждения доказывают, что если, а р преобразование, ндуцируемое тупиковым решением задачи управленияр, то [[с^]] = [[О^'У1.//" ]] причем Ръ,.р"удовлетворяют равенствам (4.17.). Обратно, рассмотрим Р0,-.Р" некоторое разбиение числа п с числом частей точно к. Определим множество.

— множество всех слов, индуцирующих преобразования с вторичной спецификацией [[0.прп'}. Покажем, что содержит тупиковое решение задачи управления. Возможно два случая:

1. 1?(ро,.,./Зп) = 0.

Задача управления решения не имеет.

2. Г (/?о,.Дг)*0.

На множестве всех слов X автомата, А введем отношение равенства слов г :

Ур, деХ*)(р* = д) ет<^>№е$)<$(*, р) = д (*, д) (4.19).

Очевидно, что т есть отношение эквивалентности. Оно обладает свойствами:

1. (Ур, д е Х*)(р, д) ет => (стр, сг (!) е е.

2. (УреГ)(ЗдеХ*)(р, д) ет&ад№р) (4.20).

3. (/р, деХ*)(р, д) ет&(р^Ж (Р0,., Рп)=>(деЖ (Р0,., Рп) (4−21) Таким образом, если р решение задачи управления, принадлежащее множеству ]?(ро,., рп) то все тэквивалентные ему слова также принадлежат множеству ]?(рй,.,/Зп). Существование такого решения следует из условия теоремы. Тогда по (4.20.) существует слово д,, являющееся минимальным в классе г — эквивалентности, содержащем р, а следовательно, и являющееся решением задачи управления.

Замечание: поскольку остается неясным вопрос о существовании решения задачи управления по длине меньшего, чем слово р, (например, в силу неоднозначности построения преобразования по вторичной спецификации), то можно говорить о построении только тупикового решения. Следовательно: Тпк > Т. Теорема доказана.

Рассмотрим, теперь, вопросы существования и построения множества минимальных решений задачи управления автоматом. Определение 4.2.

Левым (правым) частичным идеалом полугруппы, А называется такое пустое множество Ве^, что существует такое подмножество В0сВ, для которого справедливо:

АВ с В. (В^сВ).

4.22.).

Определение 4.3.

Двусторонним частичным идеалом полугруппы называется подмножество, являющееся одновременно левым и правым частичным идеалом.

Определение 4.4.

Пусть Q некоторое подмножество множества всех слов X некоторого автомата, А. Слово qeQ есть первое вхождение в слово реХ* относительно множества <2, если: где епустое слово 2. (Удев)(гЗд], д2еХ,)д = д^д2 и обозначается р—а. й.

Пусть () множество всех решений задачи управления. Теорема 4.3.

Для того, чтобы <20 с <2 было множеством минимальных решений задачи управления необходимо и достаточно, чтобы (9 было двусторонним частичным идеалом полугруппы X*: Х*0Х* с О0 и @ было множеством первых вхождений слов из <2. Доказательство.

Пусть Q0 множество минимальных решений задачи управления. В качестве ()0, очевидно, можно выбрать множество:

1. <�Уд1,д2еХ*)(р = д1дд2)=>((Ч1 Фе) ч (д2Фе)).

4.23).

Обратно, пусть () двусторонний частичный идеал в X* :

Х’ОХ* с (4.24.).

Покажем, что <2 является множеством минимальных решений задачи управления. Действительно, из (4.24.) для всех элементов множества (?0 справедливо: или дхрд2 по предположению есть очевидно, решение задачи управления. В то же время по условию: | д |<| дхрд2 | .Теорема доказана.

Доказанная теорема кроме необходимых и достаточных условий существования множества минимальных решений определяет и метод построения такого множества, связанный с изучением и выделением посторонних идеалов в произвольной полугруппе. Теорема 4.4.

Для произвольного натурального п еЫ задача управления для универсального автомата А (п, 2) с произвольным множеством конечных состояний может быть решена словом длины 1.

Доказательство теоремы следует из проведенных выше рассуждений и свойств универсального автомата.

Обозначим через КпА. множество автоматов, для которых автомат, А является контролирующим, то есть для которых возможно проведение различающего их контрольного эксперимента с помощью стандартной схемы встроенного контроля. Теорема 4.5.

Для произвольного класса / расширение универсального автомата, А есть множество автоматов, контролируемых автоматом А[.

М (А,) = Х"А/ (4.25).

Справедливость равенства (4.25.) следует из теоремы 4.4. и построения стандартной схемы встроенного контроля.

Содержательно, утверждение теоремы 4.5. может быть сформулировано следующим образом: добавление к системе произвольной компоненты Я, закон функционирования которого принадлежит расширению универсального автомата А/ не приводит к увеличению средств встроенного контроля для системы Яе У Я.

ЗАКЛЮЧЕНИЕ

.

Цель работы состояла в исследовании функционального восстановления поведения сложных систем выделенного класса, относительно которых задача функционального восстановления поведения разрешима. Для достижения указанной цели были поставлены и решены следующие задачи:

— задача синтеза универсальных автоматов в классе групповых автоматов;

— задача анализа универсальных автоматов классе (п, 2);

— задача построения отказоустойчивых систем дискретного типа с использованием модели универсального автомата.

В рамках решения первой задачи получены следующие конкретные результаты:

— разработана и исследована модель универсального автомата-перечислителя для класса групповых автоматов;

— разработан и исследован метод применения модели универсального автомата-перечислителя для решения задачи функционального восстановления поведения в классе групповых автоматов;

— найдены критерии универсальности КДА для класса групповых автоматов;

— доказано существование универсального перечислителя вида М = {<5Х, }) для класса групповых автоматов;

— найден метод синтеза универсального перечислителя для класса групповых автоматов;

— решена задача функционального восстановления поведения в классе групповых автоматов;

В рамках решения второй задачи найден критерий решения задачи анализа для более широкого класса автоматов — для произвольного универсального автомата из класса (п, 2). Показано, что решением задачи анализа является множество автоматов, пересечение (X,^-гомоморфных образов которых содержит заданный универсальный автомат.

При решении третьей задачи предложена схема построения отказоустойчивых систем с использованием модели универсального перечислителя. Показано, что при этом сложность получаемой схемы контроля не зависит от роста сложности рассматриваемой системы.

Таким образом, в работе исследована возможность приложения математического аппарата к исследованию свойств сложных систем в рамках задачи функционального восстановления поведения. Работа носит теоретический характер, разработаны новые положения, развивающие классические результаты в области синтеза, анализа и организации целенаправленного поведения конечных детерминированных автоматов для решения проблемы функционального восстановлении поведения дискретных систем с памятью.

Автор считает своим искренним долгом выразить глубокую благодарность научному руководителю действительному члену РАЕН, доктору технических наук, профессору А. А. Сытнику за постановку задачи, многолетнюю и многостороннюю помощь.