Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Сеть автоматов для моделирования асинхронного взаимодействия процессов Новик Константин Валерьевич

Сеть автоматов для моделирования асинхронного взаимодействия процессов
<
Сеть автоматов для моделирования асинхронного взаимодействия процессов Сеть автоматов для моделирования асинхронного взаимодействия процессов Сеть автоматов для моделирования асинхронного взаимодействия процессов Сеть автоматов для моделирования асинхронного взаимодействия процессов Сеть автоматов для моделирования асинхронного взаимодействия процессов Сеть автоматов для моделирования асинхронного взаимодействия процессов Сеть автоматов для моделирования асинхронного взаимодействия процессов Сеть автоматов для моделирования асинхронного взаимодействия процессов Сеть автоматов для моделирования асинхронного взаимодействия процессов
>

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

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Новик Константин Валерьевич. Сеть автоматов для моделирования асинхронного взаимодействия процессов : Дис. ... канд. физ.-мат. наук : 05.13.18 Москва, 2006 120 с. РГБ ОД, 61:06-1/604

Содержание к диссертации

Введение

ГЛАВА 1 Введение в системы взаимодействующих процессов 9

1.1 Сеть Петри для моделирования асинхронного взаимодействия процессов при использовании общих ресурсов 10

1.2 Сети с накоплениями событий 13

1.3 Сети с распознающими предикатами 15

1.4 Вычислительные сети (CN) 17

1.5 Самосинхронизирующиеся сети (SN) 21

1.6 Асинхронные преобразующие сети 22

1.7 Высказывательная (пропозиционная) сеть для экспертных систем..23

1.8 Выводы по главе 1 25

ГЛАВА 2 Теоретические основы теории joiner-сетей 26

2.1 Концептуальная интерпретация Joiner-сетей и взаимосвязей их элементов 27

2.2 Формальная система, порождающая правильно построенные формулы JN 28

2.3 Матричная форма представления JN 32

2.4 Проблемы анализа сетей и формы их представления, удобные для анализа 33

2.5 Joiner-алгебра (склеивающая алгебра) 37

2.6 Техника работы с Joiner-алгеброй 39

2.7 Теорема о ярусно-параллельной форме Joiner-сети 41

2.8 Многопроцессорное разложение сетей. Теорема о процессорной декомпозиции. Теорема о композиции локальных сетей 41

2.9 Формальная интерпретация JN сетью автоматов 45

2.10 Внутренняя структура элементарного автомата и правила его работы в сети 46

2.11 Теорема о «работающей» цепочке 47

2.12 Выводы по главе 2 49

ГЛАВА 3 Известные модели асинхронных систем управления процессами и их представление joiner- сетью 50

3.1 Сети Петри (PN) 51

3.2 Асинхронные цифровые схемы (сети) Маллера (MN) 59

3.3 Дискретные нейронные сети Мак Каллока-Питтса (VN) 60

3.4 Семантическая сеть Ван-Хао (WN) 61

3.5 Алгебраические сети (AN). Исчисление Эрбрана-Геделя. Вычислительные модели Э. Тыугу 63

3.6 Ринговые и роторные сети (RN, RoN) 66

3.7 Выводы по главе 3 67

ГЛАВА 4 Модели реальных асинхронных систем, использующих joiner-сети 69

4.1 Модель, описывающая процессы разрушения древнерусских фресок 69

4.1.1 Описание модели 69

4.1.2 Элементы модели 70

4.1.3 Сеть, описывающая состояние фрески 7Д

4.1.4 Пример работы сети 73

4.2 Модель удаленной Интернет-атаки 75

4.2.1 Описание модели 75

4.2.2 Элементы модели 76

4.2.3 Сеть для моделирования атаки 80

4.2.4 Пример работы сети 82

4.3 Модель системы связи канального процессора с двумя абонентами.84

4.3.1 Описание модели 84

4.3.2 Сеть, моделирующая систему связи канального процессора с двумя абонентами через адаптер 85

4.3.3 Пример работы сети 86

4.4 Модель информационной системы поля боя 87

4.4.1 Описание модели 87

4.4.2 Элементы модели 89

4.4.3 Сеть для четырех подразделений 90

4.4.4 Пример работы сети 92

