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

Саратовский государственный университет

ХТГ1Г РГ5 ОД

им. Н.Г. Чернышевского

7 - ДОГ 2000

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

ШУЛЬГА Татьяна Эршсовна

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

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

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

Саратов - 2000

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

Научный руководитель: академик РАЕН, доктор технических

наук, профессор А.А. СЫТНИК

Официальные оппоненты: доктор технических наук, член-

корреспондент АТН Украины, профессор Д.В. СПЕРАНСКИЙ,

кандидат физико-математических наук, доцент В.В. ПЕЧЕНКИН

Ведущая организация: Институт Проблем точной механики и управления РАН

Защита диссертации состоится «30» июня 2000 г. в 15 ч. 00 мин. в ауд. 218 на заседании Диссертационного совета К 063.74.04 в Саратовском государственном университете им Н.Г. Чернышевского по адресу: 410026, г. Саратов, ул. Астраханская, 83.

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

Автореферат разослан «¿3» МЛ& 2000 г.

Ученый секретарь диссертационного совета кандидат физико-математических наук, доцент iJW/w- П.Ф.Недорезов

1966T.0J, О + Я $/5. О

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

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

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

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

Конечный детерминированхшй автомат как математическая модель реального объекта при решении задачи ФВП требует двоякого рассмотрения. С одной стороны, автоматы можно рассматривать с преобразовательной точки зрения, то есть изучать свойства данного автомата через рассмотрение преобразования входных последовательностей в выходные, а с другой - автомат может быть определен в перечислительной форме, то есть описанием автомата является множество выходных последовательностей, которые он генерирует. Если первая точка зрения на поведение автомата выросла в серьезную научную дисциплину с большим числом работ, специфическими методами и своеобразной проблематикой, получившую существенное развитие в нашей стране, то вторая точка зрения еще недостаточно разработана.

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

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

автоматов посвящены работы В.Б. Кудрявцева, В.А. Буевича, М. Дэвиса, Р. Петера, Э.В. Евринова, И.В. Прангишвили, В.И. Варшавского, В.А. Мищенко, Я.М. Барздиня, В.М. Глушкова, исследующие универсальность на множествах

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

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

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

Для достижения указанной цели были поставлены и решены следующие задачи:

- изучение числовой модели автомата;

- описание класса автоматов, допускающих моделирование

семейством степенных многочленов (ССМ);

- решение задачи синтеза универсального автомата, моделируемого ССМ;

- решение задачи анализа универсального автомата, моделируемого ССМ;

- получения метода построения восстанавливающей последовательности относительно заданной неисправности для автомата, моделируемого ССМ.

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

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

- критерии моделируемости автомата ССМ, как с целыми, так и с рациона ль н ым и коэффициентами;

- метод построения множества, перечислимого автоматом, моделируемым ССМ;

- критерий универсальности автомата, моделируемого ССМ;

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

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

- метод построения восстанавливающей последовательности для автомата, моделируемого ССМ.

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

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

Апробация работы. Основные результаты работы докладывались и обсуждались на первой всероссийской научной конференции молодых ученых и аспирантов «Новые информационные технологии, разработка и аспекты применения», (Таганрогский радиотехнический университет, 1998), на всероссийской военно-технической конференции "Проблемы совершенствования ракетных комплексов" (Саратов, 1998), на IV международной конференции студентов и аспирантов по фундаментальным наукам "Ломоносов 99"

(МГУ, 1999), на семинарах кафедры математической кибернетики и компьютерных наук и кафедры теоретических основ информатики и информационных технологий (СГУ, 1997-2000).

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

Объем и структура работы. Работа представлена на 99 страницах машинописного текста, состоит из оглавления, введения, 3 глав и списка литературы. Библиография состоит из 62 названий.

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

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

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

Пусть возникновение неисправностей в КДА Л --- (Х,7Д ¿>,л) приводит к замене семейства отображений {/г5}5в$ (вида и, \Х~ -»}")

на семейство отображений {/ф^. Тогда под восстановлением поведения КДА А будем понимать процесс построения такого множества входных последовательностей Р (множества восстанавливающих последовательностей), что оно генерирует то же

множество выходных последовательностей для {Л^}^, что и X* для

Ю«а ' то есть ЦР) = {? I (35 е ¿?ХЭа е Р): А,' (а) = Ч} = ЦХ').

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

Пусть задан конечный детерминированный автомат А и класс возможных неисправностей I. Каждой неисправности / е / сопоставляем автомат А„ моделирующий поведение автомата А при неисправности Таким образом, предполагается заданным семейство конечных детерминированных автоматов {А/},с/ (класс возможных

неисправностей) и конечный детерминированный автомат Л.

