Сети Петри

Материал из Википедии — свободной энциклопедии

Пример сети Петри. Белыми кружками обозначены позиции, полосками — переходы, чёрными кружками — метки.

Сети Петри — математический аппарат для моделирования динамических дискретных систем. Впервые описаны Карлом Петри в 1962 году.

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

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

[править] Виды сетей Петри

Некоторые виды сетей Петри:

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

[править] Анализ сетей Петри

Основными свойствами сети Петри являются:

Ограниченность — число меток в любой позиции сети не может превысить некоторого значения K.
Безопасность — частный случай ограниченности, K=1.
Сохраняемость — постоянство загрузки ресурсов, $\sum A_i N_i$ постоянна. Где $N i$ — число маркеров в i-той позиции, $A i$ — весовой коэффициент.
Достижимость — возможность перехода сети из одного заданного состояния (характеризуемого распределением меток) в другое.
Живость — возможностью срабатывания любого перехода при функционировании моделируемого объекта.