close

Вход

Забыли?

вход по аккаунту

?

MixailovMarley

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
В. В. Михайлов, В. Е. Марлей, О. Ф. Королев
АЛГОРИТМИЧЕСКИЕ СЕТИ И ИХ ПРИМЕНЕНИЕ
Учебное пособие 2-е издание, дополненное
Санкт-Петербург 2012
УДК 004.414.23(075)
ББК 32.973
М69
Рецензенты:
заведующий кафедрой информационных систем и программного обеспечения РГПУ им. А. И. Герцена доктор физико-математических наук, профессор А. В. Флегонтов;
кафедра вычислительных систем и информатики Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Государственный университет морского и речного флота им. адмирала С. О. Макарова»
Утверждено редакционно-издательским советом университета в качестве учебного пособия
Михайлов В. В., Марлей В. Е., Королев О. Ф.
М69 Алгоритмические сети и их применение: учеб. пособие /
В. В. Михайлов, В. Е. Марлей, О. Ф. Королев. 2-е изд., доп. – СПб.:
СПбГУАП, 2012. – 136 с.: ил.
ISBN 978-5-8088-0794-5
Излагаются элементы теории скалярных и матричных алгоритмических сетей, рассматриваются операции над сетями и алгебра
сетей. Приводятся процедуры взаимного согласования алгоритмических сетей. Рассматривается формализация графического ввода
сетей. Описываются версии систем автоматизации моделирования,
построенные на основе формализма алгоритмических сетей, приводятся примеры моделей, построенных в системе КОГНИТРОН-4.0.
Учебное пособие предназначено для студентов, изучающих курсы прикладной и дискретной математики, математического моделирования. Пособие может быть полезным аспирантам и преподавателям, занимающимся теоретическими и прикладными проблемами
компьютерного моделирования.
УДК 004.414.23(075)
ББК 32.973
ISBN 978-5-8088-0794-5
© Санкт-Петербургский государственный университет аэрокосмического приборостроения (ГУАП), 2012
© В. В. Михайлов, В. Е. Марлей,
О. Ф. Королев, 2012
ВВЕДЕНИЕ
В настоящее время в математическом моделировании развиваются два равноправных взаимодополняющих направления. Первое
направление основывается на технологии вычислительного эксперимента в трактовке А. А. Самарского – новой технологии научных
исследований, направленной на создание «фундаментальных моделей» как новых парадигм науки. Подход предполагает чрезвычайно высокую математическую подготовку главных участников и
жесткое разделение труда между ними и специалистами предметной области, в задачи которых входит подготовка исходных данных, определение граничных условий, определение сценариев проводимых экспериментов и обсуждение результатов. Технология
вычислительного эксперимента, основанная на триаде «модель–
алгоритм–программа», не рассчитана на массовое внедрение в повседневную работу конечных пользователей, которые лишь опосредованно участвуют в разработке моделей.
Второе направление названо Г. С. Поспеловым новой информационной технологией моделирования и ориентировано на конечного пользователя как на непосредственного разработчика модели
[1]. Основной упор здесь делается на создание удобных и достаточно простых языков представления моделей, доступных для непрограммирующего пользователя, и инструментальных средств с элементами искусственного интеллекта, обеспечивающих поддержку
в разработке моделей, выборе численного метода решения, автоматизации синтеза расчетной программы, организации интерфейса.
Это направление рассчитано на внедрение методов моделирования
в среду неподготовленных конечных пользователей и позволяет исключить программиста, а в некоторых случаях – системного аналитика, при реализации вычислительного эксперимента.
Проблема снижения барьера между пользователем и ЭВМ началась сразу же, как появилась ЭВМ, остается актуальной в настоящее время и формулируется как задача разработки дружественного интерфейса. Одним из путей ее решения является использование
графического представления, поскольку оно отличается наглядностью, позволяет в ряде случаев снизить требования к подготовке пользователей и реально уменьшить барьер между человеком
и ЭВМ. Разрабатывались и разрабатываются все новые средства
графического представления алгоритмов, программных спецификаций, моделей. К таким средствам относятся сети Петри, семантические сети, граф-схемы алгоритмов, информационные графы,
3
сети ограничений, case-технологии и язык UML. В этом ряду стоит
и формализм алгоритмических сетей, предназначенный для описания алгоритмических моделей. Под алгоритмической моделью
здесь понимается формализованное описание сценария предметного специалиста для моделируемого процесса, структура которого
сопоставима со структурой причинно-следственных и временных
зависимостей между явлениями моделируемого процесса вместе со
всей информацией, необходимой для ее программной реализации.
Язык алгоритмических сетей был предложен В. В. Иванищевым
[2]. Разработка теории алгоритмических сетей, методов представления моделей на основе данного формализма и построение систем автоматизации моделирования выполнялись в Санкт-Петербургском
институте информатики и автоматизации РАН. Авторы настоящего пособия принимали непосредственное участие в данных исследованиях. Основные результаты исследований по проблеме алгоритмических сетей изложены в монографиях, приведенных в библиографическом списке.
4
1. ПОНЯТИЕ АЛГОРИТМИЧЕСКИХ СЕТЕЙ
1.1. Определение алгоритмической сети
Алгоритмическая сеть (АС) (рис. 1, а) определяется как ориентированный гиперграф без петель при вершинах G(V, X), в котором
дуги обозначают модельные переменные xi∈X, i = 1,n, а вершины
vj∈V – функциональные соотношения (операторы), fj∈F, j = 1,m,
связывающие модельные значения переменных на интервале времени, соответствующем Dt [3].
Структура переменных сети X=Xвх ∪Xвых ∪Xвн, где Xвх, Xвых,
Xвн – соответственно входные, выходные и внутренние переменные, причем Xвх ∩ Xвых =∅, Xвх ∩ Xвн=∅, Xвых ∩ Xвн=∅. Учитывая, что все вершины AC наблюдаемы, можно задать X=Xвх ∪
Xвыч, Xвыч – вычисляемые переменные AC, Xвыч = Xвых ∪ Xвн.
Формально AC может быть определена следующим образом:
AC:=<P, Q, X, F, P→F, Q→X>,
где P – множество вершин сети; Q – множество дуг сети; X – множество переменных, при этом X=∪Xi; Xi – множество переменных
i-й вершины; I – множество всех индексов вершин; F – множество
операторов; P→F – изоморфное отображение P на F, т. е. индекс
оператора можно считать индексом вершины; Q→X – отображение
Q на X.
Оператор fi∈F описывается как fi:=<Xi in, fi, Xi out>, где Xi in,
Xi out – множество входных и выходных переменных оператора;
fi – символ операции или функции. Для некоммутативных операторов в Xi in, Xi out должен быть задан частичный порядок для
а)
х1
б)
х3
х2
х6
х4
∆t
∆
х5
х2
х1
х6
х4
х5
х3
х7
∆t
х8
Рис. 1. Алгоритмические сети:
а – связная; б – состоящая из двух несвязных компонент
5
их элементов. Так, для операции вычитания в Xi in необходимо отметить уменьшаемое, порядок следования остальных переменных
несущественен. В общем случае fi может быть именем некоторого
программного модуля или другой AC, операторы могут быть определены над действительными числами, логическими переменными, скалярами, векторами, матрицами, информационными структурами и др. В состав операторов AC включается оператор задержки, который задает исходное состояние моделируемому процессу
и описывает переход модели на следующий шаг или определяет
задержку появления некоторой переменной в части AC. AC будем
называть канонической, если все операторы задержки определяют
рекуррентные соотношения относительно одной и той же величины и с одинаковым шагом ее изменения. Иными словами, в канонической AC все операторы задержки срабатывают одновременно
и обеспечивают формирование одного внешнего цикла счета операторов сети.
1.2. Алгоритмический базис и правила
построения AC
Множество различимых между собой операторов fj, j = 1,m, образует алгоритмический базис AC. В качестве примера в табл. 1
приведены операторы алгоритмического базиса системы автоматизации моделирования ЭКО-САПФИР [4]. В состав базиса включены арифметические операции (операторы 1–4), элементарные
функции (операторы 7–11), операторы разлияния и слияния потоков (5, 6), логический ключ (12), операторы выбора максимальной
и минимальной величины (13, 14), табличная функция (15), операторы округления и задержки на время Dt (16, 17). Операторы определены над действительными числами. Переменными AC здесь являются скалярные величины. Базис AC в общем случае является
открытым.
Алгоритмическая сеть формируется из операторов алгоритмического базиса в соответствии с синтаксическими правилами:
1) связности – вершины сети соединяются по одноименным переменным в соответствии с ориентацией дуг;
2) однозначности – не допускается вычисление одной переменной различными операторами AC;
3) ацикличности – сеть не должна иметь контуров, не содержащих операторов задержки Dt, реализующих функцию x(t)=y(t–1).
6
х3
х3
Таблица 1
х2
№
п/п
1
2
3
4
5
6
7
8
9
10
х1
х2
cos х
потоковый базис
х2 Алгоритмический
х1
2
х3
хх2
cos
системы
хх2 автоматизации моделирования ЭКО-САПФИР
хх1
2
2
х
1
х1 хх
cos
3
cos хх22
хх11
22
хх3
х
cos
cos
х
Графическое
представление
Тип
операции
хх
х1 2
3
2
1
хх33
х 1
cos х2
хх1 х2
х11х1 cos х3х2
х3
1х2
хх11 х1
х
хх ↑cos х
3
хх33
х1 х
х2 х1х1 потоков
Сложение
3
хх3
1
х
11 ↑
3
=x
+x
х
хx
х11 хх11
х3
2 3 1 1↑ 2 хх
33
х2 хх
хх2 х1 ↑
хх3
х
11
↑↑ х4 3
2 х
3
х2 х1
х3
хх22 1 ↑
хх33
хх2 х1
хх
х
х
43
↑
2
3
2 х1
х2х1
х2
х3
хх4
↑
хх22х1
Вычитание
потоков
4
х2
х3
<0 хх4 х
х2х
х1
х
2
3
xх3=x1–x2 х4
х2 1
х11
х
<0 4 хх2
х3
х
2
хх22 х1х1
хх11
<0
хх22
х11
<0хх344
хх3
х1
3
х2 х
х
<0
<0
2
1
хх33
х
х
х2
хх2 х1
<0 3
х11
х3
х
2 х
х
х
Умножение
потоков
х1 <0
33
2
хх22 х11
х
<0 хх33
х33
x3х=x
x
х2
х3
1 1 2 х
х
х3
х 1
хх1 min х 3
х22 хх1 /
х33
1
х3
х
1
х
х2 хх
2 хх11
min х3х
хх3
11 /
3
х2 х1min х3х3
х2 х1 //
хх33
х1 min
33
хх2 х
Деление
потоков
хх2 х1 //
min х3
х3
2
1 min
2 хх
1
х
х
х
х
x
=x
:x
х
min
х22 4 /
223
1 2 3
х33х
х2х1 min х3
хх21 х4 /
2
min
х
/
х х
х3
хх2
х2х1
х22х1 х44
Разлияние2 хпотока
хх23
х11 max в хзаданной
хх1 хх44
2
3
х
хпропорции
1
3
хх
2 хх
хх11 х4
хх3
11 max
22
ххх
х4
3
х
3
х
1 max
32
хх
2xх2=x
max
1х
1x4 хх33
ххх
х21 4 х4
1 max
х
233
х
х
х 1max
x232=x
(1–x4) 3
х
х12
х4 х1 2х3
хх22 1 max х3
х3
хх2
х3
х
х2
max
х44 х1 х3
х3 хх2
х2
Слияние потоков
с вычислением
их
х2х1 max
22
хх44хх1
TFвеличин
х2х
относительных
х3 х2
1
х2
х
1
4 хх
х2
хх3 х
TF3 хх2
xхх11=x2+x
х4 х11
3 2
2
1
х
1х2
TF
хх3х
4 х
х
x
=x
/x
х
TF1 хх22
31
4
2
1
1
ln х1 х
х
хх
TF 2х2
TF
х1х1
1 2
3
х 1
хх2
х
rTF хх2
ln
Логарифм
хх11
х33хх11
2
TF хх22
1
ln
хх
ln ххх22
r ) х2
хх12=ln(x
x
TF
х1х11
2
1
2
х
1
ln
ln
2
хх22
rr
х
1
х
exp
х
11
хх11
ln хх22
Экспонента
rr хх2
х1х1
ln хх22
2
exp
ххх11
х1=exp(x
r ) х2
2
x
ln
∆t
1
2
х
х
хх11
хх11 exp
r 1 хх22
exp
22
хх2
r
∆t
хх1Синус
exp х2х2
х1х1
exp
2
1
х2
sin
х
∆t
exp хх
хх1=sin(x
∆t ) хх22
хх11
1
x
22
2
1
exp
х
∆t
х1
∆t
sin хх2
2
х1
exp
х22
х2
х1
хх111
∆t х
Косинус
sin
х
х
sin
хх11
х
2
2
cos
2
∆t
sin х2
sin
x21=cos(x
х1
∆t1)
х1
sin х2
х1
sin х2
sin
7
х1
х3
х2
↑
х1
cos
cos
х2
х2
1 cos
х2
х
х
х1 1
3
х
х1
х3 2
х1 ↑cos
cos
х2
х3
↑
х2 х
1 ↑
Графическое
представление
х2 х
х
х43
х11 ↑
хх43
х2
х
х1
↑
х 3 х2
х2х
↑<0 4
х2
х2 1
<0 х4
х
х
х1 х
№
п/п
11
1
Окончание табл. 1
Тип операции
Степенная функция
x3=x1x2
2
<0 хх
х34
х2
х34
<0
х1
х2
х3
х1х1
х2
х1 <0
<0 хх
3
3
х1 min х
3
х
х2
3
min хх
33
х2 х1
min
х2 х
х3
х11 min
х3
х2 х1
х3
х1 min
min х3
х2
х2 х max х
1
3
х2
max х
3
х2 х1
max
х2 х
х3
х11 max
х3
х2
х1 max х3х2
TF х2
х2х max
х2 1
TF х
х
х1
12
13
14
15
16
17
1
хх11
хх1
1
хх1
1
х1
х
1
х1
х
х11
х1
TF
TF
r
r
TF
TF
r
r
∆t
∆t
r
r
∆t
2
хх22
х2
х2
хх2
2
х2
х
2
х2
х2
х2
Логический ключ
x3=x1 при x4<0
x3=x2 при x4≥0
Выбор потока с минимальной
интенсивностью
x3=min(x1, x2)
Выбор потока с максимальной
интенсивностью
x3=max(x1, x2)
Табличная функция
x2=TF(x1)
Операция округления
x2=[x1]
Задержка потока на время Dt
x2(t+1)=x1(t)
Алгоритмическая
х2сеть, удовлетворяющая условиям 1–3, назых1
вается правильной.
Правильная сеть может состоять из несколь∆t
х2
х1
х
х1
ких независимых
компонент
(рис. 1, б).
2
∆t
∆t
1.3. План вычислений и обратимость AC
Операторы AC, перечисленные в порядке, допускающем их вычисление, образуют план вычисления сети. В зависимости от алгоритма построения плана для AC могут быть сформированы различ8
ные изоморфные ей структуры, в частности, ярусно-параллельный
граф [4]. В ярусно-параллельном графе (рис. 2, д – в) все операторы,
относящиеся к одному ярусу, могут рассчитываться одновременно.
Это позволяет распараллеливать процесс вычислений AC. План
вычисления можно трактовать как алгоритм расчета AC. Таким
образом, AC является некоторым обобщенным алгоритмом счета
модели, представимой данной сетью. В зависимости от способа построения плана вычислений AC порождает тот или иной алгоритм
из конечного множества алгоритмов, присущих данной AC.
В процессе счета на сети реализуется рекуррентная процедура
определения очередного состояния модели на основе предыдущего
состояния и текущих значений входных переменных:
Xст(t) = M(Xст(t–1), Xвх(t–1)),
где Xст – множество переменных состояния AC. Переменными состояния сети являются выходные переменные операторов задержки.
p4
х1
а)
∆t
p 1: х5(t)=х1+х2
p 5: х6(t)=х3–х2
p 2: х7=х5 х6
p 6: х8=х6/х4
p 3: х9=х7+х12
p 7: х11=х8 х7
p 4: х1(t+1)=х9(t)
p1
х5
х2
p2
х7
х12
х9
p3
p5
х3
∆
х6
х11
х8
х4
p6
б) p 1 p 5 p 2 p 6 p 3 p 7 p 4
p7
в)
p1p2
p5p6
p3p7p4
Рис. 2. Алгоритмическая сеть и план вычислений (а)
и соответствующая расчетная программа для одного (б)
и двух (в) процессоров
9
Важным свойством АС является свойство частичной обратимости. Условиями обратимости AC относительно переменных xi∈Xвх
и xj∈Xвых являются:
1) существование одного и только одного пути по ориентации
дуг между xi и xj;
2) возможность обращения всех операторов на пути между xi и xj.
Возможность обращения оператора fi будет зависеть от реализуемой им математической операции и от набора переменных <Xвх i,
Xвых i> – операндов оператора fi. Каждый из наборов определяет
допустимый путь прохождения вершины, т. е. вариант вычисления оператора fi. Так, для оператора деления варианты его вычисления в зависимости от того, какая из переменных выбрана выходной, будут: {x3=x1/x2, x1=x2*x3, x2=x1/x3}.
Примем следующие определения компонент AC. Конус вычислимости переменной xi – это фрагмент сети, состоящий из операторов (вершин) и переменных (дуг), участвующих в вычислении xi.
Основание конуса вычислимости – это подмножество входных переменных сети и переменных состояния, входящих в состав переменных конуса вычислимости. Дерево вычислимости переменной
xi – это фрагмент сети, состоящий из операторов и переменных, в
вычислении которых участвует xi.
1.4. Алгоритмические сети и модели
Процесс создания модели в общем случае включает следующие
этапы работы.
1. Формирование целей моделирования, задач, решение которых приведет к достижению поставленных целей, предмодельный
анализ данных об объекте моделирования.
2. Разработку концептуальной модели, включающую выделение системообразующих факторов, существенных параметров, основных механизмов функционирования объекта.
3. Разработку математической модели и ее исследование аналитическими методами.
4. Разработку алгоритма функционирования модели с учетом
выбранного численного метода для цифровой имитации.
5. Составление машинной программы.
6. Настройку модели, оценку чувствительности, оценку качественного и количественного соответствия модели реальному объекту.
10
Неформальные процедуры формирования модели включают
первые два этапа и заканчиваются разработкой концептуальной
модели. Разработка концептуальной модели сложной системы основывается на структурно-функциональном подходе, методология которого связана с именами С. В. Яблонского, А. А. Ляпунова,
Г. Одума, Дж. Форрестера. Предполагается, что объект состоит из
блоков, блоки связаны между собой потоками субстанций, которые могут в них накапливаться или трансформироваться. Кроме
того, существует обмен объекта с внешней средой. Под субстанцией понимается вещество или энергия, причем набор веществ, выбранных для изучения, может быть различным. Понятие «блок»
является относительным и зависит от свойств моделируемого объекта, его изученности, задач моделирования. Блок может состоять из субблоков. Потоки субстанций, переходящие через границу
блока, характеризуются их интенсивностью. Структура модели
считается заданной, если перечислены все блоки и все связывающие эти блоки потоки, а также отмечены входные и выходные потоки.
Динамика процессов трансформации, накопления и переноса
субстанций определяется законами функционирования блоков.
В зависимости от свойств системы процесс функционирования может иметь непрерывный или дискретный характер. В качестве характеристик законов функционирования на концептуальном уровне служат вид функциональных зависимостей, предельные значения, временные дискретно-непрерывные свойства.
Совокупность структурно-функциональных свойств определяет концептуальную модель системы. Могут быть выделены классы
реальных систем, в которых то или иное свойство является преобладающим, Так, для транспортных коммуникаций, энергосетей,
нефтепроводов, информационных сетей главной является структура потоков. Модели этих объектов принято называть потоковыми
моделями [2]. В слабоструктурированных системах основная задача заключается в исследовании функционирования системы как
целого. Соответственно, в моделях таких систем главная роль отводится функциональной составляющей.
Очевидно, и это многократно подчеркивается в работах по моделированию [5, 6], что во многих случаях модель объекта может
быть представлена в дискретном виде. При разработке моделей таких объектов уместен алгоритмический подход [6, 7]. В алгоритмическом подходе модель изначально создается в виде алгоритма,
предназначенного для реализации на ЭВМ.
11
Алгоритмический подход породил понятие алгоритмической
модели как формализации описания некоторого сценария моделируемого процесса. Под сценарием будем понимать представление
предметного специалиста о процессе, которым он управляет или
изучает. Сценарию соответствует «сценарная» система причинноследственных связей, которая может отличаться от естественной
системы причинно-следственных связей реального процесса. Так,
естественная система связей управления движением самолета – это
положение педалей и ручки управления – положение рулей – разворот самолета. При решении задачи движения самолета по дуге с заданным радиусом сценарная система причинно-следственных связей будет обратной: радиус поворота – положение рулей – положение педалей и ручки управления. Данным сценариям соответствуют различные алгоритмические модели. Алгоритмический подход
может использовать различные методы формализации модели, одним из которых является представление алгоритмической модели в
форме АС. Алгоритмическая сеть при этом выступает как средство
представления модели, по которому автоматически составляется
алгоритм и расчетная программа. Визуализация информационных
связей, структуры потоков материальных субстанций и операций
над потоками делает представление модели в форме AC доступным
и удобным для предметного специалиста, который во многих случаях становится непосредственным разработчиком модели [8].
Общая структура потоков для достаточно сложного природного,
экономического или технического объекта, как правило, уникальна и может быть составлена на основе феноменологического описания. Вместе с тем отдельные блоки, регулирующие интенсивность
потоков, являются более универсальными, что позволяет надеяться на наличие их описаний в математической форме в составе имеющихся баз моделей. В работах [3, 4] приведено большое количество
примеров моделей сложных природных и эколого-экономических
систем, представленных в форме АС.
Формально алгоритмическая модель может быть представлена в
следующем виде [9]:
AM::=<IM, IO, AC, T, X→T, F→IP, IM>,
где IM – идентификатор модели; IO – феноменологическое описание объекта моделирования; AC – алгоритмическая сеть, соответствующая вычислительной структуре модели с учетом T, X→T,
F→IP; T – множество терминов предметной области (ТПО), используемых в модели (основное требование, предъявляемое к ТПО, – это
12
требование однозначного (или взаимно однозначного) именования
терминов предметной области); X→T – отображение множества
имен переменных AC в подмножество терминов предметной области; F→IP – отображение множества операторов AC в множество
процессов моделируемого объекта (возможность декомпозиции
процессов к виду, допускающему их реализацию с помощью AC
как алгоритмически полной системы операций F→IP, следует из
определения алгоритмической модели); IM – показатель, характеризующий информацию, необходимую для проведения расчетов и
интерпретации результатов (включает значения параметров модели, начальных значений переменных состояния, шаг счета, единицы измерения и др.).
13
2. АЛГОРИТМИЧЕСКАЯ ПОЛНОТА И РЕАЛИЗАЦИЯ
ВЛОЖЕННЫХ ЦИКЛОВ
2.1. Проблема алгоритмической полноты AC
Необходимым условием применения любого формализма, используемого для решения задач моделирования и вычислений, является условие алгоритмической полноты. Известно, что понятие
алгоритма не формализовано и имеет описательный характер. Под
алгоритмом в интуитивном смысле понимается точное предписание
или набор общепонятных правил, ведущих от варьируемых исходных данных к искомому результату [9]. Попытки уточнить понятие
алгоритма привели к разработке формальных моделей, к которым
относятся машины Тьюринга, примитивно-рекурсивные функции,
нормальный алгоритм Маркова, логические схемы структурного
программирования Глушкова–Дейкстры [9–11]. Эквивалентность
формальных моделей алгоритмов относительно решаемых задач
может быть строго доказана [9, 10], однако общий класс задач, решаемых любой из формальных моделей, строго определен быть не
может. Оценки вычислительных возможностей моделей алгоритмов основываются на гипотезах, известных как тезис Черча, тезис
Тьюринга, принцип нормализации алфавитного алгоритма, в соответствии с которыми класс задач, решаемых любой из формальных
моделей, включает все задачи, которые могут быть решены «интуитивно» алгоритмическими методами. Это утверждение является
общепризнанным, хотя и не может быть строго доказано [9].
Исходя из модели нормального алгоритма В. М. Глушков ввел
понятие автоматного отображения [10] и показал, что любое однозначное алфавитное отображение может быть приведено к автоматному виду, т. е. для любого однозначного алфавитного оператора
может быть построен индуцирующий его автомат. Легко показать
[4], что с помощью операторов алгоритмического базиса AC могут
быть реализованы логические операции, образующие полную систему (рис. 3). В совокупности с оператором задержки это позволяет построить любой конечный автомат.
Сравним AC с другим эффективным языком представления вычислительных алгоритмов – языком графических схем [11]. Универсальность языка графических схем подтверждается тем, что на
нем могут быть представлены машина Тьюринга, машина с неограниченными регистрами, нормальный алгоритм Маркова [11], т. е.
объекты, которые используются в качестве формальных моделей
14
UN
х2
х1
min
х3
х1
Q
∆
Q
∆t
x3= x1&x2
х2
х1
max
max
х3
x3= x1∨x2
min
UN
х1
–
j
х3
х2
k
UN
∆
k
Q(t+1) = (Q(t)&k
x2 = x 1
Рис. 3. Структурно полный набор логических элементов:
конъюнкция, дизъюнкция, отрицание, элемент памяти (j-k-триггер).
Все входные переменные и переменная состояния Q – булевы,
UN – константа единица
алгоритмов. На языке графических схем существуют три базовые
логические структуры, с помощью которых может быть реализован
вычислительный алгоритм, – это последовательностные структуры,
структуры с выбором и циклические структуры (рис. 4, а – в). Сопоставление базовых логических структур с операторами сетевого алгоритмического базиса (см. табл. 1) позволяет заключить, что любые
последовательностные схемы и схемы с выбором могут быть эффективно реализованы на AC. Специфика AC заключается в том, что на
них вычисляются все операторы сети, а в стандартной программной
среде – лишь операторы инициированной ветви алгоритма.
Однако в канонической AC отсутствуют структуры для произвольного представления циклов. Если традиционные средства программирования позволяют располагать схемы с циклом в любом
месте алгоритма, то в AC имеется лишь одна стандартная структура такого типа, которая в совокупности с операторами задержки образует внешнюю оболочку алгоритма. Таким образом, на AC могут
быть эффективно реализованы рекуррентные процедуры, описыва15
a)
б)
в)
Рис. 4. Базовые логические схемы структурного программирования:
а – последовательностная схема, б – схема с выбором (альтернатива);
в – схема цикла (итерация)
емые системой уравнений вида Xn+1=F(Xn, Xn–1, ...), где X=<x1,
x2, ..., xs>, F=<f1, f2, ..., fm>. Однако вложенные и асинхронные
итерационные процедуры на AC непосредственно представлены
быть не могут.
Таким образом, на уровне логических элементов структурного
программирования язык АС является неполным. Однако AC полны
в автоматном смысле. Поскольку конечные автоматы и логические
элементы структурного программирования по алгоритмическим
возможностям эквивалентны, то ограничение на реализацию произвольных циклических структур на AC не является принципиальным. Покажем, что ограничение может быть снято и циклы на
AC реализованы путем их имитации с помощью типовых операторов алгоритмического базиса (см. табл. 1).
2.2. Реализация вложенных циклов
на AC путем имитации
При имитации будем исходить из следующего представления
цикла как вычислительной процедуры.
1. Вычисления в цикле содержат в общем случае три основные
компоненты – ввод данных для счета, запуск итерационной процедуры счета, прекращение счета и выход из цикла.
16
2. Сигнал прекращения счета формируется, как правило, внутри цикла (по выполнению заданного количества шагов счета, достижению заданной точности и т. п.).
3. После запуска итерационной процедуры и до ее окончания все
другие вычисления в программе блокируются.
В канонической AC все операторы задержки срабатывают в каждом временном такте, изменяя значение переменных состояния.
Поэтому выключение циклов мы будем имитировать «холостой
прокруткой» итерационной процедуры с замыканием выходов операторов задержки тела цикла на собственные входы.
Алгоритмическая сеть, имитирующая структуру типа цикл, показана на рис. 5. Переменной состояния цикла является переменная x1 на выходе оператора задержки 1. Новое значение переменной
состояния x4 формируется в процессе счета на AC тела цикла. Условный оператор 2 на входе задержки 1 служит для ввода начального значения переменной состояния при запуске итерационной
процедуры счета, оператор 3 служит для замыкания задержки при
выключении процедуры счета. Переменная z1 фиксирует прекращение итерационной процедуры счета. Она формируется на AC тела
цикла и на последнем такте счета принимает значение z1=1. Опера-
х5
х вх
5
=0
х6
z1
АС тела цикла
х7
∆t
6
х8
min
4
х9
х1
1
∆t
х2
2
=0
y1
х3
3
=0
х4
y2
Рис. 5. Укрупненная АС цикла с одним оператором задержки:
y1 – сигнал ввода начальных условий (х9);
y2 – сигнал включения итерационной процедуры цикла;
z1 – сигнал окончания счета; x8 – выходная переменная цикла;
xвх – множество входных переменных АС цикла
(на время вычисления цикла хвх=const)
17
тор 4 служит для формирования управляющей переменной x6 для
оператора 5. Переменная x8 является выходной переменной цикла, оператор задержки 6 служит для хранения x8 при выключении
цикла. Запись нового значения выходной переменной x5, соответствующего окончанию итерационной процедуры счета, выполняется по сигналу z1=1 через условный оператор 5. Входные переменные
AC цикла во время его выполнения не изменяют своего значения.
Управляющими переменными цикла являются переменные y1
и y2. Первая служит для ввода начального значения переменной
состояния x4, вторая обеспечивает переключение режимов нормального счета и холостой прокрутки цикла. Переменные y1, y2 и
z1 – булевы, значение 1 соответствует выполнению указанных действий, значение 0 – запрету на выполнение.
Задача синтеза AC с циклом сводится теперь к задаче синтеза
автомата, генерирующего управляющие переменные Y=<y1, y2>.
Структура автомата определяется последовательностью работы
цикла; его входными переменными являются переменные внешней сети, управляющие запуском цикла, и переменная окончания
счета цикла, формируемая на AC тела цикла: Z=<z1>.
В качестве примера рассмотрим AC, в которой имеются два взаимосвязанных цикла C1 и C2 (рис. 6, а). Циклы включаются последовательно, сначала выполняется итерационная процедура счета в C1,
затем в C2 и т. д. Предполагается, что начальное значение переменных состояния x1 и x6 формируется в цикле C1. Выходными переменными являются x5 и x10, переменные z1 и z2 фиксируют окончание счета в циклах, внешняя переменная z3 фиксирует окончание
счета на сети. Дополнительные операторы, необходимые для хранения выходных переменных, на рисунке не показаны, так как для их
работы не требуются дополнительные управляющие сигналы.
Будем строить управляющий автомат в форме синхронного автомата Мура (рис. 6, б), состояниям которого соответствуют выходные сигналы y1–y5:
1) состояние a1, выходной сигнал y1 – ввод данных для C1;
2) состояние a2, выходной сигнал y2 – счет в C1;
3) состояние a3, выходной сигнал y3 – ввод данных для C2;
4) состояние a4, выходной сигнал y4 – счет в C2;
5) состояние а5, выходной сигнал y5 – окончание счета.
Переходы из состояний a2 в a3 и из a4 в a1 происходят при появлении сигналов z1 и z2, формируемых на AC при завершении
итерационной процедуры счета, переход из а4 в а5 происходит при
появлении сигнала z3. Ввод данных выполняется за один шаг, по18
a)
хвых1
хвых2
хвх1
хвх2
х11
С1
z1
z2
С2
х5
х1
х4
z3
х7
х10
х6
∆t
х2
=0
х3
y1
х8
б)
y1
z2 z3
z3
a4
х9
=0
y3
y2
a1
a5
∆t
=0
y4
a2
=0
y4
z1
y2
z1
a3
y3
z2 z3
Рис. 6. Укрупненная АС двух связанных одноуровневых циклов С1 и С1
(а) и граф управляющего автомата (б)
этому переход из состояний a1 в a2 и из a3 в a4 происходит по синхросигналу очередного шага счета без какого-либо дополнительного входного сигнала.
Структурный синтез автомата выполняется по известным методикам, описанным, например, в работе [12]. Для удобства формирования выходных сигналов автомата примем следующую форму
кодирования состояний:
a1 - Q1Q2Q3Q4,
a2 - Q1Q2Q3Q4,
a3 - Q1Q2Q3Q4
a4 - Q1Q2Q3Q4,
à5 – Q1Q2Q3Q4.
19
Уравнения комбинационной схемы автомата, использующего в
качестве элемента памяти j-k-триггер, имеют вид
y1 = Q1, j1 = z2 & z3 , k1 = Q1;
y2 = Q2, j2 = Q1vz1, k2 = z1;
y3 = Q3, j3 = z1, k3 = Q3,
y4 = Q4, j4 = Q3vz2 , k4 = z2 ;
y5 = Q1Q2Q3Q4.
Алгоритмическая сеть структурной схемы управляющего автомата приведена на рис. 7. При выбранном способе кодирования состояний элементы памяти автомата могут быть включены в состав
схем циклов. Синтез управляющего автомата будет при этом состоять в формировании AC комбинационной схемы.
Если внешняя к циклу сеть не содержит операторов задержки,
то на первом шаге счета на AC будут определены все необходимые
входные величины для реализации итерационной процедуры цикла. Эти величины будут сохранять свое значение до окончания счета в цикле. Значения переменных AC, в расчете которых участвуют выходные переменные цикла, будут получены по завершении
итерационной процедуры счета. Для рассматриваемого примера
результаты расчетов фиксируются при переходе управляющего автомата в состояние а1.
Входные сигналы элементов памяти:
j1 = z2 & z3 , k1 = y1; j2 = y1 Ú z1, k2 = z1;
j3 = z1, k3 = y3 ; j4 = y3 Ú z2 & z3 .
Подход является универсальным и позволяет формировать произвольные циклические процедуры в канонических AC без расширения набора операторов алгоритмического базиса. Полученные
результаты позволили доказать теорему, подтверждающую алгоритмическую полноту канонических AC [3]:
для любой частично-рекурсивной функции может быть построена реализующая ее конечная AC.
Однако такой способ построения AC с вложенными циклами весьма трудоемок. При имитации циклов к AC добавляются элементы,
связанные с особенностями организации и переключения итерационных вычислительных процедур, но не функционирования непосредственно алгоритма модели. В связи с этим далее (в разд. 6) будут
20
y1
∆t
j1
max
min
1
1
min
∆
z2
z3
∆
1
y2
∆t
j2
max
∆
max
y5
max
min
1
∆
z1
y3
∆t
z1
max
min
1
∆
y4
∆t
j4
max
min
1
∆
max
z2
k4
min
z3
Рис. 7. Алгоритмическая сеть структурной схемы
управляющего автомата
рассмотрены варианты расширения AC, позволяющие существенно
упростить процедуру построения сетей с вложенными циклами.
21
3. ОПЕРАЦИИ НАД АЛГОРИТМИЧЕСКИМИ СЕТЯМИ
Операции над AC служат для создания структур новых моделей
из ранее созданных, для проведения эквивалентных преобразований в целях оптимизации структуры моделей, преобразования
структуры моделей при подготовке и проведении вычислительного
эксперимента [5]. При этом в результирующей AC должны сохраняться вычислительные свойства тех фрагментов сетей, которые
в нее вошли, т. е. должно соблюдаться равенство или эквивалентность соответствующих вычислительных схем. Стандартные операции над графами не обеспечивают выполнение этих требований
и не гарантируют, что результатом будет правильная AC. Отношения и операции рассматриваются для AC, имеющих в своих множествах имен переменных одинаковые или взаимно однозначные
обозначения для соответствующих переменных.
Операции основываются на понятиях равенства и изоморфизма
AC: две сети считаются равными, AC1=AC2, если и только если их
множества F совпадают (F1=F2). Здесь F – множества операторов
сети с учетом наименования входных и выходных переменных. Две
сети считаются изоморфными, если и только если между их множествами F может быть установлено взаимно однозначное отображение (F1~F2). В общем случае условие изоморфизма сетей или их изоморфного вложения может устанавливаться путем полного перебора
элементов множества F. Другой подход заключается в установлении
связи имен переменных AC и переменных предметной области. Примем, что переменные предметной области поименованы взаимно
однозначно. Примем также, что между переменными каждой AC и
подмножествами переменных предметной области существует взаимно однозначное соответствие. Выполним переименование переменных сравниваемых AC в соответствии с обозначением переменных предметной области. Теперь задача изоморфизма и изоморфного
вложения сетей сводится к гораздо более простой задаче равенства и
вхождения друг в друга AC с общим множеством переменных.
3.1. Бинарные операции над сетями
1. Пересечение AC1∩AC2 равно подграфу, состоящему из вершин, совпадающих в обеих сетях (рис. 8).
2. Объединение AC1∪AC2 равно пересечению AC и всем остальным вершинам той и другой AC (рис. 9, 10, а, б). Особенность опе22
AC1
x4
x1
AC2
x4
x3
x3
x2
x7
x5
x6
∆
x7
x5
x8

