Мережа Петрі з трьох елементів: безліч місць, безліч переходів і ставлення инцидентности.
Проста мережа Петрі - це такий набір N = (S, T, F), де- - безліч місць;
- - безліч переходів таких, що.
- - відношення інцидентності таке, що
(А);
(Б)
Умови в пункті 3 кажуть, що для кожного переходу існує єдиний елемент, що задає для нього вхідну мультімножество місць і вихідна мультімножество. Дамо визначення вхідного і вихідного мультімножество.
Вхідний і вихідний мультимножини місць і переходів - знаходиться з наступних умов:Нехай задана мережа.
- Якщо для деякого переходу маємо, то будемо позначати;
- .
Будемо говорити, що - вхідні. а - вихідні місця переходу. Таким чином, згідно з визначенням, справедливо. Далі будемо говорити, що місце інцидентне переходу якщо або.
Розширимо функції і на мультимножини переходів. Нехай є мультімножество переходів таке, що. тоді покладемо
Мережі Петрі мають зручну графічну форму представлення у вигляді графа, в якому місця зображуються кружками, а переходи прямокутниками. Місця і переходи, причому місце з'єднується з переходом якщо і соедніяется з якщо для деякого натурального числа. Тут число називається кратністю дуги. яке графічно зображується поруч з дугою. Дуги, що мають одиничну кратність, будуть позначатися без приписування одиниці.
Приклад. приклад мережі
У графічній формі мережа представлена на Рис.1. Мережа має чотири місця і три переходи. Ставлення задає дуги мережі. Так, наприклад, елемент задає чотири дуги: з в і з в с кратностями 2, на підставі ст і з в з одиничними кратностями. Для переходу справедливо і. Для місця можна обчислити і.
Мал. 1: Приклад графа мережі Петрі
Саме по собі поняття мережі має статичну природу. Для завдання динамічних характеристик використовується поняття маркування мережі, тобто функції, сопоставляющей кожним місцем ціле число. Графічно маркування зображується у вигляді точок, які називаються мітками (tokens), і розташовуються в гуртках, відповідних місцях мережі. Відсутність міток в деякому місці говорить про нульову маркування цього місця.
Маркована мережа Петрі - це набір, де- - мережа;
- - початкова маркування.
Приклад. Приклад маркованої мережі.
Мал. 2: Приклад маркованої мережі Петрі
Мережі Петрі були розроблені і використовуються для моделювання паралельних і асинхронних систем. При моделюванні в мережах Петрі місця символізують якесь стан системи, а перехід символізують якісь дії, що відбуваються в системі. Система, перебуваючи в якомусь стані, часто породжує певні дії, і навпаки, виконання якоїсь дії переводить систему з одного стану в інший.
Поточний стан системи визначає маркування мережі Петрі, тобто розташування знаків (токенов) в місцях мережі. Виконання дії в системі, в мережах Петрі визначається як спрацьовування переходів. Спрацьовування переходів породжує нове маркування, тобто породжує нове розміщення міток (токенов) в мережі. Визначимо функціонування маркованих мереж, засноване на спрацьовуванні окремих переходів.
Правило спрацьовування переходів - це наступний алгоритмНехай маркована мережа.
- Перехід вважається порушеною (активованим) при маркуванні, якщо;
- Перехід, збуджений (активоване) при маркуванні, може спрацювати. привівши до нового маркування, яка обчислюється за правилом:. Спрацьовування переходу позначається як.
Іншими словами, перехід вважається порушеною (активованим) при деякій маркування, якщо в кожному його вхідному місці є кількість міток не менше кратності відповідних дуг. Збуджений (активоване) перехід може спрацювати, причому при спрацьовуванні з кожного його вхідного місця вилучається, а в кожне вхідне додається певна кількість міток, рівне кратності відповідних дуг. Якщо одночасно порушено (активоване) кілька переходів, спрацювати може будь-який з них або будь-яка їх комбінація. Наприклад, нехай в мережі на малюнку 2 спрацюють переходи і. Отримаємо мережу представлену на малюнку 3.
Мал. 3: Нова мережа з маркуванням.
Композіціональності підхід до побудови мереж Петрі передбачає можливість побудови більш складних мереж з менш складних складових. Для цього вводяться точки доступу, які дозволяють об'єднувати прості мережі шляхом синхронізації подій і станів (переходів і місць).
T-точка доступу - це точка, яка визначається наступними умовами
Нехай задана мережа і деякий алфавіт. Т-точкою доступу називається набір, де
- - ім'я (ідентифікатор) t-точки доступу;
- - деякий алфавіт;
- - пометочная функція, де. Запис означає безліч всіх кінцевих і непустих мультимножин, визначених на множині.
S-точка доступу - це точка, яка визначається наступними умовами
Нехай задана мережа. Тоді s-точкою доступу мережі N називається набір, де
- - ім'я (ідентифікатор) s-точки доступу;
- - безліч таке, що.
Введені поняття точок доступу надають можливість ввести дві основні операції над мережами Петрі для побудови композіціональності мереж:
1. Операція злиття переходів - дозволяє породжувати і описувати синхронізацію паралельних процесів (tmerge);
2. Операція злиття місць - дозволяє застосовувати до мереж операції послідовної композиції, вибору, ітерації і інші (smerge).
Мал. 4: Приклад операції злиття переходів
Мал. 5: Приклад операції злиття місць
Наведені операції мають такий зміст:
При злитті місць - визначається набір станів в мережі, які ідентифікуються, як стан мережі, певне ім'ям s-точки доступу. Злиття різних мереж проводиться так, що якщо в одній мережі досягнуто описаний стан, то в іншій мережі цей стан також виходить досягнутим;
При злитті переходів - визначається алфавіт подій, видимих з t-точки доступу. Кожен перехід в мережі позначається або невидимим подією, або комбінацією подій з алфавіту точки доступу. Злиття по переходах проводиться так, що якщо при спрацьовуванні однієї мережі виникає деяка комбінація подій, то ця ж комбінація подій відбувається в другій мережі.
Чи знаєте Ви, що синтетичні моделі - це математичні моделі, що розробляються для проектування нових, відмінних від відомих, систем із заданими властивостями. До числа синтетичних економіко-математичних моделей відносяться, наприклад, моделі машинно-тракторного парку, моделі формування інвестиційних програм і ін.
НОВИНИ ФОРУМУ
Лицарі теорії ефіру