автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Алгоритмы и программный комплекс для анализа логико-динамических моделей автоматного типа

На правах рукописи

о

Ульянов Сергей Александрович

АЛГОРИТМЫ И ПРОГРАММНЫЙ КОМПЛЕКС ДЛЯ АНАЛИЗА ЛОГИКО-ДИНАМИЧЕСКИХ МОДЕЛЕЙ АВТОМАТНОГО ТИПА

05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата технических наук

Иркутск — 2005

Работа выполнена в Институте динамики систем и теории управления СО РАН.

Научный руководитель: чл.-к. РАН Васильев Станислав Николаевич

Официальные оппоненты: доктор технических наук, профессор

Малышкин Виктор Эммануилович

кандидат физико-математических наук Козлов Равиль Измайлович

Ведущая организация: Институт вычислительного моделирования

СО РАН

Защита состоится " 11 " июля 2005 г. в 14 ч. _30_ мин. на заседании Диссертационного совета Д 003.021.01 при Институте динамики систем и теории управления СО РАН по адресу: г. Иркутск, ул. Лермонтова 134.

С диссертацией можно ознакомиться в библиотеке ИДСТУ СО РАН.

Автореферат разослан "10" июня 2005 г.

Учёный секретарь диссертационного совета

Опарин Г.А.

аадог

з

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Довольно общим методом качественного исследования нелинейной динамики является метод сравнения в математической теории систем 1, при применении которого используются и символьные, и численные процедуры обработки информации Он позволяет свести рассматриваемую задачу анализа динамического свойства к аналогичной (но более простой по замыслу) задаче для вспомогательной системы, т н системы сравнения. При этом исходная система связывается с системой сравнения с помощью некоторых отображений у, именуемых функциями сравнения и ответственных за переносимость свойства из системы сравнения (свойсхва сравнения) в исходную систему. Типичным условием, определяющим это отображение, является условие типа покомпонентного мажорирования у(х(1)) < хс{Ь) значений этой (вообще говоря, векторной) функции вдоль процессов х(<) изучаемой системы вектором состояния хс{Ь) соответствующих процессов системы сравнения в тот же момент времени

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

'Матросов В.М Мртод сравнения в динамике сг гения -1974, т 10,

№9, с 1547-1559, т И, №3, с 403-401

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

статочно требовать только до первого момента попадания :г(£) в целевое множество (при этом V называется частичным гомоморфизмом) Сказанное переводит рассмотрение в сферу применимости так называемого метода редукций, где вспомогательные функции у и системы рассматриваются в более широких классах и именуются редукторами и редуцированными моделями соответственно. При этом основное условие, накладываемое на них (условие мажорирования, условие гомоморфизма и т.п.), в огличие от прочих условий, будем называть основным условием редукции.

Возникают вопросы, насколько продуктивно использование и воз можно ли эффективное алгоритмическое построение редукторов с приемлемой компьютерной поддержкой их построения? После того, как исходная задача сведена к редуцированной, т.е. редуктор и редуцированная система построены, остаются другие нетривиальные вопросы обладает ли редуцированная система свойством сравнения, выполняются ли прочие условия редукции (переносимости свойства сравнения)7 Они также требуют своей алгоритмизации и средств автоматизации.

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

• построения гомоморфных (частично гомоморфных) автоматных моделей с монотонными правыми частями;

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

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

• проверки прочих условий редукции;

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

». » »

1 ■ • '

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

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

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

• Возможность использования разработанного программного средства при обучении и решении практических задач качественного анализа.

Апробация работы. Основные результаты диссертации опубликованы в работах [1-7]. Они докладывались на:

• конференции "Ляпуновские чтения и презентация информационных технологий" в ИДСТУ СО РАН (Иркутск, 2002);

• V конференции молодых ученых ''Навигация и управление движением" (Санкт-Петербург, 2003 г);

• ежегодных Школах-семинарах молодых ученых "Математическое моделирование и информационные технологии" (Иркутск-Ангасолка, 2002-2005 г.);

• Всероссийской конференции "Инфокоммупикационные и вычислительные технологии и системы" (Улан-Удэ — Байкал. 2003 г.);

• Пятой Всероссийской конференции с международным участием "Новые информационные технологии в исследовании сложных структур" (Иркутск, 2004 г.);