Задача 1.3.1. Определить возможность восстановления

поведения относительно заданного класса неисправностей: для каждого автомата А, семейства I проверить справедливость утверждения А1 е11пА, I е/, где и „А - множество всех универсальных автоматов для автомата А.

Задача 1.3.2. Построить метод восстановления поведения относительно заданного класса неисправностей: для каждого автомата А1 семейства I построить множество восстанавливающих последовательностей {})}ге/ : ЦР,) = Ь(Х")■

Если прямую задачу - задачу нахождения для семейства I универсального автомата А называют задачей синтеза, то обратную к ней - нахождение для автомата А семейства I, для которого А является универсальным, называют задачей анализа. Таким образом, задачу ФВП можно решать двумя способами: либо проверять, является ли автомат А решением задачи анализа для каждого автомата из класса {А: }ш, либо для автомата А решить задачу синтеза универсального автомата и проверить принадлежность каждого автомата из класса {А(}1е1 классу

всех автоматов, универсальных для А.

Выделение класса автоматов, разрешимых относительно задачи ФВП, производится на основе использования числовой модели автомата Так как наблюдаемая выходная реакция является, по существу, информацией о внутренних изменениях системы и ее состояниях, а ошибки в автоматах - это ошибки в переходах состояний, то для наглядности рассуждений рассматриваются автоматы Медведева: А -=(ХЯ$) X ={х,,х2,...хя}, \S\-m, З-.ХхЯ-^. (1)

Очевидно, что такое предположение не приводит к изменению свойств отображения И :Х' —> У *, представимого в автоматах, и, следовательно, не ограничивает общность рассуждений.

Занумеруем состояния автомата натуральными числами /У={0,1,. .. ,т-1} и представим функции переходов данного автомата в виде обобщенных подстановок:

: - :1

Обозначим ¿ = (од,...,ю-1), Рассмотрим

степенную функцию, определенную на векторе у следующего вида:

хеХ, (3)

где операции сложения, умножения и возведения в степень - это

операции кольца Zm. Будем говорить, что поведение автомата^ вида (1) моделируется семейством степенных многочленов {/х}хех в"Да (3), если (уд: е Л')^ представимо степенной функцией/х, то есть /х (л-) = ,

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

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

сравнений Ма = у , где % = - я0,/ = 1,т - 1, а=(а0,а, ) -

искомые коэффициенты, а матрица М, в дальнейшем называемая моделирующей матрицей автомата А, имеет вид 1 1 ... 1

М=

2 22 ... 2'

(т-1) (т-1)2 ... (/и-1)' Очевидно, что не каждая автоматная подстановка может быть представлена степенным многочленом. Для этого необходимо, чтобы на функцию переходов были наложены некоторые ограничения.

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

Для решения этой задачи в первом параграфе главы проводятся исследования моделирующей матрицы автомата. Эти исследования основаны на том факте, что /-ая строка моделирующей матрицы представляет собой элементы мультипликативной полугруппы вычетов по модулю т, порожденной числом л На основе утверждений теории чисел и теории полугрупп доказано 7 лемм, представляющих собой утверждения о свойствах и структуре моделирующей матрицы автомата. В свою очередь, на основании этих лемм во втором параграфе доказаны следующие теоремы, в совокупности представляющие собой условия моделируемости КДА ССМ.

Теорема 2.2.1. Поведение конечного детерминированного автомата /1=(ХД<5), |5|=ш, где т - простое число, моделируется

семейством степенных многочленов.

Теорема 2.2.2. (Необходимые условия моделируемости КДА ССМ). Пусть дан конечный детерминированный автомат А=(Х,8,3), |5]=т, и каноническое разложение числа состояний автомата т имеет вид т = р^рЧ1 •■• р"" ■ Для того, чтобы поведение автомата А моделировалось семейством степенных многочленов вида (3), необходимо, чтобы любое его отображение переходов ёх удовлетворяло системе т-р\ сравнений, из которых »11-1 имеют вид:

-у0) г 0(то<1т)Д- = 1 ,тх -1, (3)

а остальные имеют вид:

= (modm),J = 1 ,рг - 1,1 < к} < , (4)

где щ =р?-1р?...р? ■

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

Теорема 2.2.3. Пусть дан конечный детерминированный автомат А=РС,8,3), и каноническое разложение числа состояний автомата т имеет вид т=2р, где р- простое число. Для того, чтобы поведение автомата А моделировалось семейством степенных многочленов вида (3), необходимо и достаточно, чтобы любое его отображение переходов