4.5 Модель группового поведения стаи рыб 94

4.5.1 Описание модели 94

4.5.2 Элементы модели 95

4.5.3 Сеть для стаи из пяти рыб 97

4.5.4 Пример работы сети 104

4.6 Модель биржевой игры 106

4.6.1 Описание модели 106

4.6.2 Элементы модели 107

4.6.3 Сеть для двух игроков 111

4.6.4 Пример работы сети 115

Заключение 117

Список литературы

Введение к работе

Работа посвящена моделям поведения сложных систем, в которых выделены элементы и их взаимосвязи. Элементы называются процессами, а взаимосвязи определяются поставками и потреблением отдельными процессами информации, энергии, вещества. Каждый элемент системы (процесс) «живет» по собственным законам и требует для своей «жизни» определенные ресурсы, например, каналы для передачи информации, хранилища для вещества, процессоры для выполнения действий и т.д.. Говорят, что поведение такой системы асинхронно, в связи с тем, что взаимодействия (поставки и потребление ресурсов) не зависят от физического времени, а определяются событиями, которые генерируются отдельными элементами системы. События фиксируют результаты изменений в состоянии элементарных процессов, передаются (собираются) другими процессами, управляя изменением их состояния. В этом плане события являются синхронизаторами, инициаторами изменения состояний процесса. Сетевые модели в настоящее время весьма распространены, начиная с 80-х годов XX века, и насчитывают около тысячи публикаций.

1. Объект исследования.

