Відмінності між версіями «Мережі Петрі»

Версія за 08:43, 17 травня 2011

Мережа Петрі

Мережа Петрі – це графічний і математичний засіб моделювання систем і процесів.

Графічно представляється у вигляді дводольного орієнтованого мультиграфу з маркерами («фішками») (маркований орієнтований граф), який має дві групи вершин: позиції та переходи. Позиції можуть бути пустими або маркованими та визначають <стан> мережі. Переходи визначають дії. Орієнтовані ребра графу задають зв'язки між позиціями та переходами. Процес функціонування мережі Петрі полягає в послідовному «виконанні» переходів, та відповідному перерахункові кількості «фішок» у позиціях. Дуги можуть бути кратними, коли два вузли з'єднані більше ніж однією дугою однакового напрямку. Альтернативно, для відображення кратності дуг може використовуватися функція «ваги» дуг.

Як правило, мережами Петрі моделюють паралельні (синхронні та асинхронні) системи і процеси. Спочатку запропоновані в докторській дисертації Карла Петрі в 1962 році вони одержали подальший розвиток у роботах таких вчених як Тадао Мурата, Курт Йенсен, Віталій Котов, Анатолій Слєпцов. В останні часи проводиться щорічна конференція «Застосування і теорія мереж Петрі», видається в Боні інформаційний бюлетень «Новини мереж Петрі» (Petri Net Newsletter), відомо декілька сот моделюючих систем для різних програмно-апаратних платформ, існують реалізації процесорів мереж Петрі. Галузі застосування мереж Петрі включають дослідження телекомунікаційних мереж, мережних протоколів, обчислювальних систем і обчислювальних процесів, виробничих і організаційних систем.

Комп'ютерні моделюючі системи

Pndpi, Tina, Design/CPN

Дослідження мережі Петрі

Основні методи дослідження мереж Петрі:

1. Дерево досягальності,
2. Графічний,
3. Аналітичний,
4. За допомогою еквівалентних перетвореннь.

Взагалі, мережі Петрі досліджують на такі властивості:

1. Безпечність — досліджує виконання умови що кількість «фішок» в позиції не перевищує 1;
2. Обмеженість — досліджує виконання умови що кількість «фішок» в позиції не перевищує заданого числа,
3. Зберігальність — досліджує виконання умови що кількість «фішок» в мережі не змінюється,
4. Оберненість — для довільного досяжного стану досліджується існування послідовності виконань переходів яка повертає мережу в початковий стан),
5. Активність переходів — досліджує можливість виконання певних переходів та наявність тупиків — станів у яких переходи не дозволені та для яких неможливо досягти стану в якому ці переходи дозволені,
6. Досяжність маркування — досліджує існування послідовності виконань переходів при якій можна досягнути задане маркування,
7. Покриття — досліджує існування послідовності виконань переходів при якій можна досягнути маркування що покриває, тобто є більшим за задане маркування.

Умова зберігальності може бути послаблена, для чого вводять поняття функції ваги:

Неможливо розібрати вираз (невідома помилка): \mathbf W:\qquad(\mathbf T \times \mathbf P) \cup (\mathbf P \times \mathbf T) \to \mathbb N \cup \{0\}

яка залишається постійною під час роботи.

Більшість досліджень мереж Петрі можна звести до побудови дерева досяжності.

Список використаної літератури

1.

2. Зайцев Д.А. Мережі Петрі і моделювання систем: Навчальній посібник // , Одеса 2006

3. Зайцев Д.А. Математичні моделі дискретних систем: Навчальний посібник // Одеса: ОНАЗ ім. О.С. Попова, 2004. – 40 с.

4. Математичні основи теорії телекомунікаційних систем / Підручник за загальною редакцію В.В. Поповського. – Харків, ТОВ «Компанія СМІТ», 2006. – 564 с.

5. Питерсон Дж. Теория сетей Петри и моделирование систем. – М. Мир, 1984. – 264 с.

6. Котов В.Е. Сети Петри. – М.: Наука, 1984. – 160 с.

7. Ачасова С.М., Бандман О.Л. Корректность параллельных вычислительных процессов. – Н.: Наука, 1990. – 253 с.

8. Слепцов А.И., Юрасов А.А. Автоматизация проектирования управляющих систем гибких автоматизированных производств / Под ред. Б.Н.Малиновского. – К.: Технiка, 1986. – 160 с.