x6
∆
x8
∆t
x1
=
x9
x9
∆
y1
y2
AC1ÇAC2
x4
x3
x7
x5
=
x6
∆
x8
x9
F1 = { x1,x2 + x3 ; x3,x4 • x5 ; x5,x3,x9 − x6 ; x6 ,x7 / x8
}
F2 = { x3,x4 • x5 ; x5,x3,x9 − x6 ; x6 ,x7 / x8 ; y1,y 2 − x9 ; x8 ∆t x1
F1  F2 = { x3,x4 • x5 ; x5,x3,x9 − x6 ; x6 ,x7 / x8
}
}
Рис. 8. Пересечение АС
рации объединения AC: ее результат пуст, если при объединении
нарушается условие однозначности вычисления переменных или
возникают контуры, не содержащие вершин с оператором «задержка» (рис. 11, а – в).
3. Разность AC1\AC2 равна первой AC без подграфа, соответствующего пересечению исходных AC (рис. 12, а, б).
Все рассмотренные бинарные операции над AC сводятся к аналогичным теоретико-множественным операциям над множествами
Fi АС, над которыми операции выполняются.
3.2. Унарные операции над сетями
Агрегация A{pi}(AC) соответствует замене некоторого подграфа
исходной AC одной вершиной, содержащей оператор, в котором
23
AC1
x4
x1
AC2
x4
x3
x3
x2
x7
x5
∆
x8
x6
x7
x5

x6
∆
x8
∆t
x1
=
x9
x9
∆
y1
y2
AС1AC2
x1
=
x4
x3
x2
x7
x5
x6
∆
x8
∆t
x9
∆
y1
y2
F1 = { x1,x2 + x3 ; x3,x4 • x5 ; x5,x3,x9 − x6 ; x6 ,x7 / x8
}
F2 = { x3,x4 • x5 ; x5,x3,x9 − x6 ; x6 ,x7 / x8 ; y1,y 2 − x9 ; x8 ∆t x1
F1  F2 = { x1,x2 + x3 ; x3,x4 • x5 ; x5,x3,x9 − x6 ;
y1,y 2 − x9 ; x6 ,x7 / x8 ; x8 ∆t x1
}
}
Рис. 9. Объединение АС
объединены выражения, соответствующие всем операторам агрегируемого подграфа. Внешние дуги такой вершины соответствуют
внешним дугам агрегируемого подграфа, {pi} – множество вершин
агрегируемого подграфа (рис. 13, а).
Дезагрегация DApi(AC) – операция, обратная агрегации, соответствует замене некоторой вершины AC подграфом, построенным
на основании выбора выражений, определяющих оператор, приписанный вершине pi (рис. 13, б).
24
а)
АС1
АС2
x2
x5
x4
x3
x5
∆

x6
max
x7
∆t
x1
=
x1
АС1АС2
x2
x3
=
x1
x5
x7
∆t
x4
∆
max
x6
{ x2,x1 + x3 ; x3,x4 − x5 }
F2 = { x5, x6 max x7 ; x7 ∆t x1 }
F1  F2 = { x2, x1 + x3 ; x3, x4 − x5 ; x5, x6
F1 =
б)
АС1
АС2
x2