Объектом исследования являются асинхронные системы (АС), которые задаются сетью Net = (S,E,R,l), где S = {S{,...,Sn) -конечное множество процессов, Е = {е1,...,ет} - конечное множество событий, R - правила, которые приписывают каждому процессу S( подмножества так называемых входных Ex(St) и выходных Ey(Si) событий, правила имеют вид: / . :Ех(З Еу, /-интерпретация (операционная семантика), связанная с инициализацией -•• процессов, изменением и запоминанием событий. Обычно сети задаются графом с вершинами двух видов - Е и S, взаимосвязи между событиями и процессами показываются дугами. Сеть используется в виде математической модели асинхронной системы в известной цепочке перехода «от содержательной задачи к программе»:

Содержательная задача Математическая модель асинхронной системы Программа 2. Проблемы моделирования асинхронных систем с сетевыми моделями.

1) Первая проблема возникает при переходе от содержательной задачи к модели асинхронной системы. Она связана с формализацией описания взаимодействия, или, как говорил Ч. Хоар в своей книге «Взаимодействующие последовательные процессы» (1980), в составлении протокола взаимодействия между парой процессов. Даже в самых распространенных сетях Петри нет четко сформулированного протокола, удовлетворяющего всем формальным требованиям для построения его программной реализации.

2) Вторая проблема возникает при переходе от математической модели к программной реализации и связана с распознаванием корректности (адекватности) сетевой модели. Модель называется корректной, если ее поведение соответствует законам, сформулированным исследователем. Заметим, что эта проблема вызывает особые трудности и не решена до сих пор. На самом деле, поведение системы определяется последовательностями событий, некоторые из них связываются в цепочки (деревья) событий, а некоторые возникают параллельно (независимо). Тот же Ч. Хоар как пожелание высказывает предложение по построению таких графических моделей, которые бы показывали фронтальное разворачивание событий от начальных воздействий (событий) в виде бесконечно повторяющихся циклов. Понятно, что в таком случае можно было бы строить различные сценарии поведения систем и, кроме этого, создавать тесты, доказывающие корректность сетевых моделей.

3. Какие проблемы решены в диссертации.

Собственно, решению двух вышеперечисленных проблем и посвящена данная работа.

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

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

4. Научная новизна работы.

Для решения поставленных проблем, как это принято в математике, сеть разделяется на две составляющие: формальную (правильно построенные формулы) и интерпретацию знаков операций (операционная семантика).

Вводится понятие «картиночных» формул и строится формальная система порождения всех правильно построенных формул.

Вводится специальная Joiner-алгебра с двумя операциями: «•» -склеивание и «V» - композиция. Joiner-алгебра позволяет проводить эквивалентные преобразования формул. В частности, с ее помощью строятся стандартные разложения сетей.

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

Сети, построенные на этих трех принципах называются Joiner-сетями.

Эти три результата получены самостоятельно (являются оригинальными), представляют научную новизну работы и выносятся на защиту.

5. История исследований.

Исследования по сетевой тематике начались с 1999 года, были отражены в бакалаврской диссертации «Струйная томография, теория и практическое применение» (2001) и в магистерской диссертации «Ситуационная комната для анализа и парирования Internet-атак» (2003). В основном исследования проводились в рамках грантов РФФИ № 01-07-90277, «Разработка систем распределенного мозгового штурма через Internet для сложных научных проектов РАН», 2001-2002 гг.; № 03-07-90356, «Исследование моделей ситуационной комнаты, управляемой событиями, которые передаются через Internet», 2003-2005 гг.; № 04-07-90070, «Информационная система для искусствометрики памятников древнерусского искусства», 2004-2006 гг.; а также личных грантов РФФИ № 02-07-06064 и № 03-07-06149, «Программа поддержки молодых ученых», 2002 и 2003 гг., выделенных на проведение перспективных фундаментальных исследований. Большая часть результатов исследований вошла в диссертационную работу.

6. Логика построения работы и ее краткое содержание.

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

Во второй главе вводится понятие Joiner-сетей и строится их теория, состоящая из следующих разделов:

Формальная система, порождающая правильно построенные формулы Joiner-сетей (JN).

Joiner-алгебра.

Стандартные разложения JN.

Анализ циклических ярусно-параллельных разложений.

Интерпретация формул сети автоматами, автоматными пусковыми и флаговыми функциями.

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

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

Доказывается теорема о «работающей» цепочке и показывается применение этой теоремы для анализа корректности (логической неразрывности) сети.

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

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

Сети с распознающими предикатами

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

На рисунке 1.3а представлена такая сеть, а на рисунке 1.36 - пусковые и флаговые функции. Характерная особенность пусковой функции - ее триггерность: события/? (упаковка закончена) и h (упаковка не закончена) не могут быть одновременно истинными или ложными, т.е. они не могут вместе существовать или вместе быть стертыми из памяти позиций. При этом флаговая функция является недетерминированной, произвольно выставляя значения/» и h, как это показано на рисунке 1.36. h(t+ 1):= 0; \h{t + 1):=1.

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

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

Как обычно, события вин (наличие вилки и ножа) являются ресурсными, события due- синхронизирующими, событие а (на тарелке появилась еда) также является синхронизирующим, события г\ (еда вегетарианская) и г2 (еда не вегетарианская) являются триггерными. События г\ и г2 позволяют пропускать для еды только вегетарианские блюда.

Конструкция, объединяющая распознаватель R с триггерной пусковой функцией, которая управляет другими процессами, всегда будет иметь стандартную форму, показанную на рисунке 1.4. Например, если философ придерживается диеты, которая задается последовательностью блюд

[(вб) (нвб)]п, где (вб) - событие «вегетарианское блюдо», (неб) - событие «не вегетарианское блюдо», п - число повторений. Тогда при последовательности блюд (вб)(нвб), соответствующей диете, пусковая функция щ=1 и г2=1, а при последовательности (вб)(нвб)(нвб) щ=0, г2=0.

Заметим, что наличие распознающих предикатов, синхронизирующих процессы, потребовало вводить специальные конструкции сетей: т.н. сетей с переходами, управляемыми предикатами (Transition/Predicate Petri Net [38]).

Комментарий к 1.3:

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

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

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

Известно, что алгоритм вычисляет систему функций, связанную взаимными подстановками переменных (поставками информации, см. [14]). Вычисление каждой функции связано с некоторым процессом. Пусть задана система функций, показанная на рисунке 1.5а. Скобочная форма представления описывает систему подстановок так, как показано на рисунке 1.56. Систему подстановок удобно задавать графом (рисунок 1.5в), в [25] он назван информационной структурой алгоритма (ИСА), а в [4] - графом алгоритма. Для ИСА можно поставить в соответствие вычислительную сеть (Computing Net — CN), построенную в нотации сетей Такая сеть показана на рисунке 1.5г, далее приведена интерпретация этой сети.

Формальная система, порождающая правильно построенные формулы JN

Прежде чем строить формальную систему, порождающую любые JN, необходимо дать причинно-следственную их интерпретацию. Эта интерпретация должна объяснить, почему выбраны именно такие формальные порождающие правила, с помощью которых строится сеть.

На рисунке 2.1 показан элемент JN с входными позициями Р\, ..., Ph ...,Р„ для событий, которые являются причинами «включения» процесса (или его состояния) S. Следствием является единственное событие Р, которое говорит о том, что процесс S выполнен (завершен). Информация о событии «раздается» остальным элементам системы под другими именами: Р„+\, ..., Рр ..., Рп+т. Позиция Р обычно специально не указывается, она размещается «внутри» процесса S, т.к. связана с вычислением соответствующего предиката процедурами, описанными внутри процесса.

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

При помощи правил отождествления и именования происходит «склеивание» из формул-аксиом (далее они будут называться элементарными формулами) правильно построенной «картиночной» формулы FJN. Типы правил склеивания FJN иллюстрируются «картинками», приведенными ниже:

Можно прокомментировать содержательный смысл правил склеивания следующим образом:

Выделение повторяющегося фрагмента (его можно называть инвариантом) сети является одной из задач анализа сетей [5]. В случае СЯПФ такое выделение может быть проведено по цепочке максимальной длины (Lmax) без повторений событий. Заметим, что построение повторяющихся фрагментов (инвариантов) может быть сделано различными способами в любых формах представления сети. Например, в ЯПФ на рисунках 2.8в и 2.8г приведены повторяющиеся фрагменты для циклических сетей.

На рисунках 2.10 и 2.11 приведены инварианты для сетей управления конвейером и отражения ракетной атаки.

Событие «0» может быть разовым и запускать сеть JN2, которая работает ровно один цикл (рисунок 2,12а), либо циклическим, т.е. генерироваться циклической сетью JN\ (рисунок 2,126). В этом случае работа сети JNi синхронизируется событием «0». Далее всегда считается, что внешнее событие для JN является циклическим, при этом сеть, генерирующая это событие, может быть и не указана. Комментарий 2.4:

1. Картиночные формы представления JN, введенные выше, будем называть разложениями. На самом деле цепочечные, древесные и ярусные формы «раскладываются» на конечные фрагменты, которые бесконечно (циклически) повторяются, разворачивая сеть, как ковер, только в одну сторону. В этом плане матричная форма не обладает таким свойством, поэтому она редко применяется в решении задач анализа.

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

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

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

1) Интерпретация объектов и операций JN-алгебры (AJN) AJN = (C;F;R)

