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

• Ульянов, Сергей Александрович
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Ульянов, Сергей Александрович

1 Введение

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

1.2 Основные определения и обозначения.

1.3 Цели и структура работы.

1.4 Научная новизна, практическая значимость и апробация полученных результатов.

2 Теоретическое и алгоритмическое обеспечение программного комплекса РЕДУКТОР/

2.1 Критерии наличия в монотонной модели некоторых динамических свойств.

2.2 Теоремы редукции.

2.3 Алгоритмическое обеспечение программного комплекса

2.3.1 Основные структуры данных.

2.3.2 Алгоритм построения гомоморфизмов и синтеза гомоморфных автоматов.

2.3.3 Алгоритм построения множеств состояний редуцированной системы.

2.3.4 Алгоритмы вычисления операций над множествами

2.3.5 Алгоритм упрощения логических выражений.

3 Реализация программного комплекса

3.1 Структура программного комплекса.

3.1.1 Функциональная часть.

3.1.2 Интерфейсная часть.

3.2 Реализация программного комплекса

3.2.1 Реализация основных алгоритмов

3.2.2 Реализация программного интерфейса.

3.2.3 Реализация вспомогательных алгоритмов.

3.3 Методика использования

4 Применения программного комплекса

4.1 Анализ автоматной модели общего вида.

4.2 Исследование простой автоматной модели экономического взаимодействия.

Введение диссертации (часть автореферата) на тему «Алгоритмы и программный комплекс для анализа логико-динамических моделей автоматного типа»

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

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

Частным классом таких моделей являются автоматные модели с логическими функциями переходов, относимые к числу важных видов управляющих систем. Ими могут описываться технические системы управления [25], вычислительные системы и устройства [15], физические среды, в которых реализуются тепловые, волновые и другие явления [24, 35], биологические процессы распространения возбуждения в сердечной мышце [19] и самовоспроизведения [32], а также процессы, протекающие в экономике и обществоведении [21, 23]. Одной из основных задач, решаемых при этом, является задача анализа качественных и метрических характеристик процессов, протекающих внутри этих систем.

Традиционные методы анализа логико-динамических моделей автоматного типа связаны с получением количественных оценок длительности процесса притяжения к предельным циклам и неподвижным точкам [45], в том числе с использованием функций Ляпунова [44, 46, 48], с изменением пространственных форм конфигураций [22, 33], а также с качественным анализом довольно ограниченного набора динамических свойств (достижимость, возвратность и т.д.) [18, 34]. Таким образом, существующее сегодня методическое обеспечение исследования логико-динамических моделей автоматного типа требует своего дальнейшего развития в направлении расширения класса рассматриваемых динамических свойств.

Довольно общим методом качественного исследования нелинейной динамики является метод сравнения в математической теории систем, предложенный В.М. Матросова [30] и развитый в ряде работ [29, 28, 49, 12, 13], при применении которого используются и символьные, и численные процедуры обработки информации. Он позволяет свести рассматриваемую задачу анализа динамического свойства к аналогичной (но более простой по замыслу) задаче для вспомогательной системы, т.н. системы сравнения. При этом исходная система связывается с системой сравнения с помощью некоторых отображений V, именуемых функциями сравнения и ответственных за переносимость свойства из системы сравнения (свойства сравнения) в исходную систему. Типичным условием, определяющим это отображение, является условие типа покомпонентного мажорирования < хс(Ь) значений этой (вообще говоря, векторной) функции вдоль процессов х{Ь) изучаемой системы вектором состояния гсс(£) соответствующих процессов системы сравнения в тот же момент времени ¿.

Использование точных оценок (равенств вместо неравенств) превращает эти функции в отображения типа гомоморфизма (переводящего траектории в траектории) и позволяет существенно смягчить прочие условия, накладываемые на г> с учетом уже специфики конкретного изучаемого свойства, хотя удовлетворить указанным оценкам в форме неравенства проще. В зависимости от специфики изучаемых свойств условие типа гомоморфизма может варьироваться дополнительно. Например, при изучении свойств типа достижимости (управляемости) равенство = хс(1) достаточно требовать только до первого момента попадания в целевое множество (при этом v называется частичным гомоморфизмом). Сказанное переводит рассмотрение в сферу применимости так называемого метода редукций [6, 7, 9], где вспомогательные функции V и системы рассматриваются в более широких классах и именуются редукторами и редуцированными моделями соответственно. При этом основное условие, накладываемое на них (условие мажорирования, условие гомоморфизма и т.п.), в отличие от прочих условий, будем называть основным условием редукции.

В настоящее время для логико-динамических моделей автоматного типа предложено несколько конструктивных алгоритмов построения редукторов [9, 50], с использованием которых проведен анализ различных динамических свойств.