5х удовлетворяло следующий системе сравнений:

№ -О>-1)в0 = ^(то(1т)> (р+1)^ -(р + 2).50 = 0(тос1т), (5)

О^Кы -р*0=0(тойт),о</с<1^1, (6)

2

№ +0>-1>2* +5 и £0(тос1от) , (7)

2

- «о) = 0(тос12),1 <кйр-\, (8)

= ^1(тос12),1 <к< (9)

В ходе исследований выяснилось, что некоторые автоматные подстановки, не удовлетворяющие приведенным выше условиям, и, следовательно, не допускающие моделирование степенным многочленом вида (3), все же могут быть представлены степенной функцией = +а15+а2я2С рациональными

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

позволяющий по заданному числу состояний автомата Медведева найти связи между компонентами вектора переходов а*, которые представляют собой необходимые и достаточные условия моделируемости КДА семейством степенных многочленов с рациональными коэффициентами. Этот метод основан на применении метода Гаусса для решения однородной СЛАУ с транспонированной моделирующей матрицей автомата. Кроме того, доказано два следствия.

Следствие 2.2.1. (Критерий моделируемости КДА ССМ с целыми коэффициентами). Для того, чтобы автомат А=(Х,8,5), ¡&1=>л моделировался семейством степенных многочленов с целыми коэффициентами, необходимо и достаточно, чтобы любое его отображение переходов удовлетворяло т-1-г связям, способ нахождения которых дается в методе 2.2.1, а также условиям (3) и (4).

Следствие 2.2.2, Пусть дан конечный детерминированный автомат /4=(ХД<5), |5|=т, и каноническое разложение числа состояний автомата т имеет вид т=2р, где р- простое число. Для того, чтобы автомат А моделировался семейством степенных многочленов с рациональными коэффициентами, необходимо и достаточно, чтобы любое его отображение переходов удовлетворяло системе сравнений (5)47).

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

В третьей главе работы для класса автоматов, моделируемых ССМ, решается задача ФВП. В первом параграфе приведены формальные постановки задач синтеза и анализа универсального автомата, моделируемого ССМ. Так как универсальность автомата равносильна его универсальной перечислимости, то для решения поставленных задач необходимо разработать метод построения перечислимого множества для автоматов описанного класса. Такой метод (метод 3.2.2) приведен и обоснован во втором параграфе. Он

основан на изучении полугруппы Р'А = ,.••»/* )> порожденной

функциями /ч ,/Х2,.../Хп, моделирующими поведение автомата Л при

подаче входных сигналов соответственно. Предварительно

показано, что если преобразование, порожденное входными символами Х],Х2,...рс„, допускает моделирование степенными многочленами, , Д ,---,/Хп соответственно, то преобразование, порожденное

последовательностью входных символов г=г. г ...х , также допускает моделирование некоторым степенным многочленом

/,(л)= fx (Jx {...fx (s)))(modm) - Следовательно, элементы

'и Ы I '1

полугруппы F, имеют вид f , то есть представляют собой

/Л/л

функции, модулирующие поведение автомата Л на произвольных словах. Очевидно, что множество Fj различных элементов полугруппы

Fa представляет, то сути, множество L(X*), перечислимое автоматом А. Принадлежность функций, моделирующих поведение автомата А на некотором слове, к данному множеству определяется исходя из следующих соображений. Очевидно, что элементы f4,fX2,...fXn

принадлежат множеству F'a . Пусть для некоторого слова t р длины р