С - множество правильно построенных цепочек (ППС) в двусортном конечном алфавите A = {P,S}, где Р - конечный алфавит имен позиций (обычно это номера позиций), S- алфавит имен переходов (обычно им соответствует конечный алфавит малых латинских букв с индексами); F = {; V}, «» - бинарная операция склеивания цепочек (х у), «V» -бинарная операция композиции цепочек (xVy), где х,у є С.

Пусть хє С правильно построенная цепочка ППС, тогда ее структура имеет вид: т»х »п, где (т,п) є Р, а х - ППС. Элементарной ППС называется цепочка т а»п, где (т,п)е Р,а eS .

Дискретные нейронные сети Мак Каллока-Питтса (VN)

Семантическая сеть Ван-Хао (WN) определяется следующим образом: WN = (X,R), где Х- множество сущностей (концептов), R - отношение корреляционной зависимости между парой сущностей. R = УХ, н, = {+,-,0}, «+» - прямая зависимость (событие увеличения значения х, «х(» связано с событием увеличения значения х; - «їх,», а событие уменьшения значения х, - « jxj» связано с событием уменьшения значения х, -«ху»), «-» - обратная зависимость (событие увеличения значения х, - «х;» связано с событием уменьшения значения х, - [х;», а событие уменьшения значения Xj - «J,Xj» связано с событием увеличения значения Xj - «fxy»), «0» _ изменение значений концептов между собой не связаны (не коррелируют).

Рассмотрим модель семантической сети Ван-Хао [28] на примере событийной имитационной модели рынка спроса продуктов информационных технологий (1Т-продуктов). Пример 3.11. Событийная имитационная модель рынка спросов /Г-продуктов. Список сущностей (концептов) рынка спроса ІТ-продуктов в США: 1. SA — индекс торговой активности по 1000 торговым компаниям США. 2. CIT- индекс предложений ІТ-продуктов по 500 торговым компаниям США. 3. DJ- индекс активности фондового рынка (индекс Dow-Jones). 4. NIT- индекс NASDAQ цен акций ГТ-компаний. 5. РА - индекс производственной активности 1000 компаний. 6. PAIT- индекс активности компаний-производителей ІТ-продуктов. 7. СС- индекс настроения потребителя (индекс уверенности). 8. PIT- индекс спроса на ГГ-продукты. Алгебраические сети так или иначе используют концепцию алгебраических систем.

1) Алгебраические сети (AN). Формально AN = (A,0,R), где А - множество (конечное или бесконечное), О - множество операции на Ах Ах Ах ...х А = А" (декартовом произведении п-й степени), R - множество отношений и соответствующих им предикатов на А", таких, что распознавание истинности/ложности каждого предиката задано конструктивно (некоторым алгоритмом) [13]. Конкретные AN, описывающие некоторую предметную область, представляют собой множество (может быть бесконечное) предложений языка предикатов 1-го порядка. Сами предложения задаются подстановками конечных наборов термов и имеют вид обычных скобочных форм. Собственно, алгебраические сети отражают структуру подстановок. На сегодняшний день имеется около десятка различных нотаций и интерпретаций [38]. Декларативная интерпретация позиции задается списком переменных, входящих в предикаты, дуги понимаются как каналы, по которым «передвигаются» переменные, акторы (действия, процессы), производят операции над предикатами. Операционная интерпретация (семантика вычислений) определена весьма туманно, либо вообще не определена. История алгебраических сетей, по всей видимости, начинается с создания в 1934 году Эрбраном и Геделем исчисления для доказательства вычислимости арифметических функций [16] и сетевой интерпретации выводимости в исчислении, построенной Клини в 1952 году [6].

2) Пример алгебраической сети для исчисления Эрбрана-Геделя (АЭГ): АЭГ = (A,0,R), где А - множество букв и символов чисел п є К с обозначением п (т.к. числа имеют смысл обычных имен), R - множество термов вида г = s\r = (х,,..., ); = F2(xx,...,xm); Fu F2 - формулы; О-операции (правила) двух видов: 0\ - подстановка в F\ и F2 вместо переменной х некоторого имени числа [х = nj; ( - замена терма F\nx,..., nm J термом nk . Пусть заданы исходные термы: е\ -f\ ix\) = ix\) » гДе ( ) функция следования: [nj = п +1, е2 J2 \хх,х2) = /з \2,%2 /i v -i )) AN показана на рисунке 3.16.

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

