Универсальные автоматы как модели функционального восстановления поведения дискретных систем тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи

Вагарина Наталия Сергеевна

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

01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Саратов - 2005

Работа выполнена на кафедре теоретических основ информатики и информационных технологий Саратовского государственного университета им. Н.Г. Чернышевского.

Научный руководитель:

доктор технических наук, профессор Сытник Александр Александрович

Официальные оппоненты:

доктор физико-математических наук, профессор

Кудрявцев Валерий Борисович

кандидат физико-математических наук, доцент

Богомолов Сергей Анатольевич

Ведущая организация:

Институт Проблем точной механики и управления РАН

Защита диссертации состоится 2005 г. в ч. ЗО мин, в

ауд. 2/<? на заседании Диссертационного совета К 212.243.02 в

Саратовском государственном университете им. Н.Г. Чернышевского по адресу: 410012, г. Саратов, ул. Астраханская, 83.

С диссертацией можно ознакомиться в библиотеке Саратовского государственного университета.

Автореферат разослан « /<Р » 2005 г.

Ученый секретарь диссертационного совета кандидат физико-математических наук, доцент

Корнев В.В.

-Ц з

Ъ ^ ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

A.Ф. Резчикова, В.А. Твердохлебова, A.A. Сытника.

В современных условиях развития и усложнения технических объектов все большее значение приобретает поиск новых способов восстановления поведения сложных систем, позволяющих обеспечить их работоспособность и отказоустойчивость. Восстановление поведения, осуществляемое на принципах использования свойств текущего закона функционирования системы для формирования на выходах требуемой совокупности реакций, называют функциональным. Постановка задачи функционального восстановления поведения для дискретных систем с памятью впервые была сделана A.A. Сытником. При построении математических моделей законов функционирования рассматриваются различные типы отношений между входной и выходной информацией, что определяет различные виды поведения. Так, конечный детерминированный автомат можно рассматривать с преобразовательной (автомат-преобразователь) и перечислительной (автомат-перечислитель) точек зрения. В первом случае закон функционирования задается как отображение множества последовательностей входных сигналов в множество последовательностей выходных сигналов. Во втором - закон функционирования задан как перечисление всех последовательностей входных сигналов, индуцирующих данный выходной сигнал. Предложенный подход функционального восстановления поведения заключается в переходе от преобразовательного способа описания закона функционирования к перечислительному. Математической конструкцией, на основании свойств которой решается задача функционального восстановления поведения, является универсальный автомат, рассматриваемый в рамках теории универсальных автоматов. Ее возникновение связано с работами К. Шеннона, М. Минского, Дж. Фон Неймана, А. Тьюринга, определивших основные направления исследования. М. Минский поставил задачу о построении универсального автомата как базового объекта для создания некой однородной структуры, реализующей поведение любого из заданного множества элементов. Исследование данного подхода на множестве ограниченно-детерминированных (автоматных) функций проведено В.Б. Кудрявцевым и

B.А. Буевичем. А. Тьюрип!^ и ЭУ^ожность построения вычислительной машины, > ниве^эдудоутехурм смысле, что на ней можно

выполнять любое вычисление, которое могла бы выполнить любая заданная машина Тьюринга. Фон Нейманом рассматривалось обобщение универсальной вычисляющей машины с целью построения универсальной конструирующей машины. К. Шеннон исследовал возможность создания модели, имитирующей функционирование произвольной машины Тьюринга при помощи настройки этой модели соответствующими входными воздействиями (то есть доказал существование автомата, моделирующего поведение любого из заданного множества автоматов только за счет изменения соответствующих входных воздействий). Дальнейшие исследования понятия «универсальность» были посвящены уточнению и конкретизации этих результатов. К их числу относятся работы Э.В. Евреинова, И.В. Прангишвили, В.И. Варшавского, В.А. Мищенко, Я.М. Бардзиня, В.М. Глушкова, A.M. Богомолова и др.

