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

Введение.

1 Исследование специфики функционирования автоматов Медведева с

I обобщенными временными характеристиками.

1.1 Основные понятия и определения.

1.2 Автоматы с обобщенными временными характеристиками и их функционирование.

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

1.4 Основные результаты раздела.

2 Восстановление поведения системы, моделируемой КДА Медведева произвольного временного типа, на основе анализа универсального автомата с обобщенными временными характеристиками.

2.1 Анализ универсального автомата с обобщенными временными характеристиками.

2.2 ФВП системы, моделируемой КДА Медведева типа (0,t2), при изменении начального порядка расположения состояний автомата.

2.3 Основные результаты раздела.

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

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

3.2 Восстановление поведения системы, моделируемой семейством {Aj}j6i автоматов Медведева типа (0,1).

3.3 Основные результаты раздела.

Теория автоматов находит широкое применение при решении задач проектирования, технического диагностирования и восстановления поведения сложных систем [43, 44, 45, 50]. Это обусловлено способностью автоматов выступать в качестве адекватных математических моделей законов функционирования дискретных систем [29, 37]. В свою очередь, исследование проблематики автоматов позволяет в определенной мере предсказать типологию и постановку задач технической диагностики и восстановления поведения [25-27, 32, 38].

Исследования в области теории конечных детерминированных автоматов (КДА) проводятся достаточно давно, начиная с работ Э. Мура, А. Гилла, В.М. Глушкова и других авторов [1, 28, 29, 2, 3, 13, 18, 35, 36, 39, 42, 48, 61, 62].

Одно из направлений этой теории, связанное с задачами исследования математических методов технической диагностики, получило развитие в работах A.M. Богомолова, П.П. Пархоменко, М.Ф. Каравая, Д.В. Сперанского, В.А. Твердохлебова [7, 9, 12, 33, 34, 59, 43-45, 47]. А.А. Сытник использовал теоретические основы технической диагностики в качестве инструментария при построении теории восстановления поведения дискретных систем [10, 11, 16, 49, 50, 51, 55], для которых способность к восстановлению поведения означает возможность продолжения заданного закона функционирования после возникновения и обнаружения неисправности.

Одним из возможных подходов при решении задачи восстановления является использование свойств текущего закона функционирования системы, полученного после возникновения неисправности, для формирования на выходах требуемой совокупности реакций, то есть решение задачи функционального восстановления поведения (ФВП) [50, 51, 56].

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

В теории универсальных автоматов есть несколько вариантов определения универсальности. Так в определении, предложенным М. Минским [1], элемент называется универсальным, если достаточно большое множество объектов «обладает некоторыми подобными свойствами этого элемента, или отличающимися лишь в количественном отношении». Исследования данного подхода на множестве ограниченно - детерминированных функций проведено В.Б. Кудрявцевым и В.А. Буевичем [14].

В.М. Глушков [29] называет автомат универсальным, если «любой алгоритм может быть представлен в виде конечного набора выполняемых этим автоматом команд программы работы и фактически реализован им при условии игнорирования ограничений, накладываемых конечностью объема памяти автомата».

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

Дальнейшие исследования универсальности были ограничены классом булевых функций и конечных детерминированных автоматов. К их числу следует отнести работы Э.В. Евреинова, И.В. Прангишвили [31], В.И. Варшавского [18], В.М. Глушкова [29], В.А. Мищенко [40], Я.М. Барздиня [5], А.А. Сытника [50].

Понятие универсального КДА, основанное на концепции универсальности К. Шеннона, было исследовано А.А. Сытником [50].

