Эксперименты с линейными автоматами тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

1. Обобщенные эксперименты с линейными автоматами

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

1.2. Обобщенные установочные эксперименты с линейными 30 автоматами

1.3. Обобщенные диагностические эксперименты с линей- 38 ными автоматами

Теория экспериментов с автоматами представляет собой фундамент многих современных методов и средств технической диагностики цифровой аппаратуры. Одной из существенных причин, порождающих сложности при решении упомянутых проблем, является отсутствие, как правило, информации о начальном, промежуточном или конечном состоянии устройства. Для снятия указанной неопределенности и служат так называемые синхронизирующие, установочные и диагностические последовательности, подаваемые при проведении соответствующего эксперимента на входы устройства. В настоящее время теория экспериментов для автоматов общего вида достаточно хорошо развита, и ей посвящен ряд работ. Это работы Мура Э. [26], Гилла А. [11], Глушкова В.М. [14], Яблонского C.B. [46], Богомолова A.M. [2]-[5], Твердохлебова В.А. [40], Грунского И.С. [3]-[4], Кудрявцева В.Б. [23], Скобелева В.Г. [30], Спивака М.А. [39] и др. Полученные результаты позволяют сделать вывод о значительной трудоемкости методов синтеза упомянутых последовательностей. Кроме того, их длины для реальных устройств, описываемых автоматными моделями, очень велики. Вместе с тем, среди реальных устройств существуют такие классы, специфика которых позволяет существенно упростить процедуры синтеза упомянутых последовательностей, причем длины их оказываются значительно короче в сравнении с длинами экспериментов для автоматов общего вида. Так, например, такая ситуация имеет место для устройств, математическими моделями которых являются линейные и билинейные автоматы [8], [10], [12], [44], [45].

Линейные и билинейные автоматы являются математической моделью устройств, широко используемых для кодирования и сжатия информации, в качестве сигнатурных анализаторов, а также при синтезе схем встроенного контроля и систем автоматического управления [1], [15],

25], [28]. Работы по теории экспериментов с такими автоматами практически отсутствуют, хотя, как уже было отмечено, многие известные результаты и методы для автоматов общего вида могут быть сделаны более эффективными для линейных и билинейных автоматов. Эксперименты с такими автоматами изучались в работах Сперанского Д.В. [33]-[38].

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

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

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

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

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

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

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

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

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

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

- найдены оценки длин обобщенных установочных и диагностических последовательностей для ЛА;

- получены условия существования синхронизирующих, установочных и диагностических последовательностей Для последовательных, параллельных и параллельно-последовательных сетей из ЛА;

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

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

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

- предложены методы нахождения этих последовательностей;

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

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

Диссертация выполнена в течение 1996-1999 г.г., тема диссертации утверждена на заседании Ученого совета университета (прот. № 3 от 13.11.96). Исследования проводились в рамках следующих грантов: 1) "Разработка методов теории конечных автоматов и формальных языков" -грант Министерства общего и профессионального образования РФ, 19981999 г.г.; 2) "Неклассические задачи и средства исследования свойств конечных автоматов" - грант РФФИ №98-01-00113.

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

Результаты работы докладывались и обсуждались на международной конференции "Проблемы и перспективы прецизионной механики и машиностроения в управлении" (Саратов, 1997), международной конференции "Математика в индустрии" (Таганрог, 1998), международной конференции "Проблемы теоретической кибернетики" (Нижний Новгород, 1999), конференции сотрудников механико-математического факультета СГУ, посвященной 90-летию университета (Саратов, 1999), семинарах в Саратовском государственном университете.

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

Диссертация содержит 92 машинописные страницы, состоит из введения, трех основных разделов и списка литературы.

Заключение

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

1. Барашко A.C. К теории сигнатурных анализаторов // Кибернетика. -1990,-N2. -с. 18-22.

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

3. Богомолов A.M., Грунский И.С. О достижимости верхней границы длины минимального установочного эксперимента для автомата Мура//Кибернетика. 1971. -N1. - с.147-148.

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

5. Богомолов A.M., Скобелев В.Г. Об одном алгоритме решения диагностической и установочной задач с автоматом // Кибернетика. 1975.-N6.-с. 1-6.

6. Бородянский Ю.М. Эксперименты с конечными автоматами Мура // Кибернетика. 1965. -N 6. - с. 18-31.

7. Брауэр В. Введение в теорию конечных автоматов. М.: Радио и связь. - 1987. - 392 с.

8. Габасов Р., Кириллова Ф.М., Крахотко В.В., Минюк С.А. Теория управляемости линейных дискретных систем // Дифференциальные уравнения. 1972. -т.8. -N5,6,7. - с. 767-774, 1081-1092, 1283-1292.

9. Гантмахер Ф.Р. Теория матриц. М.:Наука. - 1988. - 552 с.

10. Гараев М.И., Фараджев Р.Г. Аналитические методы вычисления процессов в линейных последовательностных машинах с переменными параметрами // Автоматика и телемеханика. 1971. -N1.-с. 66-74.

11. Гилл А. Введение в теорию конечных автоматов. М.: Наука. -1996.-272 с.