Таким образом, универсальный автомат - это автомат, способный моделировать, порождать, воспроизводить заданный спектр поведений или объектов. Теория универсальных автоматов служит фундаментальной основой для решения задачи функционального восстановления поведения. Возможность функционального восстановления поведения относительно заданного класса неисправностей предполагает синтез универсального автомата для заданного класса (в смысле Шеннона). Как показано A.A. Сытником, задача построения универсального автомата относительно произвольного семейства КДА алгоритмически неразрешима. Однако возможно выделение классов, для которых эта задача имеет решение. В данной работе исследуется задача синтеза универсального автомата в классе групповых автоматов и задача анализа в классе автоматов (и,2) и их применение для решения задачи функционального восстановления. Цель работы состоит в исследовании функционального восстановления поведения сложных систем выделенного класса, относительно которых задача функционального восстановления поведения разрешима. Для достижения указанной цели были поставлены и решены следующие задачи:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации. Основные результаты работы содержатся в 7 статьях автора, список которых приведен в конце автореферата.

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

Пусть задано семейство {Ai = (Si,Xi,Y,dt,XJ}, iel конечных детерминированных автоматов, множество индексов I будем отождествлять с именем семейства. Конечный детерминированный автомат Af= (SJC,Y,S,A) назовем универсальным для семейства I, если для любого iel существует отображение вида tp,:S,xX,*-^SxX* такое, что справедливо условие (Vi е SXVp е X*)X(s,p) = X{<pfs,p)).

Конечный детерминированный автомат A=(SJC,Y,8,A) является универсальным перечислителем для автоматов семейства {A,}, iel, где L(X*) - множество, перечислимое автоматом А„ iel, если выполняется условие:

(Vie 1)ЦХ*)с L(X*).

Для того чтобы конечный детерминированный автомат Л/ был универсальным для семейства конечных детерминированных автоматов {А,}, iel, необходимо и достаточно, чтобы автомат А; был универсальным перечислителем для автоматов семейства /.

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

Пусть задан конечный детерминированный автомат А и класс возможных неисправностей /. Каждой неисправности /'е/сопоставим автомат А,. Таким образом, задано семейство {A,}, iel (класс возможных неисправностей).

Задачи восстановления поведения:

Задача 1. (возможность восстановления поведения относительно заданного класса неисправностей)

Для каждого конечного детерминированного автомата А„ iel проверить, является ли он универсальным для А, то есть проверить справедливость утверждения А, е UnA , iel, где UnA - множество всех универсальных автоматов для А.

Задача 2. (конструирование метода восстановления поведения относительно заданного-класса неисправностей)