• научных семинарах ИДСТУ СО РАН (Иркутск, 2004-2005 г).

Программный комплекс используется в исследованиях ИДСТУ СО РАН и в учебном процессе Бурятского и Иркутскою государственных университетов.

Структура и объем работы. Диссертационная работа состоит из четырех глав, в том числе введения, заключения, приложения и списка литературы. Общий объем работы — 95 страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

В §1.2 представлены необходимые сведения о методе редукции2, введены вспомогательные определения и обозначения.

Рассматривается автоматная модель с задержками, состоящая из некоторого множества I взаимодействующих по входам и выходам элементов, которые могут находиться в одном из бинарных состояний, т.е из множества Е — {0,1}. Уравнение динамики модели задается в форме синхронных итераций

х{г + 1) = Р(хЦ - т + 1), х{1 - т + 2),..., х(Ь - 1), х{Ь)), (1М)

где t £ Т = {0,1,2,...}, т — фиксировано и тп € {1,2,3,...}, х = (х1,...,х„) = х{1) €Е X = Еп, п = |/| - количество элементов системы и Р : Епт —> Е71 - векторная функция алгебры логики.

В модели (1М) рассматриваются некоторые динамические свойства, заданные в языке обобщенных позитивно-образованных формул, те. образованных из N (М > 1) т.н. заключительных формул (обычно типа утверждения о принадлежности состояния системы в текущий момент времени

2Васильев С Н К теории редукции в качественном анализе и управлении динамическими системами // Труды Ингсшу1а математики и механики УрО РАН, Екатеринбург, 2004, т 10, №2, с 20-34 Васильев С Н Управление динамикой поведения автоматных сетей с минимальным временем достижения целевых состояний // Труды ХТ Байкальской международной школы-семинара ,тМетоды оптимизации и их приложения", Иркутск, 1998, с 36-47

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

Vxo е х° 3t g т {.x(t, х0) е X* к vt g т : о < t < t x{t, х0) g х1), (Pi)

где N — 2, X* целевое множество, X1 задает фазовые ограничения. Свойство диссипативности относительно X*, равномерной по начальным состояниям хо (N — 2), имеет вид:

3i G T Vxo G Х° (x(t,xо) G X* к \ft' G T : t > t x(t ,xo) G X'). (P2)

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

Для исследования (PI), (P2J и других разнообразных сложных по характеру определения динамических свойств исходной модели (IM), в соответствии с основной идеей метода сравнения и теории редукции, вводится редуцированная модель (в дальнейшем по замыслу она будет с монотонной правой частью)

y(t + 1) = F'iyit-m+l),y(t-m + 2),..., y(t - 1 ),y(t)), (HM)

где t G T = {0,1,2,...}, m фиксировано и m G {1,2,3,...}, y = (Уъ----У к) - y(t) G Y ~ Ek, к = |J|, J = 1, к — множество идентификационных номеров элементов и F' : Ekm —» Ек векторная функция алгебры логики.

В редуцированной системе (НМ) будем интересоваться свойствами, по своей синтаксической структуре и смыслу аналогичными изучаемым свойствам исходной системы (IM). Так, свойство редуцированной модели (НМ), аналогичное (Р1), имеет вид

Vy0 EY°3teT {y{t, уо) G Y' к Vt G T : 0 < t < t y{t, y0) G F1), (Pic) a свойство, аналогичное (P2) —

3t G T Vy0 G У0 (y{t, y0) G Y* к Vt G T : t > t y(t, y0) G Y*). (P2c)

3Бурбаки H Теория множеств — \4 Мир, 1965

Функция v, v : X -> У. называется гомоморфизмом для пары F, F , если для всех xl G X, I = 1,т, выполняется следующее векторное равенство для суперпозиций:

v(F(x\ ..., xm)) = F'ivtf),v(xm)). (H)

При этом заведомо выполняется основное условие редукции в форме тра-екторного гомоморфизма

v(x(t, хо)) - y(t, «(хо)) (Vi G т, х0 е X) (ТН)

и модель (НМ) называется моделью, гомоморфной модели (IM).

Если равенство (ТН) выполняется не для всех моментов времени i G Т, а, например, только до попадания з-(-,х0) в некоторое (целевое) множество, то модель (НМ) называется частично гомоморфной, а функция v частичным траекторным гомоморфизмом.

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

Вторая глава посвящена математическому (§2.1) и алгоритмическому (§2 2) обеспечению программного комплекса РЕДУКТОР/1

В §2.1.1 с использованием понятия покрытия множества состояний автоматной модели (НМ) формулируются и доказываются новые достаточные условия наличия в монотонных моделях свойств (Pic) и (Р2с) Для множества У С Ек и дизъюнктивной нормальной формы (ДНФ) D (одной из возможных) его характеристической функции <ру: множество P(Y) = {У1,..., Ym} называется &изъюнктивным покрытием множества

_ __m _ _ _

Y, если 1)YjÇY для каждого j,j = 1, m, 2) Y = (J Yv 3) все Y3, j - 1, m,

j=i

являются интервалами элементарных конъюнкций, входящих в D. Для монотонных моделей доказана следующая лемма. Лемма 1. В монотонной автоматной модели (НМ) из того, что в некоторый момент времени t G Т верно

Vf0 € Р(У°) ЗУ* G P(Y*)(y(t, mmY°) еГ k y(t,maxY°) G Y*)

следует условие

Vy° G У0 y[t,y°) G Y",

где

maxY0 = (maa:{yi : y G У0}, -.., max{yk : y G У0})

(тггаУ0 понимается аналогично).

Найдены достаточные условия наличия в монотонной автоматной модели свойств (Pic) и (Р2с).

Лемма 2. В монотонной автоматной модели (НМ) из условия существования такого момента времени t > 0, что верно

vy° е P(Y°) [ЗУ* е P(Y*) (y{t, minY0) G У* & & y(t, maxY0) G Y*) к Vt G T : 0 < t < t ЗУ1 6 Р(У!) (Cl) (y{t',minY°) G У1 & y(t ,maxY°) G У1)]

следует наличие свойства (Pic).

Лемма 3. Если в монотонной автоматной модели (НМ) существует момент времени t > 0 такой, что для любого t' > t и любого множества Y0 из Р(У°) существует множество У* из P(Y*), удовлетворяющее условию

y(t,minY°) еГ& y{t,maxY°) G Y",

то в модели (НМ) имеет место свойство (Р2с)

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

Рассматривается следующее динамическое свойство:

Зуо G У0 Vi G T y{t,Уо) € Y*. (РЗс)

Найдены следующие необходимые условия наличия в монотонной системе свойства (РЗс).

Лемма 4. В монотонной автоматной модели (НМ) для наличия свойства (РЗс) необходимо, чтобы было верно

3t G Т УУ° G P(Y°) ЗУ* G P(Ek\Y*) (;y(t, rninY0) G У* & y{t, maxY0) G Y*).

В §2.1.2 формулируются критерии наличия свойств (Р1) и (Р2) в исходной системе. Отмечаются особенности полученных критериев

Теорема 1. Пусть для моделей (IM) и (НМ) выполняются основное условие редукции

Tî =Vxo G Х° Vy0 G У0 : Уо = *>Ы Vi е Т Vx = x(t, Xq) Vy = y{t, уо) y = v(x)

и условия у(Х°) С У0, и(Еп\Х') С Ек\У, у(Еп\Х1) С Ек\У\ Тогда из выполнимости в редуцированной системе (НМ) условия типа (С1) следует наличие свойства (Р1) в исходной системе.

В §2.2.1 вводятся структуры данных для представления автоматов, множеств состояний и траекторий процессов. Структура, задающая произвольный автомат, определяется как список правил переключения состояний элементов системы, каждое из которых представляет собой пару < Ь, Я >, где Ь — левая часть г-го уравнения (по сути, переменная состояния элемента системы), а К — правая часть, представляющая из себя некоторое логическое выражение, составленное из переменных системы, скобок и логических связок: & (конъюнкции), V (дизъюнкции) и -> (отрицания).

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

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

Остальные разделы §2 2 посвящены описанию и обоснованию основных алгоритмов, реализованных в программном комплексе РЕДУКТОР/1.

В §2.2.2 рассмотрен алгоритм построения гомоморфных или частично гомоморфных автоматных моделей (НМ) с монотонными правыми частями и траекторного гомоморфизма V = (и, в, д) модели (1М) в (НМ), где «нетождественные отображения \ц и \Р соответственно множеств управлений и возмущений исходной модели (1М) в соответствующие множества реду цированной модели (НМ). Входом алгоритма является исходная модель

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

1 Положить первую компоненту V = X].

2. Для VI образовать суперпозицию ^ = У\(Е) и уравнение у\[Ь + 1) =

К

3. В правой части уравнения -4- 1) = ^ внести отрицания внутрь скобок.

4. Для всех литер переменных состояния, входящих в правую часть уравнения 1) = Ръ выполнить: если литера совпадает с каким-

и

либо элементом vг из V, то заменить литеру на переменную редуцированной модели уи иначе добавить литеру в список V, образовать суперпозицию Р^ — у,(Р), сформировать новое уравнение уа(1+1) = Ра и заменить рассматриваемую литеру в выражении на уа, где а — индекс добавленного в V элемента.

5. Для последующих, сформированных на шаге 4, уравнений +1) = Р'3 выполнить шаг 4.

Алгоритм заканчивает работу не более, чем за 2п шагов.

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

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

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

Третья глава посвящена проектированию и реализации программ ного комплекса РЕДУКТОР/1.

В §3.1 рассмотрены вопросы проектирования программного комплекса, его структура и основные модули В программном комплексе выделены два слоя- функциональный (§3.1.1) и интерфейсный (§3.1.2).

Функциональный слой програмпого комплекса спроектирован в виде набора компонент (объектов), объединенных в модули по функциональному назначению. При проектировании использовался подход, сходный с проектированием "'сверху-вниз" для объектно-ориептированных языков. В программном комплексе выделены следующие основные объекты: "'автоматы-', "множества состояний"', "процессы", "логические вектор-функции".

Программный комплекс РЕДУКТОР/1 состоит из следующих функциональных блоков (модулей).

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

Транслятор с языка внешнего представления данных (на уровне ин терфейса пользователя) во внутренние структуры данных; при этом производится лексический и синтаксический разбор входных данных.

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

ГПЧУ — генератор правых частей уравнений динамики автоматных моделей.

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

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

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

Реализация основных алгоритмов, а также представление основных структур данных в памяти компьютера рассмотрены в §3 2 1 Вопросы реализации интерфейсной части рассмотрены в §3.2.2, а реализации вспомогательных алгоритмов — в §3.2.3.

Программная реализация комплекса осуществлена на языке Object Pascal, среда разработки - Borland Delphi 6. Комплекс РЕДУКТОР/1 функционирует во всех операционных системах, совместимых с Windows не старое Windows 95, на персональных компьютерах класса IBM AT.

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

К интерфейсу пользователя в процессе создания программного комплекса РЕДУКТОР/1 предъявлялись следующие требования:

• должен быть достаточно простым и просто реализуемым;

• независим от функциональной части программного комплекса;

• представление данных (таких, как автомат, процесс, множество состояний) должно быть естественно.

Данные требования при реализации интерфейса программного комплекса были удовлетворены использованием инструментов быстрой раз-

работки приложений RAD (Rapid Application Development), входящих в состав Borland Delphi.

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

1. Формализация задачи и представление полученной автоматной модели на языке программного комплекса.

2. Упрощение правой части уравнения динамики; введенную на этапе 1 систему можно упростить, используя возможности программного комплекса.

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

4 Синтез редуцированной системы (гомоморфной или частично гомоморфной) с монотонными правыми частями

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

6. Формирование достаточных условий наличия в монотонной автоматной модели исследуемых динамических свойств.

7. Проверка динамического свойства редуцированной монотонной модели или достаточных условий наличия этого свойства в редуцированной

8. Заключение о результате анализа.

С помощью программного комплекса РЕДУКТОР/1 решаются задачи на этапах 2,4,5,7.

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

В §4.1 изучается свойство (PI) автоматной модели 15-го порядка с глубиной памяти m = 3 (сгенерированная псевдослучайным образом при некоторых ограничениях).

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

В программном комплексе РЕДУКТОР/1 имеется возможность компьютерной имитации (назовем это "просмотром") поведения траекторий произвольной системы при различных параметрах. Если под сложностью исследования понимать максимальное количество траекторий, которые необходимо просмотреть для выявления свойства (его отрицания) или проверки достаточных условий (например, условий из лемм 3,4), то в случае анализа свойства (Р1) в исходной системе с указанными множествами начальных состояний и при фиксированной начальной функции сложность просмотра будет равна мощности множества начальных состояний |Х°| = 212 + 213 = 12288.

С использованием возможностей программного комплекса РЕДУКТОР/1 были построены редуцированная система 8-го порядка, частично гомоморфная исходной системе и частичный гомоморфизм. В редуцированной системе рассматривается свойство (Pic) (свойство сравнения), аналогичное по синтаксическому строению и смыслу исходному свойству (Р1).

Далее были получены множества состояний У0, Y* и У1, входящие в определение свойства сравнения, которые обеспечивают выполнимость прочих условий редукции: v{X°) С У0, v(En\X*) Ç Ek\Y*, v(En\Xl) С Ek\Yl, где v — построенный частичный гомоморфизм

Учитывая вид полученных множеств состояний, было установлено, сложность проверки свойства сравнения равна 160, что значительно меньше сложности решения подобной задачи в исходной системе.

Сложность задачи качественного анализа свойства (Pic) в редуцированной системе удалось уменьшить использованием Леммы 2. Проверка достаточных условий, сформулированных в Лемме 2. потребовала просмотра лишь 4 траекторий. В работе приведены эти траектории и показано, что достаточное условие наличия свойства (Pic) в редуцированной системе выполнено, а следовательно, с учетом выполнимости прочих условий редукции в исходной системе имеет место свойство (Р1).

Таким образом, с использованием программного комплекса РЕДУКТОР/1 задача качественного анализа свойства (Р1) в упомянутой исходной системе сведена к значительно более простой задаче проверки условий наличия свойства сравнения в редуцированной системе.

В §4 2 рассматривается известная в литературе простейшая автоматная модель взаимодействия двух экономических районов4, на которой проиллюстрировано применение программного комплекса РЕДУКТОР/1. При

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

этом изучалось свойство (Р2), интерпретированное в некоторых экономических терминах. С помощью программного комплекса был построен гомоморфный автомат, в котором при анализе свойства (Р2с) потребовалось проверить в 8 раз меньше траекторий.

Стоит отметить, что в выполненной программной реализации алгоритма построения редуцированной модели на ПЭВМ Pentium III 1200 Mhz с оперативной памятью 256 Мб достигнута следующая производительность: при размерностях исходной системы -50, 100, 200, 500, 1000 среднее время получения редуцированной модели составило соответственно 1, 5, 15, 115, 500 секунд.

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

Основные результаты диссертации, выносимые на защиту

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

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

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

Благодарности. Автор благодарит чл.-к. РАН Васильева С.Н. за руководство диссертационной работой и помощь в подготовке рукописи.

Публикации по теме диссертации

1. Ульянов С А Пакет программ для анализа автоматных се'1 ей // Тезисы докладов II Школы-семинара молодых ученых "'Математическое моделирование и информационные технологии". — Иркутск. ИДСТУ СО РАН. 2002. - С 30-31

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

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

4. Ульянов С.А. Программный комплекс для анализа свойств автоматных сетей // Материалы Всероссийской конференции "йнфокомму-никационные и вычислительные технологии и системы" - Улан-Удэ: Из-во Бурятского государственного университета, 2003 - Ч. II — С. 95-99.

5 Ульянов С А Программная компонента для качественного анализа автоматных сетей // Тезисы докладов IV Школы-семинара молодых ученых "Математическое моделирование и информационные технологии- управление, искусственный интеллект, прикладное программное обеспечение и технологии программирования". - Иркутск. ИДСТУ СО РАН, 2005 С 34-35

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

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

Все результаты, включенные в диссертацию, принадлежат лично автору.

2.

V

3.

It

Редакционпо-издательский отдел Института динамики систем и теории управления СО РАН 664033, г. Иркутск, ул. Лермонтова, 134.

Подписано к печати 9.06.2005. Формат бумаги 60x84 1/16, объем 1,1 п.л. Заказ 6. Тираж 100 экз.

Отпечатано в ИДСТУ СО РАН.

IM361 f

РНБ Русский фонд

2006-4 9739

?

»

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

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

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

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.