3) Вычислительные модели Э. Тыугу (ВСТ).

Вычислительные модели Тыугу являются типичными алгебраическими сетями. Эти модели были построены на основе так называемых семантических сетей Минского [17] и изложены в [29]. На основе ВСТ были созданы язык УТОПИСТ и система программирования ПРИЗ, которая широко использовалась в проектировании приборов, машиностроении, в сложных расчетных комплексах СНИП (строительные нормы и правила) в 80 - 90-х годах в СССР и ГДР. Концепция сетей Тыугу будет вполне понятна из нижеприведенного примера.

Пример 3.12. Прямолинейное движение тела. Содержательное описание объекта . Тело с массой т движется прямолинейно с постоянным ускорением а в интервале времени от t\ до ti- Начальная скорость тела - vb конечная - V2, средняя скорость на интервале At = t2 - tx - v, пройденный путь - AS, сила инерции —f, выполненная работа - АЕ, кинетическая энергия в начале и конце пути -Е\И Е2, приращение скорости - Av.

Сеть, описывающая состояние фрески

В качестве следующей модели рассматривается модель биржевой игры. Будем рассматривать только игроков-спекулянтов (т.е. обладающих малым объемом денег для проведения операций на рынке). Кроме того, считается, что все игроки имеют фиксированное количество средств, а торги ведутся по единственной бумаге. Помимо игроков-спекулянтов на рынке могут появляться крупные участники (имеющие значительный объем средств), обычно их появление выражается в резком росте объема торгов. Появление таких игроков ведет к резкому изменению цены. Для рассматриваемой модели данный фактор является «внешним», т.е. отсутствует элемент модели, описывающий поведение крупных игроков. Кроме этого, в модели будет учитываться новостной фон (т.е. наличие отрицательных или положительных для рынка новостей). Новостной фактор также является внешним для рассматриваемой модели.