Для каждого автомата А„ iel построить множество отображений {?>„}, iel, таких что <pl](Ay=A„jeI„ iel.

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

функций переходов универсального автомата, доказана теорема о существовании универсального перечислителя вида М' = {Б,Х,{5х,8^})для рассматриваемого класса.

Пусть дан конечный детерминированный автомат М={Б,Х, У, 5, А). Обозначим его внутренние состояния символами от 0 до п-1, то есть

5^={0,......п-1}. При фиксированном хеХ функцию переходов 8 данного

автомата можно полагать как объединение подстановок вида

Всевозможные подстановки на множестве 8, представимые в виде ¿^(^¿(зрс), где хеХ*, являются элементами полугруппы автомата М, множество {8Х}, хеХ является порождающим множеством полугруппы преобразований автомата М. Исследование поведения автомата М так или иначе связано с изучением элементов этой полугруппы. Рассмотрим случай, когда полугруппа является группой. Так как наблюдаемая выходная реакция является по существу информацией о внутренних изменениях системы и ее состояниях, а неисправности в автоматах это ошибки в переходах состояний, то без ограничений на общность рассуждений будем рассматривать конечные детерминированные автоматы вида М={8^(, 8).

Введем несколько обозначений.

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

2. Пусть подкласс автоматов из 3„ таких, что их функция переходов реализуется только четными автоматными подстановками.

являющаяся циклом и и ь - номера двух различных состояний из этого цикла. Обозначим ¿¡г2 и назовем расстоянием между состояниями и $,гв исходном цикле наименьшее целое число между 0 и п-2, такое, что г, + г, ¡2 = /2(тос1(и)).

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

В первом параграфе второй главы исследуется вид функции переходов универсального перечислителя для класса групповых автоматов. Теорема 2.1.3. Пусть дан конечный детерминированный М=(8,Х 8) с множеством состояний 5=(0,.../1-1), где п^З, и множеством входных

4= , то есть 8 = {8г},хе X .

\ 'о '»-I у

3. Пусть дана автоматная подстановка 8{ -

символов X =( р >1. Тогда если

3=\ т ■т + к Ч где 0<к<п-1, О^т^п-1, и числа большие \т + 1... т )

п-1 берутся по модулю и-1, то М является универсальным перечислителем для автоматов из класса 3^ (3^), если хотя бы одно из чисел п, к четно (оба нечетны).

Лемма 2.1.5. Пусть дан конечный детерминированный автомат М=(5Д", 8) с множеством состояний 5=(0,...и-1) и множеством входных символов Х=(х0,...^Ср). Пусть

( ' " \

VxeX 5 =

¿„■■■Я/ •••5, •••■5л-1

' н

... в, •■•«„-1

,г = \...к,к > 1.

Тогда, если множества ,5, ,.ч2,х2 } и } имеют,

по крайней мере, один общий элемент, то М является универсальным перечислителем для всех автоматов, множества состояний которых есть

{^Л'ЫХ-

Приведенные результаты легли в основу доказательства следующих критериев.

Теорема 2.1.4. Для того чтобы КДА 5=(0,...п-1), и>4,

Х=(хо,...^ср-\) с функцией переходов, реализуемой подстановками вида

„ ГО 1...И-1 „ <5,= и 8,=

' П 2... О 1 2

, где три его различных

состояния был универсальным перечислителем для автоматов из класса 3

(если л-четное) или 3^ (если п - нечетное) необходимо и достаточно, чтобы выполнялось равенство

ЕЙ*. ,и-1)=1. Теорема 2.1.5. Для того чтобы конечный детерминированный автомат 5^=(0,...и-1), и^З, с функцией переходов, реализуемой

подстановками вида 8, =

0 1

1 2... О

¿„+1... и-1

и 8,

..л, ...«,,...^1

где ят - некоторое состояние М, а гь Н, Н таковы, что, по крайней мере, одно меньше или равно т и одно больше т, был универсальным перечислителем для автоматов из класса 3^(если п четно) или З'п(если п нечетно),

необходимо и достаточно, чтобы выполнялось равенство

Д/и,и-1-?и,й0=1,

где с! - абсолютное значение разности номеров тех состояний из х , и ^, которые содержатся в одном и том же цикле автоматной подстановки 8,. Результаты, полученные в первом параграфе, дали возможность доказать теорему о существовании универсального перечислителя вида М' = (8,Х,{8%,8Х1}) для класса групповых автоматов, следствием которой

является теорема об условиях разрешимости задачи функционального восстановления поведения автоматов из рассматриваемого класса. Теорема 2.2.1. Пусть дан конечный детерминированный автомат с множеством состояний 5=(0,...и-1), п>3 и множеством входных символов Х=( х0,...^ср). Тогда V* е X, 8Х существует автоматная подстановка дХ1

такая, что автомат М' = (Я,.У, {£„,£}) является универсальным перечислителем для автоматов из класса . Исключение составляют

автоматные подстановки Го

0 1У2 Го 2У1 3"! Го 3¥1 2\

1 0^3 2)'{2 0^3 ^43 0^2 1/

Теорема 2.2.2. Пусть дан конечный детерминированный автомат Л/=(5Д<У), 5={0,...я-1}, п>Ъ , X -{х0,...^ср}, класс его возможных неисправностей {М, )} 1е/ и универсальный для М автомат вида Мг=(5уХ,(8,,82))•

Задача функционального восстановления поведения для автомата М разрешима, если

(5, еф^&^е {$,}«,)•

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

Дан конечный детерминированный автомат А/=(5Д', 8) с множеством состояний 5=(0>---и-1), множеством входных символовХ=(хо,.-рр) и функцией

» Л

переходов 6 = {5х},хе X где 8Х

Л.....5,

. Его возможные неисправности

описываются классом автоматов {(/- некоторое множество индексов) с функцией переходов {8',}, хеХ. Необходимо построить автомат М',=(Б^,(61,82)), который является универсальным перечислетелем для /ЩМ}. Вход

конечный детерминированный автомат М=(8,Х,^) и класс его возможных

неисправностей {М,=(8,Х,^')},с<

Выход

Автомат Л/;=(5Д,(£,,52)), являющийся универсальным перечислетелем для

/ и {Щ.

ШАГ 1

а) Полагаемую/.

b) Выбираем автомат Л/у=(8,хД) из класса неисправностей

c) Выбираем произвольную автоматную подстановку е {8х}хсХ ■ ШАГ 2

Г0 1 ..и-Г) ,Л

a) если <5, =1 ^ ^ ^ , то переходим к пункту Ь), иначе I).

