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

• Автор: Ульянов, Сергей Александрович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Иркутск
• Количество страниц: 95 с. : ил.

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

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

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

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

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

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) значений этой (вообще говоря, векторной) функции вдоль процессов х(Ь) изучаемой системы вектором состояния хс{{) соответствующих процессов системы сравнения в тог же момент времени ? В зависимости от специфики изучаемых свойств условие типа гомоморфизма может варьироваться дополнительно. Например, при изучении свойств типа достижимости (управляемости) равенство v(x(t)) — хс(Ь) достаточно требовать только до первого момент попадания х(? V называется частичным гомоморфизмом). Сказанное переводит рассмотрение в сферу применимости так называемого метода редукций [6, 7, 9], где вспомогательные функции V и системы рассматриваются в более широких классах и именуются редукторами и редуцированными моделями соответственно. При этом основное условие, накладываемое на них (условие мажорирования, условие гомоморфизма и т. В настоящее время для логико-динамических моделей автоматного типа предложено несколько конструктивных алгоритмов построения редукторов [9, ], с использованием которых проведен анализ различных динамических свойств. Сложность исследования логико-динамических моделей автоматного типа может быть уменьшена не только использованием редукторов, но и применением алгоритмов и методов минимизации логических функций, например, в классе дизъюнктивных нормальных форм (ДНФ). В большинстве известных на сегодняшний день алгоритмах минимизации ДНФ выделяют два этапа []: порождение простых импликаит и решение задачи поиска минимального покрытия. Первый этап соответствует построению сокращенной ДНФ, а второй — минимальной. Стоит отметить, что задача поиска минимального покрытия является НР-полной и для ее решения не существует эффективных алгоритмов []. Одним из классических алгоритмов минимизации логических функций является алгоритм Квайна-Мак-Класски ((Зшпе-МсСЬэкеу) (, ].