Определенный в [10, 50] универсальный КДА А{ для класса автоматов

Aj}.! позволяет моделировать поведение любого автомата из этого класса с точки зрения выходных реакций. Осуществляется этот процесс путем подбора в универсальном автомате инициального состояния и входного сигнала (в общем случае последовательности входных сигналов), вызывающих ту же выходную реакцию, что и зафиксированный входной сигнал в рассматриваемом автомате семейства. Соответственно, эквивалентность в поведении универсального Aj и моделируемого А(, iel автоматов понимается в смысле перечислимости одинакового множества выходных сигналов. Данный подход является редукцией концепции К. Шеннона на множестве КДА.

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

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

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

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

Решение этих задач в каждом конкретном случае требует их формализации [41], например, с использованием математического аппарата конечно-автоматных преобразований симметрической полугруппы [17, 50, 51] или на основе построения числовой модели системы, допускающей моделирование многочленами [55, 56].

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

В.А. Твердохлебовым [58, 59, 60].

В работах А.А. Сытника [49, 50] по ФВП систем автоматы типов (tvt2,t3,t4) использовались для определения временного режима наблюдения выходных реакций при восстановлении поведения в перечислительной форме. При этом не рассматривался класс нарушений функционирования, который составляют изменения временных характеристик процесса формирования реакций системы. Моделирование поведения систем для данного класса неисправностей может быть адекватно реализовано с использованием автоматов с обобщенными временными характеристиками типа (/j,^,^,^).

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

Объектами исследований в работе являются математические модели дискретных систем, представляющие собой инициальные КДА A = (S,X,Y,S,A,s0) [28, 29]. Их поведение р представляется в виде объединения автоматных преобразований, индуцируемых всем множеством сигналов подаваемых на вход:

Р= и >/>))}> реХ* где X - расширенная функция выходов автомата А.

Предметом диссертационного исследования являются траектории изменения состояний КДА, что позволяет рассматривать вместо автоматов А = (S,X,Y,S,A,s0) автоматы Медведева [48]:

A = {S,X,S,s0) S:SxX^S

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

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

- исследование специфики функционирования и восстановления поведения систем, моделируемых автоматами Медведева с обобщенными временными характеристиками;

- разработка метода решения задачи ФВП системы, моделируемой КДА Медведева с обобщенными временными характеристиками, на основе приведения КДА Медведева типа (0, t2) к автомату Мура;

- разработка метода восстановления поведения системы, моделируемой КДА Медведева с обобщенными временными характеристиками типа (0,/2), в случае изменения начального порядка расположения состояний, формируемых размещениями;

- разработка метода восстановления поведения системы, основанного на синтезе универсального автомата Медведева А1 типа (О,/^) Для заданного семейства КДА Медведева At, г el типов ^0,/^) по известным временным характеристикам автоматов Д; - разработка метода восстановления поведения сложной системы, моделируемой семейством {At }ieI автоматов Медведева типа (0,1), на основе использования универсального для семейства {А( }.6/ автомата Медведева типа (0,t2) с заданным начальным порядком расположения состояний.

Совокупность полученных в работе новых научных результатов позволила сформулировать следующие положения, выносимые на защиту:

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

2. Разработанные методы решения задач анализа и синтеза универсальных автоматов с обобщенными временными характеристиками типа (0,t2) позволяют восстанавливать поведение моделируемой системы при изменениях временных характеристик процесса функционирования.

3. Моделирование поведения сложной системы, компоненты которой описываются автоматами Медведева Ап iel типа (0,1), возможно пучком автоматов типа (1,1,0,0), эквивалентным универсальному для семейства Ai }/е/ автомату Медведева Af типа (0,/2).

Диссертация состоит из введения, трех разделов, заключения и списка использованных источников.

Основные результаты работы заключаются в следующем:

1. Установлено, что задача ФВП дискретных систем, моделируемых автоматами Медведева с обобщенными временными характеристиками, разрешима тогда и только тогда, когда она разрешима для автоматов Мура типа (1,1,0,0) их представляющих.