b) Положим к=0, переходим к с).

„ГО 1... к А + 1...и-Г| .

c) Если Эх е X, такое что <5 =1 е {8х}, то переходим к

1...Л + 1 к ...п-\)

е), иначе полагаем к=к+1 и переходим к <1). сГ) Если к<п-1, то повторяем с), иначе переходим к шагу 3. е) Полагаем 82=8Х и переходим к шагу 9.

'«„„Л...«„..А,

1) Если ЭхеХ, такое что ф

е{8х], где * * ^ -

¿7, -А ...-У, V

V О '2 'I /

три различных состояния автомата М, и число п четно, то полагаем 82=8х и переходим к шагу 5. ШАГ 3

а) Положим к=0, переходим к Ь).

, ч „ ~ (0 1... к к +1 к + 2...п-\Л . ~ .

о) Если ЭхеХ, такое что о=\ ё {[ и и -

' * [О 1...А + 1 к + 2 к ...п-\) 1

четное число, то переходим к с1), иначе полагаем к=к+1 и переходим к

с).

с) Если к<п-1, то повторяем Ь), иначе переходим к шагу 4. с!) Полагаем 81=8Х и переходим к шагу 9. ШАГ 4

a) Положим к=1, т=0 и переходим к Ь).

, , ,, „ ( т .. от + А-Г) , ~ .

b) Если Эх е X, такое что д=\ е {8Х} и одно из чисел п или

^лг + 1... т )

к четно, то переходим к е), иначе переходим к с).

c) Полагаем т=т+\. Если т<п-1, то повторяем Ь), иначе переходим к

<)) Полагаем /п= 0, к=к+1. Если к<п -1, то повторяем Ь), иначе переходим к шагу 5.

е) Полагаем 82=8Х и переходим к шагу 9. ШАГ 5

три различных состояния автомата М, и число п четно, то переходим к Ь), иначе полагаем 82=8Х и переходим к шагу 6. Ь) Если 0(;2;'3,я-1)=1, то переходим к с), иначе полагаем 8г=8х и переходим к шагу 6.

а) Если Э* е X, такое что бх=

е{8х}, где -

и 5т - такое

с) Полагаем 82=8Х и переходим к шагу 9. ШАГ6

.. , „ . (О 1...5„У^+1... Л-П

a) Если ЗхеХ, такое что <5= " I

состояние автомата такое, что по крайней мере одно из чисел и ;']_ 12, и ¿з в подстановке 52 меньше или равно т и одно больше т, то переходим к Ь), иначе - к шагу 7.

b) Если Е)(т,п-\-т,<1)=\, где ё - абсолютное значение разности номеров тех состояний из ^ _ ¡,г, и , которые содержатся в одном и том же

цикле автоматной подстановки 8Х, то переходим к с), иначе - к шагу 7.

c) Полагаем 8, =8Х и переходим к шагу 9. ШАГ 7

a) Полагаем к=3, переходим к Ь).

b) Если ЗхеХ, такое что ^ ^|е {} а к нечетное, то полагаем

81=8Х и переходим к с1), иначе к с).

c) полагаем к=к+\, и если к<п, то переходим к Ь), иначе - к шагу 8. ё) полагаем /=0 и переходим к е).

е {(?,}, то полагаем 8г=5х

е) Если ЗхеХ, такое что 5=\ I 4-1 **

и переходим к к §), иначе к ^ полагаем /=/+1, и если 1<к-3, то повторяем к шаг е), иначе к шагу 8. §) Если 8) и 8г не являются исключительным случаем теоремы 2.1.6., то переходим к шагу 9, иначе к шагу 10.

ШАГ 8

a) Полагаем к=\, переходим к Ь).

b) Если ЗхеХ, такое что ^""^е {<?,}, то полагаем <5, =4 и

переходим к (!), иначе к с).

c) полагаем £=Л+1, и если к<п-1 , то переходим к Ь), иначе к ШАГУ 10.

(1) полагаем г'=0 и переходим к е).

/ \ .у .у ^ ^ ^ 1 __

е) Если 3*6 X, такое что 8 = ' 1+1 " * 4+1 "' е{<5х}, то полагаем

82=8Х и переходим к к g), иначе к 0. 1) полагаем ¿=/+1, и если ¿¿к, то повторяем к шаг е), иначе к шагу 10. §) Если <У,и 82 не являются исключительным случаем теоремы 2.1.7. и по крайней мере одно из чисел к, л-г четно, то переходим к шагу 9, иначе к шагу 10.