12. Гилл А. Линейные последовательностные машины. М. : Наука. -1974.-287 с.

13. Гинзбург С. О длине кратчайшего однородного эксперимента // Кибернетич. сб. вып. 3. - 1961. - с. 25-30.

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

15. Казначеев В.И. Диагностика неисправностей цифровых автоматов. М. : Сов. радио. 1975. - 256 с.

16. Клячко A.A., Рысцов И.К., Спивак М.А. Об одной экстремальной комбинаторной задаче, связанной с оценкой длины возвратного слова в автомате // Кибернетика. 1987. - N2. - с. 16-21, 25.

17. Колдобанова М.В. Эксперименты с сетями линейных последовательностных машин // Теоретические проблемы информатики и ее приложений, Саратов: изд. СГУ. 1997. - вып.1. -с. 67-75.

18. Колдобанова М.В. Установочные эксперименты с сетями линейных последовательностных машин // Проблемы и перспективы прецизионной механики и машиностроения в управлении, Саратов. -1997.-с. 51-53.

19. Колдобанова М.В. Эксперименты для сети из линейных автоматов с потерей информации // Математика в индустрии. Труды Международной конференции, Таганрог. 1998 - с. 190-191.

20. Колдобанова М.В. Распознавание входных сигналов для сети из линейных автоматов с потерей информации// Теоретические проблемы информатики и ее приложений, Саратов: изд. СГУ. 1998.- вып.2. с. 57-62.

21. Колдобанова М.В. Установочные и диагностические эксперименты с билинейными дискретными системами // Проблемы теоретическойкибернетики. Тезисы докладов XII Международной конференции, Москва.-1999,-с.105.

22. Колдобанова М.В. Условия существования экспериментов для билинейных систем // Автоматизация проектирования дискретных систем. Материалы III Международной конференции, Минск. 1999. -т.З.-с. 6-13.

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

24. Курош А.Г. Курс высшей алгебры. М.: Наука. - 1976. - 432 с.

25. Латыпов Р.Х., Нурутдинов Ш.Р., Столов Е.Л., Фараджев Р.Г. Применение теории линейных последовательностных машин в системах диагностирования // Автоматика и телемеханика. 1988. -N8.-с. 3-27.

26. Мур Э. Умозрительные эксперименты с последовательностными машинами// сб. "Автоматы". М.: ИЛ. - 1956. - с. 179-210.

27. Новиков П.С. Элементы математической логики. М.:Наука. - 1973. - 400 с.

28. Пархоменко П.П., Согомонян Е.С. Основы технической диагностики. -М.: Энергоиздат. -1981.-319 с.

29. Рысцов И.К. О слабой эквивалентности автоматов // Кибернетика. -1990. N5. - с.85-89,134.

30. Скобелев В.Г. О сложности поиска диагностических и установочных слов для конечного автомата // Кибернетика. 1985. - N4. - с. 116118.

31. Соловьев H.A. Тесты. Новосибирск: Наука. - 1978. - 189 с.

32. Сперанский Д. В. Обобщенные линейные автоматы без потери информации // Известия РАН. Теория и системы управления. 1998. -N1. - с.166-172.

33. Сперанский Д.В. Синхронизация линейных последовательностных машин // Автоматика и телемеханика. 1996. - N5. - с. 141-149.

34. Сперанский Д.В. Обобщенная синхронизация линейных последовательностных машин // Кибернетика. 1998. - N3. - с. 1725.

35. Сперанский Д.В. Установочные и диагностические последовательности для линейных автоматов // Автоматика и телемеханика. 1997. -N5. - с. 133-141.

36. Сперанский Д.В., Сперанский И.Д. Эксперименты с линейными дискретными системами// Электронное моделирование (в печати).

37. Сперанский Д.В. Experiments with bilinear discrete systems // Proceedings of the International Conference, Minsk. 1999. - v.l.

38. Сперанский Д.В., Колдобанова M.B. Обобщенные эксперименты с линейными динамическими системами// Информационно-управляющие системы на железнодорожном транспорте, Харьков. -1997.-с. 84.

39. Спивак М.А. Некоторые свойства множества экспериментов автомата // Кибернетика. 1996. -N6. - с. 1-7.

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

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

42. Фараджев Р.Г. Линейные последовательностные машины. М.:Сов. радио. - 1975. - 256 с.

43. Хиббард Т.Н. Точные верхние границы длин минимальных экспериментов, определяющих заключительное состояние для двух классов последовательностных машин // Кибернетич. сб. вып. 2. -1966.-c.7-23.

44. Цыпкин Я.З., Фараджев Р.Г. Преобразование Лапласа-Галуа в теории последовательностных машин // Доклады АН СССР. 1966. - т. 166. -N3.- с. 570-574.

45. Элспас Б. Теория автономных линейных последовательностных сетей // Кибернетич. сб. вып. 7. - 1963. - с. 32-36

46. Яблонский C.B. О построении тупиковых кратных экспериментов для автоматов. М.: Тр. МИАН им. В.А. Стеклова. - т. CXXXIII. - с. 263-272.

47. Янушевский Р.Т. Управление объектами с запаздыванием. -М.:Наука, 1978.-416 с.