Сложность исследования логико-динамических моделей автоматного типа может быть уменьшена не только использованием редукторов, но и применением алгоритмов и методов минимизации логических функций, например, в классе дизъюнктивных нормальных форм (ДНФ). В большинстве известных на сегодняшний день алгоритмах минимизации ДНФ выделяют два этапа [43]: порождение простых импликант и решение задачи поиска минимального покрытия. Первый этап соответствует построению сокращенной ДНФ, а второй — минимальной. Стоит отметить, что задача поиска минимального покрытия является ^-полной и для ее решения не существует эффективных алгоритмов [53].

Одним из классических алгоритмов минимизации логических функций является алгоритм Квайна-Мак-Класски (С^шпе-МсС1и8кеу) [51, 52].

Этот алгоритм может и довольно эффективно решать задачу порождения простых импликант. Тем не менее, современные, основанные на эвристиках алгоритмы (например, [43, 47]), позволяют существенно повысить эффективность решения задачи минимизации (в том числе задачи порождения простых импликант) по сравнению с алгоритмом Квайна-Мак-Класски.

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Ульянов, Сергей Александрович

Заключение

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

• Критерии наличия в монотонных автоматных моделях динамических свойств типа достижимости и диссипативности.

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

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

• Технология и примеры использования разработанного программного комплекс.

Реализованный программный комплекс РЕДУКТОР/1 автоматизирует следующие этапы качественного исследования логико-динамических моделей автоматного типа с использованием метода редукции: построение редукторов, упрощение правых частей уравнений динамики исследуемых моделей, проверка различных условий редукции и критериев наличия в редуцированной модели некоторых динамических свойств типа достижимости и диссипативности.

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

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

Список литературы диссертационного исследования кандидат технических наук Ульянов, Сергей Александрович, 2005 год

1. Архангельский А.Я. Программирование в Delphi 7. — М.: ООО «Бином-Пресс», 2003 г.

2. Бадд Т. Объектно-ориентированное программирование в действии, Спб.: Питер, 1997.

3. Бакнелл Джулиан М. Фундаментальные алгоритмы и структуры данных в Delphi: Пер. с англ./Джулиан М. Бакнелл. — СПб: ООО "Диа-СофтЮП", 2003.

4. Бурбаки Н. Теория множеств. — М.: Мир, 1965.

5. Буч Г., Рамбо Д., Джекобсон А. Язык UML. Руководство пользователя: Пер. с англ., М.: ДМК Пресс, 2001.

6. Васильев С.Н., Лакеев A.B., Н.Н.Максимкин, и др. Методы редукции в качественном анализе логико-динамических систем // Вестник Томского госуниверситета, Томск, 2004, №9(1), с.193-198.

7. Васильев С.Н. К теории редукции в качественном анализе и управлении динамическими системами // Труды Института математики и механики УрО РАН, Екатеринбург, 2004, т. 10, №2, с. 20-34.

8. Васильев С.Н. Достижимость и связность в автоматной сети с общим правилом переключения состояний // Дифференциальные уравнения, 2002, т. 38, N И, с. 1533-1539.

9. Васильев С.H. Управление динамикой поведения автоматных сетей с минимальным временем достижения целевых состояний // Труды XI Байкальской международной школы-семинара "Методы оптимизации и их приложения", Иркутск, 1998, с. 36-47.

10. Васильев С.Н., Кузнецов, Лакеев A.B. Анализ процессов в цифровых схемах. I. Математическая модель // Изв. РАН, сер.'Теория и системы управления", 1996.

11. Васильев С.Н., Жерлов А. К. Об исчислениях типово-кванторных формул // Докл. РАН, т.343, 1995, №5, с. 583-585.

12. Васильев G. Н. Метод сравнения в анализе систем. I-IV. // Дифференц. уравнения, 1981, т. 17, №9, с. 1562-1573; т. 17, №11, с. 1945-1954; т. 18, №, с. 197-205; т. 18, №6, с. 938-947.

13. Васильев С.Н. Некоторые вопросы математической теории систем. Канд. дисс. к.ф.-м.н., Иркутск, 1976.

14. Васильев Ю.Л., Ветухновский Ф.Я., Глаголев В.В., Журавлев Ю.И., Левенштейн В.И., Яблонский C.B. Дискретная математика и математические вопросы кибернетики, т. I, под общей редакцией C.B. Яблонского и О.Б. Лупанова, М.: Наука, 1974.

15. Глушков В.М., Капитонова Ю.В., Мищенко А. Т. Логическое проектирование дискретных устройств. Киев: Наук, думка, 1987.

16. Гулямов Ш.Б. Математическое и программное обеспечение решения первопорядковых логических уравнений. Канд. дисс. к.ф.-м.н., Иркутск, 1997.

17. Алистер Коберн Быстрая разработка программного обеспечения. — М.: Лори, 2002.

18. Кобринскии U.E., Трахтенброт Б.А. Введение в теорию конечных автоматов. — М.: Физматгиз, 1962.