ШАГ 9. РЕЗУЛЬТАТ: автомат м; =(£,>¥,(является универсальным перечислетелем для /11{М}.

ШАГ 10.

a) полагаем/=^+1

b) если у е /, то переходим к пункту Ь) шага 1, иначе к шагу 11.

ШАГ 11. РЕЗУЛЬТАТ: не существует решения задачи функционального восстановления поведения при помощи универсального конечного детерминированного автомата вида

В третьей главе рассматривается задача анализа универсального автомата. Если задача синтеза решена для класса групповых автоматов, то задачу анализа удалось решить для более широкого класса автоматов. Задача анализа решалась относительно произвольного универсального автомата из класса (и,2). Она заключается в определении класса автоматов, для которого заданный является универсальным. Вводится понятие расширения, связанное с процессом порождения е -эквивалентных преобразований внутри зафиксированного класса е -эквивалентности, помеченных некоторой функцией Хх.

Пусть 5 -некоторое конечное множество состояний мощности п. С„ -симметрическая полугруппа степени п, преобразований, действующих на множестве 5. А„ - симметрическая группа перестановок, также определенных на 5. Введем в полугруппе преобразований (7Л отношение е следующим образом:

(\/<т,с?еС„Х|7,сг)е£ <=>(3а: еАП) а = ааа~\ Рассмотрим произвольный автомат ) из класса (и,2), где:

|5| = л, < л; Х = {х1,х2,...хк}; Г = {0,1}. Среди всех преобразований <тХ1,<тХ2,...,сгн выберем г-различные. Без ограничений на общность рассуждений, будем предполагать, что все 0-^,0-^,...,ач £ -не эквивалентны, а ст^о^ принадлежат одному и тому же классу отношения е.

Для каждого преобразования <уХ: , ' = 3, к определим множество Лг,) следующим образом (то есть выделяем классы эквивалентности): К(<т,,ЛХ1) ={(аД) | ((¿г,<т, ) е е) & (Л = Лх ), аеС„}. Для преобразований <7^, <7Хг это выражение примет вид

К(ац,(^,Лч))Л)|((а,аХ1)е£)&(Л=Лх^(Л=ЛХ1), ЭеОп} = = {(а,Л)\((*,аХ1 )Е£)&(Л=ЛХ^(Л=ЛХ1), аеС„}. Варьируем произвольное натуральное число / и на множестве автоматных

преобразований (<?", Л) определим отношение :

г,((<г,Л)) = {(<М) = | № Д) е (8, Л))

3(<ТХ/,Л^) е(аЛЖЛ) е К(стХ1 ,ЛХ])

Положим г = ит'и дадим определение операции расширения

/ел'

произвольного конечного детерминированного автомата М. Под расширением автомата М (обозначается /?5(Л/)) будем понимать множество конечных детерминированных автоматов для которого

выполняется следующее равенство:

млм)=[}<,$м,лмх

/Е/