x1
x2
∆
x6
x4
x3
=
x5
x1
∆
x6
x5
F1 = { x1,x2 + x3
F2 = { x4,x5 −
}
x6 }
}
АС1АС2
x4
x3
max x7 ; x7 ∆t x1
F1  F2 = { x1,x2 + x3 ; x4,x5 − x6
}
Рис. 10. Частные случаи операции объединения: а – соединение АС;
б – результат, состоящий из двух компонент связности
Частичное обращение AC′=Ob{R}(AC) – операция, результатом
которой является новая AC с множеством входных переменных R.
Сеть AC′ строится путем обращения некоторых из операторов исходной сети на основании R и связей между вершинами (рис. 14, а – д).
Для единичного оператора fi частичное обращение состоит в
разрешении исходной операции fi относительно другой выходной
переменной на основании входного набора R. В частности, если R
равен множеству входных переменных исходной сети, то обращенный оператор совпадает с исходным. Обращение оператора невоз25
x1
а)
x4
x3
∆
x5
x2
x5
x3
∆t
x1
x4
б)
x2
x1
x3
в)
∆
x2
x4
x1
x3
x3
x2
∆
x3
x2
x4
Рис. 11. Примеры пар АС, для которых нельзя выполнить операцию
объединения: а, б – нарушение условия вычисления переменной
только в одной вершине; в – возникновение контура
без вершины с оператором «задержка»
можно, если R недостаточен для определения типа операции или
избыточен – оператор переопределен. Некоторые типы операторов,
в частности операторы задержки, считаются однонаправленными,
для них допустим лишь один входной набор.
Пример. Исходный оператор х1+х2=х3.
Обращение оператора для входных наборов:
R=(х1, х3) – набор допустим, обращенный оператор х3–х1=х2;
R=(х2) – набор недостаточен, обращение невозможно;
R=(х1, х2, х3) – набор избыточен, оператор переопределен, обращение невозможно.
Условия обращения единичного оператора могут быть распространены на произвольную AC: R избыточен – обращение AC невозможно (результат операции пуст); R недостаточен – обращается
26
а)
АС1
x1
АС2
x3
АС1 \ АС2
x3
x4
x5
x1
x5
\x
∆t
4
x1
x3
=
x2
x2
{ x1,x2 + x3 ; x3,x4 • x5 }
F2 = { x3, x4 • x5 ; x5 ∆t x1 }
F1 \ F2 = { x1, x2 + x3 }
F1 =
б)
АС1
x1
АС1 \ АС2
x3
x4
x3
x2
АС2
x5
\
x1
x5
x4
x3
=
x2
Рис. 12. Разность АС:
а – общий случай; б – частный случай – редукция
лишь подграф A′ исходной сети: 0 ⊆A′⊂A; R допустим – операция
частичного обращения выполнима для всех вершин исходной сети.
Так, для сети, представленной на рис. 14, недостаточным является
набор Oaˆ {x1,x2 } (AC), избыточным – набор Oaˆ {x1,x5 ,x6 } (AC).
Входные переменные операторов задержки и других однонаправленных вершин добавляются по умолчанию к R.
Преобразование выражения в вершине Chqpi (AC) выполняется
для вершины pi, математическое выражение оператора которой допускает равносильное преобразование q. Преобразования включают вынесение за скобки, раскрытие скобок, внесение и исключение
тавтологий и др. Преобразования не должны приводить к частичному обращению оператора в вершине pi и исключению переменных,
по которым pi связывается с другими вершинами AC (рис. 15, а, б).
Выделение подграфа по заданным подмножествам входных
и выходных дуг AC′=SOI(AC), где O, I – множества переменных
исходной AC, соответствующие которым дуги будут внешними выходными (входными) дугами получаемого подграфа (рис. 16, а,
б; 17). Возможны следующие случаи:
– задано множество O, I=∅. Получаемый подграф будет состоять из всех вершин, вычисляющих эти переменные, и всех вершин,
27
a)
A{ p , p , p } (AC)
2 3 4
АС
x5
x1
x3
x3
∆ p2
x6
p1
x4
x7
p3
x5
x1
x6=x3–x5
x7=x3•x4
x6 /x7
x3
x2
x8
p1
x6
x4
p4
F = { x1,x2 + x3 ; x3,x5 − x6 ; x3,x4 • x7 ; x6 ,x7 / x8
}
DAp2 (AC)
АС
x5
x1
x2
p1
x4
x1
x6
x6=x3–x5
x7=x3•x4
x6 /x7
x3
x7
p2
F ¢ = { x1,x2 + x3 ; x3,x4,x5 x6 = x3 − x5,x7 = x3 • x4,x6 /x7 x6 ,x7,x8
б)
x8
p2
x8
x7
x3
x3
}
x5
∆ p2
x6
p1
x4
x7
p3
F = { x1,x2 + x3 ; x3,x4,x5 x6 = x3 − x5,x7 = x3 • x4,x6 /x7 x6 ,x7,x8
F¢ = { x1,x2 + x3 ; x3,x5 − x6 ; x3,x4 • x7 ; x6 ,x7 / x8 }
x8
p4
}
Рис. 13. Агрегация (а) и дезагрегация (б) АС
из которых можно найти путь, приводящий к вершинам, вычисляющим эти переменные. Процесс заканчивается вершинами с
операторами «задержки» или вершинами, все входные дуги которых – внешние для исходной сети. Если входом вершины с оператором задержки является выход другого оператора «задержки», то
он также включается в подграф;
– задано множество I, O=∅. Получаемый подграф будет состоять из всех вершин, для которых эти переменные являются входными, и всех других вершин, достижимых из упомянутых. Процесс заканчивается достижением вершин с операторами типа «задержка» либо вершинами, все выходные дуги которых – внешние
к исходной сети;
– оба множества не пусты. Результирующий подграф является
пересечением подграфов, получаемых только для входов и только
для выходов.
28
а)
x2
AC
x1
x8
F = { x1,x2,x3 + x5 ;
x6
x1,x5 / x6 ;
x5
x2,x5 / x8 ;
x4,x5 / x7 ;
x7
x3,x5 / x9
x4
x3
б)
}
x9
Ob {
x1,x2 ,x3 ,x4 }
(AC) = AC ;
F= F¢
x8
x2
x1
F ¢ = { x5,x1,x3,x4 − x2 ;
x6
x1,x6 • x5 ;
x5
∆
x2,x5 / x8 ;
x4,x5 / x7 ;
x7
x3,x5 / x9
x4
}
x9
x3
Ob {
x6 ,x1,x3 ,x4 }
x1
(AC)
x6
в)
F ¢ = { x1,x6 • x5 ;
x5
x3
Ob {
x6 ,x1,x3 }
x3,x5 / x9
}
x9
(AC) – набор недостаточен, обращается только подграф
исходной АС
Рис. 14. Частичное обращение АС: а – исходная АС и повторение
исходной АС; б – полное частичное обращение АС;
в – неполное частичное обращение АС
3.3. Свойства операций над AC
Введенные ранее операции над AC однозначны.
Операции объединения и пересечения алгоритмических сетей
ассоциативны и дистрибутивны друг относительно друга:
29
a
а)
a
AC
ax+ay+
+ax
x
y
x
z
p1
Ch qp (AC)
1
z
a(2x+y)
p1
y
q – вынесение за скобки и приведение подобных
F = { a,x,y , ax+ ay + ax z }
a
б)
x
AC
x
z
a+ x-a
y+b
y
F ¢ = { a,x,y , a( 2x+ y) z }
b
q – приведение подобных
x
F ¢ = { x,y,b , x /( y + b) z }
AC
a
x
z
ax+b
z
p1
b
F = { a,x,y,b , (a+ x− a)/( y + b) z }
a
1
x
y+ b
y
p1
Ch qp (AC)
1
ax+b+
+y–y
y
p1
Ch qp (AC)
p1
b
b
q – добавление и вычитание одной и той же величины
F = { a,x,b , ax+ b z }
x
a
F ¢ = { a,x,y,b , ax+ b + y − y z }
AC
x
ax+b
z
x
а
Ch qp (AC)
1
z
y
ax+ y
y+b
а
p1
b
q – разбиение на промежуточные выражения
F = { x,a,b , ax+ b z }
z
p1
b
F ¢ = { x,a,b , ax = y,y + b z,y }
AC
ax= y
y+b
x
z
y
p1
b
q – поглощение промежуточных выражений
F = { x,a,b , ax = y,y + b z,y }
a
Ch qp (AC)
1
z
ax+b
b
p1
F = { a,x,b , ax+ b z }
Рис. 15. Преобразования вершины единичной АС:
а – не меняющие множества X; б – меняющие множества Х
30
O (AC)
S∅
АС
а)
O = {x6 , x11}
x1
x1
x6
x3
x11
∆
x4
x7
∆
x2
x5
∆t
x8
x10
max
F = { x1,x2,x3 + x6 ; x6 ,x7 − x8 ;
x10 ∆t x5 ; x5,x3 − x11 ;
x4,x5 • x3 ; x8,x9 max x10
x6
x2
x3
x9
x4
x5
x4,x5 • x3 ; x10 ∆t x5
}
O = {x6 , x11 }
I = {x1, x2, x4 }
x1
x6
x11
x5
x8
x10
x1
max
x3
x9
x2
x3
x4
x5
F ¢ = FI¢  FO¢ = { x1,x2,x3 + x6 ;
}
x5,x3 − x11 ; x4,x5 • x3
x1
S IO (AC)
x2
}
O = {x5, x6 }
x3
x5
x7
x6
x11
∆
x4
AC
x5
x6
x2
F ¢ = { x1,x2,x3 + x6 ; x6 ,x7 − x8 ;
I
x9,x8 max x10 ; x5,x3 − x1 ; x4,x5 • x3
б)
x1
x7
∆
x2
x4
}
O
S IO (ÀÑ) = SI∅ (ÀÑ )  S∅
(ÀÑ )
I = {x1, x2, x4 }
∆
x10
∆t
FO¢ = { x1,x2,x3 + x6 ; x5,x3 − x11 ;
S I∅ (ÀÑ)
x3
x11
∆
I = {x1, x3 }
x6
x4
Рис. 16. Выделение подграфа: пример результата операции,
приводящего к связному (а) и к несвязному (б) подграфу
31
AC
x6
x1
x7
x4
x11
x2
x13
x10
x5
x3
x8
∆
x12
x9
O
S I 1 (ÀÑ) O1 = {x7 , x8 }
1
I1 = {x1, x5 }
x6
x1
x7
x4
x2
x5
O
∆
x8
O
S I 2 (ÀÑ) ⊂ S I 1( ÀÑ ) O2 = {x8 } ⊂ O1
1
1
I2 = {x1 } ⊂ I1
x5
x1
x4
∆
x8
x2
Рис. 17. Выделение подграфа, соотношения выделяемых подграфов
для случая, когда множества I и О одного являются
подмножествами O и I другого
(AC1∪AC2) ∪AC3=AC1∪ (AC2∪AC3);
(AC1∩AC2) ∩AC3=AC1∩ (AC2∩AC3);
(AC1∪AC2) ∩ AC3=(AC1∩AC2) ∪ (AC1∩AC3);
(AC1∩AC2) ∪ AC3=(AC1∪AC2) ∩ (AC1∪AC3).
32
Операция разности ассоциативна и дистрибутивна относительно
операции пересечения:
(AC1\AC2) \AC3=AC1\ (AC2\AC3);
(AC1\AC2) ∩ AC3=(AC1∩AC2) \ (AC1∩AC3);
(AC1∩AC2) \ AC3=(AC1\AC2) ∩ (AC1\AC3).
Операции пересечения и объединения коммутативны и идемпотентны:
AC1∪AC2=AC2∪AC1, AC1∩AC2=AC2∩AC1;
AC1∪AC1=AC1, AC1∩AC1=AC1.
Правила поглощения:
(AC1∩AC2) ∪AC1=AC1; (AC1∪AC2) ∩AC1=AC1;
(AC1\AC2) ∪AC1=AC1; (AC1∪AC2) \AC1=AC2;
(AC1∩AC2) \AC1=∅; AC1/AC1=∅;
(AC1\AC2) ∩AC1=AC1\AC2; (AC1\AC2) ∪AC2=AC1∪AC2.
Операции с пустой сетью ∅:
AC1∪∅=∅∪AC1=AC1; AC1∩∅=∅∩AC1=∅;
AC\∅=AC1; ∅\AC1=∅.
Если считать, что все ACi есть подсети всеобщей сети AC, то такая сеть будет единицей для пересечения и нулем для объединения:
AC1∪ AC = AC ∪AC1= AC; AC1∩ AC = AC ∩AC1= AC1;
Дополнение некоторой AC1 до всеобщей обозначим AC1:
AC1=AC\AC1.
Свойства дополнения и правило де Моргана для сетей:
 (AC1)=AC1;
(AC1∪AC2)= AC1∩AC2, (AC1∩AC2)= AC1∪AC2;
AC=∅;
AC1∪AC1=AC, AC1∩AC1=∅, AC1\AC1=AC1, AC1\AC1=AC1,
AC1∪AC1=AC.
Множество всех АС и заданные операции определяют алгебру
AC [13]
A=<{AC}, W>,
где {AC} – множество всех возможных AC; W – множество операций
над AC.
Алгебра AC создает основу для создания метаязыка для описания всех возможных действий, проводимых над AC, в процессе создания моделей, проведения вычислительного эксперимента и принятия решений.
Отметим, что справедливость законов алгебры AC ограничивается подмножествами сетей, в которых объединение любых непустых
сетей также не пусто. Это ограничение непосредственно связано с
особенностями задания указанной операции над AC.
33
4. СОГЛАСОВАНИЯ ФРАГМЕНТАРНЫХ AC
4.1. Операции согласования AC
Обозначим символом AS множество AC, в котором объединение
любых двух сетей не пусто. Проанализируем структуру множества
AS. Построим полную сеть ACS, выполнив объединение всех сетей
Ai∈ AS. Любой фрагмент ACj, полученный путем перерезания входных и выходных дуг на его границе (исключая входные и выходные
дуги ACS), может быть включен в множество AS, поскольку объединение такого фрагмента с любым другим не пусто и не образует некорректно заданных циклов (не-циклов). Таким образом, множество
всех возможных фрагментов ACS и образует AS. Это множество конечно, но ввиду возможного пересечения фрагментов весьма велико.
Возможно наращивание множества AS новыми сетями ACi с расширенным составом переменных и операторов при условии, что ACS ∪
ACi ≠ ∅. Сети, входящие в AS, назовем взаимно согласованными.
Требование согласованности является весьма жестким. Формирование моделей тех или иных фрагментов предметной области
выполняется, как правило, различными группами специалистов и
в разное время. При построении фрагментарных моделей в форме
AC легко обеспечить однозначность именования переменных (использование общего словаря переменных для моделей предметной
области обязательно!) и синтаксическую правильность сетей каждого из фрагментов. Однако выполнить требования однозначности
вычисления переменных и исключить возможность образования
не-циклов при произвольном объединении AC фрагментарных моделей весьма сложно. К тому же требование однозначности может
привести к нежелательной потере информации.
Задача согласования может быть представлена следующим образом. Имеется множество фрагментарных моделей Ag объектов
предметной области, представленных правильными алгоритмическими сетями ACj с однозначным именованием переменных. Назовем это множество «серой» базой моделей предметной области.
Требуется обеспечить взаимное согласование сетей, т. е. устранить
неоднозначность вычисления переменных и исключить образование не-циклов при объединении любых ACj, ACk∈Ag. Полученное
в результате взаимного согласования сетей множество Aw назовем
«белой» базой моделей предметной области. Объединение в нем любых двух сетей ACm, ACn∈Aw не пусто. Таким образом, на Aw могут
быть реализованы все операции алгебры AC.
34
В состав набора процедур согласования включим операции вычитания, слияния AC, а также операцию частичного обращения
AC, рассмотренную ранее [3].
Операция вычитания ADB=C состоит в том, что из исходной сети
A удаляются операторы, генерирующие одноименные вычисляемые
переменные сетей A и B, а также операторы конусов вычислимости
этих переменных за исключением операторов, генерирующих переменные, которые являются входными для сети B, являются аргументами оставшихся в сети A операторов или имеют статус критериальных (рис. 18). Вместе с операторами удаляются их выходные
переменные. В результате обеспечивается взаимная однозначность
B и результирующей сети C. Область определения операции – правильные AC с однозначным именованием переменных.
Операция слияния A ∞ B = C включает операцию объединения
AC с процедурой коррекции не-циклов (рис. 19). Слияние выполняется над AC, в которых однозначное вычисление переменных обеспечено, например, с помощью операции вычитания. В слитой сети
выполняется коррекция не-циклов. Особенность процедуры коррекции не-циклов состоит в ее неоднозначности, поскольку статус
переменной состояния может быть присвоен различным переменным контура. Рассмотрим AC, показанную на рис. 20. Сеть синтаксически некорректна, так как содержит два пересекающихся цикла
(операторы 1, 2, 3, 5 и 1, 2, 4, 5), но в составе операторов сети нет
задержки. На сети возможны четыре варианта коррекции путем постановки одного оператора задержки в разрыв переменной x1 (оператор 6), переменной x2 (оператор 7), переменной x3 (оператор 8) или
двух операторов в разрыв переменных x4 и x5 (операторы 9 и 10). Эти
варианты соответствуют различным и не эквивалентным между
х1
х2
1
4
х8
2
х5
х1
х12
х4
3
х10
8
х18
х11
10
9
х6
х1
х10
х6
1
х9
х14
5
11
х15
12
∆t
х4
х7
8
х18
х10
7
х3
х16
х6
6
х7
∆t
7
A
В
С
Рис. 18. Операция вычитания С=АDВ
35
х7
х3
х2
х3
х1
↑
х4
х8
х14
х5
х6
х6
exp
х13
х9
х12
х11
х10
А
х2
х1
х3
х4
В
х14
х5
exp
х6
↑
х9
х7
х13
х8
х12
х11
х10
С=А∞ В
Рис. 19. Операция слияния алгоритмических сетей С=А∞В
х2
2
1
7
х3
3
8
6
9
х5
10
х1
5
х4
4
Рис. 20. Варианты корректировки циклов на АС
собой по виду и порядку разностным моделям имитируемого процесса. В связи с этим предусматриваются два режима коррекции
не-циклов – автоматический и интерактивный. В автоматическом
режиме статус переменной состояния получает та переменная (например, переменная x1), которая замкнула не-цикл при слиянии
36
сетей. Коррекция состоит в разрыве переменной x1, объявленной
переменной состояния цикла, включении оператора задержки в место разрыва, переименовании на сети его входной переменной в xе
с учетом однозначности именования переменных в базе. В интер- активном режиме первоначально происходит полное замыкание
дуг, затем выполняется проверка комплексной сети на наличие нециклов. Пользователь получает информацию о переменных, входящих в каждый из не-циклов, определяет состав переменных состояния и включает процедуру коррекции циклов.
Область определения операции слияния – множество AC с однозначно вычисляемыми переменными. Если A и B – взаимно неоднозначные сети, то сети A и BDA – однозначны, и между ними возможна операция слияния C =A∞(BDA), удовлетворяющая правилам
A∞(BDA) = B∞(ADB);
ADBDC = AD (B∞(CDB)).
На множестве алгоритмически неоднозначных сетей может
быть организована итерационная процедура, включающая операцию вычитания для устранения неоднозначности вычисления
переменных и операцию слияния. Конечный результат процедуры
зависит от порядка слияния сетей:
S1 = A∞(ADB);
S2 = S1∞(CDS1);
............
Sn = Sn–1∞(KDSn–1),
высший приоритет здесь имеет сеть A, которая целиком включается в объединенную сеть, далее приоритеты сетей соответствуют
порядку их слияния.
Операции вычитания и слияния применимы к любым правильным AC из области определения, их результатом также будут правильные AC. В работе [3] доказана теорема, подтверждающая это
утверждение, и приведены алгоритмы выполнения операций.
4.2. Процедуры согласования AC и формирование
«белой» базы фрагментарных моделей
Процедура согласования AC моделей некоторой предметной области и построение «белой» базы могут быть выполнены путем последовательного применения над множеством фрагментарных AC
37
двух операций: вычитания – для устранения неоднозначности вычисления переменных и затем слияния – с устранением не-циклов.
Однако формальное применение этих операций может вызвать потерю информации о предметной области или получении результатов,
не имеющих смысловой интерпретации в рамках решаемой задачи.
Наиболее просто задача согласования фрагментарных моделей
решается при их парном переборе. Однако для того чтобы не нарушить целостность базы как модели предметной области, перебору
должен предшествовать анализ фрагментарных моделей с присвоением всем одноименным переменным статуса критериальных. Это
позволит сохранить связывающее базу множество переменных при
выполнении операции вычитания над фрагментами. Напомним,
что операция вычитания наряду с устранением неоднозначно вычисляемой переменной xi удаляет переменные и операторы, образующие конус вычислимости xi. В число удаляемых при этом могут
войти переменные, которые используются для организации счета
в других моделях, т. е. являются общими переменными при иных
парных комбинациях фрагментов. В результате предварительной
отметки любая общая переменная моделей базы получает статус
критериальной и не подлежит удалению при выполнении операции вычитания. При этом на AC сохраняются также переменные и
операторы конусов вычислимости помеченных переменных.
Проанализируем причины возникновения несогласованности
фрагментарных моделей «серой» базы. Примем, что модели базы
представлены правильными AC, соответствуют одинаковому уровню детализации предметной области и имеют общий временной
шаг счета. Последовательность вычисления переменных в моделях
может соответствовать последовательности событий в реальных
объектах предметной области, будем называть такие модели каузально ориентированными. Если направление вычислений противоположно последовательности событий, то модели будем называть
инверсно ориентированными. Модели с одинаковой ориентацией
вычисления общих переменных будем называть каузально (или
инверсно) согласованными.
Неоднозначность в согласованных моделях связана с повторным вычислением в моделях одной и той же переменной по одинаковым или различным алгоритмам. Такая ситуация вполне может
возникнуть, если фрагментарные модели базы разрабатываются
независимо. Для устранения неоднозначности требуется отобрать
подходящую модель и удалить из другой общие компоненты с помощью операции вычитания C=ADB.
38
Если неоднозначность возникла из-за несогласованности направления вычисления переменной в анализируемых моделях, то
естественный способ ее устранения будет состоять в обращении одной из AC и переводе неоднозначно вычисляемой переменной в ней
из подмножества вычисляемых в подмножество входных. Инвертирование направления вычислений переменных диктуется, как
правило, соображениями прагматики. Так, в каузально ориентированной модели летательного аппарата отклонение руля поворота
на некоторый угол приведет к движению по определенному радиусу. Если радиус поворота аппарата задан, то необходимое отклонение руля в общем случае может быть найдено методом подбора.
В модели, инвертированной относительно переменных «положение руля поворота – радиус вращения аппарата», угол отклонения
руля для заданного радиуса вращения находится непосредственно
по заданному радиусу вращения без использования процедур подбора. Однако возможности обращения сложных алгоритмических
моделей весьма ограничены, кроме того, обращенная модель утрачивает универсальность. По этим причинам при формировании
«белой» базы мы будем стремиться к каузальной согласованности
фрагментарных моделей. Если по каким-либо причинам желательно сохранить инверсность вычисления переменных, то процедура
частичного обращения может быть применена к каузально ориентированным фрагментам. Успех такой операции не гарантирован,
в то время как у каузально согласованной модели есть в большинстве случаев прецедент – это реальный объект моделирования.
Вторая проблема, которая может возникнуть в результате каузальной рассогласованности фрагментарных моделей, – это потеря
вычислимости, когда вычисляемая переменная в результате обращения получает статус входной. При этом AC комплексной модели
может быть формально правильной, но неприемлемой для решения
поставленных задач. Восстановление вычислимости производится
также методом обращения. Альтернатива – сохранение статуса переменной как входной, если это допустимо.
Таким образом, центральной при устранении неоднозначности
вычислений является задача определения каузальной ориентированности AC фрагментарных моделей. Для решения этой задачи
будем использовать граф причинно-следственных связей событий
предметной области, накрываемых разрабатываемой комплексной
моделью. Будем отождествлять вычисление переменных AC, имеющих содержательную интерпретацию в терминах предметной области, с событиями на графе причинно-следственных связей. Опери39
руя с графом причинно-следственных связей, будем использовать
термин «переменная», подразумевая под этим событие, заключающееся в вычислении указанной переменной. Соответственно, список переменных – это последовательность событий по вычислению
переменных списка. Потребуем, чтобы алфавит событий графа и
переменных базы моделей был общим.
Для решения задачи согласования фрагментарных моделей достаточно иметь сокращенный граф, вершины которого отождествлены с фрагментарными моделями.
Отметим, что граф причинно-следственных связей строится на основе семантической информации о процессах в моделируемой предметной области, включая блок-схемы, временные диаграммы, данные
экспертов, натурных экспериментов и т. п. База фрагментарных моделей при этом служит «шаблоном» для упрощения структуры графа,
но не средством для определения последовательности событий на нем.
Для установления каузальной ориентированности анализируемых моделей использован аппарат несимметричной временной логики с точечными событиями [14]:
R0(x, y) – событие x происходит одновременно с y;
R1(x, y) – событие x происходит раньше y;
R2(x, y) – событие x происходит не раньше y.
Если переменная y вычисляется на основе x, то эти события связаны отношением R1(x, y). Для ярусно-параллельного плана вычислений операторов AC подобное отношение справедливо лишь для событий, принадлежащих разным ярусам. Выявление каузальной ориентированности AC состоит в сравнении последовательности вычисления переменных на AC с цепочками событий CTj, соответствующими
их причинно-следственной зависимости на графе причинно-следственных связей. Для построения цепочек CTj анализируем исходный
граф причинно-следственных связей. При наличии циклов выполняем их разрыв, условно вводя на графе события-состояния. В результате получаем древовидный граф, основаниями которого служат входные события и события-состояния. Для древовидного графа строится
полное множество путей от оснований графа к вершинам. Каждому
пути соответствует цепочка событий CTj ,  CTj = CT, j = 1, s; s – обj
щее количество путей на графе. Любые две переменные пути всегда
связаны соотношением R1(x, y), если событие x на пути предшествует
y, или R1(y, x), если y предшествует x.
Пусть уk – общая вычисляемая переменная сетей A и B; X1 и
Z1 – множества переменных сети A, входящих соответственно в ко40
нус и дерево вычислимости для yk; X2 и Z2 – множества переменных сети B, входящих в конус и дерево вычислимости для уk (см.
подразд. 1.3). Для сетей A и B всегда справедливы соотношения
R1(X1, yk), R1(yk, Z1), R1(X1, Z1);
R1(X2, yk), R1(yk, Z2), R1(X2, Z2).
Выполним проверку данных соотношений на цепочках переменных CTj∈CT. Если выполняется условие
(∀x∈X)(∀z∈Z)(∀CTj∈CT)[(x, z∈CTj → R1(x, z))&
&(x, yk∈CTj → R1(x, yk)) & (yk, z∈CTj → R1(yk, z))],
то соответствующая АС каузально ориентирована. Если условие выполняется при перестановке порядка переменных в соотношениях
R1, то AC инверсно ориентирована. В противном случае имеет место
частичное инвертирование причинно-следственных отношений.
При инверсии делается попытка частичного обращения AC одной из моделей для устранения неоднозначности вычисления переменных или восстановления вычислимости. Если операция обращения не может быть выполнена, то проводится ручная модификация сети.
В согласованных AC корректировка неоднозначности вычисления переменных выполняется путем удаления тех фрагментов
сети, которые служат для повторного вычисления общих переменных. Находятся разности:
ADB = C1, BDA = C2, ADC1 = C3, BDC2 = C4,
где C1 и C2 – фрагменты сетей (A или B), из которых удалены общие вычисляемые переменные и конусы их вычислимости; C3
и C4 – удаляемые из моделей фрагменты. Если C3 = C4, то имеет
место тавтология – сети A и B содержат совпадающие части. При
тавтологии общая часть устраняется в одной из моделей с помощью
вычитания и в базе моделей выполняется замена:
< A, B > ⇒ < A, C2 > или, что равноценно, < B, C1 >.
Если C3 ≠ C4, то сети A и B алгоритмически неоднородны, одноименные переменные рассчитываются в них различным способом.
Если предпочтителен алгоритм расчета, примененный в модели A,
то выполняется замена моделей < A, B > на < A, C2 >, в противном
случае – замена на < B, C1 >.
Корректировка не-циклов выполняется с использованием операции слияния AC, представленной в подразд. 4.1.
Последовательность процедур согласования фрагментарных моделей базы приведена на рис. 21. Согласование выполняется путем
41
Исходная «серая» база
фрагментарных моделей
Выявление одноименных переменных моделей
и присвоение им статуса критериальных
Построение древовидного графа
причинно-следственных связей
Корректировка неоднозначности вычисления переменных фрагментарных
моделей и потери вычислимости переменных при парном переборе фрагментов.
1. Проверка ориентированности вычисления переменных АС с учетом
последовательности событий на графе причинно-следственных связей.
2. АС казуально не согласованы.
Устранение неоднозначности и потери вычислимости переменных путем
частичного обращения АС.
3. АС казуально согласованы.
Устранение неоднозначности с помощью операции вычитания
Слияние АС фрагментарных моделей базы
для выявления и коррекции не-циклов.
Пополнение АС фрагментов операторами задержки
с введением переменных состояния
Согласованная «белая» база фрагментарных моделей
Рис. 21. Последовательность процедур согласования
фрагментарных моделей
парного перебора моделей, определения каузальной направленности вычисления переменных, коррекции неоднозначности и потери вычислимости, коррекции не-циклов. Процедуры алгоритма
частично автоматизированы, но в общем случае выполняются в
диалоговом режиме. В результате взаимного согласования моделей
формируется «белая» база фрагментарных моделей предметной области. Модели в ней представлены правильными AC, помимо этого
модели удовлетворяют условиям взаимной однозначности вычис42
ления переменных и полноты переменных состояния. Таким образом, на полученном множестве моделей могут быть реализованы
все операции алгебры AC.
4.3. Пример согласования и комплексирования
фрагментарных моделей
Рассмотрим задачу моделирования агроэкосистемы, расположенной на водосборе озера. Блок-схема моделируемой системы показана на рис. 22. В состав системы входят животноводческая ферОбщий
прирост
биомассы
Численность
закупаемых
животных
x 12
x11
Конечный
вес
животных
x15
Животноводческая
ферма
x10
Жидкие
стоки
Органические
удобрения
Начальный
вес животных
Кормовые
корнеплоды
x1
x18
x7
Очистные
сооружения
x19
x22
x23
Жесткая
фракция
стоков
Поле
Минеральные
удобрения
Стоки с полей
x3
Вынос
фосфора x26
с речным
стоком
Озеро
x27
Очищенные
стоки
Захоронения
фосфора в донных
отложениях
Рис. 22. Блок-схема модели агроэкосистемы
43
ма по доращиванию телят, поле для производства кормов, очистные
сооружения, озеро. Ферма ежегодно закупает x11 голов молодняка
весом x10, выкармливает его в течение года и затем реализует. Вес
животных после доращивания равен x15, общий прирост биомассы
выкармливаемых животных равен x12. Животные откармливаются корнеплодами x7, которые выращиваются на поле, расположенном в пределах водосбора озера. Навоз с фермы x18 используется в
качестве удобрения, жидкие стоки x19 проходят систему очистки.
Собранная в очистных сооружениях органика x22 также используется в качестве удобрений, очищенные стоки x23 поступают в озеро.
Органические удобрения с фермы и с очистных сооружений предварительно накапливаются и вносятся в почву под урожай следующего года. Кроме органических для выращивания корнеплодов используются минеральные удобрения x1. Удобрения, поступившие
на поля, частично используются растениями в процессе вегетации
x7, частично смываются с полей в озеро x2, остаток x8 накапливается в почве. Будем считать, что продукционные процессы в озере
и в поле лимитируются фосфором. Концентрация фосфора в озерной воде зависит от его поступления с водными стоками очистных
сооружений и стоками с полей, выноса фосфора с речными водами
x26 и его захоронения в донных отложениях озера x27. Концентрация фосфора в озерной воде определяет интенсивность внутриводоемных продукционных процессов – трофический статус озера.
С увеличением концентрации фосфора качество воды как питьевого ресурса снижается. Рыбная продуктивность озера первоначально возрастает, однако при высокой концентрации фосфора резко
падает. Модель агроэкосистемы может служить для обоснования
стратегии развития хозяйственной деятельности на водосборе в зависимости от целей использования ресурсов озера (как источника
питьевой воды, рыбохозяйственного водоема и т. п.).
Доля фосфора в биомассе кормовых корнеплодов, теле животных, неассимилированной пище определяется известными стехиометрическими соотношениями. Таким образом, переход в переменных модели от единиц фосфора в биомассе к единицам биомассы,
как и обратный переход, выполняется путем умножения на некоторый постоянный коэффициент. Это позволяет выбрать в качестве
моделируемой субстанции общий фосфор (органический и минеральный в сумме) или использовать смешанные единицы измерения (общая масса – масса фосфора). Переменные x10, x12, x15, x18,
x19 представлены в единицах массы, переменные x1, x7, x22, x23,
x26, x27 – в единицах фосфора.
44
Будем считать, что в базе моделей имеются модели отдельных
компонент агроэкосистемы – пόля, животноводческой фермы,
очистных сооружений, экосистемы озера (рис. 23, а – г). Модели
k4
a)
x1
x18
k1
x5
x2
x20
x4
x3
min
x6
x28
x22
z1
x8
∆t
x7
x11
x10
б)
k2
x7
k4
x13
x15
x14
x12
k3
x9
x16
k5
x17
k3
x18
k5
в)
x19
x21
k6
x21 x19
x19
x22
x23
k7
x23
г)
x19
x3
x26
x27
z2
x25
∆t
Рис. 23. Алгоритмические сети фрагментарных моделей
агроэкосистемы: а – поле; б – ферма; в – очистные сооружения; г – озеро
45
представлены в форме AC и имеют общий алфавит переменных.
Соответствие содержательных именований основных переменных
и принятой на AC кодировки приведено в описании функционирования агроэкосистемы. Символами k1–k8 обозначены постоянные
входные коэффициенты.
Укрупненный граф причинно-следственных связей моделируемой агроэкосистемы (рис. 24) отражает естественный ход событий
в системе:
– формирование минерального состава почвы на начало вегетации с учетом внесенных удобрений и их смыва в озеро;
– выращивание корнеплодов, сопровождающееся потреблением
фосфора из почвы;
– откармливание телят корнеплодами, сопровождающееся ростом их биомассы и накоплением неассимилированной органики;
– очистка жидких стоков c фермы;
– использование навоза с фермы и органики с очистных сооружений в качестве удобрений для выращивания корнеплодов;
– формирование трофического статуса экосистемы озера с учетом баланса по фосфору.
Запас фосфора
Минеральные в почве
удобрения
z1
Органические
удобрения
x18
x1
x7
ПОЛЕ
Кормовые
корнеплоды
Прирост
биомассы
x12
ФЕРМА
x22
x3
Жесткая
фракция
стоков
Сток
с полей
z2
Запас
фосфора
в озере
Очищенные
стоки
x26
Вынос
фосфора
с речным
стоком
x27
Жидкие x
19
стоки
ОЗЕРО
x23
ОЧИСТКА
Захоронение фосфора
в донных отложениях
Рис. 24. Граф причинно-следственных связей агроэкосистемы
46
Данная последовательность событий будет циклически повторяться. В качестве временного интервала счета моделируемой агроэкосистемы примем годовой шаг.
Выполним согласование фрагментарных моделей для построения модели агроэкосистемы в соответствии с процедурами (см. подразд. 4.2).
1. Формирование множества критериальных переменных фрагментарных моделей базы.
Критериальными являются общие переменные фрагментарных
моделей базы (см. рис. 23): <x3, x7, x18, x19, x21, x22, x23 >. Здесь
x21 – количество фосфора в жидких стоках.
2. Формирование древовидного графа причинно-следственных
связей агроэкосистемы и составление множества путей на графе.
Переход от циклического графа (см. рис. 24) к древовидному
выполняем с помощью разрыва циклов по переменным состояния.
На исходном графе существует 4 цикла – петля переменной остаточного фосфора в почве (x8) при вершине ПОЛЕ, петля переменной остаточного фосфора в озере (x25) при вершине ОЗЕРО, циклы
переменных <кормовые корнеплоды–органические удобрения> и
<кормовые корнеплоды–жидкие стоки–органика очистных сооружений> (переменные x7–x18 и x7–x19–x22 соответственно). Разрыв
петель x8 и x25 выполняется однозначно, переменным состояния
присваиваем имена z1 и z2. Для разрыва оставшихся циклов будем
учитывать, что органические удобрения с фермы и с очистных сооружений накапливаются в течение года (шага счета в модели),
затем вносятся в почву и используются растениями. Таким образом, разрыв циклов должен проходить по переменным x18 и x22.
Переменным состояния присвоим имена z3 и z4. В результате разрыва циклов по переменным состояния получим древовидный граф
(рис. 25). Корневые переменные графа – переменные состояния z1,
z2, z3, z4 и входная переменная x1. Полное множество путей древовидного графа соответствует следующему списку:
(z1, z3, z4, x1), x7, x18;
(z1, z3, z4, x1), x7, x12;
(z1, z3, z4, x1), x7, x19, x22;
(z1, z3, z4, x1), x7, x19, x23, x25;
(z1, z3, z4, x1), x7, x19, x23, x26;
(z1, z3, z4, x1), x7, x19, x23, x27;
(z1, z3, z4, x1), x3, x25;
47
(z1, z3, z4, x1), x3, x26;
(z1, z3, z4, x1), x3, x27;
z2, x25;
z2, x26;
z2, x27.
3. Проверка однозначности вычисления переменных.
Проверку выполняем путем сравнения статуса одноименных
переменных фрагментарных моделей базы при парном переборе
моделей. Из сравнения моделей «Поле» и «Ферма» видно, что переменная x7 вычисляется как в первой, так и во второй модели, и
ее значение может быть неоднозначным. Для моделей «Ферма» и
«Очистной комплекс» общей вычисляемой переменной является
переменная x21. Для других пар моделей условие однозначности
вычисления общих переменных сетей не нарушается. Так, модели
«Поле» и «Экосистема озера» имеют общую переменную x2. Эта
переменная вычисляется в модели «Поле» и служит входной для
модели «Экосистема озера».
4. Проверка потери вычислимости переменных.
Для этой цели формируется множество переменных – претендентов на статус входных комплексной модели. Это множество образуют входные переменные фрагментарных моделей за вычетом
переменных, вычисляемых на других моделях базы. Переменная из
x1
z1
x8
x 12
x7
z3
x 18
z4
x 19
x3
x 22
z2
x 25
x 26
x 23
x 27
Рис. 25. Древовидный граф причинно-следственных связей
агроэкосистемы
48
множества вычислимых по блок-схеме модели агроэкосистемы (см. рис. 22), попавшая в множество претендентов, теряет вычислимость.
Восстановить вычислимость можно путем обращения AC. Если обращение невозможно, модель должна быть модифицирована.
Для фрагментарных моделей агроэкосистемы полное множество
входных переменных
<x1, x3, x5, x10, x11, x15, x18, x19, x22, x23, x28>;
множество переменных – претендентов на входные для комплексной модели
<x1, x5, x10, x11, x15, x28>;
множество вычисляемых переменных по блок-схеме (см. рис. 22)
<x3, x12, x15, x18, x19, x22, x23, x26, x27>.
Из сравнения множеств видно, что потеряла вычислимость переменная x15.
5. Определение каузальной ориентированности неоднозначно
вычисляемой переменной x7.
Определяем каузальную ориентированность вычисления переменной x7 в моделях «Поле» и «Ферма» с учетом порядка событий
графа причинно-следственных связей. На модели «Ферма» конус
вычислимости переменной x7 – это <x9, x16, x12, (x13, x14), (x10, x11,
x15)>, дерево вычислимости пусто. Таким образом, переменные x7
и x12 связаны соотношением R1(x12, x7). На множестве путей древовидного графа причинно-следственных связей находим путь, содержащий события x7 и x12: <(z1, z3, z4, x1), x7, x12>. Сравнив последовательность событий пути и порядок вычисления переменных
на AC, получим <(z1, z3, z4, x1), x7, x12> → R1(x7, x12), что противоположно порядку вычисления отмеченных переменных на AC модели «Ферма». Для переменной x7 на модели «Поле» конус вычислимости <(x6, (x5, x28)), x4, (x2, x3), (x1, x20, x22, z1), x18>, дерево
вычислимости также пусто. Из этой последовательности следуют,
в частности, соотношения R1(x1, x7) и R1(z1, x7). Сравнивая путь на
графе причинно-следственных связей, содержащий события x1, z1 и
x7, с порядком вычисления переменных на AC, получим
<(z1, z3, z4, x1), x7> → R1(R0(z1, x1), x7).
Таким образом, порядок вычисления переменной x7 в модели
«Поле» ориентирован каузально, в модели «Ферма» – инверсно. Для
корректировки неоднозначности вычисления переменной x7 может
быть использовано частичное обращение AC одной из моделей.
49
6. Устранение неоднозначности вычисления переменной x7.
Устранение неоднозначности будем выполнять путем обращения AC модели «Ферма». Переменная x7 в ней вычисляется инверсно относительно направления причинно-следственных связей, а по
переменной x15 имеет место потеря вычислимости. Попытаемся обратить операторы по цепочке переменных <x15, x14, x12, x16, x9,
x7>. Все операторы на этом пути обратимы (см. подразд. 3.2). AC,
полученная в результате обращения, показана на рис. 26. На сети
переменная x7 имеет статус входной, а x12 – выходной, что одновременно устранило неоднозначность вычисления первой переменной и потерю вычислимости второй.
7. Определение каузальной ориентированности неоднозначно
вычисляемой переменной x21.
Определяем каузальную ориентированность вычисления переменной x21 в моделях «Ферма» (скорректированный вариант –
рис. 26) и «Очистные сооружения». Конус вычислимости переменной x21 в модели «Ферма» – это <x19, x18, x17, x9, x7>, дерево вычислимости пусто. Отсюда следует, в частности, R1(x19, x21), R1(x7,
x19). Анализируя пути на графе, получим <(z1, z3, z4, x1), x7, x19,
x22> → R1(x7, x19), т. е. порядок вычисления x19 каузально ориентирован. Относительно x21 такого заключения нельзя сделать.
В модели «Очистные сооружения» конус вычислимости переменной x21 – это <x19>, дерево вычислимости <(x22, x23)>. Отсюда
следует R1(x19, x21), R1(x21, x22), R1(x21, x23). Сравнивая эти соотношения с путями на графе
<(z1, z3, z4, x1), x7, x19, x22> и <(z1, z3, z4, x1), x7, x19, x23, x25>,
x 11
x 10
k4
k2
x7
x 13
k3
x 14
x 15
x 12
x9
x 16
k5
x 17
k3
x 19
x 24
x 21
x 18
Рис. 26. Обращенная относительно переменных x7–x15
алгоритмическая сеть модели «Ферма»
50
видим, что соотношения справедливы и вычисление переменной
x21 каузально ориентировано. Полученный результат позволяет
сделать заключение, что порядок вычисления пары переменных
x19 и x21 в модели «Ферма», удовлетворяющий условию R1(x19,
x21), также каузально направлен. Таким образом, неоднозначность
вычисления переменной x21 должна устраняться здесь с использованием операции вычитания AC.
Рассмотрим, как определяется каузальная направленность вычисления x21 на исходной (не обращенной) модели «Ферма» (см.
рис. 23). Конус вычислимости переменной x21 – это <x19, x18, x17,
x9, x16, x12, (x13, x14), (x10, x11, x15)>, дерево вычислимости пусто.
Отсюда следует, в частности, R1(x19, x21). Анализ путей на графе
причинно-следственных связей не позволяет идентифицировать
каузальную направленность вычисления переменной x21. Это связано с инверсностью порядка вычисления в модели переменных x7
и x12.
Доказательство каузальной направленности порядка вычисления переменных x19 и x21 в модели «Очистные сооружения» (см.
ранее) позволяет сделать вывод, что порядок вычисления пары переменных x19 и x21 в модели «Ферма», удовлетворяющий условию
R1(x19, x21), также каузально направлен. Таким образом, результат не изменился. Неоднозначность вычисления переменной x21
должна устраняться с использованием операции вычитания AC.
8. Корректировка неоднозначности вычисления переменной x21.
Обозначим для сокращения A – модель «Ферма», В – модель
«Очистные сооружения». Выполним вычитание ADB=C1, BDA=C2,
ADC1=C3, BDC2=C4. Фрагменты сетей C3 и C4, участвующие в расчете общих переменных, совпадают (проверить это!). При корректировке сохраняем неизменной модель «Очистные сооружения»,
AC модели «Ферма» заменяем разностью Ă=ADB.
9. Коррекция не-циклов.
В результате слияния фрагментарных моделей на AC комплексной модели (рис. 27) возникает 2 не-цикла, образованных цепочками переменных <x2, x3, x4, x7, x9, x17, x18, x20, x2> и <x2, x3, x4,
x7, x9, x17, x19, x21, x22, x2>. Разрыв циклов выполним по переменным x18 и x22 с учетом аналогичных действий на графе причинно-следственных связей. Подставим в разрыв переменных операторы задержки и присвоим выходным переменным операторов
(переменным состояния) имена z3 и z4. Добавленные элементы AC
показаны на рис. 27 пунктиром. В результате проделанных процедур получим правильную AC комплексной модели агроэкосистемы
51
z4
x18
∆t
z3
k4
x1
x22
k1
x2
x20
∆t
x5
x4
x3
min
x6
x28
x7
z1
∆t
x8
x11
x10
x14
x13
k3
k4
x15
x12
x9
x16
k2
x17
k3
x18
k6
k5
x19
x22
x21
x23
k7
x26
x24
x3
z2
∆t
x25
x27
Рис. 27. Алгоритмическая сеть комплексной модели агроэкосистемы
(см. рис. 27). Множество моделей, образованное путем сегментации
данной сети, образует «белую» базу моделей, для которой справедливы правила алгебры AC (см. разд. 3).
52
5. ФОРМАЛИЗАЦИЯ ГРАФИЧЕСКОГО ВВОДА
АЛГОРИТМИЧЕСКОЙ СЕТИ
Для реализации возможности строить АС в создаваемых программных комплексах потребовалась формализация технологии
ввода и синтаксиса графического представления АС.
В данном разделе описывается технология создания АС при графическом вводе. Выбираются объекты, описывающие графическое
представление АС, дается определение графического представления. Рассматриваются графический ввод и блочно-фрагментарная
технология ввода АС. На основе предложенной технологии ввода
предлагаются правила графического синтаксиса [15, 16].
5.1. Технология создания АС при графическом вводе
Рассмотрим объекты (графические примитивы), описывающие
графическое представление АС [15, 16].
Знак оператора p. Данный объект характеризуется соответствующими ему операцией O и координатами (x, y):
p::= <O, (x, y)>.
Областью знака оператора Area(p) называется замкнутая область, равная описанному вокруг знака оператора квадрату со
сторонами, параллельными осям координат (на рис. 28 указаны
пунктиром). Размером знака оператора называется радиус окружности, вписанной в область знака оператора.
В алгоритмическом базисе (см. табл. 1) применяются знаки операторов с формой круга и ромба. В принципе, знаком оператора может быть любой графический образ, ограниченный областью знака
оператора.
Связь знака оператора с дугами может осуществлять только в
точках возможных связей (на рис. 28 помечены жирными точками). Количество таких точек зависит от принятых соотношений
размеров знака операторов и стрелок на окончаниях дуг. Будем далее считать, что знак оператора имеет 8 точек возможных связей.
+
=0
Рис. 28. Знак оператора
53
Простая дуга q в общем случае представляет собой ломаную,
имеющую начало и конец (рис. 29).
Простая дуга состоит из трех частей (рис. 30): E(q) – окончание
дуги, B(q) – тело дуги, S(q) – начало дуги.
Начало дуги характеризуется соответствующими ему координатами (xS, yS).
Тело дуги, в свою очередь, состоит из отрезков; точками разделения B(q) на отдельные отрезки являются точки излома тела дуги.
Каждый отрезок характеризуется координатами своих относительно граничных точек (x1, y1) и (x2, y2). Можно ввести координатное
множество тела простой дуги q, характеризующее его расположение:
A=
N
 {(x1j , y1j ),(x2j , y2j )},