Определим следующие внешние события: 1. Объявлена положительная информация для рынка - игрокам становится известна некоторая информация, которая, с их точки зрения, приведет к росту цены бумаги. 2. Объявлена отрицательная информация для рынка - игрокам становится известна некоторая информация, которая, с их точки зрения, приведет к падению цены бумаги. 3. Крупный игрок покупает бумаги - данная ситуация выражается в резком росте объема торгов и в росте цены на бумагу. 4. Крупный игрок продает бумаги - данная ситуация выражается в резком росте объема торгов и в падении цены.

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

Определим следующие типы игроков: 1. Жадный игрок - игрок, для которого прибыль важнее убытка. Игрок будет закрывать позицию в случае, если доход по этой позиции составит не менее чем Gp%, либо если убыток по позиции составит не менее чем GL% (Gp GL). Такой игрок будет открывать длинную позицию на положительных новостях по рынку или в случае покупок крупного игрока, а короткую позицию будет открывать на отрицательных новостях или в случае продаж крупного игрока. При отсутствии этих сигналов, жадный игрок равновероятно может открыть длинную, короткую позицию или не открывать позиций вообще. Открывая позицию, игрок выставляет заявку на закрытие позиции по цене, соответствующей заданной доходности Gp%. В случае, если выполняется условие возникновения убытка GL%, заявка на фиксацию прибыли снимается и ставится рыночная заявка на закрытие позиции.

2. Умеренный игрок - игрок, которому важно минимизировать потери. Игрок будет закрывать позицию в случае, если доход по этой позиции составит не менее чем МР%, либо если убыток по позиции составит не менее чем ML% (МР ML, при этом, МР GP). Такой игрок будет закрывать длинную позицию на отрицательных новостях или в случае продаж крупного игрока, а короткую позицию будет закрывать на положительных новостях или в случае покупок крупного игрока. Если у игрок позиции нет, то он может равновероятно открыть длинную, короткую позицию или не открывать позиций вообще. Открывая позицию, игрок выставляет заявку на закрытие позиции по цене, соответствующей заданному убытку ML%. В случае, если выполняется условие достижения заданной доходности МР%, заявка на фиксацию убытка снимается и ставится рыночная заявка на закрытие позиции. Каждый игрок открывает позицию целиком на все имеющиеся денежные средства.

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

В диссертационной работе получены следующие основные выводы и результаты:

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

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

3. Определена интерпретация базовых элементов сети. Позиции представляют собой распределенную память о событиях сети, а переходы интерпретируются элементарными автоматами, которые запускаются входными событиями (пусковыми функциями) и генерируют выходные события (флаговые функции). Каждый переход представляет собой отдельный процесс или его состояние (подпроцесс). Такие сети названы Joiner-сетями. Показано, что Joiner-сеть является обобщением известных моделей асинхронных систем. Построены Joiner-сети для сетей Петри, семантических сетей Ван-Хао, диаграмм Маллера, дискретной нейронной сети Мак Каллока-Питтса.

4. Построена теория Joiner-сетей, базирующаяся на специально разработанной Joiner-алгебре. Алгебра позволяет строить стандартные формы представления (разложения) сетей, удобные для анализа и программирования. Доказаны теорема о декомпозиции сетей на множество процессоров и теорема о «работающей цепочке», позволяющая порождать множество сценариев развития событий в сети.

5. Приведены примеры задач, для решения которых используются математические модели в виде Joiner-сетей и соответствующие комплексы программ. В частности, JN-модель поведения стаи рыб, JN-модель поведения биржевых игроков, JN-модель «жизни» настенных росписей (выполнялась для Ферапонтова монастыря, который входит в список объектов ЮНЕСКО), JN-модель Интернет-атаки и т.д.

Похожие диссертации на Сеть автоматов для моделирования асинхронного взаимодействия процессов