Теорема 2.4.1. Предельное решение задачи анализа произвольного детерминированного автомата равно расширению этого автомата: (V« е Щ(\/М е (п,2))М"0 = ЯБ(М).

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

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

Теорема 2.4.2. Класс конечных детерминированных автоматов {М,}^, является решением задачи анализа произвольного конечного автомата М тогда и только тогда, когда выполняется следующее условие:

(V/,./ е /)/ * у => М е Нот(ХЛ)М1 П Нот{Х ^М].

То есть универсальный автомат принадлежит пересечению (X,,^-гомоморфных образов автоматов из заданного класса.

Теорема 2.4.3. Пусть дан КДА 5^(0,...и-1}, п>Ъ , X ={х0,...^ср},

класс его возможных неисправностей {М, =(5^, Л,)} . Задача восстановления поведения автомата А разрешима, если

VI е I М,е НотмМ.

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

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

ЩА,) = К„А,

(то есть добавление к некоторой системе ^ произвольной компоненты Л, закон функционирования которой принадлежит расширению универсального автомата Л/, не приводит к увеличению средств встроенного контроля для системы Яе К.)

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

ОСНОВНЫЕ ВЫВОДЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

Автор выражает глубокую благодарность и признательность своему научному руководителю Александру Александровичу Сытнику за постоянное внимание и поддержку в работе.

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

публикациях:

1. Вагарина Н.С., Сытник A.A. The approach to the decision of intellectual systems behavior correction problem// Материалы V международного конгресса по математическому моделированию (30.09.02-06.10.02, Дубна). - М.: Изд-во «Janus-K», 2002. Т.2. - С. 132 (авторских 1 е.).

2. Вагарина Н.С., Сытник A.A. Группы автоматных преобразований при синтезе автоматов-перечислителей// Теоретические проблемы информатики и ее приложений. - Саратов: Изд-во Саратов.ун-та, 2002. -Вып. 5. - С. 42-47 (авторских 3 е.).

3. Вагарина Н.С., Сытник A.A. Задача восстановления поведения в классе систем без потери информации// Материалы Международной науч.-техн. конф. 20-25 сент., 2004. - Таганрог: Изд-во ТРТУ, 2004. -С. 193-196 (авторских 3 е.).

4. Вагарина Н.С., Сытник A.A. Задача восстановления поведения в классе систем без потери информации// Искусственный интеллект - ИЛИИ. Донецк. - №4. - С. 100-107 (авторских 4 е.).

5. Вагарина Н.С., Сытник A.A. Модели автоматов-перечислителей при проектировании отказоустойчивых дискретных систем// «Автоматизация проектирования дискретных систем»: Материалы V Междунар. конф. (Минск, 16-17 нояб. 2004 г.) - Минск: ОИПИ HAH, Беларусь, 2004. - Т.1. - С. 79-86 (авторских 4 е.).

6. Вагарина Н.С. Задача восстановления поведения в классе систем без потери информации// Социально-экономическое развитие России. Проблемы, поиски, решения: Сборник науч. тр. по итогам НИР СГСЭУ в 2003 г. - Саратов: Изд. центр СГСЭУ 2004. - 4.2. - С. 81.

7. Вагарина Н.С., Сытник A.A. О синтезе универсального перечислителя для класса автоматов без потери информации// Проблемы теоретической кибернетики: Тезисы докл. XIV Междунар. конф. (Пенза, 23-28 мая 2005 г.)/ Под ред. О. Б. Лупанова. — М.: Изд-во мех.-матем. фак. МГУ, 2005. - С.190 (авторских 1 е.).

124533

РНБ Русский фонд

2006-4 25455

ВВЕДЕНИЕ.

ГЛАВА 1. Математические модели функционального восстановления поведения дискретных систем.

1.1. Основные положения и обозначения.

1.2. Постановка задачи функционального восстановления поведения сложных систем.

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

ГЛАВА 2. Универсальность в классах групповых автоматов. ф 2.1. Критерии универсальности для класса групповых автоматов.

2.2. Теорема о существовании универсального перечислителя для класса групповых автоматов.

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

ГЛАВА 3. Полнота и анализ универсальных автоматов.

ГЛАВА 4. Применение модели универсального автомата для решения задач технической диагностики.

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

В процессе эксплуатации сложных систем с течением времени может происходить трансформация их первоначального поведения. Это обусловлено самим характером материальной природы систем. Дж. фон Нейман в своей работе указывал, что ".неисправности компонент. существенная и неотъемлемая часть их работы" [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 где: a; j -й показатель первичной спецификации преобразования где Д, - нулевой показатель вторичной спецификации преобразования сгр, к - мощность множества конечных состояний автомата, п - мощность состояний автомата.

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 (Ô(s, q2 ) e S f ))

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

-,3q e X')0/s e S)(ô(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,^-гомоморфных образов которых содержит заданный универсальный автомат.

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

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

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

1. Автоматы: Сб. статей под ред. КШеннона. М.: Иностранная литература, 1956. -403 С.

2. Айзерман М.А. и др. Логика. Автоматы. Алгоритмы. — М.: Физматгиз, 1963. -140 С.

3. Алгебраическая теория автоматов, языков, полугрупп: Сб. статей под ред. М. Арбиба- М.: Статистика, 1975. 335 С.

4. Бардзинь Я.М. О проблеме универсальности в теории автоматов. Дис.канд., Новосибирск, 1965.

5. Бардзинь Я.М., Калниньш Я.Я. Универсальный автомат с переменной структурой// Автоматика и вычислительная техника, 1974. №2. С.9-18

6. Богомолов A.M. и др. Эксперименты с автоматами. Киев: Наукова Думка, 1973.-144С.

7. Богомолов А.М., Грунский И.С., Сперанский Д.В. Контроль и преобразование дискретных автоматов. Киев: Наукова Думка, 1975. -174 С.

8. Богомолов A.M., Сытник A.A. Универсальные конечные автоматы//Доклады АН СССР. 1987. Т. 294. -№3. -С.525-528.

9. Варшавский В.И. Коллективное поведение автоматов. Москва.: Наука, 1973-407 с.

10. Буевич В.А. Постороение универсальной о.-д. Функций с двумя переменными// Проблемы кибернетики, 1965. -№15. С.249-252.

11. Вагнер В.В. Теория полугрупп и ее приложение. Саратов: Изд-во СГУ, 1965.-С.З-179,

12. Гилл А. Введение в теорию конечных автоматов. -М.: Наука, 1966. -272 С.

13. Глушков В.М. Абстрактная теория автоматов// Успехи мат. наук, 1961. -Т. 14.-Вып. 5.-С.З-62.

14. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962. -476 С.

15. Евреинов Э.В., Прангишвили И.В. Цифровые автоматы с настраиваемой структурой. -М.: Энергия, 1974. -240С.

16. Кратко М.И. Алгоритмическая неразрешимость одной задачи из теории конечных автоматов. В кн.: «Дискретный анализ», №2, Новосибирск, 1964.

17. Кудрявцев В.Б., Алешин С.В, Подколзин A.C. Введение в теорию автоматов. -М.: Наука, 1985.-319 С.

18. Курош А.Г. Курс высшей алгебры-М.: Наука, 1975.-345 С.

19. Многофункциональные автоматы и элементная база цифровых ЭВМ/ под ред. В.А. Мищенко -М.:Радио и связь, 1981. 240 С.

20. Нейман Дж. Теория самовоспроизводящихся автоматов. М.: Мир, 1971. -382С.

21. Пархоменко П.П., Согомонян Е.С. Основы технической диагностики, оптимизации алгоритмов диагностирования, аппаратурные средства. -М.: Энегоиздат, 1981.-320 С.

22. Посохина Н.И. Об одном подходе к решению задачи синтеза автоматов-перечислителей// Теоретические проблемы информатики и ее приложений. -Саратов: ГосУНЦ "Колледж", 1997. -Вып.1 -С.101-109

23. Посохина Н.И., Шульга Т.Э. Об одном подходе к построению автомата-перечислителя// Методы кибернетики и информационные технологии/под ред. Д.С.Черешкина Саратов: ГосУНЦ "Колледж", 1997.-Вып. 2. -С.113-115.

24. Сытник A.A. Восстановление поведения сложных систем. Саратов: Изд-во СГУ, 1992. - 192С.

25. Сытник A.A. Перечислимость при восстановлении поведения автоматов// Доклады РАН. -1993. -Т.238. С.25-26.

26. Сытник A.A., Посохина H.H., Шульга Т.Э. Об одном подходе к решению задачи синтеза автоматов-перечислителей// Теоретические проблемы информатики и ее приложений. Саратов: ГосУНЦ "Колледж", 1998. -Вып.2. -С.103-116.

27. Твердохлебов В.А. Логические эксперименты с автоматами. Саратов: Изд-во СГУ, 1988.-184 С.

28. Трахтенброт Б.А., Бардзинь Я.М. Конечные автоматы. Поведение и синтез. -М.: Наука, 1970. -400 С.

29. Хоредж Ф. Преобразования, определенные конечными автоматами// Проблемы кибернетики. 1963. -Вып 9. - С. 23-26.

30. Цыпкин Я.З. Адаптация и обучение в автоматических системах. М.: Наука, 1968. -399С.

31. Шульга Т.Э. Необходимые условия моделируемости автоматных функций степенным многочленом// Теоретические проблемы информатики и ее приложений. Саратов: ГосУНЦ "Колледж",1998. -Вып 2. - С.145-153.

32. Шульга Т.Э. Численные критерии восстановимости поведения КДА степенным многочленом // Теоретические проблемы информатики и ее приложений. -Саратов: ГосУНЦ "Колледж", 1997. -Вып.1. С.132-137.

33. ЭдрюсГ. Теория разбиений. -М., «Наука», 1982. С. 80-87.

34. Яблонский C.B. Введение в дискретную математику. -М: Наука, 1979. -272 С.