Моделирование модульных систем с применением дискретной теории паттернов
Рассмотрены основные понятия и положения дискретной теории паттернов и паттерновых сетей — нового направления анализа и моделирования модульных систем. Описаны примеры использования паттерновых сетей в задачах моделирования локальных компьютерных сетей и представления сценариев на основе И–ИЛИ-графо...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/12413 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Моделирование модульных систем с применением дискретной теории паттернов / _ И.И. Коваленко, О.А. Кудин // Систем. дослідж. та інформ. технології. — 2009. — № 2. — С. 78-91. — Бібліогр.: 7 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-12413 |
|---|---|
| record_format |
dspace |
| spelling |
Коваленко, И.И. Кудин, О.А. 2010-10-07T20:07:05Z 2010-10-07T20:07:05Z 2009 Моделирование модульных систем с применением дискретной теории паттернов / _ И.И. Коваленко, О.А. Кудин // Систем. дослідж. та інформ. технології. — 2009. — № 2. — С. 78-91. — Бібліогр.: 7 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/12413 004.7:004.93 Рассмотрены основные понятия и положения дискретной теории паттернов и паттерновых сетей — нового направления анализа и моделирования модульных систем. Описаны примеры использования паттерновых сетей в задачах моделирования локальных компьютерных сетей и представления сценариев на основе И–ИЛИ-графов (деревьев). Розглянуто основні уявлення і положення дискретної теорії паттернів та паттернових мереж — нового напряму аналізу та моделювання модульних систем. Описано приклади використання паттернових мереж у задачах моделювання локальних комп’ютерних мереж і зображення сценаріїв на основі І–АБО-графів (дерев). Principles of the discrete theory of patterns and pattern networks, which is new trend in analyzing and simulating module systems are described. Examples of the use of pattern networks in modeling local networks and notation of scripts on the basis of the AND-ORchart (trees) are demonstrated. ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Математичні методи, моделі, проблеми і технології дослідження складних систем Моделирование модульных систем с применением дискретной теории паттернов Modeling of module systems using the discrete theory of patterns Моделювання модульних систем із застосуванням дискретної теорії паттернів Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Моделирование модульных систем с применением дискретной теории паттернов |
| spellingShingle |
Моделирование модульных систем с применением дискретной теории паттернов Коваленко, И.И. Кудин, О.А. Математичні методи, моделі, проблеми і технології дослідження складних систем |
| title_short |
Моделирование модульных систем с применением дискретной теории паттернов |
| title_full |
Моделирование модульных систем с применением дискретной теории паттернов |
| title_fullStr |
Моделирование модульных систем с применением дискретной теории паттернов |
| title_full_unstemmed |
Моделирование модульных систем с применением дискретной теории паттернов |
| title_sort |
моделирование модульных систем с применением дискретной теории паттернов |
| author |
Коваленко, И.И. Кудин, О.А. |
| author_facet |
Коваленко, И.И. Кудин, О.А. |
| topic |
Математичні методи, моделі, проблеми і технології дослідження складних систем |
| topic_facet |
Математичні методи, моделі, проблеми і технології дослідження складних систем |
| publishDate |
2009 |
| language |
Russian |
| publisher |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| format |
Article |
| title_alt |
Modeling of module systems using the discrete theory of patterns Моделювання модульних систем із застосуванням дискретної теорії паттернів |
| description |
Рассмотрены основные понятия и положения дискретной теории паттернов и паттерновых сетей — нового направления анализа и моделирования модульных систем. Описаны примеры использования паттерновых сетей в задачах моделирования локальных компьютерных сетей и представления сценариев на основе И–ИЛИ-графов (деревьев).
Розглянуто основні уявлення і положення дискретної теорії паттернів та паттернових мереж — нового напряму аналізу та моделювання модульних систем. Описано приклади використання паттернових мереж у задачах моделювання локальних комп’ютерних мереж і зображення сценаріїв на основі І–АБО-графів (дерев).
Principles of the discrete theory of patterns and pattern networks, which is new trend in analyzing and simulating module systems are described. Examples of the use of pattern networks in modeling local networks and notation of scripts on the basis of the AND-ORchart (trees) are demonstrated.
|
| issn |
1681–6048 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/12413 |
| citation_txt |
Моделирование модульных систем с применением дискретной теории паттернов / _ И.И. Коваленко, О.А. Кудин // Систем. дослідж. та інформ. технології. — 2009. — № 2. — С. 78-91. — Бібліогр.: 7 назв. — рос. |
| work_keys_str_mv |
AT kovalenkoii modelirovaniemodulʹnyhsistemsprimeneniemdiskretnoiteoriipatternov AT kudinoa modelirovaniemodulʹnyhsistemsprimeneniemdiskretnoiteoriipatternov AT kovalenkoii modelingofmodulesystemsusingthediscretetheoryofpatterns AT kudinoa modelingofmodulesystemsusingthediscretetheoryofpatterns AT kovalenkoii modelûvannâmodulʹnihsistemízzastosuvannâmdiskretnoíteoríípatternív AT kudinoa modelûvannâmodulʹnihsistemízzastosuvannâmdiskretnoíteoríípatternív |
| first_indexed |
2025-11-25T21:07:29Z |
| last_indexed |
2025-11-25T21:07:29Z |
| _version_ |
1850550888519696384 |
| fulltext |
© И.И. Коваленко, О.А. Кудин, 2009
78 ISSN 1681–6048 System Research & Information Technologies, 2009, № 2
УДК 004.7:004.93
МОДЕЛИРОВАНИЕ МОДУЛЬНЫХ СИСТЕМ
С ПРИМЕНЕНИЕМ ДИСКРЕТНОЙ ТЕОРИИ ПАТТЕРНОВ
И.И. КОВАЛЕНКО, О.А. КУДИН
Рассмотрены основные понятия и положения дискретной теории паттернов и
паттерновых сетей — нового направления анализа и моделирования модуль-
ных систем. Описаны примеры использования паттерновых сетей в задачах
моделирования локальных компьютерных сетей и представления сценариев на
основе И–ИЛИ-графов (деревьев).
ВВЕДЕНИЕ
В настоящее время для моделирования структур и содержаний информаци-
онных систем используются чаще всего два метода — графовый и таблич-
ный, которые позволяют создавать наглядные и понятные модели информа-
ционных и других систем. Однако появление в последние 10–15 лет
сложных территориально-распределенных информационных систем, рабо-
тающих на основе компьютерных сетей, всевозможных Web-страниц, язы-
ков HTML, XML и т.д. обусловило необходимость создания новых методов
моделирования и проектирования информационных систем, расширяющих
и дополняющих графовые и табличные методы.
Этой потребности отвечают паттерновые сети и основанная на них
«парадигма модульного мышления», которая появилась в конце 20-го века в
результате создания У. Гренандером теории паттернов (pattern — образ)
[1–4]. В дальнейшем в результате ограничения области действия формаль-
ного аппарата теории паттернов были созданы основы дискретной теории
паттернов, опубликованные в работе [5]. Данная теория послужила основой
построения нового вида модульных систем, названных паттерновыми сетя-
ми. Благодаря своим модульным свойствам, паттерновые сети моделируют
структуры, содержание и другие характеристики модульных систем. Дис-
кретная теория паттернов и паттерновые сети в настоящее время находятся
в начальной стадии развития и их практическое применение в основном
сводится к моделированию компьютерных гипертекстов как модульных
систем.
Цель статьи — изложение основных положений нового направления
анализа систем (теории паттернов и паттерновых сетей) и рассмотрение не-
которых примеров их возможного применения в компьютерной науке и
практике.
ОСНОВНЫЕ ПОНЯТИЯ И ПОЛОЖЕНИЯ ДИСКРЕТНОЙ ТЕОРИИ
ПАТТЕРНОВ [5]
Прежде всего рассмотрим основные понятия и определения теории пат-
тернов.
Моделирование модульных систем с применением дискретной теории паттернов
Системні дослідження та інформаційні технології, 2009, № 2 79
Паттерновые сети состоят из элементарных модульных логических
объектов, называемых образующими (generators), которые являются моде-
лями реальных модулей. Любая образующая имеет неотделимые от нее свя-
зи (bonds), ориентированные (входные/выходные) или неориентированные.
Две связи, принадлежащие разным образующим, соединяются в связку пат-
терновой сети (linkage). Путем такого попарного (одна с одной) соединения
связей в связки из образующих строятся паттерновые сети (pattern
network — PN) — модели реальных модульных систем. На рис. 1 дано гра-
фическое представление информационных структур паттерновыми и графо-
выми сетями, что дает возможность оценить их основные различия.
Практика решения компьютерных задач с помощью паттерновых сетей
показала, что реальные модули с разным числом входов и выходов модели-
Рис. 1. Графическое представление информационных структур паттерновыми и
графовыми сетями
Cвязка
И.И. Коваленко, О.А. Кудин
ISSN 1681–6048 System Research & Information Technologies, 2009, № 2 80
руются ориентированными образующими, определяемыми следующим па-
раметрическим вектором признаков [5]:
),,,()( outin
1 irimii iaga ββγ= , (1)
где ig — образующая ( ni ,,2,1 …= ); )( iga — вектор признаков образую-
щей; i — порядковый номер образующей ig в конечном множестве обра-
зующих nG ; 1iγ — компонента вектора признаков, называемая атрибутом
образующей; outin , irim ββ — компоненты вектора, называемые показателями
(переменными) входных и выходных связей образующей ig ; rm, — пара-
метры, числовые значения которых обозначают соответственно числа вход-
ных и выходных связей образующих.
Чтобы вектор (1) представлял как структуры, так и информационное
содержимое образующих, его компонентам ставятся в соответствие домены
outin
1 ,, irimi DDD , которые определяются как конечные или счетные множест-
ва данных о реальных модулях.
На каждой связке паттерновой сети устанавливается бинарное отноше-
ние между двумя ее переменными β , называемое отношением связей и
обозначаемое символом ρ (соединено). В общем случае связка сети может
быть представлена в виде inout βρβ , ρ — соединено ИСТИНА или ЛОЖЬ.
Изменение числовых параметров m и r в векторе (1) позволяет модели-
ровать реальные модули с различным числом входных и выходных связей, а
также формировать различные типы (классы) образующих. Например, если
1== rm , то в результате получается линейная образующая ( L -образующая,
рис. 2,а) — модель модулей с одним входом и одним выходом.
При 2≥m и 1=r линейная образующая преобразуется в образующую
синтеза ( S -образующую, рис. 2,б), а при 1=m , 2≥r получается образую-
щая анализа ( A -образующая, рис. 2,в).
Рис. 2. Основные типы образующих
in
1iβ
in
miβ out
riβ
in
1iβ
in
1iβ
out
1iβout
1iβ
in
ilD out
1iD ilD
ili γ,
ili γ, ili γ,
1
),,,()( out
1
in
1
==
=
rm
iaga iiili ββγ
1,2
),,,()( out
1
in
=≥
=
rm
iaga iimili ββγ
2,1
),,,()( outin
1
≥=
=
rm
iaga riiili ββγ
(L-образующая) (S-образующая) (A-образующая)
а б в
out
1iβ
Моделирование модульных систем с применением дискретной теории паттернов
Системні дослідження та інформаційні технології, 2009, № 2 81
В качестве примера приведем формальное описание некоторой абст-
рактной паттерновой сети (рис. 3).
⇒сети скелет йСтруктурны
⎪
⎪
⎪
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎧
⎢
⎢
⎢
⎣
⎡
⇒
⎢
⎣
⎡
⇒
⎢
⎢
⎢
⎢
⎣
⎡
=
=
=
⇒
⇒
−
out
3131
out
2121
out
13
out
12
out
11131211
312111
31
out
3131
out
1221
out
1112
out
21
3131313
out
2121212
out
13
out
12
out
11131211111
,,,
,,,,,
,,
Содержание
ИСТИНАсоединение
,,,Структура
),,,3()(
),,,2()(
),,,,,,,1()(
Состав
DDDD
DDDDDD
DDD
aga
aga
aga
inin
ininin
inininin
outin
in
ininin
ρ
βρβρββρββρββ
ββγ
ββγ
ββββββγ
МОДЕЛИРОВАНИЕ ЛОКАЛЬНЫХ КОМПЬЮТЕРНЫХ СЕТЕЙ
Рассмотрим локальную компьютерную сеть (ЛКС) с соединением компью-
теров по схеме типа «звезда». Эта схема наиболее часто применяется в ЛКС
из-за ее надежности и удобства в эксплуатации. Типовая схема и граф такой
ЛКС приведены на рис. 4.
На основании теории паттернов в этой схеме можно выделить три ато-
марных (модульных) объекта — компьютеры, коммутатор и соединитель-
ные линии. Их можно представить в виде образующих (рис. 5).
В качестве примера рассмотрим процесс формализации параметров об-
разующей, моделирующей соединительную линию. Сначала зададим обра-
зующую в абстрактном виде, без учета среды, в которой она может действо-
out
3.1β in
1.1β
in
2.1β out
2.1β
in
2.1β out
1.3β
in
1.3βout
1.2β
out
1.1β
1.2,2 γ 1.2,3 γ
1.1,1 γ
in
3.1β
Рис. 3. Абстрактная паттерновая сеть
И.И. Коваленко, О.А. Кудин
ISSN 1681–6048 System Research & Information Technologies, 2009, № 2 82
вать. Так как мы говорим о соединительной линии между компьютером и
коммутационным устройством или между двумя коммутационными
устройствами, то эта образующая будет иметь один вход и один выход
(рис. 6).
В качестве идентификатора образующей примем обозначение ig , кото-
рое является индексом образующей во множестве образующих G ,
{ }ni gggGg ,,, 21 …=∈ . Тогда вектор признаков образующей будет иметь
вид
( )2.11.12.11.11
out
2.1
in
1.111 ,,,,,,,,1)( ρρββγ DDDga = , (2)
Рис. 4. Схема и граф соединения компьютеров в локальную сеть с топологией
«звезда»
out
4.1β in
4.1β
in
.2 nβ out
.2 nβ in
4.3β out
3.3β
in
1.1β out
2.1β
in
1.2β out
1.2β
in
2.2β
out
2.2β
in
)1.(2 −nβ out
)1.(2 −nβ in
1.3β out
2.3β
Рис. 5. Образующие паттерновой сети
Рис. 6. Абстрактная образующая соединительной линии
out
2.1βin
1.1β
1.1D 2.1D1D
2.1ρ 1.1ρ
Моделирование модульных систем с применением дискретной теории паттернов
Системні дослідження та інформаційні технології, 2009, № 2 83
где 1 — индекс класса, а 1γ — атрибут (идентификатор) образующей;
in
1.1β — показатель входной и out
2.1β — выходной связи; 1D — домен допус-
тимых значений параметров образующей и 1.1D — домен входной и 2.1D —
выходной связи; 1.1ρ — отношение согласования (отношение связи) для
входной и 2.1ρ — выходной связи.
Наполнение элементов вектора признаков соответствующими значе-
ниями параметров позволит перейти от абстрактной образующей к конкрет-
ной. Это наполнение будем производить в следующем порядке.
1. Определение атрибута образующей. В качестве атрибута (иденти-
фикатора образующей) примем iL .1 , где L — идентификатор образующей
(line); 1 — индекс класса образующей; i — порядковый номер образующей
в классе.
2. Определение множества допустимых значений доменов. Для
определения множества допустимых значений доменов 2.11.11 ,, DDD вос-
пользуемся таблицей.
Домен 1D содержит множество данных, относящихся ко всей обра-
зующей. Его можно представить так:
mjniLTD ji ,,2,1,,,2,1,},{1 …… === , (3)
где iT — множество подмножеств параметров, характеризующих тип со-
единительной линии; jL — множество всех допустимых значений, которые
может принимать длина соединительной линии.
В свою очередь, множества iT и jL имеют вид
},,,{},,,,{ 21maxmax mjiiiii lllLvlksT …== , (4)
где i — номер подмножества iT ( ni ,,2,1 …= ); j — номер множества jL
( mj ,,2,1 …= ); is — обозначение типа линии по спецификации IEEE 802.3;
ik — категория кабеля; ilmax — максимально допустимая длина линии со-
гласно спецификации IEEE 802.3; ivmax — максимальная пропускная спо-
собность линии.
Домен 1.1D содержит множество данных, относящихся к входной связи
образующей. Это множество запишем как
},,,{ )in(ininin1.1 pNZYXD = , (5)
где inX — множество координат inx точек соединения входной связи со-
единительной линии с выходной связью коммутационного устройства;
inY — множество координат iny ; inZ — множество координат inz ;
)in(pN — номер порта коммутационного устройства, к которому подключа-
ется входная связь соединительной линии.
И.И. Коваленко, О.А. Кудин
ISSN 1681–6048 System Research & Information Technologies, 2009, № 2 84
Параметры соединительной линии
Атрибут
образу-
ющей
Наименова-
ние
специфика-
ции по
IEEE802.3
Катего-
рия
кабеля
Макси-
мальная
длина
соедине-
ния, м
Макси-
мальная
пропус-
кная
способ-
ность,
Мбит/с
Н
аи
ме
но
ва
ни
е
об
ра
зу
ю
щ
ей
Наиме-
нование
техноло
гии
сетевого
соеди-
нения
1γ is ik maxl maxv
Примечание
g1 L1.1 100Base-TX UTP5 100 100
g 2 L1.2 100Base-TX STP1 100 100
g3 L1.3 100Base-T4 UTP3 100 100
g4 L1.4 100Base-T4 UTP4 100 100
g5 L1.5 100Base-T4 UTP5 100 100
g6 L1.6 100Base-FX MMF 412 100
Многомодовое
оптоволокно 62,5/125
мкм (полудуплекс)
g7
Fast
Ethernet
L1.7 100Base-FX MMF 2000 100
Многомодовое
оптоволокно 62,5/125
мкм (дуплекс)
g8 L1.8 1000Base-SX MMF 500 1000
Многомодовое
оптоволокно 62,5/125
мкм, λ=850нм
g9 L1.9 1000Base-
SX MMF 500 1000
Многомодовое
оптоволокно 50/125
мкм, λ=850нм
g10 L1.10 1000Base-
LX MMF 500 1000
Многомодовое
оптоволокно 62,5/125
мкм, λ=1300нм
g11 L1.11 1000Base-
LX MMF 500 1000
Многомодовое
оптоволокно 50/125
мкм, λ=1300нм
g12 L1.12 1000Base-
LX SMF 2000 1000 Одномодовое
оптоволокно, λ=1300нм
g13 L1.13 1000Base-
CX STP 25 1000
Экранированный
сбаланс. медный кабель
с волн. сопр. 150 Ом
g14
Gigabat
Ethernet
L1.14 1000Base -T UTP5 100 1000 Счетверенная неэкр.
витая пара
g15 L1.15 10GBase-
LX4 MMF 200 10000 Многомодовое
оптоволокно, λ=1310нм
g16 L1.16 10GBase-
LX4 SMF 10000 10000 Одномодовое
оптоволокно, λ=1310нм
g17 L1.17 10GBase-
WS SMF 10000 10000 Одномодовое
оптоволокно, λ=850нм
g18 L1.18 10GBase-
WL SMF 10000 10000 Одномодовое
оптоволокно, λ=1310нм
g19 L1.19 10GBase-
WE SMF 40000 10000 Одномодовое
оптоволокно, λ=1550нм
g20 L1.20 10GBase-RS SMF 10000 10000 Одномодовое
оптоволокно, λ=850нм
g21 L1.21 10GBase-RL SMF 10000 10000 Одномодовое
оптоволокно, λ=1310нм
g22
10G
Ethernet
L1.22 10GBase-RE SMF 40000 10000 Одномодовое
оптоволокно, λ=1550нм
Моделирование модульных систем с применением дискретной теории паттернов
Системні дослідження та інформаційні технології, 2009, № 2 85
Домен 2.1D содержит множество данных, относящихся к входной связи
образующей. Это множество можно представить в виде
},,,{ )out(outoutout2.1 pNZYXD = , (6)
где outX — множество координат outx точек соединения выходной связи
соединительной линии с входной связью коммутационного устройства;
outY — множество координат outy ; outZ — множество координат outz ;
)out(pN — номер порта коммутационного устройства, к которому подклю-
чается выходная связь соединительной линии.
3. Определение показателей связи. Показатели связи образующей
1.1βig и 2.1β будут результатами конъюнкции параметров is и ik (3). Тогда
ii ks ∧== out
2.1
in
1.1 ββ . (7)
4. Определение отношения согласования. Условием соединения
out
комβ и in
линβ , а также out
линβ и in
комβ , является равенство
⎪⎩
⎪
⎨
⎧
=
=
,
,
in
ком
out
лин
in
лин
out
ком
ββ
ββ
(8)
где out
комβ — показатель выходной связи коммутационного устройства;
in
линβ — показатель входной и out
линβ — выходной связи линии; in
комβ — по-
казатель входной связи коммутационного устройства.
Формулы (2)–(8) являются математической моделью соединительной
линии.
Образующие (рис. 5) можно объединить в паттерновую сеть (конфигу-
рацию), если задать систему правил, определяющих, какие конфигурации
можно считать допустимыми или регулярными [4]. Для этого найдем пока-
затели связи β и отношение связи ρ .
Показатели связи β для всех входных и выходных связей являются ре-
зультатом конъюнкции логических высказываний A и B , например: A —
соединительный разъем RJ45; B — протокол физического уровня Fast
Ethernet. Тогда значение показателя связи можно записать в виде логиче-
ской формулы BA∧=β . Если считать отношение связи ρ равенством, то
правило соединения образующих можно записать в виде →inout βρβ
inout ββ =→ .
Приведенные на рис. 5 образующие позволяют сформировать конфигу-
рацию паттерновой сети РN для ЛКС типа «звезда» (рис. 7). Выполним ее
формальное описание. Принимая во внимание, что все ветви являются иден-
тичными, выкладки приведем для одной из них.
И.И. Коваленко, О.А. Кудин
ISSN 1681–6048 System Research & Information Technologies, 2009, № 2 86
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎧
⎢
⎢
⎢
⎢
⎣
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
⎢
⎢
⎣
⎡
⎢
⎢
⎢
⎢
⎣
⎡
=
=
=
=
−
−
out
12
out
14
out
32
out
34
out
21
out
2
in
2
in
21
in
33
in
31
in
13
in
11
321
32133123
out
2
inin
2
outout
12
inin
11
out
in
13
out
32
in
33
out
21
in
21
out
34
in
31
out
14
out
2
out
21
out
34
out
32
out
14
out
12
in
2
in
21
in
33
in
31
in
13
in
11
out
34
out
32
in
33
in
3133
out
2
out
22
in
2
in
2122
out
14
out
12
in
13
in
1111
,,,,,
,,,,,
,,
Содержание
,,,Связки
ЛОЖЬсоединение
;;;
ИСТИНАсоединение;.
;;;
Структура
,,,,,Выходные
,,,,,Входные
Связи
),,,,,3()(
),,,,,2()(
),,,,,1()(
Состав
DDDDDD
DDDDDD
DDD
NNNN
aga
aga
aga
PN
n
n
nn
n
n
nn
ρ
βρββρββρββρβ
ρρββ
βρββρββρβ
ββββββ
ββββββ
ββββγ
ββββγ
ββββγ
Если сравнить рис. 4 и рис. 7, то очевидно, что рис.7 содержит больше
информации о структуре, составе и содержании ЛКС, чем графовая модель,
что позволяет более детально подойти к процессу их анализа и синтеза.
ПРЕДСТАВЛЕНИЕ И–ИЛИ-ГРАФОВ (ДЕРЕВЬЕВ) ПАТТЕРНОВЫМИ
СЕТЯМИ
Графы-деревья широко используются для построения различных сценариев,
возникающих в процессе прогнозирования и исследования технических,
экономических, социальных и других процессов и систем. Наиболее общей
интерпретацией И–ИЛИ-графа является то, что его вершинам соответству-
ют отдельные задачи, а дуги отображают взаимосвязь между задачами.
Для отображения различного рода альтернатив на входах и выходах
вершин графа могут быть использованы логические условия ∧ (И), ∨
(ИЛИ) и ∨ (логическая операция, исключающая ИЛИ). Причем любой тип
входа может быть скомбинирован с любым типом выхода. Опыт построения
рассматриваемых моделей показывает, что для отображения альтернатив-
ных ситуаций в реальном процессе можно выделить восемь типов вершин e,
которые образуются различными комбинациями входов и выходов.
∧∨∨∨∨∨∨∨∧∨∨∧∨∧∧∧ eeeeeeee ,,,,,,, .
Моделирование модульных систем с применением дискретной теории паттернов
Системні дослідження та інформаційні технології, 2009, № 2 87
Например, тип вершины ∨∧ e означает, что на входе e имеет место ус-
ловие И, т.е. вершина e считается свершенной после окончания всех работ,
непосредственно предшествующих ей, а условие ∨ на выходе e означает,
что будет реализована одна и только одна из всех работ, исходящих из нее.
Рассмотренные типы вершин можно представить паттерновыми обра-
зующими, связям которых приданы логические условия (рис. 8).
Выполним формальное описание каждой из образующих.
Образующая 1.
),,,,,,1()( out
1
in
111
out
1
in
1111 rmrm DDDaga ββγ= ,
1,1 ≥≥ rm .
in
.2 nβ
out
2.1β in
1.1β
out
2.1β
in
1.1β out
2.1β in
1.1β
out
2.3β
in
1.3βout
2.3β
in
1.3β out
2.3β
in
1.3β
out
)1(2 −nβ
in
)1(2 −nβout
2.2β
in
2.2βout
1.2β
in
1.2β
out
4.1β
in
3.1β in
3.1β
in
3.1β
out
4.3β out
4.3β
out
4.3β out
3.3β out
3.3β
in
3.3β
out
4.1β out
4.1β
out
.2 nβ
Рис. 7. Конфигурация паттерновой сети для ЛКС типа «звезда»
И.И. Коваленко, О.А. Кудин
ISSN 1681–6048 System Research & Information Technologies, 2009, № 2 88
)(1ОБРАЗУЮЩАЯ 111 ∧∧= gD ; in
1
in
12
in
11
in
1 mmD βββ ∧∧∧= … ,
out
1
out
12
out
11
out
1 rrD βββ ∧∧∧= … .
Образующая 2.
),,,,,,2()( out
2221
out
2
n
2212 r
in
mr
i
m DDDaga ββγ= ,
out
51βout
11β
out
61β
in
61β
in
11β in
1mβ in
5mβ
out
5rβ
out
31β
Образующая 1 (∧ g1 ∧) Образующая 5 (∨ g5 ∨)
Образующая 2 (∧ g2∨) Образующая 6 (∨ g6 ∨ )
Образующая 3 (∧ g3 ∨) Образующая 7 (∧ g7)∨(∨g7)
Образующая 4 (∨ g4 ∧) Образующая 8 (g8 ∨)∨(g8 ∧)
m≥1, r≥1 m≥1, r≥1
m≥1, r=1 m≥1, r≥1
m≥1, r=0
m≥1, r=1
m≥1, r=0
m≥1, r≥1 out
81β
in
71β
in
41β
out
1rβ
in
51β
in
21β in
2mβ in
6mβ
in
7mβ
out
21β out
2rβ
out
8rβ
in
31β in
3mβ
out
4rβ
in
4mβ
out
41β
Рис. 8. Виды образующих, построенных по типовым вершинам графа типа «дерево»
Моделирование модульных систем с применением дискретной теории паттернов
Системні дослідження та інформаційні технології, 2009, № 2 89
1,1 ≥≥ rm .
)(2ОБРАЗУЮЩАЯ 221 ∨∧= gD ; in
2
in
22
in
21
in
2 mmD βββ ∧∧∧= … ,
out
2
out
22
out
21
out
2 r
t
rD βββ ∨∨∨= … .
Образующая 3.
),,,,,,3()( out
3
in
331
out
3
in
3313 rmrm DDDaga ββγ= ,
1,1 =≥ rm .
)(3ОБРАЗУЮЩАЯ 331 ∨∧= gD ; in
3
in
32
in
31
in
3 mmD βββ ∧∧∧= … ,
out
31
out
3 β=rD .
Образующая 4.
),,,,,,4()( out
4
in
441
out
4
in
4414 rmrm DDDaga ββγ= ,
1,1 ≥≥ rm .
)(4ОБРАЗУЮЩАЯ 441 ∧∨= gD ; in
4
in
42
in
41
in
4 mmD βββ ∨∨∨= … ,
out
4
out
42
out
41
out
4 rrD βββ ∧∧∧= … .
Образующая 5.
),,,,,,5()( out
5
in
551
out
5
in
5515 rmrm DDDaga ββγ= ,
1,1 ≥≥ rm .
)(5ОБРАЗУЮЩАЯ 551 ∨∨= gD ; in
5
in
52
in
51
in
5 mmD βββ ∨∨∨= … ,
out
5
out
52
out
51
out
5 rrD βββ ∨∨∨= … .
Образующая 6.
),,,,,,6()( out
6
in
661
out
6
in
6616 rmrm DDDaga ββγ= ,
1,1 =≥ rm .
)(6ОБРАЗУЮЩАЯ 661 ∨∨= gD ; in
6
in
62
in
61
in
6 mmD βββ ∨∨∨= … ,
out
61
out
6 β=rD .
Образующая 7.
),,,,7()( in
771
in
7717 mm DDaga βγ= ,
0,1 =≥ rm .
И.И. Коваленко, О.А. Кудин
ISSN 1681–6048 System Research & Information Technologies, 2009, № 2 90
)()(7ОБРАЗУЮЩАЯ 7771 ggD ∨∨∧= ,
in
7
in
72
in
71
in
7
in
72
in
71
in
7 mmmD ββββββ ∨∨∨∨∧∧∧= …… .
Образующая 8.
),,,,8()( out
881
out
8818 rr DDaga βγ= ,
0,1 =≥ rm .
)()(8ОБРАЗУЮЩАЯ 8881 ∧∨∨= ggD ,
out
8
out
82
out
81
out
8
out
82
out
81
out
8 rrrD ββββββ ∧∧∧∨∨∨∨= …… .
Из представленных образующих путем попарного соединения состав-
ляются паттерновые сети при наличии идентичности логических условий на
входных и выходных связях inβ и outβ . Эти условия являются основными
для формирования отношения связи )( outinρββρ .
Например, рассмотрим процедуру соединения в сеть образующих 1g и
2g (рис. 9) для формализации ρ . Пусть kjP jn ,,1},{ …== ρ — множество
отношений связей и }{ outout
2
out
1
out
rB βββ ∧∧∧=∧ … , …∧∧=∧
inininB 21{ ββ
}in
mβ∧… — соответственно множества входных и выходных связей, объе-
диненных одной и той же логической функцией. Тогда
⎪⎩
⎪
⎨
⎧
∉∃∧∉∃
∈∃∧∈∃
⇒∈∃
−
−
.ЛОЖЬ)]()([
,ИСТИНА)]()([
2
outout
1
2
outout
1соединено
inin
ii
inin
ii
n
BB
BB
P
ββ
ββ
ρ
Из представленных образующих путем попарного соединения состав-
ляются паттерновые сети при наличии идентичности логических условий на
входных и выходных связях inβ и outβ . Эти условия являются основными
для формирования отношения связи )( outin βρβρ .
Рис. 9. Схема связывания образующих в сеть
out
1rβ
in
1mβ
out
11βin
11β
in
2rβ
in
21β
ρ (соединение-связка)
∧
Моделирование модульных систем с применением дискретной теории паттернов
Системні дослідження та інформаційні технології, 2009, № 2 91
ВЫВОДЫ
1. Паттерновые сети, наряду с табличными и графовыми методами
представления и анализа систем, можно рассматривать как новый инстру-
мент математического моделирования и инженерного проектирования мо-
дульных систем.
2. Применение паттерновых сетей при анализе и синтезе модульных
систем позволяет более детально представлять модели информационных
структур и потоков.
3. Путем варьирования значений параметров m и r в векторе (1), можно
генерировать различные виды образующих и на этой основе создавать базы
данных для автоматизированного проектирования различных модульных
систем.
4. В работе [5] доказано единство модульных, графовых и табличных
моделей информационных систем, что дает возможность использовать их
как отдельно, так и в различных сочетаниях.
5. Дискретная теория паттернов и паттерновых сетей находится на на-
чальной стадии своего становления и дальнейшее ее развитие, несомненно,
расширит сферу практических приложений.
ЛИТЕРАТУРА
1. Гренандер У. Лекции по теории образов: Синтез образов / Пер. с англ. — М.:
Мир, 1979. — 383 с.
2. Гренандер У. Лекции по теории образов: Анализ образов / Пер. с англ. — М.:
Мир, 1981. — 446 с.
3. Гренандер У. Лекции по теории образов: Регулярные структуры / Пер. с англ.
— М.: Мир, 1983. — 432 с.
4. Grenander U. General Pattern Theory. — Oxford: University Press, 1993. — 904 p.
5. Шуткин Л.В. Новое мышление компьютерного мира: паттерновые сети для
моделирования информационных систем. — НТИ. — Сер. 2 // Информаци-
онные процессы и системы. — 2001. — № 6. — С. 5–17.
6. Мамиконов А.Г., Кульба В.В. Синтез оптимальных модульных систем обработ-
ки данных. — М.: Наука, 1986. — 275 с.
7. Трахтенгерц Э.А. Программное обеспечение автоматизированных систем
управления. — М.: Статистика, 1974. — 288 с.
Поступила 17.12.2008
|