j=1
где N – число отрезков, составляющих тело простой дуги.
Окончание дуги характеризуется соответствующими ему координатами (xE, yE). Выполняются соотношения
(x11, y11)=(xS, yS) и (x2N, y2N)=(xE, yE).
Рис. 29. Примеры простых дуг
y
yS
S(q)
B(q)
E(q)
y1i
yE
y2i
0
xE
x2i
x1i
xS
Рис. 30. Структура простой дуги
54
x
Полностью однозначно описать расположение дуги можно с помощью
q::= <(xS, yS), A, (xE, yE)>
(достаточно указать координаты либо начала, либо окончания).
Областью простой дуги Area(q) называется замкнутая область,
занимаемая телом простой дуги (с учетом толщины отрезков).
Простая дуга может быть входной для АС, выходить из оператора АС (при этом соответствовать вычисляемой или выходной переменным АС) или выходить из другой дуги АС.
Простые дуги АС можно классифицировать по типу начала
Type[S(q)]:
1-й тип – начало дуги совпадает со знаком оператора;
2-й тип – начало дуги является точкой ветвления сложной дуги;
3-й тип – все остальные дуги.
В процессе построения АС тип начала дуги может изменяться.
В случае, когда одна простая дуга выходит из другой, они соединяются в сложную дугу (рис. 31). Точка соединения называется
ветвлением сложной дуги. Число окончаний сложной дуги равно
числу простых дуг, составляющих ее; начало же сложной дуги
единственно и совпадает с началом той простой дуги, которая не
выходит ни из одной другой.
Веткой сложной дуги будем называть часть тела простой дуги
в составе сложной, началом которой является ближайшее к концу
данной дуги ветвление. В случае простой дуги ветка простой дуги
совпадает с телом простой дуги. Пример веток дуги см. на рис. 32
(отмечены жирным шрифтом).
Стволом сложной дуги будем называть часть тела простой дуги
в составе сложной, начало которой совпадает с началом сложной
дуги, а концом является ближайшее к началу ветвление. В случае
простой дуги ствол простой дуги совпадает с телом простой дуги.
Пример ствола см. на рис. 32 (отмечен пунктиром).
Рис. 31. Пример сложной дуги
Рис. 32. Структура сложной дуги
55
Метка переменной x характеризуется соответствующим ей именем N (состоит из короткого и длинного имен), статусом видимости
имени V (видны короткое и длинное имена, только короткое или
длинное, оба имени невидимы) и координатами (x, y):
x::= <N, (x, y), V>.
Областью метки переменной Area(x) называется замкнутая область, границей которой является описанный вокруг видимого
текста метки прямоугольник со сторонами, параллельными осям
координат.
Координаты (x, y) задают точку привязки текста метки. Это могут быть правый нижний угол, центр или какая-либо другая точка
области метки переменной.
Значок для разметки дуг s (специальные знаки, используемые
для разметки дуг в случае, когда соответствующий оператор некоммутативен либо имеет несколько выходных переменных). Данные
значки характеризуются своим типом T («крестики», «нолики») и
координатами (x, y):
s::= <T, (x, y)>.
Областью значка разметки Area(s) называется замкнутая область, границей которой является описанный вокруг значка квадрат со сторонами, параллельными осям координат.
Графическое представление АС
GV(АС)::= <P, Q, X, S, R>,
где P – множество знаков операторов; Q – множество простых дуг;
X – множество меток переменных; S – множество значков для разметки дуг; R = {r(o1, o2): o1∈O1, o2∈O2}, где O1, O2∈{P, Q, X, S} –
множество различных графических отношений между элементами
множеств P, Q, X и S, удовлетворяющих вводимым далее синтаксическим правилам:
∃ r(o1, o2): o1∈O1, o2∈O2, O1, O2∈{P, Q, X, S} ⇔ Area(o1) ∩ Area(o2) ≠ ∅.
Ввод АС осуществляется так, что множества P, Q, X и S вводятся явно – данные множества вводятся поэлементно. Отношения R
вводятся при этом параллельно с ними неявно.
Графический ввод или графическое построение АС включают:
– ввод графических элементов;
– изменение атрибутов графических элементов;
– удаление графических элементов;
– завершение работы.
56
Ввод графических элементов.
Возможен ввод знаков операторов, простых дуг, меток переменных и значков разметки.
Знаки операторов и простые дуги могут вводиться в произвольной
последовательности. Однако удобнее наносить сначала знаки операторов, а потом соединять их дугами, в этом случае при промежуточном построении получаются конструкции, по которым легче представить окончательный вид АС. Также возможно последовательное пристраивание к уже имеющемуся фрагменту дуг и знаков операторов.
Метки переменных соответствуют простым дугам, поэтому вводу
метки переменной должен предшествовать ввод соответствующей
дуги. Построение метки переменной xj осуществляется в два этапа:
1) указывается тело какой-либо дуги qi, которой будет соответствовать данная метка. Тем самым получаем начальное приближение для расположения текста метки;
2) вводится имя метки переменной и корректируется ее расположение таким образом, чтобы после нанесения текста не были
пересечены никакие графические объекты АС. При этом Area1 = = Area(xj) ∩ Area(qi) ≠ ∅, Area1⊂ Gr(Area(xj)), где Gr(Area(xj)) – граница области.
Отметим, что при построении АС вручную п. 1 осуществляется
неявно.
Ввод значков разметки возможен только после ввода размечаемых ими дуг и соответствующих знаков операторов. Значки наносятся на тела размечаемых дуг. Поскольку значки разметки используются для задания частичного порядка входных (выходных)
переменных операторов, то их расположение возможно только в
окрестности соответствующих операторов.
Возможные координаты выходного значка ×=(x, y) задаются
формулой
´= XS + ee,
где XS=(xS, yS) – координаты начала дуги; e – малый положительный параметр; e – единичный вектор, задающий направление дуги
в точке ее начала.
Возможные координаты входного значка ×=(x, y) задаются формулой
´= XE - ee,
где XE=(xE, yE) – координаты окончания дуги; e – единичный вектор, задающий направление дуги в точке ее окончания.
57
Прежде чем построить графический элемент, необходимо проверить возможность его построения – не нарушит ли построение
правил графического синтаксиса. Построение происходит только в
случае выполнения синтаксических правил.
Изменение атрибутов графических элементов.
Координаторы знака оператора указываются при его вводе.
В дальнейшем их изменение невозможно. Возможно изменение
только операции, соответствующей знаку оператора. Однако, например, число входных дуг у оператора сложения может быть
различным, а у логического оператора является фиксированным.
В результате изменение типа оператора со сложения на логический
при имеющемся числе входных дуг может оказаться недопустимым. Поэтому в целях исключения синтаксически недопустимых
конструкций проводится соответствующая проверка.
Расположение простой дуги задается при ее построении. Дальнейшее его изменение невозможно.
Для метки переменной возможно изменение всех атрибутов.
Возможность корректировки расположения вводится по причине
того, что после изменения имен и статуса видимости область, занимаемая выводимым текстом, может накладываться на другие
графические элементы. Перед изменением атрибутов метки переменной выполняется синтаксическая проверка. (Например, нельзя
изменить имя метки на имя, уже присвоенное какой-либо другой
дуге АС.)
Расположение и тип значка разметки задаются при его вводе, их
дальнейшее изменение невозможно.
После изменения атрибутов графического элемента осуществляется корректировка атрибутов связанных с ним элементов.
Удаление графических элементов.
Значки разметки связаны со знаком оператора. Поэтому удаление знака оператора влечет за собой удаление связанных с ним
значков разметки.
Метки переменных и значки разметки соответствуют простым
дугам. Поэтому удаление простой дуги влечет за собой удаление
связанных с ней меток переменных и значков разметки.
Удаление значка разметки само по себе невозможно.
После удаления графического элемента осуществляется корректировка атрибутов связанных с ним элементов.
Завершение работы.
Завершение работы возможно с выполнением общей синтаксической проверки АС и без таковой. В случае отказа от проверки АС счи58
59
Модель
пригодна
для расчета
Да
Выход
Метка переменной
Простая дуга
Проверка возможности
построения с точки зрения
графического синтаксиса
Да
Построение
графического
элемента
Значок разметки
Знак оператора
Ввод графического
элемента
1
X, Y, имя (короткое,
длинное), статус
видимости
Метка переменной
Корректировка атрибутов
зависимых графических
элементовв
Изменение
атрибута
Проверка возможности
изменения с точки зрения
графического синтаксиса
Да
Операция
Знак оператора
Изменение атрибутов
графического элемента
1
Значок
разметки
Простая дуга
Метка переменной
Значок
разметки
Знак оператора
Удаление
графического элемента
Рис. 33. Технология создания алгоритмической сети при графическом вводе
Модель
не пригодна
для расчета
Общая
синтаксическая
проверка
Завершение
работы
Графическое
построение АС
тается незаконченной и ее расчет невозможен. В случае удачной синтаксической проверки (т. е. все синтаксические правила выполнены)
модель является законченной и ее расчет возможен. Случай неудачной синтаксической проверки эквивалентен отказу от проверки.
Рассмотренная технология изображена на рис. 33.
5.2. Блочно-фрагментарная технология ввода АС
С помощью технологии, описанной в подразд. 5.1, предлагается
строить фрагментарные модели. Построенные модели имеют наглядное графическое представление, но процесс построения модели трудоемок, и размеры модели ограничены возможными границами восприятия.
Возможным подходом к созданию более крупных моделей является создание комплексных моделей на основе заранее подготовленной «белой» базы фрагментарных моделей. В разд. 4 были описаны процедуры, необходимые для создания «белой» базы. Данный
процесс является достаточно трудоемким, особенно в части программной реализации описанных процедур.
Поэтому необходима технология ввода АС, которая снимала бы
ограничения по размеру создаваемых АС, но была бы достаточно
проста в восприятии и программной реализации.
Рассмотрим требования к этой технологии:
1) модель должна иметь наглядное графическое представление;
2) возможность повторного использования фрагментов модели
(наличие средств дублирования уже созданных фрагментов модели);
3) возможность внесения изменений в фрагментарную модель,
входящую в слитую модель, без изменения комплексной модели;
4) процесс построения модели должен быть менее трудоемок;
5) размеры модели не должны быть ограничены реализацией системы (желательно расширение границ восприятия больших моделей).
Решением проблемы является блочно-фрагментарная технология ввода АС.
Вводятся два дополнительных типа операторов:
– оператор ссылки на другую модель;
– оператор ссылки на другую модель, считаемую со своим шагом
расчета (рассматривается также в разд. 6).
Модель строится по технологии, описанной в подразд. 5.1, но
под знаками оператора понимаются также знаки оператора ссылки
60
на другую модель. Поскольку нет никаких ограничений на графический образ знака оператора, знаку оператора можно сопоставить
соответствующую иконку. В результате сохраняется наглядное
графическое представление создаваемой модели.
Повторное использование фрагментов модели достигается за
счет возможности многократного включения моделей в комплексную модель с предварительным переименованием вычисляемых
переменных. В случае ссылки на модель со своим шагом расчета
переименовывать переменные не требуется.
Наличие средств дублирования уже созданных фрагментов моделей достигается за счет реализации операций над АС [13]. С точки зрения пользователя это выглядит как работа с буфером обмена:
1) копирование в буфер – выделение подграфа;
2) вырезание в буфер – выделение подграфа и разность АС;
3) вставка из буфера – объединение АС.
Возможность внесения изменений в фрагментарную модель,
входящую в комплексную модель, без изменения комплексной модели достигается за счет реализации наряду с технологией моделирования снизу вверх технологии сверху вниз.
1. Технология снизу вверх. Сначала строятся модели, которые будут включаться в комплексную модель. Затем строится комплексная
модель, ссылающаяся на уже построенные модели. Сначала детально
описываются функциональные отношения, связывающие переменные модели, затем описывается общая взаимосвязь блоков модели.
2. Технология сверху вниз. Сначала строится комплексная модель, ссылающаяся на еще не существующие блоки, которые будут
включаться в комплексную модель. Затем строятся модели, соответствующие используемым блокам. Сначала описывается общая
взаимосвязь блоков модели, затем детально описываются функциональные отношения, связывающие переменные модели.
3. Смешанная технология. Возможно чередование элементов
первой и второй технологий. Например, сначала строятся модели,
которые будут включаться в комплексную модель. Затем строится
комплексная модель, ссылающаяся на уже построенные модели.
После этого уже построенные модели, соответствующие блокам,
подвергаются дальнейшему изменению.
Для уменьшения трудоемкости создания моделей используется
также шаблонная технология ввода АС.
1. Оператор можно вводить путем последовательного ввода составляющих его графических элементов: знака оператора, дуг,
значков разметки, меток переменных.
61
2. Ввод максимальной формы оператора. Наряду со знаком оператора сразу же вводится максимально допустимое число связанных с
ним дуг и все необходимые значки разметки. Пользователю остается
проименовать при необходимости нужные дуги и удалить лишние.
3. Ввод минимальной формы оператора. Наряду со знаком оператора сразу же вводится необходимое минимальное число связанных с ним дуг и все необходимые значки разметки. Пользователю
остается достроить и проименовать необходимые дуги.
Поскольку включаемые в комплексную модель блоки можно
рассматривать как отдельные модели, технология работы приобретает свойство многомодельности. При этом возможна работа как с
логически связанными, так и с независимыми моделями.
За счет перечисленного ряда факторов процесс построения модели становится менее трудоемким, и возможно расширение границ
восприятия больших моделей за счет использования блоков.
5.3. Правила графического синтаксиса
Различаются два вида отношений: недопустимые (запрещенные
отношения между объектами) и допустимые (отношения между
объектами, которые могут быть разрешены). Разрешение или запрет допустимых отношений зависит от отношений с другими объектами. Запрет отношений задает ограничения на возможные взаимные расположения графических элементов.
Недопустимость тех или иных отношений порождается тремя
различными причинами:
1) необходимостью обеспечить возможность интерпретации введенных конструкций как математического объекта (1-й тип недопустимых отношений);
2) принятой технологией построения АС (2-й тип);
3) желанием обеспечить хорошее визуальное восприятие вводимой АС (3-й тип).
Рассмотрим всевозможные варианты отношений r(o1, o2) между
элементами o1∈O1 и o2∈O2, где O1, O2∈{P, Q, X, S} [16, 17] (табл. 2).
Строки в таблице соответствуют элементам o1, столбцы – элементам o2. Отношение r(o1, o2) возникает, когда элемент o1 уже построен, а элемент o2 еще строится.
В таблице «Д» означает, что данные отношения допустимы;
«Н» – отношения недопустимы (индекс указывает на причину недопустимости отношения). Различие индексов у дуг qi и qj, стоя62
Таблица 2
Правила графического синтаксиса
Графический примитив
А
Б
В
Г
Д
Е
№ Pj
E(qj)
B(qj)
S(qj)
xj
sj
1
2
3
4
5
6
7
8
9
Pi
E(qi)
B(qi)
S(qi)
E(qj)
B(qj)
S(qj)
xi
si
Н3
Д
Н3
Д
—
—
—
Н3
Н3
Д
Н1
Н1
Д
—
Н1
Н1
Н2
Н2
Н3
Н1
Д
Д
—
Д
Н3
Н2
Н2
Д
Д
Д
Н2
—
—
—
Н2
Н2
Н3
Н2
Д
Н2
—
—
—
Н3
Н3
Н3
Н2
Д
Н2
—
—
—
Н3
Н3
щих соответственно в столбце и строке, указывает, что рассматриваются две различные дуги; совпадение индексов указывает, что
рассматривается одна дуга.
Отметим, что ситуация окончание дуги – окончание дуги (Б5)
принципиально невозможна, так как дуга имеет только одно окончание; ситуации окончание дуги – тело дуги (В5), окончание дуги –
начало дуги (Г5), тело дуги – начало дуги (Г6) принципиально невозможны, так как технология построения дуги такова, что дуга
строится от начала к концу; ситуация начало дуги – начало дуги
(Г7) принципиально невозможна, так как дуга имеет только одно
начало.
Кратко перечислим условия, при которых допустимые отношения разрешены:
1) Б1, А2 – окончание дуги совпадает с точкой возможных связей знака оператора, при этом число входных дуг не превышает их
возможное число, зависящее от типа оператора;
2) Г1, А4 – начало дуги совпадает с точкой возможных связей
знака оператора, при этом число выходных дуг не превышает их
возможное число, зависящее от типа оператора;
3) Г2 – всегда разрешено;
4) В3, В6 – тела дуг могут совпадать только в точках, не совпадающих с окончаниями составляющих тела дуг отрезков;
5) Д3 – место построения не должно являться точкой пересечения простых дуг (для устранения неоднозначности – непонятно,
какой дуге сопоставляется метка);
63
– меткам переменных с разными именами должны соответствовать разные сложные дуги;
– меткам переменных с одинаковыми именами должна соответствовать одна и та же сложная дуга;
6) Е3 – место построения не должно являться точкой пересечения простых дуг;
– входной (выходной) значок может лежать только на теле дуги
в окрестности знака оператора, для которого данная дуга является
входной (выходной) и который допускает наличие данного значка;
7) Г3 – точка, в которой начинаем строить дугу, не является точкой пересечения уже построенных дуг;
8) Б4 – если дуги связаны с метками переменных, то данное отношение не должно приводить к нарушению второго условия для
меток;
9) В4 – если дуги связаны с метками переменных, то данное отношение не должно приводить к нарушению второго условия для меток;
– точка, в которой тело строящейся дуги пересекает начало существующей, не является точкой ветвления уже построенных дуг.
Из таблицы видно, что отношения знаков операторов, меток переменных и значков для разметки дуг между собой непосредственно недопустимы, а связующую роль играют дуги.
Выше предполагалось, что отношения возникают в процессе построения АС, на создаваемое изображение накладывались ограничения, чтобы оно удовлетворяло синтаксическим правилам. При
этом использовалась информация о порядке ввода графических
примитивов.
Однако может осуществляться статическая проверка: для уже
построенного изображения нужно выяснить, удовлетворяет ли оно
синтаксическим правилам. При этом нет информации о порядке
ввода графических примитивов. Возникает вопрос: как распознавать вид отношения? Для ответа на него отметим следующие особенности статической проверки:
1) отношения А1, Б1 (А2), В1 (А3), Г1 (А4), Д1 (А8), Е1 (А9), Б2,
В2 (Б3), Д2 (Б8), Е2 (Б9), В3, Г4, Д4 (Г8), Е4 (Г9), Д8, Е8 (Д9), Е9
являются симметричными, поэтому порядок ввода неважен;
2) отношения Б6, В6, Б7, В7 распознаются однозначно;
3) отношения между метками переменных и телами дуг следует рассматривать как отношение Д3, а отношения между значками
разметки и телами дуг – как Е3;
4) отношение между окончанием одной и началом другой дуги
следует рассматривать как Б4;
64
5) в случае отношения между началом одной дуги и телом другой следует проверять условия отношения Г3 и первое условие отношения В4.
После построения АС необходимо произвести общую синтаксическую проверку, отслеживающую ситуации, которые не могут
быть отслежены рассмотренными правилами.
1. Графическое представление АС может быть некорректным
из-за того, что какая-то часть информации просто не была введена.
Например, оператор «/» на рис. 34 введен неправильно (нет значка
разметки). Поэтому для обеспечения правильного в аналитическом
смысле ввода операторов необходимо, чтобы для каждого оператора АС была введена его минимальная форма: должны быть введены
необходимые входные дуги и выходные дуги, а также необходимые
значки разметки.
2. Для придания введенной АС свойства вычислимости необходимо отсутствие в АС контуров, не содержащих оператора задержки. Осуществление контроля возможно на уровне графического
или аналитического представления АС [17, 18] (предпочтительнее
аналитическое представление, так как данное условие имеет аналитическую природу).
Первоначально данный вопрос рассматривался только для технологии повершинного ввода операторов [17]. Оператор включался
в АС только после ввода минимальной формы оператора, включение осуществлялось нажатием кнопки. Синтаксический контроль
производился при включении каждого оператора в АС.
+
–
/
Рис. 34. Пример нарушения минимальной формы
65
При графическом вводе признака включения оператора в АС не
существует, поскольку АС строится путем ввода отдельных графических примитивов (знаков операторов, простых дуг и т. д.). Выполнять проверки после ввода каждого графического примитива
нецелесообразно с точки зрения неоправданных затрат времени
и неудобства технологии построения АС. Поэтому контроль приходится осуществлять после ввода всей сети, что потребовало разработки нового алгоритма, который ищет все контуры во всей АС.
Данный алгоритм подробно рассмотрен в работе [18].
Доказана теорема [16], что синтаксически верному графическому представлению соответствует АС.
На основе введенных синтаксических правил разработаны алгоритмы синтаксического контроля графического представления АС
[16].
66
6. РАСШИРЕНИЯ ЯЗЫКА: МАТРИЧНЫЕ
АЛГОРИТМИЧЕСКИЕ СЕТИ И ИТЕРАЦИОННЫЕ ПРОЦЕДУРЫ
Алгоритмические сети как глобальный формализм представления процессов в качестве переменных допускают использование
математических объектов различных классов: простых переменных, комплексных переменных, массивов, символьных переменных и т. п. Однако введение каждого нового класса требует соответствующего расширения языка AC, грамматики и функций инструментальной системы. Матричное расширение языка AC состоит во
введении массивов в качестве переменных сетей и матричных операторов для работы с массивами [3, 19].
6.1. Матричный алгоритмический базис и правила
построения матричных АС
Набор операторов матричного алгоритмического базиса и их
идеографическое изображение представлены в табл. 3. Операторы
с 1-го по 10-й – поэлементные. Оператор 11 – возведение в степень,
выполняется над скалярными величинами и квадратными матрицами, возведение матрицы в матричную степень не допускается.
Оператор 12 – вычисление матричной экспоненты, выполняется
над квадратными матрицами. Оператор 13 – матричный ключ,
управляемый скалярной переменной, входные массивы ключа
имеют одинаковую размерность.
Операторы с 14-го до 22-го выполняют типично матричные действия. К ним относятся: 14 – операция матричного умножения; 15,
16 – операция матричного деления слева и справа; 17–19 – операции обращения, транспонирования матриц и вычисления определителя соответственно; последние две операции являются связующими при переходе от массивов к простым переменным и обратно,
это операции 20 считывания и 21 записи по индексам. Оператор
записи реализует процедуру замены элемента массива X1 с адресом, задаваемым вектором X2 на элемент x3. Оператор считывания реализует процедуру выборки элемента входного массива X1
по адресу, задаваемому вектором X2. Оператор 22 реализует сдвиг
элементов массива X1 по индексу x2 на x3 позиций вправо, если x3
положительно, и влево, если x3 отрицательно.
Построение матричной алгоритмической сети (МАС) выполняется по общим правилам композиции идеограмм – связности, однозначности и ацикличности.
67
Таблица 3
X1
X1
X2
sin X2
X1
sinоперации
X1
X2
X1 Тип
sin X2
sin X2
X1
X1 sin X2
X2
X1
cos
Сложение
матриц cos
X1
X2
cos X2
X1 X3=X1+X2
X1
X1 cos X2
X2
X1
X2
cosF X2
X1
X1 cosF X2
X1
F X2
X1
F X2 матриц Вычитание
X1
X2
F
X1
X1 ∆t X2
X2
X3=X1–X2
X1 F∆t X2
X1 ∆t X2
X1
∆t X2
X1
∆t X2
X1 X1
∆t X3
X3матриц
X1
Умножение
X1 ↑ X3
X2
поэлементное
X3=X1*X2
↑
X2 X1
X3
X2 X1 ↑ X3
↑ X3
X2
↑
X2
X2 X1
X1 ↑
X2
X2
X1 матричного алгоритмического
X1
Список операторов
базиса
sin X2
№ п/п
1
2
3
4
5
X1
X1
X1
X1
X2
X2X1
X2
X2
6
X3
X3
X3
X3
7
X3
X2X1
X1
X38
X1
X1∆
X3
X3
X2
X3
X1 ∆
9
X2
∆
∆ X3
X2
X2
∆
10
X2X1
X1
X3
X1
X1
X3
X2
X3
X3
X1
X2
11
X3
X2
X2
X2X1
X1
X3
X1
X3
X1:
68X3
X2
X3
X1 :
X2
::
X3
X2
X2
:
X2
X1
X1
X3
X1
X3
X1представление
Графическое
X3
X2X1
X2
X3
X1
X3
X2
X3
X2
X2
X1
X2 X1
X3
X1
X3
∆
X1 ∆
X3
X2 X1
X2
X3
X1 ∆ X3
∆
X2
X3
∆
X2
X2 X1∆
X1
X2
X3
X1
X3
X1
X3
X2
X2X1
X3
X1
X3
X2
X3
X2
X2
X1
X2 X1
X3
X3
X1
X1 :: X3
X2X1
X3
X2
X1 :
X3
:
X2
X3
:
X2
X2
:
X1
X2 X1
X3
X1
X3
X1 max
X1 max X3
X2
X2
X1 max X3
X2 max X3
X2 max X3
X2 X1max
X2 X1
X3
X1
X3
X1 min X2
X1
min
X3
X2X1
X1 sin X2
X2
X1 minsinX3
X1 min X3X2
X2
X2X1
sinX3
X2X1 minsin
X2
X2
minsin
X2
X2X1
X1 cos X2
cos
X1
X2
X1
X2
cos
cos X2
X1
X1
X2
F
X1 cos
X2
X1
F X2
X1
X2
F
F
X1
X2
X1
X2
X1 ∆tF X2
∆t
X1
X2
X1
X2
∆t
∆t
X1X1
X2
∆t
X1 X3
X1
X1
X3
↑
X2
X3
X2 X1↑ X3
↑
X2
↑
X3
X2
↑
X2
X1
X2
X1 exp
X2
exp
X1
X1 exp X2
X2
X1
exp
exp
x3
x
X2
X1
X1
X1
X1
X2 X1
X2
X1
X2
X2
X2
X1
X2 X1
X3
X3
X3
X3
X3
X3
X3
X1
X3
X1
X3
X2 X1
X3
X2
X1
X3
X2
X3
X2
X2
X2
X2
X1
X1
–1 X2
X1 –1 X2
X1 –1 X2
X1 –1 X2
X1 –1 X2
X2
X1
X1
X2
T
–1T
X1
X2
X1
T X2
X1
T X2
T X2
X1
X1 T
X
Деление матриц
exp поэлементное X1
X
exp
det
det
X1X3=X1:X2
X2
X1
X2
X1 exp X2
X1 det X2
X1 exp X2
det X2
X1
X2
X1 expx X2
det X2
X1
X2
3
expx3
det
X2
X1
X2
X1
X
x
X1
X2
3
X1
Rx
Матрица-максимум
->iX2X
R
3 X2
->i
X2X4
X1
X1
x
3
X3=max(X1,
R X4
X4X2 X2)
X1
X1 ->i X2
X4
xX4
R x3 X2
X1
3
->i x
X1
3
R
X4
->i X4
X1
X2
X1
R X4
3
->i x
x3
X1 X4
x3 x
X1
X4
X1
x3
Матрица-минимум
X1
X3
->x3 3
X1
X1
X3
ii ->
x
X1
3
X1
X3=min(X1,
X2)
X1 X3X3
X2
X1 X3
X1 i -> x3
X2
X1
X3
x
X1
X1
3
i
->
X1 X3
X2
X3
x3
X3
X2 X2
X1 i -> X2
X1
X2
X3 i
->
X2
Cинус
X2
X2
X3
X2
X2
X2
X2 X2=sin(X1)
X2
x2
x
2
X2
X2 X1
Косинус x
X1
X4
2 X4
X1 X3
X1
X2=cos(X1)
→ x2
X1
→
X1
x
X3
X1
2X4
X3
X2 X1
X3 преобразование X1 → x2X4
Функциональное
xX4
X1
→
3
X2
x
3
X2=F(X1)
X1 → X4
X3
X2
X2
x
→ 3
x3
Задержка X2
x3
X2
X1 X2(t+1)=X1(t)
x3
X2
X1 –1
X1
X2
X1 –1 X2
–1
Возведение
в степень –1
X2
X1
X1
X2
X3=X1X2
–1
X1 T
X2
X1
T X2
X1
X2
T
T
X1
X2
T X2
X1
det
X1
X2
X1
X1 det X2
X2
X1
det
det
X2 X2
X2
det
X1
X2
X2
X2
X3
X3
X1
X3
X1
X1 :
X3
X2
: X3 № п/п
X2 :
X2
12
X1
X1
X1 max
X2
max
X2 X1
max
X2 X1
X1
X1
X1
X3
X3 13
X3
X2
X2
sin
sin X2
X2
sin
sin
X1
X3
X2
X1X1min
14
sin
X3
X2
X1
X2
X2 X1
X1mincos
X2
X3
sin
cos
X1
X2
X2 X1
min
X1
X2
cos X2
2
cos
sin
X1
X2
X1
X2
X2
X1
X2
sin
F
F X2
X1 cos
X2
X1
X2
15
cos
FF
X1
X2
X1
X1
X2
X1 cos
X2
F X2
∆t
X1
∆t X2
X1 cos
X2
F X2
X1
∆t
X1 ∆t X2
X1X1 F X2
X216
X1
X1 X1∆t
X2
X3
F
X1∆t X3
X1
X2
X3
X1 ↑↑ X3
X2
X2
X1 ∆t X2
X1
↑
X2
X2 X1↑∆t X317
X3
X2X1X1↑
X2
18
X2
X2X1 ↑exp
X1 exp X3
X1
X2
X1 exp X3
X2
↑exp 19
X2
X1
X2
↑
X2
xx3 X2
X1 exp
3
exp X2
X1
X1
xx3 X2
X1 RR 3 X2
X1
X2
exp X2
X1
R X4
X1 R
xX4
3 X2
20
exp
x3 X2
X1
X4
X4
R
X1
X2
R x3
X1
X1 X4
xX3
X1
3 X2
X1 R X4
X3
X1X1
X2
X3
R X4
X2
X3
X2 X1
21
X2 X1 X4
X2
X3
X2 X1
X2 X1
X2
X2
X3
X3
X3
22
X1
X3
X1
X1 ↑
X3
X2
X3
↑
X2
↑
X2
X1
X2
Графическоеexp
представление
X1
X2
exp X2
X1
exp
x3
X1
x X2
Rx3 3
X1
X2
R X4X2
X1
R
X1
X4
X1
X3
X1 X4X3
X1
X3
X1
X3
X2
X2 X1
X3
X1
X3
X2X1
X1
X2
X3
X2
X3
X3
X2
X1
X2 X1
X1
X2
X3
X2 X1
X3
X1
X3
X1
X3
X3
X2
X3
X2
X2 X1
X2
X2 X1
X3
X2
X3
X2 X1
X2
X2X1
X1
X3
X2
X1
–1
–1 X3
X2
X1
X2X1 –1 X2
–1
X2X1
X2
X1
X1 –1 X2
X1 TT X2
X1 –1 X2
X2
X1
T
X1 T X2
X1 –1 X2
X1
T X2
X1
X2
X1
X1 –1
X2
det
T
det
X1
X2
X1
X2
X1 det
det X2
T X2
X1
X2X2
X1
T X2X2
X1 det
X2
detX2
X1
X4
X1 ->i
X4
->i
X1
X2
X1
X4
X2X4
X1
det
->i X2
X1 ->i
xx3
det X2
3X4
X1
->i
x3X4
x
X1
X2
3
->i
X2
xx3
X1
X1
X1 i -> x3 X4
3
i->i
-> x3xX4
x3
X1
X1
X1 ->i
3
->
ii->
x3x
X2
X1
3
X2
x3x3
X1 i -> X2
X2
i ->
x
x
X1
2 3
X2
i -> x2x3
X1
X2
x
X1
2X4
->x2X4
X1 i→
→ X2
X1
X4
X1
x X4
→ 2
→
X2
xx32
X1
X4
3
X1 → xx3X4
→ 32
x
X1
x23X4
→ xX4
X1
3
→
x3
x3
X2
–1 X2
–1
X1
X2
X1 T X2
X1
T X2
Окончание табл. 3
T
X1
X1
X1
X1
X1
X2операции
Тип
X2
det Экспонента
X2
det
det
X2=exp(X1)
X2
X2матричный:
Ключ
X1
X4
->iX2 при x истинно X4=X1
X1
X4
3
->i X4при x ложно X1 X4=X2
3
->i x3
R – логическое
отношение
x3
x3
x3
X1
Умножение
матричное
i -> x
X1
3
x3
i ->X3=X1⊗X2
X1
i -> X2
X2
X2
Деление
левое x2
X3=X1\X2
xX4
2
X1
→x2
X1
X4
X1
→ X4
→Деление
x3
правое x3
X3=X1/X2
x3
Обращение матрицы X2=X1–1
Транспонирование матрицы
X1=X2T
Определитель матрицы
X2=det(X1)
Запись по индексу X1(X2)=x3
Считывание по индексу
x3=X1(X2)
Сдвиг массива X1 по индексу
x2 на x3 позиций
69
Синтаксический контроль правильности построения АС выполняется на этапе ее ввода. Контроль размерности переменных выполняется на этапе ввода данных.
6.2. Определение типов переменных
и размерностей массивов в МАС
Для операций, включенных в матричный алгоритмический базис, размерности массивов переменных на их входах и выходах
жестко связаны. В этом случае размерность массивов переменных
АС определяется однозначно по размерностям входных переменных и переменных состояния. В общем случае эта информация
избыточна. Эта избыточность может использоваться как для сокращения объема входной информации о размерности входных
данных, так и для контроля этой информации. Описание соответствующих алгоритмов приведено в работе [3].
В МАС при увеличении количества переменных AC, размерности массивов и числа шагов счета ресурсы компьютера могут быть
исчерпаны. Для сокращения необходимого для модели объема памяти применен подход, состоящий в том, что на сети выделяется
подмножество критериальных переменных, значение которых на
всем интервале счета должно храниться в памяти машины. Имена
этих переменных задаются пользователем при подготовке условий
проведения имитационного эксперимента. В состав критериальных
по умолчанию включаются входные переменные сети и переменные
состояния. По окончании сеанса моделирования любая из этих переменных может использоваться для анализа поведения исследуемой системы на интервале счета. Значения остальных переменных
сохраняются лишь в течение текущего такта счета. Данный способ
является эффективным и достаточно простым в реализации методом сокращения памяти. Однако он не исчерпывает всех возможностей снижения затрат памяти под переменные модели. Фактически
значения переменных должны сохраняться лишь в течение времени, необходимого для реализации вычислительного процесса.
При ручном программировании подобная задача решается путем повторного использования одинаковых имен в цепочке вычислений. В синтаксически корректной AC различным дугам не могут
быть приписаны одинаковые имена. В связи с этим именование дуг
МAC проводится в два этапа. В исходной сети выполняется однозначное именование дуг, и эти имена сохраняются вплоть до постро70
ения плана вычислений. На этапе расчета сети проводится автоматическое переименование дуг в целях сокращения памяти. При
этом уникальные имена сохраняются лишь для критериальных
переменных, значения которых требуется хранить в течение всего
цикла решения задачи. Фактические имена остальных переменных
AC (назовем их эфемеридами) не известны пользователю и идентифицируют значение переменной лишь в течение времени, необходимого для реализации вычислительного процесса. Алгоритмы автоматического распределения памяти в МAC описаны в работе [3].
Эффективность предложенного подхода будем оценивать по величине относительного уменьшения затрат памяти на проведение
имитационного эксперимента:
T
K=
s
s
i=1
i=1
s
å ni Mi + å (Ni - ni )Mibi
T
,
å Ni Mi
i=1
где Т – количество тактов счета на сети; Ni, Mi – количество и размерность переменных i-го размерного класса; ni – количество критериальных переменных i-го размерного класса; S – количество
размерных классов; bi – коэффициент снижения затрат памяти под
переменные-эфемериды в i-м размерном классе:
bi =
Ci
,
Ni - ni
Ci – количество независимых имен переменных эфемерид в i-м размерном классе после переименования.
Если переменные сети имеют одинаковую размерность (S=1), то
формула для K примет вид
K = a + b(1–a)/T, a = n/N.
Например, при a=0,1, Т=10, b=1 получим K=0,19, если b=0,3,
то K=0,13; при a=0,01, Т=10, b=1 получим K=0,11, если b=0,3, то
K=0,04.
6.3. Обратимость операторов МAC
Для поэлементных операций над матрицами вопросы обратимости решаются таким же образом, как для операций со скалярными
71
переменными. Так, для операции сложения возможными вариантами обращения (аксиомами вычислимости) являются
< A+B=C, C–B=A, C–A=B >,
и в зависимости от того, какие из операндов известны, реализуется
тот или иной вариант вычисления оператора. При обращении тригонометрических и табличных функций результат определен на
интервале однозначности их значений.
Для типично матричных операций алгоритмического базиса
возможность обращения в общем случае зависит от размерностей
массивов и значений числовых данных. Операция транспонирования симметрична и выполнима для любой прямоугольной матрицы, варианты вычислимости для транспонирования: <A=BТ, B=AТ >.
Для произвольной прямоугольной матрицы А существует единственная псевдообратная матрица А+, которая соответствует наилучшему по методу наименьших квадратов решению уравнения А Х = Е и удовлетворяет условию (А+)+=А [20]. Если А – невырожденная квадратная матрица, то для нее существует единственная
обратная матрица А–1, причем (А–1)–1=А, А–1=А+. Таким образом, аксиомы вычислимости для операции обращения матриц на
АС имеют вид <А–1=B, В–1=А>, для квадратной невырожденной
матрицы выполняется обращение, для произвольной прямоугольной матрицы – псевдообращение [20].
Операции матричного умножения и деления выполняются над
сцепленными матрицами и имеют одинаковый набор аксиом вычислимости:
<АВ = C, А\C = В, C/В = А>.
Деление сводится к умножению на обратную (псевдообратную)
матрицу. Особый случай – C = 0 при А ≠ 0, В ≠ 0.
Для функций матриц exp(А) и XY, включенных в алгоритмический базис, обращение связано с оценкой свойств матриц-аргументов. Задание функций матриц является обобщением на матричный
аргумент функций скалярного аргумента F(l) и основывается на
следующей теореме [20]: если функция F(l) разлагается в степенной ряд в круге |l – l0| < r:
F (l ) =
¥
å a p (l
p=0
72
-l 0 ) p ,
то это разложение сохраняет силу, если скалярный аргумент l заменить любой квадратной матрицей А, характеристические числа
которой лежат внутри круга сходимости.
Отсюда следуют, например, следующие разложения, справедливые для произвольных квадратных матриц:
exp(A) =
¥
¥
¥
2 p+1
(-1) p 2 p
Ap
p A
cos
sin
(
)
;
;
A
=
A
;
A
=
1
å p!
å (2 p)!
å
(2 p + 1)!
p=0
p=0
p=0
ch =
¥
A2 p
p=0
Разложение ln =
¥
¥
A2 p+1
å (2 p)! ; sh = å (2 p + 1)!.
p=0
p-1
(-1)
p
p=0
å
(A - E) p справедливо при l k – 1 < 1, k = 1, s.
l k – 1 < 1, k = 1, s.
В соответствии с [20] для невырожденной квадратной матрицы
А может быть выбрана однозначная ветвь многозначной функции
l , определенной в области, не содержащей 0 и содержащей все
характеристические числа матрицы А. Тогда имеет смысл l и
( l )2 = А, что позволяет записать аксиомы вычислимости оператора А2:
< Â = À2 , À = B > .
Для невырожденной квадратной матрицы А может быть выбрана однозначная ветвь ln(A) многозначной функции ln(l), определенной в области, не содержащей 0 и содержащей все характеристические числа матрицы А. Тогда справедливо
ехр(ln(А)) – A = 0,
т. е. матрица В = ln(A) удовлетворяет матричному уравнению
ехр(В) = А. Условие невырожденности А является необходимым и
достаточным условием решения уравнения. Необходимым и достаточным условием того, что вещественная невырожденная матрица
А имеет вещественный логарифм В, будет отсутствие элементарных делителей, соответствующих отрицательным характеристическим числам, или повторение таких элементарных делителей четное число раз [21]. Таким образом, для операции ехр(А) аксиомы
вычислимости
<В= ехр(А), А = ln(В)>.
73
Операции минимума, максимума, сдвига, вычисления определителя, записи и считывания по индексам и логический ключ не
обратимы.
6.4. Расширение языка АС для представления
итерационных процедур
Как было показано в разд. 3, на AC со стандартным набором операторов алгоритмического базиса (см. табл. 1, 3) не могут быть эффективно представлены вложенные и асинхронные итерационные
процедуры. В результате многие практически важные и рядовые
для традиционных языков программирования задачи на AC решены быть не могут.
Построение АС с вложенными циклами требует введения новых
понятий – локального циклового времени и локальных цикловых
начальных условий. Локальное время запускается при входе в цикл
и до его завершения фиксирует шаг счета всех внешних циклических процедур модели. В отличие от начальных значений переменных состояния главной сети, которые задаются однократно, цикловые начальные условия устанавливаются при каждом входе в цикл.
Один из путей снятия ограничения состоит во включении в состав алгоритмического базиса операторов, непосредственно предназначенных для реализации циклических процедур.
Второй вариант реализации вложенных циклов состоит в том,
что вложенный цикл оформляется в виде локальной AC, которая
рассчитывается со своим шагом расчета. Организуется система
ссылок, обеспечивающая ввод исходных данных, запуск на счет,
остановку вычислений и вывод результатов из локальной во внешнюю сеть. Такой способ организации вложенных циклов не требует
расширения состава операторов алгоритмического базиса. Данный
способ реализован в текущей версии системы автоматизации моделирования КОГНИТРОН.
Ссылка на модель, считаемую со своим шагом расчета, дает возможность построить библиотеку необходимых функций. Примером таких функций могут быть:
– набор табличных функций с различным методом аппроксимации;
– реализация операций с векторами;
– реализация операций с матрицами.
Пример реализации табличной функции показан на рис. 35.
Пример операции с векторами приведен в подразд. 6.5.
74
res
>=
x1_prev
∆t
x_arg
x1
<
y_res_prev
res
res2
value_out
<>0
y_res
y1_prev
y1
∆t
y1_prev
y_res_prev
x1
∆t
x1_prev
y_res_prev
y_res
x_arg
<>0
res2
x1_prev
Рис. 35. Модель «Табличная функция»
75
6.5. Упрощенная поддержка работы
с матричными переменными
Изложенная выше работа с матричными переменными требует
серьезных трудозатрат при реализации системы. Одним из возможных решений является интеграция со специализированными программными продуктами, например Matlab (см. разд. 7).
Но для программной реализации, не зависящей от внешних программных продуктов, потребовалось ввести некоторые упрощения,
изложенные ниже.
Будем считать, что все переменные модели являются одномерными массивами размера n. По умолчанию n = 1.
Все стандартные операторы, работающие с вещественными числами, работают только с первым элементом массива. Пусть, например, определена переменная X1, являющаяся массивом размерности 3: X1 = {1.57, 0, 4}. cos(X1) = cos(X1[1]) = 0.
Особым случаем является оператор задержки. Для правильной
организации вычислений он должен переносить все элементы массива на следующий расчетный период.
Пусть X1(t+1) = X2(t), где размерности X1 и X2 соответственно
n и m:
при n ≤ m X1[i](t+1) = X2[i](t), где i = 1 … n;
при n > m X1[i](t+1) = X2[i](t), где i = 1 … m;
X1[i](t+1) = 0, где i = m+1 … n.
Кроме того, нужны собственно операторы, позволяющие работать с массивами, для этого достаточно операторов 20 и 21 из
табл. 3.
Оператор записи i-го элемента массива
Op(X1, i, x) = X′1,
′
где размерности X1 и X 1 соответственно m и n:
при n ≤ m X ¢1[ j ] = X1[ j ] ïðè j ≠ i; X ¢1[ j ] = x ïðè j = i;
при n > m
X ¢1[ j ] = X1[ j ] ïðè j ¹ i; X ¢1[ j ] = x ïðè j = i, j = 1¼m;
X1[ j] = 0 ïðè j = m + 1¼n.
Оператор чтения i-го элемента массива
Op(X1, i) = X1 [i].
Используя ссылки на АС со своим шагом расчета, можно реализовать операторы из табл. 3. Пример реализации оператора 1 показан на рис. 36.
76
1
∆t
i
i
x1
i->
x1_i
y
∆t
∆t
->i
i
y0
x2
i->
x2_i
∆t
Рис. 36. Алгоритмическая сеть,
описывающая сложение векторов X1 и X2
6.6. Примеры реализации моделей на языке МAC
Пример 1. Рассмотрим модель динамики изолированной популяции, численность которой X регулируется промыслом (D) и ограничивается емкостью кормовой базы (В):
æ
ö÷a
N
çç
X(t + 1) = (X(t) - X(t) * D) Ä K * ç1 - å xj (t) / B÷÷÷ .
çç
è j=1
ø÷÷
Переменная Х является массивом, определяющим численность
животных по возрастным группам, выделенным в соответствии с
требованиями решаемой задачи; xi – элемент массива Х; K – транспонированная матрица Лесли, задающая коэффициенты размножения и выживания животных (без учета промыслового изъятия).
Нагрузка на кормовую базу характеризуется отношением общей
численности популяции к емкости кормовых угодий, показатель
степени «а» определяет жесткость влияния условий питания на показатели воспроизводства популяции. Для простоты здесь принято,
что интенсивность влияния одинакова для всех групп животных.
Алгоритмическая сеть модели показана на рис. 37. Основные
переменные сети именуются теми же обозначениями, что и в уравнении динамики численности. Символы операторов соответствуют
табл. 3. Суммирование элементов массива Х осуществляется путем
77
D
K
UN
х4
х1
∆
A
х5
B
х6
↑
E
х7
х3
х2
X
∆t
х1
Рис. 37. Алгоритмическая сеть модели изолированной популяции
умножения вектора-строки Х на единичный вектор-столбец Е. Размерности массивов на сети не указываются, а задаются при вводе
начальных условий задачи. Так, первая отладка модели может выполняться для скалярных переменных.
Пример 2. Двумерный процесс распространения тепла.
Математическая модель процесса
¶u ¶2u ¶2u
=
+
+ F (x, y, t)
¶t ¶x2 ¶y2
с граничными условиями первого рода на области G, G=(x, y), ограниченной кривой Г:
U(G,0) = U0(G), U |Г = M(Г, t).
Процесс распространения тепла может быть аппроксимирован
системой разностных уравнений, решаемых по явной схеме:
uij1+,i12 - uij1,i2
L(u j } =
1
h12
(
)
= L uij1,i2 + ϕ;
τ
U(G,0) = U0 (G), U Ã = M;
(uij1-1,i2 - 2uij1,i2 + uij1+1,i2 ) + h12 (uij1,i2-1 - 2uij1,i2 + uij1,i2+1 ).
2
На рис. 38 представлена АС модели процесса распространения
тепла при использовании локально-одномерного метода решения с
расщеплением по координатам. Метод основан на введении на временном шаге двух промежуточных этапов, на каждом из которых
78
Fx
t
h1
x1
x1
x12
x2
→
x3
x8
x7
→
x5
x11
i ->
x4
x1
x13
→
x6
:
x10
x9
x4
u 11
x15
NG
x37
x16
i ->
h2
x1
x1
x24
x1
→
x23
x25
x5
u
∆t
x34
x35
i ->
x26
x33
UG
x29
x22
→
→
→
x36
Fy
t
x17
t
x27
:
x28
x30
x31
x32
NG
Рис. 38. Алгоритмическая сеть модели диффузии-теплопроводности
(двумерный вариант)
проводится одномерная аппроксимация по одной из координат. На
сети обозначено: u – массив температур поверхности; u11 – значение температур после расчета по первой координате (x); x33 – значение температур после расчета по второй координате (y); x16 – массив значений температур на границе на t-шаге; NG – единичная ма79
трица с нулевыми элементами на границе области G; UG – матрица
граничных условий с нулевыми элементами вне границы области G.
Пример 3. Нейронные сети (НС) являются одним из компонентов
технологий «мягких вычислений». Они способны решать широкий
круг задач распознавания образов, идентификации, прогнозирования, оптимизации, управления сложными объектами. Современные технологии позволяют создавать БИС, содержащие до 106 и
более нейронных элементов (НЭ). Для представления и имитации
НС такой размерности удобно использовать язык МAC. В качестве
примера будем использовать многослойную BP-нейронную сеть.
В BP-сетях используются НЭ с нелинейными дифференцируемыми
трансформационными функциями (сигмоида, sin или tanh). По топологии – это бесконтурные НС с полным набором связей выходов
НЭ одного слоя с входами другого. Название сетей данного класса связано с методом настройки весовых коэффициентов – Back
Propogation, реализующим градиентный алгоритм подбора весов с
движением от выходов к входам. Ввиду эффективности настройки
эти нелинейные многослойные НС нашли широкое распространение в таких областях, как искусственное зрение, чтение рукописных текстов, автоматическая классификация, распознавание речи.
G3
Iout
UN3
TF3
:
exp
Yout
s3
Yhd
s2
Yin
s1
Wout
G2
Ihd
UN2
TF2
:
exp
Whd
G1
I in
X in
UN1
exp
TF1
:
Win
Рис. 39. Алгоритмическая сеть модели трехслойной ВР-нейронной сети
80
На рис. 39 показана МAC, реализующая трехслойную BPнейронную сеть произвольной размерности. В качестве суммирующей функции НЭ используется взвешенная сумма, в качестве трансформационной служит сигмоидная функция y=1/(1+ +exp(–gi)), где i – взвешенная сумма; g – константа. На AC взвешенные суммы множества НЭ каждого слоя НС реализуются с помощью оператора матричного умножения, сигмоидные функции
задаются с помощью матричных операторов, которые выполняют поэлементные действия над массивами переменных. Так, для
первого слоя НС массиву значений взвешенных сумм соответствует переменная Iin=XinWin. Эта переменная является входной для
матричной трансформационной функции TF1 (см. рис. 39), где
G1 – вектор значений коэффициентов; UN1 – единичный вектор.
Массиву выходных переменных НЭ первого слоя соответствует переменная Yin. AC инвариантна к числу НЭ, размерности переменных и операторов сети устанавливаются автоматически при вводе
исходных данных. Описание блока настройки BP-нейронной сети,
представленного в виде AC, имеется в работе [3].
81
7. ПОСТРОЕНИЕ СИСТЕМ АВТОМАТИЗАЦИИ МОДЕЛИРОВАНИЯ НА ОСНОВЕ ФОРМАЛИЗМА АЛГОРИТМИЧЕСКИХ СЕТЕЙ
7.1. Предыдущие версии системы автоматизации
Первая версия системы автоматизации моделирования на основе языка алгоритмических сетей САПФИР-Искра была ориентирована на решение задач экономики и социально-экономического
развития совместно с Госпланом РСФСР. Система имела ограниченный алгоритмический базис и интервал счета до 20 машинных
шагов, что было достаточно для решения поставленных задач.
Первой универсальной системой автоматизации моделирования
была система ЭКО-САПФИР [4]. Состав операторов алгоритмического базиса был расширен за счет включения элементарных и
блочных функций (макросов), было снято ограничение на количество шагов счета модели. В состав системы были включены оптимизационные поисковые процедуры настройки параметров моделей.
Система широко использовалась для решения практических задач
в области экологии, экономики, химической кинетики, техники,
имитации военных действий и показала перспективность применения языка АС для моделирования.
Следующим шагом была разработка в Санкт-Петербургском институте информатики и автоматизации РАН версии системы автоматизации моделирования КОГНИТРОН 2.0 [3]. Принципиально новым
свойством данной версии системы является реализация в ней объектно-ориентированной технологии множественного моделирования.
Система обслуживала пользователей:
– работающих только с готовыми моделями;
– способных выбрать из базы в режиме «кнопочной» технологии
интересующие их фрагментарные модели, которые автоматически
объединяются в сложный модельный комплекс;
– системных аналитиков, осуществляющих синтез моделей на
языке AC.
Переменными AC в данной версии системы КОГНИТРОН являются вещественные числа.
Система состояла из графического редактора, блока построения
плана вычислений, блока формирования массивов исходных данных, блока анализа и обращения АС (блока принятия решения),
вычислительного блока, блока вывода результатов счета, базы моделей и базы данных.
82
Графический редактор выполнял двухуровневый синтез АС.
Первый уровень – уровень синтеза элементарной AC. Ввод сети
осуществляется путем наложения «мышью» на экран дисплея операторов алгоритмического базиса, задания связей и имен переменных. Вид экрана показан на рис. 40. При вводе моделей допускается скроллирование экрана, однако для обозримого представления
размеры сети ограничиваются полем 20×16 ячеек, в узлах которых
может располагаться один оператор.
На втором уровне выполняются процедуры синтеза комплексной модели в режиме «кнопочной» технологии моделирования на
основе заранее разработанных и взаимосогласованных фрагментарных моделей. Фрагментарные модели хранятся в базе, где каждая модель представлена АС и помечена персональной пиктограммой. Экран (рис. 41) содержит область визуализации пиктограмм
всех моделей базы и область слияния, куда помещаются иконки
выбранных моделей. Пиктограммы моделей базы, имеющие общие переменные с моделями из области слияния, подсвечиваются,
и дальнейший отбор выполняется на подмножестве помеченных
Рис. 40. Окно построения фрагментарной алгоритмической сети
83
Рис. 41. Окно формирования комплексной алгоритмической сети
на основе визуализированной базы моделей предметной области
таким образом моделей. После завершения отбора формируется
АС комплексной модели путем автоматического слияния сетей ее
фрагментов.
Следующий этап состоит непосредственно в проведении имитационного эксперимента. Система обеспечивает вывод в табличной
или графической форме значений любой переменной (набора переменных) AC на интервале счета. В системе для достижения желаемого результата может быть применен метод обращения. При этом
пользователь указывает имя выходной переменной, которой следует присвоить статус входной, и задает значения этой переменной.
Система определит, существуют ли преобразования AC, позволяющие перевести отмеченную выходную переменную во множество
входных, и выдаст имена входных переменных, одну из которых
необходимо будет перевести в выходные. Далее система генерирует
новую расчетную программу и осуществляет требуемый расчет.
Инструментальная система КОГНИТРОН 2.0 была реализована
на языке Visual Basic 3.0 в среде Windows 95. Информация о моделях и данных хранится в базе данных СУБД Microsoft Access.
84
Для расширения вычислительных возможностей системы моделирования, выполнения операций над матрицами и работы с
массивами была разработана интегрированная версия системы
КОГНИТРОН-Matlab [3]. Структура интегрированной версии системы представлена на рис. 42. Интегрированная система включает
все основные блоки верхнего уровня скалярного КОГНИТРОНа –
двухуровневый графический редактор с базой моделей, планировщик, блок анализа и обращения AC. Ввиду идентичности синтаксических правил построения и формальных преобразований матричных и скалярных AC эти блоки лишь незначительно модифицированы с учетом расширения алгоритмического базиса. Пакет Matlab
привлечен для расчета моделей. Для большинства операторов (см.
табл. 3) имеет место прямое отождествление с базовыми операциями Matlab. Это – поэлементные арифметические операции, матричное умножение и деление, определение матриц минимальных
и максимальных элементов, элементарные функции – sin, cos, exp,
степенная, обращение и транспонирование матриц, вычисление
определителя, считывание элементов матрицы по индексам. Для
КОГНИТРОН
База
моделей
План вычислений
Список переменных
Интерфейсный
блок
Массивы
данных
m-файлы
Отдельные команды
Результаты
расчетов
Matlab
Графики
Рис. 42. Структурная схема интегрированной версии
автоматизации моделирования
85
реализации остальных операторов матричного алгоритмического базиса (запись и считывание по индексам, логический ключ и
т. п.) формируются соответствующие m-файлы на входном языке
системы Matlab. В состав пакета Matlab кроме чисто математических функций входит множество функций для графического представления результатов вычислений, так что задача представления
результатов также возложена на него.
7.2. Краткое описание версии КОГНИТРОН 4.0
В настоящее время в Санкт-Петербургском институте информатики и автоматизации РАН разработана и эксплуатируется версия
системы автоматизации моделирования КОГНИТРОН 4.0.
Система разработана на языке C с использованием библиотеки
интефейса GTK и является переносимой на уровне иcходного кода
между MS Windows и Linux.
Система имеет неограниченные возможности по расширению
операторного базиса и типов данных.
Все объекты, с которыми работает система (модели, массивы данных, конфигурационные файлы), сохраняются в текстовом формате.
Система поддерживает полный цикл работы с моделью – от создания до расчета. Это реализуется через три основных режима работы системы (рис. 43) «Модель», «Данные», «Эксперимент».
Режим «Модель» предназначен как для создания новой модели,
так и для редактирования и просмотра уже созданной.
В режиме «Данные» подготавливаются массивы значений для
всех переменных модели.
Режим «Эксперимент» позволяет проводить вычислительные
эксперименты с моделью, используя данные, подготовленные в режиме создания данных.
Режим «Модель»
Предлагаемая версия графического редактора обеспечивает:
1) ввод и редактирование операторов АС;
2) ввод и редактирование имен переменных;
3) синтаксическую поверку правильности введенного оператора;
4) синтаксическую проверку правильности введенной АС;
5) сохранение введенной АС модели.
После входа в режим необходимо выбрать действие: «Создать»
или «Открыть» модель (рис. 44). Также возможен вход в режим в
86
Рис. 43. Экран выбора режима работы системы
Рис. 44. Режим «Модель»
87
режиме просмотра (при вызове из режима данных или эксперимента с уже открытой моделью).
Ввод операторов АС
Процесс ввода операторов АС в графическом редакторе предстает в виде последовательно чередующихся вводов графических элементов АС: знаков операторов, дуг, значков разметки дуг.
Знаки операторов и простые дуги могут вводиться в произвольной последовательности. Однако удобнее вводить сначала знаки
операторов, а потом соединять их дугами. В этом случае при промежуточном построении получаются конструкции, по которым легче
представить окончательный вид АС. Также возможно последовательное пристраивание к уже имеющемуся фрагменту дуг и знаков
операторов.
Ввод графических элементов осуществляется путем нажатия соответствующей кнопки панели инструментов (рис. 45).
Графические элементы располагаются на рабочем поле графического редактора (рис. 46).
Режим удаления
Значок “крестик”
Знаки операторов
Метка переменной
Построение дуги
Рис. 45. Панели инструментов режима создания модели
88
Рис. 46. Поле графического редактора
Ввод знака оператора
Знак оператора характеризуется соответствующими ему операцией и координатами (x, y). Располагаться знак оператора может
только в узлах сетки рабочего поля графического редактора. Большинство знаков операторов имеет форму круга, хотя графический
образ знака оператора может быть произвольным. Связь знака оператора с дугами может осуществляться только в точках возможных
связей. Знак оператора имеет 8 точек возможных связей, поэтому
оператор потенциально может иметь не более 8 связанных с ним дуг.
Построение знака оператора осуществляется следующим образом.
1. Выбирается соответствующая знаку оператора команда в
меню или нажимается кнопка на панели инструментов, если таковая имеется.
2. Щелчком мыши указывается узел сетки рабочего поля, в котором будет располагаться знак оператора.
Ввод дуги
Построение простой дуги осуществляется следующим образом.
1. Выбирается соответствующая команда в меню или нажимается кнопка построения дуги на панели инструментов.
89
2. Щелчками мыши указываются начало дуги, затем точки излома дуги.
3. Для окончания построения дуги следует повторно выполнить
действие п. 1.
Если конец дуги совпадает со знаком оператора, то конец дуги
строится автоматически, п. 3 является ненужным.
Ввод значка для разметки дуг
Ввод значков разметки возможен только после ввода размечаемых ими дуг и соответствующих знаков операторов. Поскольку
значки разметки используются для задания частичного порядка
входных (выходных) переменных операторов, то их нанесение на
размечаемые дуги допускается только в окрестности соответствующих операторов.
Построение значка разметки осуществляется следующим образом.
1. Выбирается соответствующая значку разметки команда в
меню или нажимается кнопка на панели инструментов, если таковая имеется.
2. Щелчком мыши указывается дуга, которой будет соответствовать значок.
Ввод метки переменной
Метки переменных соответствуют простым дугам, поэтому вводу
метки переменной должен предшествовать ввод соответствующей дуги.
Построение метки переменной осуществляется следующим образом.
1. Выбирается соответствующая команда в меню или нажимается кнопка метки переменной на панели инструментов.
2. Щелчком мыши указывается дуга, которой будет соответствовать данная метка. Тем самым получаем начальное приближение для расположения текста метки. После этого появляется окно
«Новая метка дуги» (рис. 47).
Рис. 47. Метка переменной
90
3. Вводится имя метки переменной, статус видимости имени на
рабочем поле, тип переменной (размерность массива). В случае если
значения переменной являются константой и система не должна в
режиме «Эксперимент» позволять выбирать данную переменную
как переменную, путем варьирования значений которой достигаются необходимые значения критериальной переменной модели,
следует активировать флаг «Константа» (подробнее см. в описании
режима «Эксперимент»).
4. Корректировка расположения метки осуществляется следующим образом:
– нажимается правая кнопка мыши на метке переменной;
– при нажатой кнопке мышь перемещается в новое положение;
– кнопка отпускается.
Изменение атрибутов графических элементов
Для знака оператора возможно изменение только операции, соответствующей знаку оператора. Порядок действий следующий.
1. Выбирается соответствующая знаку оператора команда в
меню или нажимается кнопка на панели инструментов, если таковая имеется.
2. Щелчком мыши указывается узел сетки рабочего поля, в котором будет располагаться знак оператора.
Для метки переменной возможно изменение всех атрибутов.
1. Выбирается соответствующая команда в меню или нажимается кнопка метки переменной на панели инструментов.
2. Щелчком мыши указывается модифицируемая метка – появляется окно «Новая метка дуги» (см. рис. 47).
3. Корректируются атрибуты метки переменной.
Атрибуты дуг и значков разметки корректировке не подлежат.
Удаление графических элементов
Удаление знака оператора
1. На панели инструментов выбирается режим удаления.
2. Щелчком мыши указывается удаляемый оператор.
При этом удаляются все связанные со знаком оператора значки
разметки.
Удаление дуги
1. На панели инструментов выбирается режим удаления.
2. Щелчком мыши указывается удаляемая дуга. Появляется запрос на подтверждение удаления (рис. 48). Удаляются все связанные с дугой значки разметки и метки переменных.
91
Рис. 48. Удаление дуги
Удаление метки переменной
1. На панели инструментов выбирается режим удаления.
2. Щелчком мыши указывается удаляемая метка.
Значки разметки отдельно удалить нельзя.
Синтаксическая проверка
Для текущей проверки построенной графической конструкции
на соблюдение синтаксическим правилам можно выбрать пункт
«Проверить синтаксис» меню «Модель». Синтаксическая проверка
осуществляется в несколько этапов.
1. Проверяется соблюдение требований к минимальной форме
каждого оператора. Если ошибки не обнаружены, то переход к следующему пункту. Иначе выдается сообщение «Имеются проблемы
с минимальной формой» и подсвечиваются знаки неправильно введенных операторов.
2. Проверяется отсутствие контуров, не содержащих операторы
задержки. Если ошибки не обнаружены, то модель считается синтаксически верной. Иначе выдается сообщение «В модели имеются
циклы», подсвечиваются найденные контуры.
Если модель верна, то можно перейти к заданию массива данных. Для этого необходимо сохранить модель, нажав кнопку «Сохранить модель» на панели инструментов или выбрав пункт меню
«Модель\Сохранить». Если модель сохраняется впервые, то будет
запрошено имя файла модели. Как только модель сохранена, можно переходить в режим «Данные» для создания массива данных
для сохраненной модели, выбрав пункт меню «Режим\Данные».
Задание общих свойств и сохранение модели
Для задания свойств модели выбирается пункт «Свойства модели…» меню «Модель». После этого появляется окно (рис. 49), в
котором можно задать имя модели, масштаб по горизонтали и вертикали, описание модели.
92
Рис. 49. Свойства модели
Для сохранения модели с заданным именем выбирается пункт
«Сохранить как…» меню «Модель». После этого появляется окно
(рис. 50).
Рис. 50. Сохранение модели
93
Дополнительные возможности и пример
построения модели
Кратко перечислим дополнительные возможности графического редактора системы.
1. Спрятать-показать сетку рабочего поля графического редактора (пункт «Спрятать сетку» меню «Вид»).
2. Изменение масштаба модели.
3. Печать модели на бумагу (пункт «Печать…» меню «Модель»).
4. Экспорт модели в Microsoft Word (пример – рис. 51).
Рассмотрим пример построения модели. Предположим, что необходимо создать модель «Расчет численности населения», позволяющую определять численность населения в некотором регионе
за определенный период. Очевидно, в этой модели должна присутствовать переменная «численность населения в текущем году», а
также переменные, на основании которых она может быть вычислена: «численность населения в прошлом году», «прирост населения в текущем году» и «убыль населения в текущем году». Определив функциональные отношения, связывающие интересующие нас
переменные, и описав их в языке АС, получим АС искомой модели
(см. рис. 51).
На рисунке указаны короткие имена переменных (х1 – х5). Сопоставим им длинные имена:
х1 – численность населения на конец предыдущего периода;
х2 – прирост населения в текущем периоде;
х3 – численность населения с учетом прироста в текущем периоде;
х4 – убыль населения в текущем периоде;
х5 – численность населения в текущем периоде.
x4 (убыль населения)
x2 (прирост населения)
x3
x5
∆t
x1 (численность населения)
Рис. 51. Модель «Расчет численности населения» –
пример экспорта в MS Word
94
Из рисунка видно, что искомая численность населения в текущем периоде (х5) вычисляется на основании значений переменных
х1, х2, х4. Вычисления производятся по выражениям
х3(t) = х1(t) + х2(t);
х5(t) = х3(t) – х4(t);
х1(t+1) = х5(t).
Как видно из рис. 51 и приведенных формул, внесение оператора «задержка» (Dt) позволило внести динамику в модель, организовать расчет х5, используя на последующих шагах данные, формируемые в модели.
Рассмотрим один из возможных вариантов ввода модели «Расчет численности населения» в графическом редакторе по шагам
(рис. 52–56).
Операции по работе с буфером обмена
В текущей версии системы КОГНИТРОН поддерживаются операции по работе с буфером обмена в меню « Рисование».
– выделение фрагмента (пункт «Выделить фрагмент »);
– копирование выделенного фрагмента в буфер (пункт «Копировать в буфер»);
Рис. 52. Ввод знаков операторов
95
Рис. 53. Ввод дуг
Рис. 54. Ввод значков разметки
96
Рис. 55. Нанесение меток переменных
Рис. 56. Модель после присвоения ей имени «Пример»
97
– копирование выделенного фрагмента с удалением его из текущей модели (вырезка выделенного фрагмента) (пункт «Вырезать в
буфер»);
– вставка фрагмента из буфера (пункт «Вставить из буфера»).
Поскольку в системе поддерживается работа с несколькими моделями, буфер обмена хранится в оперативной памяти, как обычная модель, отличающаяся только тем, что она не доступна пользователю путем переключения окон моделей и не имеет имени файла,
в котором хранится модель.
Копирование фрагмента в буфер осуществляется путем создания
в модели буфера обмена копий графических элементов, попавших
в выделенный фрагмент. Если во фрагмент попала только часть
дуги, то в буфер копируется только часть, попавшая в выделение.
Если дуге уже было сопоставлено имя, то дуга в буфере сохраняет
его, независимо от того, попадает метка в выделенный фрагмент
или нет. Это сделано для того, чтобы скопированный фрагмент был
эквивалентен исходному с точки зрения вычислений.
При вырезке выделенного фрагмента дополнительно к случаю
копирования необходимо удаление в исходной модели попавших в
выделение графических элементов. Наиболее сложным является
случай обработки дуг, поскольку может подлежать удалению только часть дуги. Разработан специальный алгоритм обработки дуг.
Вставка фрагмента из буфера происходит как последовательная
имитация интерактивного ввода соответствующих графических
примитивов. Сначала вставляются знаки операторов, затем дуги,
в последнюю очередь – метки переменных и значки разметки. При
вставке каждого примитива, как и при интерактивном вводе, происходит синтаксическая проверка. В результате может быть вставлено только то подмножество графических примитивов, которое не
противоречит правилам графического синтаксиса.
Режим «Данные»
Если вход в режим был осуществлен сразу после запуска системы, то необходимо открыть нужную модель («Модель\Открыть...»)
(рис. 57). Если модель является синтаксически неверной, то автоматически будет осуществлен переход в режим «Модель». Переход
в режим «Данные» из режима «Модель» для выбранной модели допускается только для синтаксически верной модели.
В случае необходимости просмотра АС можно вызвать пункт
меню «Модель\Просмотреть». При этом выбранная модель открывается в режиме «Модель», но никакие действия по изменению мо98
Рис. 57. Режим «Данные»
дели невозможны. Для возврата к режиму данных в режиме просмотра АС нужно вызвать «Модель\Закрыть».
При создании и редактировании массивов доступны следующие
функции:
1) редактирование значений массива;
2) заполнение массива с использованием линейной аппроксимации;
3) заполнение массива константой;
4) сохранение массива на диск;
5) дублирование массива под другим именем;
6) изменение свойств массива (названия, описания, числа периодов и т. д.).
Создание массива данных
Для создания массива данных нужно вызвать пункт меню «Данные\Создать…» или нажать кнопку на панели инструментов. При
этом появится диалог свойств массива (рис. 58).
Общий вид системы при вводе (редактировании) данных показан на рис. 59.
99
Рис. 58. Диалог задания свойств массива данных
Рис. 59. Режим «Данные» – ввод данных
100
По умолчанию в данном режиме отображаются выходы задержек и входные переменные. Для просмотра расчетных переменных
нужно активировать «Вид\Показать расчетные переменные».
Ввод массива данных
Для изменения отдельного значения необходимо кликнуть левой кнопкой мыши в соответствующую ячейку и отредактировать
значение. Система позволяет редактировать только выходы задержек на первом расчетном шаге и входные переменные.
Для заполнения всех значений переменной значением, введенным в текущей ячейке, нужно вызвать пункт меню «Ввод\Константа…» или нажать кнопку на панели инструментов (рис. 60).
Рис. 60. Заполнение константой
Рис. 61. Режим «Данные» – аппроксимация
101
Ряд значений можно добавить с использованием линейной аппроксимации. Для этого необходимо ввести начальное и конечное
значения для переменной, выделить диапазон и вызвать «Ввод\Аппроксимировать» (или нажать кнопку
на панели инструментов)
(рис. 61). Также возможно задание значений на первом и последнем шаге расчета, в этом случае выделение диапазона не требуется.
Если модель содержит большое количество переменных, затрудняющее их поиск в таблицах, то можно выполнить их поиск, используя кнопку
(рис. 62). В результате система выделит строку,
содержащую искомую переменную (рис. 63).
Рис. 62. Поиск переменной
Рис. 63. Результат поиска переменной
102
Сохранение массива данных
Для сохранения массива данных на диске воспользуйтесь пунк- том меню «Данные\Сохранить» или кнопкой на панели инструментов. При этом анализируется, все ли значения переменных введены
(еще не введенные значения отмечены «–»). В случае если все переменные уже введены, при сохранении данных автоматически будет
выполнен расчет модели и будут заполнены значения расчетных
переменных и значения выходов задержки на шагах, отличных от
начального.
Также расчет модели можно вызвать принудительно пунктом
«Ввод\Рассчитать» или нажав кнопку
на панели инструментов.
Для изменения свойств массива данных нужно вызвать пункт
меню «Данные\Свойства данных…» или нажать кнопку
на панели инструментов. При этом появится диалоговое окно свойств
массива (см. рис. 58).
При необходимости можно создать копию массива под другим
именем, вызвав «Данные\Дублировать как…». (Важно: для сохранения на диске после дублирования необходимо вызвать «Данные\
Сохранить»).
Режим «Эксперимент»
Проведение эксперимента. Создание эксперимента
Если вход в режим был осуществлен сразу после запуска системы, то необходимо открыть нужную модель («Модель\Открыть...»)
(рис. 64). Если модель является синтаксически неверной, то автоматически будет осуществлен переход в режим «Модель». Переход
в режим «Эксперимент» из режима «Модель» для выбранной модели допускается только для синтаксически верной модели. В случае
необходимости просмотра АС можно вызвать пункт меню «Модель\
Просмотреть».
Для создания эксперимента нужно вызвать пункт меню «Эксперимент\Создать…» или нажать кнопку на панели инструментов. При
этом появится диалоговое окно создания эксперимента (рис. 65).
В окне необходимо выбрать массив данных, на основе которого хотите создать эксперимент, ввести имя эксперимента и нажать «Ok».
Общий вид системы в режиме эксперимента показан на рис. 66.
Пользователю доступны таблицы выходов задержек, входных и
расчетных переменных слева и рабочая таблица с таблицей ограничений справа.
103
Рис. 64. Режим «Эксперимент»
Рис. 65. Создание эксперимента
104
105
Рис. 66. Режим «Эксперимент» – общий вид
Заполнение данных константой и аппроксимация в режиме эксперимента осуществляется так же, как и в режиме данных (пункты
меню «Выполнение\Константа…» и «Выполнение\Аппроксимировать» соответственно).
Поиск переменных в режиме эксперимента работает аналогично
режиму данных.
Создание рабочей таблицы
Для работы с рабочей таблицей нужно справа выбрать закладку
«Рабочая таблица». Рабочая таблица используется для сокращения
списка анализируемых переменных. Для того чтобы отображать в
таблицах только переменные, включенные в рабочую таблицу, нужно снять галку у пункта меню «Выполнение\Определить среду».
Включение выделенной переменной осуществляется вызовом
пункта «Выполнение\Включить переменную» либо нажатием
кнопки
на панели инструментов (рис. 67). Включение всех переменных — вызовом пункта «Выполнение\Включить все переменные» либо нажатием кнопки
на панели инструментов.
Исключение текущей переменной из рабочей таблицы осуществляется вызовом пункта «Выполнение\Исключить переменную»
либо нажатием кнопки
на панели инструментов. Для полной
очистки рабочей таблицы нужно вызвать пункт меню «Выполнение\Очистить таблицу» либо нажать кнопку
на панели инструментов.
Создание таблицы ограничений
Для задания ограничений на переменные нужно справа выбрать
закладку «Ограничения». Для того чтобы наложить на переменную ограничение, достаточно добавить ее в таблицу ограничений
справа и задать ограничение в соответствующей ячейке таблицы
ограничений. Операции с таблицей ограничений осуществляются
аналогично операциям с рабочей таблицей (при этом должна быть
активна закладка таблицы ограничений). После выполнения расчета ячейки, значения в которых не удовлетворяют заданным ограничениям, будут выделены красным цветом (рис. 68).
Сохранение эксперимента и построение графиков
Для сохранения эксперимента на диске воспользуйтесь пунктом
меню «Эксперимент\Сохранить» или кнопкой на панели инструментов. При сохранении автоматически будет выполнен расчет мо106
107
Рис. 67. Добавление переменных в рабочую таблицу
108
Рис. 68. Таблица ограничений и нарушение ограничений
дели. При необходимости можно создать копию эксперимента под
другим именем, вызвав «Эксперимент\Дублировать как…». (Важно: для сохранения на диске после дублирования необходимо вызвать «Данные\Сохранить»).
Также расчет модели можно выполнить принудительно, вызвав
«Выполнение\Рассчитать» или нажав кнопку
на панели инструментов.
Рассчитанные значения можно просмотреть на графике, причем на один график можно наложить несколько переменных (или
ограничений). Для этого необходимо отметить нужные переменные
(ограничения) в столбце «График» рабочей таблицы (таблицы ограничений).
Для просмотра графика (рис. 69) необходимо выбрать пункт
меню «Выполнение\График…» либо нажать кнопку
на панели
инструментов.
Методы достижения заданных значений критериальной переменной
Система позволяет достигать необходимых значений критериальных расчетных переменных с помощью метода обращения или
метода подгонки.
Рис. 69. График
109
110
Рис. 70. Задание анализируемой переменной
В данный момент система позволяет задать только одну анализируемую переменную. Для этого необходимо отметить нужную
переменную в столбце «Задать» рабочей таблицы (рис. 70).
Анализ может осуществляться в табличном или графическом
виде. Для анализа в табличном виде необходимо вызвать пункт
меню «Выполнение\Таблица…» или нажать кнопку
на панели инструментов. Для анализа в графическом виде необходимо
вызвать пункт меню «Выполнение\График…» или нажать кнопку
графика на панели инструментов.
Метод подгонки
В случае, если флаг «Выполнение\Численный метод» неактивен, система анализирует, возможно ли применение метода обращения для заданной переменной. (Важно: одним из необходимых
условий для применения метода обращения является то, что переменная не должна входить в контур.) Если флаг «Выполнение\Численный метод» активен или применение обращения невозможно,
применяется метод подгонки (рис. 71).
В открывшемся окне необходимо:
– путем перемещения точек на графике задать необходимые целевые значения (в случае вызова «Выполнение\Таблица…» целевые значения вводятся в таблице);
Рис. 71. Метод подгонки
111
– выбрать переменную, путем изменения значений которой
предлагается достичь заданных целевых значений;
– указать максимальное число итераций;
– задать точность вычислений;
– задать нижние и верхние пределы.
Для поиска решения необходимо нажать кнопку «Рассчитать».
Подгонка осуществляется для всех расчетных периодов. Критерием останова на текущем шаге является получение значения с заданной точностью либо достижение верхнего предела переменной
подгонки. Расчет производится для значений переменной подгонки, начиная с нижнего предела с шагом, равным разнице верхнего
и нижнего пределов, поделенным на заданное число шагов. Если
включен флаг «Использовать относит. значения», то нижний и
верхний пределы вычисляются как произведения заданного относительного значения на исходное значение переменной подгонки.
Например, переменная подгонки x2 равняется 5. Нижний предел
задан как 0.5, верхний – как 1.5. Используются значения x2 в ин-
Рис. 72. График после отработки метода подгонки
112
тервале от 2.5 до 7.5. Повторно построенный график после применения метода подгонки показан на рис. 72.
Метод обращения
В случае если флаг «Выполнение\Численный метод» неактивен
и обращение возможно, применяется метод обращения.
Для демонстрации возможностей метода откроем модель «Демография» (рис. 73).
Модель описывает процессы, происходящие с населением региона в течение выбранного интервала времени, и обеспечивает нахождение количества населения на конец года (x10) в зависимости
от начального значения (x1), доли убытия (x2), коэффициента естественного прироста (x6), механического прироста (x9). Модель позволяет рассмотреть процесс во времени за счет использования оператора «задержка» (∆t), определяющего значение переменной на
конец текущего периода в качестве начального значения соответствующей переменной для последующего периода: x1(t+1)=x10(t).
Кроме того, модель определяет величину трудового ресурса региона (x12) на основании доли трудового ресурса (x11) и количества
имеющегося населения (x10).
Выберем в качестве критериальной переменной переменную x12
(рис. 74). Вызовем «Выполнение\График…» (рис. 75).
В открывшемся окне необходимо:
– путем перемещения точек на графике задать необходимые целевые значения (в случае вызова «Выполнение\Таблица…» целевые значения вводятся в таблице);
– выбрать переменную для обращения.
Для поиска решения необходимо нажать кнопку «Рассчитать».
Повторно построенный график после применения метода обращения показан на рис. 76.
x4
x3
x6
x5
x9
x7
x8
x11
x10
x12
x1
∆t
Рис. 73. Алгоритмическая сеть модели «Демография»
113
114
Рис. 74. Рабочая таблица модели «Демография»
Рис. 75. Метод обращения
Рис. 76. График после отработки метода обращения
115
7.3. Примеры моделей, реализованных в системе
КОГНИТРОН 4.0
Модель решения СЛАУ методом Гаусса
Данная модель создана в качестве примера, демонстрирующего
возможности, рассмотренные в подразд. 6.4 и 6.5. Модель может
быть использована как библиотечная в более сложном модельном
комплексе.
Рассмотрим постановку задачи.
Требуется решить систему линейных алгебраических уравнений (СЛАУ)
AX = F,
где A – матрица системы размером n × n; X – вектор неизвестных
размером n; F – вектор правых частей размером n.
Решение системы методом Гаусса состоит из прямого и обратного хода.
В результате прямого хода система уравнений преобразуется к
виду
RX = G,
где R – матрица системы треугольного вида размером n × n с единицами на главной диагонали и нулями ниже нее; X – вектор неизвестных размером n; G – вектор правых частей размером n.
Формулы прямого хода:
(k-1) -1 (k-1)
Rk = [akk
] Ak
;
(k-1) -1 (k-1)
gk = [akk
] fk
;
(k-1)
Ai(k) = Ai(k-1) - aik
Rk ;
(k-1)
fi(k) = fi(k-1) - aik
gk ;
k = 1, n; i = k + 1, n
где Ai(k) – i-й столбец матрицы A на k-м шаге; fi(k) – i-й элемент вектора F на k-м шаге; Rk – k-й столбец матрицы R; gk – k-й элемент
вектора G.
В результате обратного хода получаем значения вектора X.
Формула обратного хода
xk = gk -
n
å
j=k+1
rkj xj , k = n, 1,
где xk – k-й элемент вектора X; rkj – элемент на пересечении k-й
строки и j-го столбца матрицы R.
116
Для реализации формул метода Гаусса необходимо использовать
вложенные циклы, а для хранения матрицы системы и вектора правых частей – массивы. Для организации вложенных циклов в АС реализовано обращение к модели, считаемой со своим шагом расчета.
В итоге, решение системы уравнений реализовано с помощью
АС, изображенных на рис. 77–88.
На рис. 77 реализована агрегированная модель метода Гаусса.
Оператор с номером 1 соответствует прямому ходу, с номером 2 –
обратному. Окна настройки дополнительных параметров (используются для задания параметров расчета вложенных моделей) операторов с номерами 1 и 2 показаны соответственно на рис. 78 и 79.
F¢
A
F
1
A¢
X¢
2
n
Рис. 77. Модель решения СЛАУ методом Гаусса
Рис. 78. Окно дополнительных параметров оператора 1 на рис. 77
117
Рис. 79. Окно дополнительных параметров оператора 2 на рис. 77
В окне дополнительных параметров задаются путь к вызываемой модели, массив данных модели, фактическое число расчетных
периодов (должно не превышать число периодов, заданное в указанном массиве данных), соответствие переменных в вызывающей
и вызываемой АС для входных и выходных переменных.
На рис. 80 показана модель, реализующая прямой ход метода Гаусса. В ней введен цикл по k. Данная АС ссылается в свою очередь
(k-1) -1 параметров
на две другие. Окна настройки дополнительных
операRk = [akk
] Ak(k-1) ;
торов с номерами(k0-и
1
показаны
соответственно
на
рис.
81
и
82.
(k-1) -1 (k-1)
gk = [akk
] fk
;
R = [akk 1) ]-1 Ak(k-1) ;
Операторk с номером
0 соответствует
реализации
формулы
k
k
k
(
)
(
1
)
(
1
)
k
k
(
1
)
(
1
)
1
(k-1g
) -=
1 [a(k-1) ] f
A
=
A
a
R
;
;
k
Rk = [akk k] Akkk ;(см.kрис. 83). Оператор
1 реализует
i
i с номером
ik
(k)
(k-1)
(k-1)
(k1) (k-1()k-1)
(k-1)
(k-1)Af
=
f
a
g
формулы
,
,
=
A
a
R
;
k ; i = k+1, n
k i
gk = [akk ]i fk i ;
i
ik
ik
k
k
k
(
)
(
1
)
(
1
)
(см.
рис.
84).
)
f(ik-1) R a
gk ; k = 1, n; i = k + 1, n
Ai(kАлгоритмическая
= Ai(k-fi1) -=aik
k ; ik показанная
сеть,
на рис. 84, ссылается, в свою
; i = k + 1, n
) = 1, (n
1k
fi(k) = fi(k-на
- aikk-1) g–k ;оператор с номером 2, соответствующий реаочередь,
другую
лизации
k = 1, n; i формулы
= k + 1, n Ai(k) = Ai(k–1)–aik(k–1)Rk (см. рис. 85). Окно настройки дополнительных параметров показано на рис. 86.
На рис. 87 реализована общая схема обратного хода метода Гаусса. В ней введен цикл по k. Данная АС ссылается в свою очередь на
другую (оператор 0, окно настройки дополнительных параметров
показано на рис. 88), соответствующую сумме rkjxj (рис. 89).
118
∆t
1
k
1
akk
A
i->
<>0
k
kk
kk
n
n
A
∆t
n
akk
F¢¢
A¢
0
1
k
akk
k
F
k
F¢
i->
A¢¢
F
F¢
->i
k
∆t
F¢¢
Рис. 80. Модель, реализующая прямой ход метода Гаусса
119
Рис. 81. Окно дополнительных параметров оператора 0 на рис. 80
Рис. 82. Окно дополнительных параметров оператора 1 на рис. 80
120
akk
n
akk¢
j
∆t
<
<>0
1
1
n
k
akk¢
j
kj
A
i->
->i
A¢
kj
A
∆t
Рис. 83. Модель, реализующая прямой ход метода Гаусса:
преобразование k-й строки матрицы СЛАУ
Пример решения системы
x1 + 3x2 + x3 = 4
2x1 + 3x2 + x3 = 3
–2x1 + 3x2 – 4x3 = –8
показан на рис. 90 (значения переменной X′).
121
aik
k
∆t
aik¢
i
>
–1
1
<
n
k
A
i->
aik
F
i->
aik¢
F
->i
i
k
i->
F¢
i
i
n
t
i
∆t
A
n
aik¢
A¢
2
k
Рис. 84. Модель, реализующая прямой ход метода Гаусса:
преобразование строк матрицы и элементов правой части
СЛАУ при i = k+1, n
122
n
∆t
aik
aik¢
j
<
1
kj
i
ij
n
j
k
kj
A
i->
aik¢
A
->i
ij
i->
A¢
ij
∆t
Рис. 85. Модель, реализующая прямой ход метода Гаусса:
преобразование i-й строки матрицы СЛАУ
Рис. 86. Окно дополнительных параметров оператора 2 на рис. 84
123
n
k
k0
1
∆t
X
xk
A
0
k
∆t
∆t
k
xk
X
X¢
F
i->
->i
k
∆t
Рис. 87. Модель, реализующая обратный ход метода Гаусса
Рис. 88. Окно дополнительных параметров оператора 0 на рис. 87
124
n
∆t
j
flag
<
1
>
k
j
X
n
k
i->
j
kj
∆t
kj
A
xk
i->
flag
Рис. 89. Модель, реализующая обратный ход: вычисление суммы rkjxj
Моделирование полета ракеты
Простейшая модель движения ракеты с учетом силы тяги двигателей [22] может быть получена из закона сохранения импульса.
Считаем, что продукты сгорания топлива покидают сопло ракеты
со скоростью u. За время dt часть топлива выгорает, вес ракеты
уменьшается на dm, а ее скорость увеличивается на dv. При этом
суммарный импульс ракеты остается неизменным, т. е.
m(t)v(t) = m(t+dt)v(t+dt)–dm(v(t +εdt)–u).
Учитывая, что m(t+dt) = m(t)+dm, закон сохранения импульса
можно переписать в виде
dv
dm
m
=u.
dt
dt
Здесь m – масса ракеты; v – скорость движения ракеты; ε – параметр усреднения для скорости.
125
Рис. 90. Режим данных модели решения СЛАУ методом Гаусса
В конечных разностях уравнения, описывающие движение ракеты, будут иметь вид
mt((tt +
+D
Dtt)) =
= mt
-D
Dmt
mt
mt((tt)) mt;;
D
=
D
m
mt
;
Dm = Dmt;
m
= mt
+ mp
+ ms
m((tt)) =
mt((tt)) +
mp +
ms;;
D
Dm
m
D
Dv
v((tt)) =
=u
u m(t) ;;
m(t)
v
v((tt +
Dtt)) =
v((tt)) +
Dv
v((tt)) gD
Dtt,,
+D
=v
+D
-g
где mt – масса топлива; mp – масса полезного груза; ms – масса конструкционных элементов двигателей и баков; g – ускорение силы
тяжести, ∆mt – удельный расход топлива; ∆t – шаг счета.
Данная система уравнений позволяет описать движение как
одно-, так и многоступенчатой ракеты. В многоступенчатой ракете при выгорании топлива i-ступени происходит отделение баков и
двигательной установки этой ступени, в результате чего начальная
масса (i+1)-ступени становится равной массе полезного груза предыдущей ступени.
126
127
dm2f
∆t
∆t
∆t
dm3f
m
dm3f
dm2f
dm 1 f
u
dv
nul
nul
>=0
>=0
>=0
nul
v
dm33f
dm22f
dmt1
vn
nul
dmt3
nul
∆t
>=0
>=0
dmt2
g
max
dt
mt3
dm1f
mt2
mt1
∆t
hn
h
mb3
m3f
dm2f
mb2
m2f
mb1
m1f
m22f
dm2f
nul
dm1f
m11f
nul
=0
nul
=0
=0
Рис. 91. Алгоритмическая сеть модели полета многоступенчатой ракеты
dmf
dm1f
mt3
mt3n
mt2
mt2n
mt1
mt1n
dt
vn
m33f
m
Для проведения расчетов на каждой ступени должны быть заданы начальная масса топлива, масса двигательной установки и
баков, масса полезного груза, удельный расход топлива. За начальную скорость движения i-ступени ракеты принимаем конечную
скорость, достигнутую на предыдущем этапе разгона.
Соотношение масс для трехступенчатой ракеты может быть
представлено в виде
mp3 + mt1 + ms1 + mt2 + ms2 + mt3 + ms3
;
mp3 + mt2 + ms2 + mt3 + ms3
mp3 + mt2 + ms2 + mt3 + ms3
δ2 =
;
mp3 + mt3 + ms3
mp3 + mt3 + ms3
δ3 =
.
mp3
δ1 =
В числителе выражений – полная масса ракеты при включении
двигателя, в знаменателе – полезная нагрузка для 1-, 2- и 3-й ступени ракеты соответственно. В оптимальном случае δ1 = δ2 = δ3.
Рис. 92. Исходные данные
128
Рис. 93. Рабочая таблица
Рис. 94. График скорости
129
Рис. 95. График ускорения
В приведенном ниже примере задано:
– масса топлива [кг]: mt1=90 000, mt2=9000, mt3=900;
– масса двигательной установки, баков и полезного груза ступеней ракеты [кг]: mb1=1000, mb2=1000, mb3=100;
Рис. 96. График высоты полета
130
Рис. 97. График массы
– удельный расход топлива [кг/с]: dmt1=450, dmt2=45,
dmt3=4,5;
– скорость истечения газов u=3000 м/с, шаг счета dt=1 с;
– g=9,8 м/с2.
Алгоритмическая сеть модели трехступенчатой ракеты приведена на рис. 91; исходные данные (режим данных) и рабочая таблица
(режим эксперимент) – на рис. 92 и 93 соответственно; графики скорости, ускорения, высоты полета и массы ракеты – на рис. 94–97.
131
Заключение
Придирчивый читатель обнаружит много недостатков и ограничений в алгоритмическом подходе к моделированию и в формализме АС. Не будем ему мешать в этом. Обратим внимание на достоинства и преимущества, которые, на наш взгляд, АС имеют.
1. Алгоритмическая сеть – это средство представления моделей.
Для многих, по-видимому, для большинства людей графический
образ понятнее и ближе, чем список формул. Особенно если это
касается трубопроводов, транспортных и энергетических систем,
потоков энергии и вещества в экосистемах. АС отображает здесь
структуру потоков реального объекта.
2. Алгоритмическая сеть – это максимально распараллеленный
алгоритм, по которому может быть построена расчетная программа автоматически без участия человека-программиста. Напомним,
что в популярной и превосходной во многих отношениях вычислительной среде Matlab требуется не только разработать алгоритм, но
и составить компьютерную программу.
3. Алгоритмическая сеть строится по простым правилам и с
ограниченным набором операторов. Предметный специалист, не
знакомый с языками программирования, легко осваивает способы
построения своих моделей в форме АС. Для проведения компьютерных экспериментов он имеет инструментальную систему моделирования КОГНИТРОН. Это технология моделирования «без
посредника» [8]. Однако операторный базис сетей может быть расширен.
4. Алгоритмическая сеть – это вычислительная структура алгоритмической модели. Она не содержит дополнительных элементов
для организации ввода-вывода данных. Это позволило ввести операции над сетями и построить алгебру эквивалентных преобразований моделей. В частности, для «ленивых» пользователей на этой
основе реализована «кнопочная» технология синтеза модели, напоминающая детскую игру в кубики.
Внимательный читатель сможет найти и развить другие полезные для себя свойства АС. Успехов ему в этом!
132
Библиографический список
1. Поспелов Г. С. Искусственный интеллект – основа новой информационной технологии. М.: Наука, 1988. 178 с.
2. Иванищев В. В. Автоматизация моделирования потоковых
систем. М.: Наука, 1986. 142 с.
3. Иванищев В. В., Михайлов В. В. Автоматизация моделирования экологических систем / СПбГТУ. СПб., 2000. 171 с.
4. Иванищев В. В., Михайлов В. В., Тубольцева В. В. Инженерная экология (вопросы моделирования). Л.: Наука, 1989. 147 с.
5. Иванищев В. В., Марлей В. Е. Введение в теорию алгоритмических сетей / СПбГТУ. СПб., 2000. 180 с.
6. Советов Б. Я., Яковлев С. А. Моделирование систем. М.: Высш.
шк., 2007. 365 с.
7. Пономарев В. М. Алгоритмические модели в задачах исследования систем //Алгоритмы и системы автоматизации исследования и проектирования. М.: Наука, 1980. С. 4–8.
8. Иванищев В. В. Моделирование без посредника // Теория и
системы управления / Изв. РАН. 1997. № 5. С. 95–98.
9. Успенский В. А. Лекции о вычислимых функциях. М.: Физматгиз, 1960. 495 с.
10. Глушков В. М. Синтез цифровых автоматов. М.: Физматгиз,
1962. 476 с.
11. Блох А. Ш. Граф-схемы и алгоритмы. Минск: Высш. шк.,
1987. 144 с.
12. Ерош И. Л., Михайлов В. В. Проектирование цифровых
автоматов: учеб. пособие. Ч. 1. СПб.: СПбГУАП, 2009. 80 с.
13. Марлей В. Е. Алгебра алгоритмических сетей // Теоретические основы и прикладные задачи интеллектуальных информационных технологий. СПб.: Анатолия, 1998. С. 200–207.
14. Кандрашина Е. Ю., Литвинцева Л. В., Поспелов Д. А. Представление знаний о времени и пространстве в интеллектуальных
системах. М.: Наука, 1989. 326 с.
15. Королев О. Ф. Синтаксис графического построения алгоритмических сетей // Информационные технологии и интеллектуальные методы / СПИИРАН. СПб., 1999. Вып. 3. С. 112–131.
16. Королев О. Ф. Методы графического представления моделей
на основе алгоритмических сетей и их программная реализация:
дис. ... канд. техн. наук. СПб., 2003. 162 с. (СПИИРАН, СПб.)
17. Морозов В. П. Алгоритмы синтаксического контроля при автоматической генерации программ в системе САПФИР-Искра.87 //
133
Методы и средства информационной технологии в науке и производстве. СПб.: Наука, 1992. С. 114–130.
18. Королев О. Ф. Алгоритмы поиска контуров в алгоритмической сети // Информационные технологии и интеллектуальные методы / СПИИРАН. СПб., 1999. Вып. 3. С. 147–156.
19. Михайлов В. В. Матричные алгоритмические сети и их применение // Теоретические основы и прикладные задачи интеллектуальных информационных технологий. СПб.: Анатолия, 1998.
С. 207–221.
20. Гантмахер Ф. Р. Теория матриц. М.: Наука, 1988. 547 с.
21. Стренг Г. Линейная алгебра и ее применения. М.: Мир,
1980. 454 с.
22. Самарский А. А., Михайлов А. П. Математическое моделирование: идеи, методы, примеры. М.: Наука. Физматгиз, 1997. 320 с.
134
СОДЕРЖАНИЕ
Введение........................................................................... 3
1. Понятие алгоритмических сетей....................................... 5
1.1. Определение алгоритмической сети............................ 5
1.2. Алгоритмический базис и правила построения AC........ 6
1.3. План вычислений и обратимость AC........................... 8
1.4. Алгоритмические сети и модели................................. 10
2. Алгоритмическая полнота и реализация вложенных циклов. 14
2.1. Проблема алгоритмической полноты AC..................... 14
2.2. Реализация вложенных циклов на AC путем имитации. 16
3. Операции над алгоритмическими сетями........................... 22
3.1. Бинарные операции над сетями................................. 22
3.2. Унарные операции над сетями................................... 23
3.3. Свойства операций над AC......................................... 29
4. Согласования фрагментарных AC..................................... 34
4.1. Операции согласования AC........................................ 34
4.2. Процедуры согласования AC и формирование «белой» базы фрагментарных моделей.......................................... 37
4.3. Пример согласования и комплексирования фрагмен- тарных моделей............................................................. 43
5. Формализация графического ввода алгоритмической сети... 53
5.1. Технология создания АС при графическом вводе.......... 53
5.2. Блочно-фрагментарная технология ввода АС............... 60
5.3. Правила графического синтаксиса............................. 62
6. Расширения языка: матричные алгоритмические сети и итерационные процедуры................................................. 67
6.1. Матричный алгоритмический базис и правила постро- ения матричных АС....................................................... 67
6.2. Определение типов переменных и размерностей масси- вов в МАС..................................................................... 70
6.3. Обратимость операторов МAC.................................... 71
6.4. Расширение языка АС для представления итерацион- ных процедур................................................................ 74
6.5. Упрощенная поддержка работы с матричными пере- менными...................................................................... 76
6.6. Примеры реализации моделей на языке МAC. ............. 77
7. Построение систем автоматизации моделирования на основе
формализма алгоритмических сетей..................................... 82
7.1. Предыдущие версии системы автоматизации............... 82
7.2. Краткое описание версии КОГНИТРОН 4.0................. 86
7.3. Примеры моделей, реализованных в системе КОГНИТРОН 4.0........................................................... 116
Заключение...................................................................... 132
Библиографический список................................................. 133
135
Учебное издание
Михайлов Владимир Валентинович
Марлей Владимир Евгеньевич
Королев Олег Федорович
АЛГОРИТМИЧЕСКИЕ СЕТИ И ИХ ПРИМЕНЕНИЕ
Учебное пособие
Редактор А. Г. Ларионова
Верстальщик С. Б. Мацапура
Сдано в набор 22.12.12. Подписано к печати 13.02.13.
Формат 60×84 1/16. Бумага офсетная. Усл. печ. л. 8,5.
Уч.-изд. л. 8,2. Тираж 100 экз. Заказ № 624.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
Документ
Категория
Без категории
Просмотров
0
Размер файла
7 726 Кб
Теги
mixailovmarley
1/--страниц
Пожаловаться на содержимое документа