19. Колотое А. Т. Автоматная модель сердца // Сб. Проблемы кибернетики, вып. 20, М.: Наука, 1968.

20. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ / Пер. с англ. под ред. А. Шеня. М.: МЦНМО, 2002.

21. Кудрявцев В.Б., Кнап Ж., Саксида С. Об автоматном моделировании в обществоведении // Сб. Искусственный интеллект. Теория и приложения, вып. 1, Саратов, 1993, С. 134-146.

22. Кудрявцев В.Б., Подколзин A.C., Болотов A.A. Основы теории однородных структур. — М.: Наука, 1990.

23. Левин В.И. Математическое моделирование социально-экономических процессов (автоматно-логические методы и модели), Пенза: изд-во Пенз. технологического института, 1997.

24. Лоскутов А. Ю., Михайлов A.C. Введение в синергетику: Учеб. пособие, М.: Наука, 1990.

25. Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики. Вып. 10. — М.: Физматгиз, 1963. С. 63-97.

26. Максимкин H.H., Цивилина А.Ю. // Оптимизация, управление, интеллект. 2000. №5(2). С. 287-298.

27. Мальцев А.И. Алгебраические системы. М.: Наука, 1970.

28. Матросов В.М., Васильев С.Н., Каратуев В.Г. и др. Алгоритмы вывода теорем метода векторных функций Ляпунова. Новосибирск, Наука, Сиб. Отд-ние, 1981.

29. Матросов В.М., Анапольский Л.Ю., Васильев С.Н. Метод сравнения в математической теории систем. — Новосибирск: Наука, 1981, 480 с.

30. Матросов В.М. Метод сравнения в динамике систем. I-II // Дифферент уравнения. 1974. Т. 10. №9. С. 1547-1559; Т. И. №3. С. 403-401.

31. Минский М. Вычисления и автоматы. — М.: Мир, 1971.

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

33. Подколзин A.C. О поведении однородных структур // Проблемы кибернетики. Вып. 31. М.: Наука, 1974. С. 133-166.

34. Поспелов Д.А. Логические методы анализа и синтеза схем, М.: Энергия, 1987.

35. Тоффоли Т., Марголус Н. Машины клеточных автоматов: Пер. с англ.- М.: Мир, 1991.

36. Ульянов С.А. Пакет программ для анализа автоматных сетей // Тезисы докладов II школы семинара молодых ученых "Математическое моделирование информационные технологии" (25-29 сентября 2002 г.).- Иркутск: ИДСТУ СО РАН, 2002. С. 30-31.

37. Ульянов С. А. Программный комплекс для анализа свойств дискретных динамических систем // Тезисы докладов конференции " Ляпуновские чтения и презентация информационных технологий" (25-27 ноября 2002 г.). Иркутск: ИДСТУ СО РАН, 2002. - С. 39.

38. Ульянов С. А. Программный комплекс для анализа свойств автоматных сетей // Материалы V конференции молодых ученых "Навигация и управление движением", Санкт-Петербург, 2003. С. 129-134.

39. Ульянов С. А. Качественный анализ динамических свойств монотонных автоматных моделей с задержками // Вестник БГУ. Серия "Математика и информатика". — Улан-Удэ: Издательство Бурятского государственного университета, 2005.

40. Ульянов С.А. Автоматизация процедуры качественного анализа свойств автоматной модели // Материалы 10-ой Байкальской Всероссийской конференции "Информационные и математические технологии в науке, технике и образовании", 2005.

41. Fiser Р., Hlavicka J. BOOM a Boolean Minimizer, Research Report DC-2001-05, Prague, CTU Publishing House, 2001, 37 pp.

42. Fogelman-Soulie F., Gols E., Martinez S., Majia C. Energy Functions in Neural Networks with Continuous Local Functions. Submitted Complex Systems, 1998.

43. Goles E., Martinez S. Neural and Automata Networks. Dynamic Behavior and Applications. Kluwer Acad. Press., 1990.

44. Goles E. Lyapunov Functions Associated to Automata Network, in Automata Networks in Computer Science, F. Fogelman, Y. Robert, M. Tchuente (eds), Manchester University Press, 1987, 58-81.

45. Bachtel G.D., Somenzi F. Logic synthesis and verification algorithms. Boston, MA, Kluwer Academic Publishers, 1996.

46. Hopfield J.J. Neural Networks and Physical Systems with Emergent Collective Computational Abilities, Proc. Natl. Acad. Sei. USA., 79, 1982, 2554-2558.

47. Vasiliev S.N. Machine synthesis of mathematical theorems. Internat. Journal "Logic Programming", USA, 1990, vol.9, №23, p.235-266.

48. McCluskey E.J. Minimization of boolean functions. Bell System Technical Journal, 1956.

49. Quine W. The problem of simplifying truth functions. American Mathematical Monthly, 1952.

50. Ingo Wegener. The complexity of Boolean functions. — Stuttgart: Teubner, 1987.