выполняется равенство (5) = f.(s), где f. е Ь"*л J/"I <1^1(1 il-

длина слова 0- Тогда, очевидно, функция ft (s) не включается в

множество р'А. Кроме того, любая функция, моделирующая

перестановку, порожденную словом, имеющим слово t в качестве

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

существует, то ft (5) включается в множество F"a. Пусть для некоторого слова t р длиныр выполняется равенство ft (s) = c-const, с e f 0, т -1]. Тогда любая функция, моделирующая перестановку, порожденную словом, имеющим слово t р в качестве суффикса, равна той же константе и, следовательно, также не включается в множество F"a . Пусть для некоторого слова I р длины р выполняется равенство ft (s) = s. Тогда любая функция, моделирующая

перестановку, порожденную словом, имеющим слово t р в качестве

префикса или суффикса, равна одной из функций, моделирующих перестановку, порожденную словом короче данного, и, следовательно, также не включается в множество F* ■

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

Теорема 3.3.1. Автомат Л (X,S, <5), который допускает моделирование семейством степенных многочленов {f„}xcX > является универсальным перечислителем для семейства автоматов {At}ieI \А, = (Xi,S,Si), где А, допускает моделирование семейством

степенных многочленов > тогда и только тогда, когда

(V/ е /)( V .r е X,) f^eL(X'), где множество L(X') строится с

помощью метода 3.2.2.

На основании данной теоремы в четвертом параграфе решается задача анализа универсального автомата. Показывается, что семейство автоматов, для которых А является универсальным, содержит 2" - 2 автоматов (где п - мощность множества, перечислимого автоматом А LJX*)), которые строятся следующим образом. Рассматриваются 2" -2 подмножеств множества 1,Л(Х*), то есть все подмножества, за исключением пустого подмножества и подмножества, совпадающего с LAX'), и выделяются множества (F,\ —, где F,- множество

подмножеств множества LA(X') мощности к, \fk,k = \,n-l конструируются автоматы Aü = {Xk,S,öh), где Хк={хг,хг,...хк}, а функции переходов моделируются степенньши функциями { Гт} _,

j J 1 >'•

где {f'^,/^'" f^'} s J'k ■ Заметим, что для каждого к таких

автоматов будет Скп (число сочетаний из п по к), то есть ; = 1, С* ■

В пятом параграфе решается задача синтеза. Согласно теореме S.S. 1, автомат А, моделируемый функциями множества F, где F = (J{/(0,/w,...,/(0} ("г мощность множества входных символов

iel

автомата А,), является универсальным перечислителем для семейства MJiW. Однако показана возможность построить универсальный перечислитесь А семейства с меньшей мощностью множества

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

быть порождена функциями ,j , то есть не

совпадает ни с одной из функций множества LA .(X*), перечислимого

автоматом А}- (/е/./'тЧ).

В шестом параграфе предложен метод 3.6.1 построения восстанавливающей последовательности. Характерной особенностью данного метода является одновременность синтеза восстанавливающей последовательности и конструктивности проверки ее существования для заданной неисправности.

Вход , метода: степенные функции gx.,i = \,n вида (3),

моделирующие поведения А=(ХДЗ) типа (1); степенная функция (1 ^ /г < л, (5-) ^ (у)) вида (3), моделирующая поведение

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

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

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

неисправности.

Метод основан на некоторой модификации метода 3.2.2 построения множества, перечислимого автоматом А=(Х,Б,д), поведение которого моделируется степенными функциями Д ,/ = 1,и, где

и одновременной проверки принадлежности функции /х (я) = gXh (х) этому множеству.

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

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

Работа посвящена выделению класса конечных

автоматов. В работе решены следующие три основные задачи:

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

2. Описан класс автоматов, допускающих моделирование семействами степенных многочленов.

3. Для описанного класса решена задача функционального восстановления поведения.

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

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

- предложены в аналитическом виде необходимые условия моделируемости КДА ССМ с целыми коэффициентами;

- для частного случая числа состояний автомата т~2р, где р -простое число, предложены критерии моделируемости КДА ССМ с целыми и рациональными коэффициентами;

- сформулирован и обоснован метод нахождения необходимых и достаточных условий моделируемости КДА ССМ с

. рациональными коэффициентами;

- на основе этого метода получены критерии моделируемости произвольного КДА ССМ с целыми и рациональными коэффициентам.

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

При решении третьей задачи получены следующие результаты:

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

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

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

- для автоматов, допускающих моделирование ССМ, получен метод конструктивной проверки существования восстанавливающей последовательности (относительно заданной неисправности) и ее построения.

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

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

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

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

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

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

5. Шульга Т.Э. О некоторых аспектах задачи восстановления поведения сложных систем/У Тез. докл. Первой всероссийской науч. конф. молодых ученных и аспирантов "Новые информационные технологии разработка и аспекты применения",- Таганрог: изд. ТРУ, 1998. - С. 150-151.

6. Шульга Т.Э. О возможностях восстановления поведения сложных систем // Сборник научных трудов всероссийской военно-технической конференции "Проблемы совершенствования ракетных комплексов" - Саратов: изд-во Саратовского филиала ВАУД999. - С 30-34.

7. Шульга Т.Э. О моделировании автоматных функций. // Тез. докл. IV Международной конференции студентов и аспирантов по фундаментальным наукам "Ломоносов 99"- М.: изд-во МГУ, 1999,-С.255-256.