Содержание к диссертации
Введение
1 Введение 5
1.1 Актуальность задачи качественного исследования автоматных моделей и предмет диссертации 5
1.2 Основные определения и обозначения 8
1.3 Цели и структура работы 13
1.4 Научная новизна, практическая значимость и апробация полученных результатов 15
2 Теоретическое и алгоритмическое обеспечение программного комплекса редуктор 17
2.1 Критерии наличия в монотонной модели некоторых динамических свойств 17
2.2 Теоремы редукции 22
2.3 Алгоритмическое обеспечение программного комплекса 23
2.3.1 Основные структуры данных 25
2.3.2 Алгоритм построения гомоморфизмов и синтеза гомоморфных автоматов 28
2.3.3 Алгоритм построения множеств состояний редуцированной системы 33
2.3.4 Алгоритмы вычисления операций над множествами . 37
2.3.5 Алгоритм упрощения логических выражений 40
3 Реализация программного комплекса 46
3.1 Структура программного комплекса 47
3.1.1 Функциональная часть 48
3.1.2 Интерфейсная часть 56
3.2 Реализация программного комплекса 59
3.2.1 Реализация основных алгоритмов 61
3.2.2 Реализация программного интерфейса 62
3.2.3 Реализация вспомогательных алгоритмов 65
3.3 Методика использования 66
4 Применения программного комплекса 69
4.1 Анализ автоматной модели общего вида 69
4.2 Исследование простой автоматной модели экономического взаимодействия 77
Литература 89
- Научная новизна, практическая значимость и апробация полученных результатов
- Алгоритм построения гомоморфизмов и синтеза гомоморфных автоматов
- Реализация программного комплекса
- Исследование простой автоматной модели экономического взаимодействия
Введение к работе
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, именуемых функциями сравнения и ответственных за переносимость свойства из системы сравнения (свойства сравнения) в исходную систему. Типичным условием, определяющим это отображение, является условие типа покомпонентного мажорирования v(x(t)) < xc{t) значений этой (вообще говоря, векторной) функции вдоль процессов x(t) изучаемой системы вектором состояния xc(t) соответствующих процессов системы сравнения в тот же момент времени t.
Использование точных оценок (равенств вместо неравенств) превращает эти функции в отображения типа гомоморфизма (переводящего траектории в траектории) и позволяет существенно смягчить прочие условия, накладываемые на г> с учетом уже специфики конкретного изучаемо-
го свойства, хотя удовлетворить указанным оценкам в форме неравенства проще. В зависимости от специфики изучаемых свойств условие типа гомоморфизма может варьироваться дополнительно. Например, при изучении свойств типа достижимости (управляемости) равенство v(x(t)) = xc(t) достаточно требовать только до первого момента попадания х(t) в целевое множество (при этом v называется частичным гомоморфизмом). Сказанное переводит рассмотрение в сферу применимости так называемого метода редукций [6, 7, 9], где вспомогательные функции г; и системы рассматриваются в более широких классах и именуются редукторами и редуцированными моделями соответственно. При этом основное условие, накладываемое на них (условие мажорирования, условие гомоморфизма и т.п.), в отличие от прочих условий, будем называть основным условием редукции.
В настоящее время для логико-динамических моделей автоматного типа предложено несколько конструктивных алгоритмов построения редукторов [9, 50], с использованием которых проведен анализ различных динамических свойств.
Сложность исследования логико-динамических моделей автоматного типа может быть уменьшена не только использованием редукторов, но и применением алгоритмов и методов минимизации логических функций, например, в классе дизъюнктивных нормальных форм (ДНФ). В большинстве известных на сегодняшний день алгоритмах минимизации ДНФ выделяют два этапа [43]: порождение простых импликант и решение задачи поиска минимального покрытия. Первый этап соответствует построению сокращенной ДНФ, а второй — минимальной. Стоит отметить, что задача поиска минимального покрытия является NP-полной и для ее решения не существует эффективных алгоритмов [53].
Одним из классических алгоритмов минимизации логических функций является алгоритм Квайна-Мак-Класски (Quine-McCluskey) [51, 52].
Этот алгоритм может и довольно эффективно решать задачу порождения простых импликант. Тем не менее, современные, основанные на эвристиках алгоритмы (например, [43, 47]), позволяют существенно повысить эффективность решения задачи минимизации (в том числе задачи порождения простых импликант) по сравнению с алгоритмом Квайна-Мак-Класски.
Работа посвящена алгоритмизации и разработке программного комплекса, автоматизирующего этапы качественного исследования разнообразных сложных динамических свойств логико-динамических систем автоматного типа на основе метода редукции.
1.2. Основные определения и обозначения
Объектом исследования в данной работе является бинарный автомат (т.е. автомат логического типа) с задержками, состоящий из некоторого множества / взаимодействующих по входам и выходам элементов, которые могут находиться в одном из бинарных состояний, т.е. из множества Е = {0,1}. Уравнение динамики соответствующей модели с задержками, заданное в форме синхронных итераций [8], имеет вид
x(t + 1) = F{x{t - т + 1), x{t - т + 2),..., x{t - 1), x(t)), (1.1)
где t Є Т = {0,1,2,...}, m — фиксировано и m Є {1,2,3,...}, х = (xi,...,xn) = x(t) X = Еп, п = \І\ — количество элементов системы и F : Ептп -> En — векторная функция алгебры логики. Система (1.1) имеет задержки, т.е. состояние в момент времени t + 1 зависит от состояний элементов в предыдущие моменты времени на некоторую глубину памяти т. В соответствии с [45] такие модели называют автоматными сетями или автоматами, состоящими из элементов [31].
Очевидно, что если в (1.1) заданы значения x-m+1 = х(—m + 1),...,х-1 = х(—1),х = а:(0) из множества X, то в модели (1.1) функ-
ция F = (Ft,..., Fn) определяет и притом единственным образом процесс х : Т —> X. При этом произвольно заданная "начальная" функция (начальный процесс) хиач : {—га + 1,..., -1} -> X как бы расширяет область определения процесса х : Т -> X до множества D = {—га +1,..., — 1} U Т, определяя вместе с (1.1) "надпроцесс" х : D —> X. Далее, если не указано другого, мы будем считать начальную функцию хная произвольной, но фиксированной, варьируя только начальное состояние хо-
Некоторые результаты, представленные в работе, в частности алгоритмы построения редуцированных моделей, относятся к более общей модели
x{t + 1) = F(x(t -m + l),x{t-m +2),...,x(t- 1), x(t), u{t),p{t)),
щеи = (и1,...,и1) = u(t) Є U, U СЕ1, р = (рь...,р,) =p(t) ЄР, PC Eq, a F : Enm xU x P —> En — векторная функция алгебры логики. Через U и Р обозначются соответственно множества допустимых управлений и возмущеий.
Определение 1.1 [8] Автоматная модель (1.1) с глубиной памяти га называется монотонной, если монотонна функция F, т.е.
(Vx,x Є пш : Vz = ї~йгахг- < 5) Р(х) < Р(х),
где отношение < на Еп понимается как покомпонентное отношение нестрогого порядка < на Е.
В системе (1.1) будем рассматривать различные динамические свойства, заданные относительно различных множеств состояний (например, множеств целевых X* и начальных Х состояний) и моментов времени.
Наиболее удобно динамические свойства задавать на языке обобщенных позитивно-образованных формул Р [13], основными синтаксическими элементами которого являются заключительные формулы Р\,...,Р^
(N > 1), так называемые типовые кванторы [4] (ТК) всеобщности tuQ = \fza(Za —> _) и существования rt)Q = 3za(Zak__), а также логические связки V и &. Как правило, в качестве заключительных формул выступают простые утверждения, например, о принадлежности состояния системы в текущий момент времени некоторому оценочному множеству. Выражение Za в записи ТК, ограничивающее область изменения переменной za, называется типовым условием, а переменная za — операторной переменной квантора toa (или tua). Число N называется степенью свойства.
Заметим, что в отличие от позитивно-образованных формул из [11] части Pq, Za обобщенной позитивно-образованной формулы Р не обязаны быть конъюнкциями атомов первопорядкового языка или константными предикатами True, False и даже могут быть естественно-языковыми выражениями (вставками в частично-формализованный текст Р), но с эф-фективновыделяемыми вхождениями в Pq или Za всех "индивидных" переменных, позволяющих рассматривать Pq или Za как атомы с соответствующими наборами аргументов. Позитивно-образованные формулы [11] обобщают, в свою очередь, понятие позитивных формул логики первого порядка (см., например, [27]).
Пример 1.1 Свойство достижимости целевого множества X* из некоторого множества начальных состояний Х при фазовых ограничениях Xі (степень свойства N = 2) на языке позитивно-образованных формул запишется
Vx0GX 3teT (я(*,хо) еГ к
к \ft eT:0
Пример 1.2 Другое свойство второй степени — свойство диссипативности относительно X*, равномерной по начальным состояниям хо — на языке
позитивно-образованных формул примет вид З* Є Т Vx0 Є Х (ж(*,хо) ЄХ* &Vt eT:t >t x{t\x0) Є X*). (1.3)
В дальнейшем язык обобщенных позитивно-образованных формул будем использовать не только для представления определений динамических свойств, но и для всех вводимых далее в работе условий. Уместно также заметить, что язык обобщенных позитивно-образованных формул особенно полезен при использовании алгоритмов вывода теорем о переносимости свойств из вспомогательных моделей в изучаемые (см., например [16]).
Для исследования (1.2), (1.3) и других разнообразных сложных по характеру определения динамических свойств исходной модели (1.1), в соответствии с основной идеей метода сравнения и теории редукции, введем вторую (редуцированную) модель (в дальнейшем по замыслу она будет с монотонной правой частью)
y(t + l) = F'{y(t-m + l),y{t-m + 2),...,y(t-l),y(t)), (1.4)
где t Є Т = {0,1,2,...}, га — фиксировано и га Є {1,2,3,...}, у = (уь---зУА;) = y{t) Є Y = Ек, к = \J\, J = 1, к — множество идентификационных номеров элементов и Ґ : Ект -> Ек — векторная функция алгебры логики.
В редуцированной системе (1.4) будем интересоваться свойствами, по своей синтаксической структуре и смыслу аналогичными изучаемым свойствам исходной системы (1.1). Так свойство аналогичное (1.2) в редуцированной модели запишется как
VyoGY0 3teT (y(t,y0)eY* &
(1.5) & \ft Є T : 0 < t < t y{t\y0) Є Г1),
а свойство аналогичное (1.3) —
3t Є T Vy0 Є Y (у(*,уо) Є Y* к Vt Є Т :t > t y(t',yQ) Є Г*). (1.6)
Определение 1.2 Функция v, v : X -» Y, называется гомоморфизмом для пары F, F [8], если для всех х1 Є X, I = 1, m, выполняется следующее векторное равенство для суперпозиций
u(F(x\ ..., хта)) = FXx1),..., v(xm)). (1.7)
При этом заведомо выполняется основное условие редукции в форме траєкторного гомоморфизма
v(x(t, х0)) = y(i, и(хо)) (V* Є Т, хо Є X) (1.8)
и модель (1.4) называется моделью, гомоморфной модели (1.1).
Определение 1.3 Если равенство (1.8) выполняется не для всех моментов времени t Є Т, а, например, только до попадания ж(-,х) в некоторое (целевое) множество, то модель (1.1) называется частично гомоморфной, а функция v частичным траєкторним гомоморфизмом [8].
Для монотонной модели верно следующее утверждение [8].
Лемма 1.1 Если правая часть F уравнения (1.4) монотонна, то
(Vy, у0 Є Ekm : Vt = ЇМ у? < у?) y(t, у0) < y(t, у0).
Из леммы 1.1 вытекает следующее утверждение [8].
Лемма 1.2 Если система (1.4) монотонна и обладает свойством типа выпуклости множества Y* С Ек
Vy, у" Є F*(Vy Є Ек : у < у < у") у Є Y\ (1.9)
то (при фиксированной начальной функции унач : {—т +1,..., —1} —> Е1^) из того, что в некоторый момент t Є Т справедливо включение
{у(*, штУ), у(*, таяУ0)} С Y* (1.10)
следует
VyeYy(ty)eY\ (1.11)
maxY0 = (max{yi : у Є У0},..., тах{ук : у Є У0})
(minY0 понимается аналогично).
Использование леммы 1.2 может значительно снижать сложность качественного исследования редуцированной автоматной модели рассмотрением лишь двух траекторий, выпущенных из "минимального" (minY0) и "максимального" (maxY0) векторов начальных состояний вместо перебора всех траекторий, которые соответствуют полному множеству начальных состояний (заметим, что при этом вектора minY0, maxY0 не обязательно принадлежат множеству У0). Однако применение этой леммы ограничено наличием требования (1.9) (типа выпуклости целевого множества У*). Подход, с помощью которого снимается это требование, предложен в разделе 2.1.
1.3. Цели и структура работы
Основной целью данной работы является алгоритмизация и разработка программного комплекса, автоматизирующего этапы качественного исследования автоматных моделей с применением гоморфизмов. Решаются задачи алгоритмизации и автоматизации:
построения вспомогательных (гомоморфных) автоматных моделей с монотонными правыми частями (удовлетворяющих условию связи с равенством);
выбора множеств, входящих в определение свойства сравнения, по критерию облегчения его выполнимости;
проверки свойства сравнения в монотонных автоматных моделях с задержками;
проверки прочих условий переносимости свойства;
имитационного моделирования и визуализации динамики для тестирования алгоритмов на этапе разработки, построения наглядных примеров, использования в процессе обучения пользованию программным комплексом и прочее.
Структура работы. Диссертация состоит из четырех глав, первая из которых (настоящая) является вводной, а также заключения и приложения. Глава 2 посвящена математическому (2.1) и алгоритмическому (2.2) обеспечению программного комплекса РЕДУКТОР/1. В 2.1.1 с использованием понятия покрытия множества состояний автоматной модели формулируются и доказываются новые достаточные условия наличия в монотонных моделях свойств типа достижимости и диссипативности, а в 2.1.2 рассматриваются критерии наличия в исходных (немонотонных) моделях этих свойств. В 2.2.1 вводятся структуры данных для представления автоматов, множеств состояний и траекторий процессов. Остальные разделы 2.2 посвящены описанию и обоснованию алгоритмов. Конкретно, в 2.2.2 рассмотривается алгоритм построения гомоморфных или частично гомоморфных автоматных моделей, в 2.2.3 описывается алгоритм построения множеств состояний, входящих в определение свойства редуцированной системы, в 2.2.4 — алгоритмы, реализующие различные операции над множествами состояний и их характеристическими функциями, а также проверки теоретико-множественных включений, в 2.2.5 — алгоритм построения сокращенной ДНФ, который используется для упрощения правых частей уравнений динамики и удаления из множеств состояний избыточных элементов.
Научная новизна, практическая значимость и апробация полученных результатов
Использование леммы 1.2 может значительно снижать сложность качественного исследования редуцированной автоматной модели рассмотрением лишь двух траекторий, выпущенных из "минимального" (minY0) и "максимального" (maxY0) векторов начальных состояний вместо перебора всех траекторий, которые соответствуют полному множеству начальных состояний (заметим, что при этом вектора minY0, maxY0 не обязательно принадлежат множеству У0). Однако применение этой леммы ограничено наличием требования (1.9) (типа выпуклости целевого множества У ). Подход, с помощью которого снимается это требование, предложен в разделе 2.1.
Основной целью данной работы является алгоритмизация и разработка программного комплекса, автоматизирующего этапы качественного исследования автоматных моделей с применением гоморфизмов. Решаются задачи алгоритмизации и автоматизации: построения вспомогательных (гомоморфных) автоматных моделей с монотонными правыми частями (удовлетворяющих условию связи с равенством); выбора множеств, входящих в определение свойства сравнения, по критерию облегчения его выполнимости; проверки свойства сравнения в монотонных автоматных моделях с задержками; проверки прочих условий переносимости свойства; имитационного моделирования и визуализации динамики для тестирования алгоритмов на этапе разработки, построения наглядных примеров, использования в процессе обучения пользованию программным комплексом и прочее.
Структура работы. Диссертация состоит из четырех глав, первая из которых (настоящая) является вводной, а также заключения и приложения. Глава 2 посвящена математическому (2.1) и алгоритмическому (2.2) обеспечению программного комплекса РЕДУКТОР/1. В 2.1.1 с использованием понятия покрытия множества состояний автоматной модели формулируются и доказываются новые достаточные условия наличия в монотонных моделях свойств типа достижимости и диссипативности, а в 2.1.2 рассматриваются критерии наличия в исходных (немонотонных) моделях этих свойств. В 2.2.1 вводятся структуры данных для представления автоматов, множеств состояний и траекторий процессов. Остальные разделы 2.2 посвящены описанию и обоснованию алгоритмов. Конкретно, в 2.2.2 рассмотривается алгоритм построения гомоморфных или частично гомоморфных автоматных моделей, в 2.2.3 описывается алгоритм построения множеств состояний, входящих в определение свойства редуцированной системы, в 2.2.4 — алгоритмы, реализующие различные операции над множествами состояний и их характеристическими функциями, а также проверки теоретико-множественных включений, в 2.2.5 — алгоритм построения сокращенной ДНФ, который используется для упрощения правых частей уравнений динамики и удаления из множеств состояний избыточных элементов. Глава 3 посвящена проектированию и реализации программного комплекса РЕДУКТОР/1. В 3.1 рассматриваются вопросы проектирования программного комплекса, его структура и основные модули. Реализация основных алгоритмов, а также представление основных структур данных в памяти компьютера описывается в 3.2.1. Вопросы реализации интерфейсной части рассмотриваются в 3.2.2, а реализации вспомогательных алгоритмов — в 3.2.3. Методика использования программного комплекса описана в 3.4.
Глава 4 посвящена применениям программного комплекса в качественном анализе некоторых логико-динамических моделей автоматного типа. В 4.1 изучается свойство достижимости целевого множества из некоторого множества начальных состояний при фазовых ограничениях автоматной модели 15-го порядка с глубиной памяти т — 3, сгенерированной псевдослучайным образом при некоторых ограничениях. В 4.2 рассматривается известная в литературе простейшая автоматная модель взаимодействия двух экономических районов, на которой проиллюстрировано применение программного комплекса РЕДУКТОР/1. В заключении приводится перечень результатов, выносимых на защиту.Приложение сождержит описание грамматики входного языка.
В диссертационной работе предложены и оформлены в виде единого программного комплекса новые алгоритмы качественного анализа динамики автоматных моделей на базе построения и исследования гомоморфных монотонных автоматов и проверки условий переносимости свойств. Для некоторых динамических свойств сформулированы критерии их наличия, получены леммы, значительно упрощающие анализ этих свойств в монотонных вспомогательных моделях. Разработана методология использования созданного программного комплекса при анализе динамических свойств автоматных моделей.
Результаты, представленные в работе, позволяют автоматизировать и повысить эффективность исследований в области качественного исследования динамики автоматных моделей. Кроме того, имеется возможность использования разработанного программного средства при обучении и решении практических задач качественного анализа.
Алгоритм построения гомоморфизмов и синтеза гомоморфных автоматов
С архитектурной точки зрения в программном комплексе РЕДУКТОР/1 условно можно выделить два слоя: функциональный, в котором реализованы алгоритмы и структуры данных для решения задач анализа и синтеза автоматных моделей, описанные в Главе 2, и интерфейсный, осуществляющий взаимодействие между пользователем программного комплекса и функциональным слоем. Данное разделение представляется естественным и позволяет в каждом слое придерживаться своего стиля программирования и, соответственно, использовать свои методы проектирования. Кроме того, данное разделение позволяет использовать реализованные структуры данных, процедуры и функции при создании подобных программных систем.
Функциональный слой программного комплекса спроектирован в виде набора компонент (объектов), объединенных в модули по функциональному назначению. При проектировании программного комплекса используется подход, сходный с проектированием "сверху-вниз" для объектно-ориентированных языков в соответствии с методом из [2], но с учетом реализации на языке Паскаль без использования объектных расширений языка.
Использованная технология проектирования функционального слоя, называемая "технологией проектирования на основе ответственности" [2], представляет программу в виде компонент, взаимодействующих друг с другом через посылку сообщений. Компонента программной системы определяется некоторой структурой данных языка Паскаль и набором процедур и функций, меняющих состояние этой структуры. Такой набор процедур функций реализует поведение компоненты. Компоненты взаимодействуют друг с другом через посылку сообщений, результатом выполнения которой является некоторый ответ, который в некоторых случаях интерпретируется как структура некоторой другой компоненты. Посылка сообщения компоненте — это передача управления процедуре, реализующей это сообщение и принадлежащей этой компоненте. Набор компонент, осуществляющих одну общую функцию, формирует функциональный блок, представимый нами как программный модуль.
Качество модульности программы определяется двумя параметрами: связностью — степенью сцепления различных методов друг с другом внутри компоненты и зацеплением — степенью сложности взаимодействия между компонентами и модулями. Оптимально модульная программа должна быть одновременно сильно связной и иметь слабое зацепление, при этом обеспечивая возможность и удобство модификации и дальнейшего совершенствования. Проектирование функционального слоя программного комплекса РЕДУКТОР/1 выполнялось в условиях контроля над оптимальностью параметров, характеризующих качество модульности разрабатываемого слоя программной системы.
Проектирование вышеописанным образом позволило разбить функциональную часть программного комплекса на следующие компоненты: "автоматы", "множества состояний", "процессы", "логические вектор-функции" (гомоморфизмы).
Стоит отметить, что процедуры и структуры данных, разработанные на языке "Паскаль" без использования объектных расширений, предста-вимы в виде набора методов и компонент, не нарушая общего принципа проектирования программной системы "как можно ближе к ООП". В связи с этим вполне оправдано будет использование вместо термина "структура данных" термин "класс" или "компонент", а вместо термина "процедура" — "метод" в том понимании, в котором мы их понимаем в ООП. Во избежание путаницы далее будем использовать термины "класс" и "метод".
Приближение к ООП сделало возможным при проектировании программной системы использование унифицированного языка моделирования программных систем UML (Unified Modeling Language) [5], который является удобным графическим языком для визуализации, спецификации, конструирования и документирования систем. На рис. 3.1 с использованием языка UML представлена диаграмма классов реализованного программного комплекса. Диаграммой классов в языке UML называют диаграмму, на которой показано множество классов и отношений между ними. В диаграмме используются 3 вида отношений: зависимости, которые описывают существующие между классами отношения использования; обобщения, связывающие обобщенные классы со специализированными.
Реализация программного комплекса
Таким образом, с одной стороны опыт, приобретенный при построении объектно-ориентированных программ, оказался полезным при проектировании систем на процедурно-функциональном языке программирования. Результатом такого подхода к проектированию являются не только достаточно хороший дизайн программной системы, но и высокое быстродействие, вследствие отказа от ООП-расширений языка Паскаль, и возможность использования такого мощного инструмента для моделирования и проектирования объектно-ориентированных систем, как язык UML.
С другой стороны, вследствие модульности реализации системы РЕДУКТОР/1 есть возможность без значительных временных затрат и без кардинального переписывания кода добавлять новые реализации алгоритмов теории редукции, используя уже имеющиеся структуры данных и простейшие подпрограммы для работы с этими структурами, или использовать разработанные модули при проектировании и реализации других проектов в области автоматных сетей.
К интерфейсу пользователя в процессе создания программного комплекса РЕДУКТОР/1 предъявлялись следующие требования: должен быть достаточно прост; независим от функциональной части программного комплекса; представление данных, таких как автомат, процесс, множество состояний, должно быть естественно; время на написание интерфейса должно составлять незначительную часть от общего времени реализации системы, что дает разработчику сосредоточиться на реализации функциональной части системы. Как известно немаловажной составляющей любого программного продукта является интерфейс, с помощью которого пользователь общается с программой для решения своих задач. Действительно, именно интерфейс создает первое впечатление о программной системе, и именно его простота и понятность привлекает пользователя. Немаловажную роль играет и то, насколько интерфейс соответствует общепринятым стандартам. Данные требования при реализации программного комплекса были удовлетворены использованием инструментов быстрой разработки приложений RAD Rapid Application Development [17]. RAD - это комплект специальных инструментальных средств быстрой разработки прикладного программного обеспечения, позволяющих оперировать с определенным набором графических объектов, функционально отображающих отдельные информационные компоненты приложений. Средства RAD дали возможность реализовать совершенно иную технологию создания приложений: информационные объекты формируются как некие действующие модели (прототипы), чье функционирование согласовывается с пользователем, а затем разработчик может переходить непосредственно к формированию законченных приложений, не теряя из виду общей картины проектируемой системы.
Подобное свойство инструментов RAD появилось как результат объектно-ориентированного подхода. Объектно-ориентированное программирование реально возникло тогда, когда было обеспечено слияние (инкапсуляция) данных с процедурами, описывающими поведение реальных объектов, в объекты программ, которые могут быть отображены определенным образом в графической пользовательской среде. Это позволило приступить к созданию программных систем, максимально похожих на реальные, и добиваться наивысшего уровня абстракции. В свою очередь, объектно-ориентированное программирование позволяет создавать более надежные коды, так как у объектов программ существует точно определенный и жестко контролируемый интерфейс.
Разработка приложений с помощью инструментов RAD ведется на основе использования множества готовых объектов, сохраняемых в общедоступном хранилище. При этом важно, чтобы инструменты RAD в полной мере были объектно-ориентированными, что становится возможным тогда, когда используемый для их написания язык программирования сам является объектно-ориентированным.
Объектно-ориентированные инструменты RAD в среде графического пользовательского интерфейса GUI (Graphic User Interface) позволяют на основе стандартных классов объектов, для которых инкапсулированы атрибуты и внутренние процедуры, формировать простые приложения без написания кода программы. Это составляет первое преимущество RAD, так как теперь даже конечный пользователь может создавать приложения, предназначенные для решения собственных задач. Объектная ориентация инструментов RAD позволяет самим разработчикам сосредоточиться на сущности задачи. Это в итоге не может не повлиять на качество отображения моделируемых условий функционирования системы и требований пользователей в создаваемых прототипах и приложениях.
С активным распространением системы Windows и появлением визуальных RAD-сред широкую популярность приобрел событийный подход к созданию программ - событийно-ориентированное программирование. Выбор пункта меню, нажатие на кнопку мыши и т.д. генерирует событие — подходящее сообщение, отсылаемое окну соответствующей событийно-ориентированной программы, главная часть которой представляет один бесконечный цикл, опрашивающий операционную систему, не появилось ли новое сообщение. При его обнаружении вызывается подпрограмма, ответственная за обработку соответствующего события (обрабатываются не все события, их сотни, а только нужные), и подобный цикл опроса продолжается до тех пор, пока не будет получено сообщение "Завершить работу". События могут быть пользовательскими, возникшими в результате действий пользователя, системными, возникающими в операционной системе (например, сообщениями от таймера), и программными, генерируемыми самой программой (например, обнаружена ошибка, и ее надо обработать). Событийное программирование является развитием идей нисходящего проектирования, когда постепенно определяются и детализируются реакции программы на различные события. В настоящее время существует довольно много RAD-сред на основе различных популярных языков программирования (например, Паскаль, С), которые предлагают мощные и удобные средства для редактирования, компиляции и отладки программ, большое количество визуальных компонент. Интерфейс пользователя программного комплексе РЕДУКТОР/1 реализован с использование большинства возможностей RAD-технологии.
Исследование простой автоматной модели экономического взаимодействия
Множества v(X), v(X ) и v(X ) приведены с учетом сужения и удаления избыточных (дублированных) состояний. Сужение множеств было произведено для обеспечения выполнимости условий теоремы редукции 2.1. Легко проверить, что при построенных множествах условия теоремы сравнения 2.1 верны.
Коль скоро условия редукции для свойства достижимости при фазовых ограничениях выполнены, то в соответствии с теоремой 2.1 для заключения о наличии исследуемого свойства (1.2) в исходной системе (4.1), необходимо выявить свойство сравнения (1.5) в редуцированной системе (4.2). Сложность этой задачи довольно высока — требуется просмотреть 160 траекторий, хотя она значительно меньше, чем сложность решения подобной задачи в исходной системе.
Так как система (4.2) по построению монотонна, то можно воспользоваться леммой 2.2 и еще снизить сложность задачи. Для этого вместо выявления свойства (1.5) необходимо проверить условие вида, которое является достаточным для наличия свойства (1.5) в системе (4.2). Найдем покрытия множеств У0, Y и У1, входящие в (4.4). В силу того, что любое множество состояний автоматной модели мы можем записать в виде ДНФ его характеристической функции, эта задача довольно проста, так как каждому элементу покрытия в этом случае будет соответствовать элементарная конъюнкция. Пусть В соответствии с полученными покрытиями для того, чтобы проверить условие (4.4), необходимо просмотреть лишь четыре траектории: выпущенные из минимального minY и максимального maxY векторов первого элемента покрытия множества У0 и выпущенные из минимального minY и максимального maxY векторов второго элемента покрытия множества У0. Эти траектории приведены, соответственно, в таблицах 4.1-4.42.
Из приведенных таблиц видно, что в момент времени t = 7 все четыре траектории одновременно попали в множество У2 э следовательно, первая часть условия (4.4) верна. Вторую часть условия (4.4) необходимо проверять отдельно для каждой пары траекторий, выпущенных из одного и того же множества (или из У]0 или из У2)- Рассмотрим, например, траектории, выпущенные из minYi и maxY. Эти траектории в отрезок времени [0, 2] одновременно находятся в множестве Yi, а, начиная с момента времени t = 3, до попадания в целевое множество (t — 7), одновременно лежат в множествах Х\ и Х\, следовательно, для элемента покрытия Y условие верно.
Аналогично рассматривается пара траекторий, выпущенных из minY и maxY. Как нетрудно заметить, во все моменты времени t О до момента попадания в целевое множество найдется множество, принадлежащее покрытию Р(У01), что обе траектории будут находиться в этом множестве. Следовательно, с учетом вышесказанного относительно траекторий, выпущенных из У]0, можно заключить, что условие (4.4) верно при найденных покрытиях Р(Х), Р(Х ) и Р(Х1). Отсюда и из леммы 2.2 следует, что во редуцированной системе имеет место свойства (1.5), а, значит, по теореме 2.1 (так как верны условия сохранимости свойства) в исходной системе имеет свойство (1.2).
Рассмотренный пример демонстрирует эффективность реализованных в программном комплексе РЕДУКТОР/1 алгоритмов метода редукции и довольно полную автоматизацию этапов задачи качественного исследования. Используя возможности программного комплекса, мы редуцировали сложность задачи анализа свойства (1.2) в системе (4.1) размерности равной 15, где для выявления исходного свойства требовалось просмотреть 12288 траектории, переходом к задаче анализа свойства сравнения (1.5) в более простой системе (4.2) гомоморфной (4.1), где проверка достаточного условия наличия в редуцированной системе свойства сравнения требовала просмотра лишь 4 траекторий. При этом отметим, что размерность построенной гомоморфной системы значительно меньше (равна 8), а правые части проще (сложность системы равна 4), чем в исходной системе.
Пусть Pi и Рг экономические районы, связанные друг с другом и не имеющие внешних связей. Характерными для них будем считать три типа состояний: развитие, стагнации и регрессии. Предположим, что у Pi имеется три вида состояний типа развития: +, +ь +2 (при этом будем считать, что первое из них более "сильное", чем второе и второе более "сильное", чем третье); одно состояние стагнации о (оно слабее любого из состояний развития) и одно состояние регрессии — (самое слабое состояние). У Рг имеется одно состояние развития +, одно состояние стагнации о и одно состояние регрессии — (здесь допущения относительно их "силы" аналогичны указанным выше). Будем считать, что логика изменения состояний рассматриваемых районов во времени имитируется автоматами Мура. Входом автоматов является состояние соседнего района, а выход в качестве значений принимает значение своего текущего состояния. Диаграммы переходов автоматов для районов Pi и Рг представлены, соответственно, на рис. 4.2 и 4.3.
Похожие диссертации на Алгоритмы и программный комплекс для анализа логико-динамических моделей автоматного типа
