Выполнил студент группы ИТО-4-07 Лазарев Никита. В практике моделирования объектов часто приходится решать задачи, связанные с формализованным описанием. - презентация

1 Выполнил студент группы ИТО-4-07 Лазарев Никита

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

3 Теория сетей Петри развивается в нескольких направлениях : разработка математических основ, структурная теория сетей, различные приложения ( параллельное программирование, дискретные динамические системы и т. д.). Формально сеть Петри (N- схема ) задается четверкой вида N=, где В конечное множество символов, называемых позициями, D конечное множество символов, называемых переходами,, ; I входная функция ( прямая функция инцидентности ) ; О выходная функция ( обратная функция инцидентности ),.

4 Графически N - схема изображается в виде двудольного ориентированного мультиграфа, представляющего собой совокупность позиций и переходов

5 Как видно из этого рисунка, граф N- схемы имеет два типа узлов : позиции и переходы, изображаемые 0 и 1 соответственно. Ориентировочные дуги соединяют позиции и переходы, причем каждая дуга направлена от элемента одного множества ( позиции или перехода ) к элементу другого множества ( переходу или позиции ). Граф N- схемы является мульти графом, так как он допускает существование кратных дуг от одной вершины к другой.

6 Приведенное представление N- схемы может использоваться только для отражения статики моделируемой системы ( взаимосвязи событий и условий ), но не позволяет отразить в модели динамику функционирования моделируемой системы. Для представления динамических свойств объекта вводится функция маркировки ( разметки ):

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

8 Функционирование N- схемы отражается путем перехода от разметки к разметке. Начальная разметка обозначается как. Смена разметок происходит в результате срабатывания одного из переходов сети. Необходимым условием срабатывания перехода d j является, где, - разметка позиции b i. Переход d j для которого выполняется указанное условие, определяется как находящийся в состоянии готовности к срабатыванию или как возбужденный переход.

9 Срабатывание перехода изменяет разметку сети М (b) = ( М (b 1 ), М (b 2 ),..., M(b n )) 2 на разметку М (b) по следующему правилу : M'(b) = M(b)-I(d j ) + O(d j ) т. е. переход d j изымает по одной метке из каждой своей входной позиции и добавляет по одной метке в каждую из выходных позиций.

10 Пример функционирования размеченной N- схемы

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

12 Такая схема должна одновременно выполнять несколько функций : 1) являться адекватным математическим описанием системы S; 2) служить основой для построения алгоритмов и программ при машинной реализации модели М ; 3) позволять в упрощенном варианте ( для частных случаев ) проводить аналитические исследования.

13 В качестве элемента А - схемы выступает агрегат, а связь между агрегатами осуществляется с помощью оператора сопряжения R. Агрегат сам может рассматриваться как А - схема, т. е. может разбиваться на элементы ( агрегаты ) следующего уровня. Любой агрегат характеризуется следующими множествами : моментов времени Т, входных X и выходных Y сигналов, состояний Z в каждый момент времени t. Состояние агрегата в момент времени t T обозначается как z(t) Z, а входные и выходные сигналы как x(t) X и y(t) Y соответственно.

14 Будем полагать, что переход агрегата из состояния z(t 1 ) в состояние z(t 2 )z (t 1 ) происходит за малый интервал времени, т. е. имеет место скачок δ z. Переходы агрегата из состояния z (t 1 ) в z(t 2 ) определяются собственными ( внутренними ) параметрами самого агрегата h(t) Н и входными сигналами х (t) X. Для описания скачков состояний δ z в особые моменты времени t δ будем использовать случайный оператор W, представляющий собой частный случай оператора U, т. е. z(t δ + 0)=W[t δ, z(t δ )].

15 В множестве состояний Z выделяется такое подмножество Z (Y), что если z(t δ ) достигает Z (Y), то это состояние является моментом выдачи выходного сигнала, определяемого оператором выходов y=G[t δ, z(t δ )]. Таким образом, под агрегатом будем понимать любой объект, определяемый упорядоченной совокупностью рассмотренных множеств Т, X, Y, Z, Z (Y), H и случайных операторов V, U, W, G.

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

17 Для построения агрегата вводятся предположения о закономерностях функционирования А - схем, в соответствии реальной системой : 1) взаимодействие между А - схемой и внешней средой Е, а также между отдельными агрегатами внутри системы S осуществляется при передаче сигналов, причем взаимные влияния, имеющие место вне механизма обмена сигналами, не учитываются ; 2) для описания сигнала достаточно некоторого конечного набора характеристик ;

18 3) элементарные сигналы мгновенно передаются в А - схеме независимо друг от друга по элементарным каналам ; 4) к входному контакту любого элемента А - схемы подключается не более чем один элементарный канал, к выходному контакту - любое конечное число элементарных каналов при условии, что ко входу одного и того же элемента А - схемы направляется не более чем один из упомянутых элементарных каналов.

19 Структура агрегативной системы

20 Взаимодействие А - схемы с внешней средой Е рассматривается как обмен сигналами между внешней средой Е и элементами А - схемы. В соответствии с этим внешнюю среду Е можно представить в виде фиктивного элемента системы А о, вход которого содержит I 0 входных контактов, а выход J 0 выходных контактов. Сигнал, выдаваемый А - схемой во внешнюю среду Е, принимается элементом А о как входной сигнал, состоящий из элементарных сигналов х 1 (0) (t), х 2 (0) (t),..., х I0 (0) (t) Сигнал, поступающий в А - схему из внешней среды Е, является выходным сигналом элемента А о и состоит из элементарных сигналов y 1 (0) (t), y 2 (0) (t),..., y I0 (0) (t).

21 Таким образом, каждый А n ( в том числе и А о ) как элемент А - схемы в рамках принятых предположений о механизме обмена сигналами достаточно охарактеризовать множеством входных контактов Х 1 (n), Х 2 (n),..., Х In (n) которое обозначим { Х i (n) }, и множеством выходных контактов Y 1 (n), Y 2 (n),..., Y J (n) которое обозначим { Х j (n) }, где. Полученная пара множеств { Х i (n) }, { Х j (n) } является математической моделью элемента А n используемого для формального описания сопряжения его с прочими элементами А - схемы и внешней средой Е.

22 Если в А - схеме к контакту Х i (n) не подключен никакой элементарный канал, то оператор R не определен на этом контакте Х i (n). Оператор R называется оператором сопряжения элементов ( агрегатов ) в А - схему. Совокупность множеств { Х i (n) }, { Х l (k) } и оператор R образуют схему сопряжения элементов в систему S. Оператор сопряжения R можно задать в виде таблицы, в которой на пересечении строк с номерами элементов ( агрегатов ) n и столбцов с номерами контактов i располагаются пары чисел k, l, указывающие номер элемента k и номер контакта l, с которым соединен контакт Х i (n).

23 Таким образом, использование обобщенной типовой математической схемы моделирования, т. е. А - схемы, в принципе не отличается от рассмотренных ранее D-, F-, Р -, N-, Q- схем. Для частного случая, а именно для кусочно - линейных агрегатов, результаты могут быть получены аналитическим методом. В более сложных случаях, когда применение аналитических методов неэффективно или невозможно, прибегают к имитационному методу, причем представление объекта моделирования в виде А - схемы может являться тем фундаментом, на котором базируется построение имитационной системы и ее внешнего и внутреннего математического обеспечения. Стандартная форма представления исследуемого объекта в виде А - схемы приводит к унификации не только алгоритмов имитации, но и к возможности применять стандартные методы обработки и анализа результатов моделирования системы S.

24