2. Предложен и обоснован метод решения задачи ФВП систем, моделируемых автоматами Медведева А = (s, с обобщёнными временными характеристиками типа (0,/2), основанный на типа (1,1,0,0).

3. Установлена возможность ФВП поведения системы, моделируемой КДА Медведева типа (0, t2), при изменениях временных характеристик процесса формирования ее выходных реакций, которые представлены изменениями начального порядка расположения состояний автомата, формируемых размещениями.

4. Разработан и обоснован метод восстановления поведения системы, моделируемой КДА Медведева с обобщенными временными характеристиками типа (0,f2) при изменениях начального порядка расположения состояний, формируемых размещениями, на основе решения задачи анализа универсального автомата.

5. Разработан и обоснован метод решения задачи ФВП системы, моделируемой КДА Медведева с обобщенными временными представлении их автоматами Мура характеристиками типа (0,/2) при изменении начального порядка расположения состояний автомата, формируемых перестановками.

6. Определены достаточные условия решения задачи синтеза универсального автомата Медведева с обобщенными временными характеристиками для семейств автоматов произвольных временных типов.

7. Разработан и обоснован метод восстановления поведения системы, основанный на синтезе универсального автомата Aj = (^Х,^,.?0] типа (0J2) Для заданного семейства КДА Медведева Ai = (s^X,^.,,?,0), /е/ типов {o,tl^j.

8. Предложен и обоснован метод представления поведения автомата Медведева Aj типа (0,/2) с заданной начальной перестановкой состояний эквивалентным пучком автоматов типа (1,1,0,0).

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

Заключение

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

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

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

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

4. Баранов С.И. Синтез микропрограммных автоматов. -Л.: «Энергия», 1979. -232 с.

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

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

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

8. Богомолов A.M., Салий В.Н. Алгебраические основы теории дискретных систем. -М.: Наука, 1997. -368 с.

9. Богомолов A.M., Сперанский Д.В. Аналитические методы в задачах контроля и анализа дискретных устройств. Саратов: Изд-во Сарат. ун-та, 1986.-240 с.

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

11. Богомолов A.M., Сытник А.А., Твердохлебов В.А. Автоматные модели и рекурсивный конструктивизм. Саратов: Изд-во Сарат. ун-та, 1992. -76 с.

12. Богомолов A.M., Твердохлебов В.А. Целенаправленное поведение автоматов. -Киев: Наукова думка, 1975. -123 с.

13. БрауэрВ. Введение в теорию конечных автоматов/ Пер. с англ. Под ред. Журавлева Ю.И. -М.: Радио и связь, 1987. -392 с.

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

15. Булева алгебра и конечные автоматы/ Под ред. д-ра техн. наук Пархоменко П.П. -М.: Мир, 1969. -294 с.f 16. Вагарина Н.С., СытникА.А. Задача восстановления поведения в классесистем без потери информации//Искусственный интеллект. -2004, №4 -С. 100-107.

16. ВагаринаН.С., СытникА.А. Полугрупповые методы при синтезе универсальных автоматов- перечислителей// Теоретические проблемы информатики и ее приложений: Сб. науч. тр. -Саратов: Изд-во Сарат. ун-та, 2004.-Вып. 6.-С. 53-61.

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

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

19. ВахлаеваК.П. Автоматное моделирование многозадачных ( систем// Теоретические проблемы информатики и ее приложений: Сб. науч.тр. -Саратов: Изд-во Сарат. ун-та, 2003. -Вып. 5. -С. 47-59.

20. Вахлаева К.П. Применение управляющих функций для настройки системы автоматов на заданное поведение , в перечислительной форме// Теоретические проблемы информатики и ее приложений: Сб. науч. тр. -Саратов: Изд-во Сарат. ун-та, 2004. -Вып. 6. -С. 61-67.

21. Ведешенков В.А. Организация самодиагностирования технического состояния цифровых систем// Автоматика и телемеханика. —2003, № 11. — С. 165-183.

22. Гилл А. Введение в теорию автоматов/ Пер. с англ. Дауровой А.Т. и др. Под ред. Пархоменко П.П. -М.: Наука, 1966. -272 с.

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

24. Дискретная математика и математические вопросы кибернетики/ Под общей ред. Яблонского С.В. и ЛупановаО.Б. -М.: Наука, 1974. -Т. 1. -311 с.

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

26. Какубава Р.В., Хуродзе Р.А. Вероятностный анализ производительности технических систем со структурной и временнойизбыточностью// Автоматика и телемеханика. -2004, № 5. -С. 154-166.

27. Каравай М.Ф. Математические основы отказоустойчивости//Методы и системы технической диагностики: Материалы VII Всесоюз. совещания по технической диагностике и отказоустойчивости. -Саратов: Изд-во Сарат. ун-та, 1990. -Вып. 14. -4.1. -С. 3-7.

28. Каравай М.Ф. Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурация при отказах// Автоматика и телемеханика. -2004, № 12. -С. 159-178.

29. Кобринский Н.Е., Трахтенброт Б.А. Введение в теорию конечных автоматов. —М.: Физматгиз, 1962. -404 с.

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

31. Левин В.И. Математическое моделирование систем с помощью динамических автоматов// Информационные технологии. —1997, № 9.

32. Мамедли Э.М., Соболев Н.А. Метод обеспечения отказоустойчивости в резервированных управляющих вычислительных системах// Автоматика и телемеханика. -2000, № 2. -С. 172-183.

33. Мелихов А.Н. Ориентированные графы и конечные автоматы. -М.: Наука, 1971. —416 с.

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

35. Моисеев Н.Н. Математические задачи системного анализа. -М.: Наука, 1981. —488 с.

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

37. Основы технической диагностики/ Под ред. Пархоменко П.П. -М.: Энергия, 1976. -4.1. -464 с.

38. Пархоменко П.П. О технической диагностике. -М.: Знание, 1969. -64 с.

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

40. РиорданДж. Введение в комбинаторный анализ/ Пер. с англ. Садовского JI.E. Под ред. Куликова Л.Я. -М.: Изд-во Иностранная1 литература, 1963. —287 с.

41. Сперанский Д.В. О тестировании линейных автоматов// Автоматика и телемеханика. -2000, № 5. -С. 157-166.

42. Спивак М.А. Введение в абстрактную теорию автоматов. -Саратов: Изд-во Сарат. ун-та, 1970. -109 с.

43. Сытник А.А. Восстановление поведения дискретных систем//Методы и системы технической диагностики: Материалы VII Всесоюз. совещания по технической диагностике и отказоустойчивости. -Саратов: Изд-во Сарат. ун-та, 1990.-Вып. 14.-4.1.-С. 149-151.

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

45. Сытник А.А. Методы и модели восстановления поведения автоматов// t Автоматика и телемеханика. -1992, №11. -С. 149-159.

46. Сытник А.А., Вахлаева К.П. Об использовании автоматных моделей при построении отказоустойчивых вычислительных систем// Электронное моделирование. -2004. -Т. 26, № 3. -С. 51-64.

47. СытникА.А., ПосохинаН.И. Об одном подходе к восстановлению поведения конечных детерминированных автоматов// Известия РАЕН, серия МММИУ. -1999. -Т. 3, № 1. -С. 91-99.

48. СытникА.А., ШульгаТ.Э. Числовые методы функционального * восстановления поведения систем// Автоматика и телемеханика. -2003,10.-С. 123-140.

49. Таирбеков Ч.Б.о. Автоматы с обобщенными временными характеристиками как перечислители// Теоретические проблемы информатики и ее приложений: Сб. науч. тр. -Саратов: Изд-во Гос. УНЦ «Колледж», 1999. -Вып.З.-С. 115-118.

50. Твердохлебов В.А. Аксиоматический подход к диагностированию систем в целом//Математические модели поведения: Межвуз. науч. сб. -Саратов: Изд-во Сарат. ун-та, 1981. -Вып. 5. -С. 105-113.

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

52. Твердохлебов В.А. Построение тестов для автоматов с произвольными \ временными характеристиками// Микропроцессорная техника, техническаядиагностика и структура систем управления. -Саратов: Изд-во Сарат. ун-та, 1987.-С. 11-17.

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

54. Чирков М.К. Основы общей теории конечных автоматов. -JL: Изд-во Ленингр. ун-та, 1975. -280 с.

55. Яблонский С.В. Введение в дискретную математику. -М.: Наука, 1979. — 319 с.