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

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 автоматизирует следующие этапы качественного исследования логико-динамических моделей автоматного типа с использованием метода редукции: построение редукторов, упрощение правых частей уравнений динамики исследуемых моделей, проверка различных условий редукции и критериев наличия в редуцированной модели некоторых динамических свойств типа достижимости и диссипативности.

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

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