Jndtns gj ujcfvvvv

  • 07 сент. 2012 г.
  • 2192 Слова
123
Сети Петри (СП): структура, выполнение. Анализ СП деревом достижимости.
Сети Петри – математический аппарат для моделирования динамических дискретных систем. Впервые описаны немецким математиком Карлом Петри в 1962 году.
Структура
Сеть Петри представляет собой двудольный* ориентированный граф, состоящий из вершин двух типов – позиций и переходов, соединённых между собой дугами, вершиныодного типа не могут быть соединены непосредственно. В позициях могут размещаться метки (маркеры, фишки), способные перемещаться по сети.
Сеть Петри – это четверка ‹P,T,I,O›, где P – множество позиций, T – множество переходов, I и O – соответственно входные и выходные функции – отображение переходов в комплекты позиций.
Выполнение
Сеть Петри выполняется посредством запусков переходов. Переходзапускается удалением фишек из его входных позиций и образованием новых фишек, помещаемых в его выходные позиции. Переход может запускаться только в том случае, когда он разрешен. Запуски могут осуществляться до тех пор, пока существует хотя бы один разрешенный переход. Когда не останется ни одного разрешенного перехода, выполнение прекращается.
Разрешенный переход – переход, у которого каждая из его входныхпозиций имеет число фишек, по крайней мере, равное числу дуг из позиции в переход.
Разрешающие фишки перехода – фишки во входной позиции, которые разрешают этот переход.
Тупик сети Петри – это множество переходов, которые в некоторой маркировке не разрешены.
Ресурс – позиция, являющаяся разрешенной, но не имеющая прямого отношения к процессу.
Маркировка сети Петри – это функция, отображающаямножество позиций на множество натуральных чисел. Маркировку можно также определить как вектор.
Маркированная сеть Петри С = есть совокупность структуры сети Петри и маркировки μ.
Свойства сетей Петри
– ограниченность – число меток в любой позиции сети не может превысить некоторого значения K;
– безопасность – частный случай ограниченности, K=1;
– сохраняемость – постоянство загрузкиресурсов,
[pic] постоянна, где [pic] – число маркеров в i-той позиции, [pic] – весовой коэффициент;
– живость – возможность срабатывания любого перехода при функционировании моделируемого объекта.
– устойчивость – для любых двух разрешённых переходов срабатывание одного не приводит к запрещению другого.
– активность перехода – каждый переход может обладать одним из пяти уровней активности:
– 0-йуровень (пассивность перехода) – у перехода отсутствует достижимая маркировка, в которой он разрешен.
– 1-й уровень – переход потенциально достижим, т.е. существует допустимая маркировка, в которой он разрешен.
– 2-й уровень – существует послед-сть запусков переходов, где этот переход присутствует ограниченное число раз.
– 3-й уровень – есть бесконечная послед-ть запуска переходов, где этот переходприсутствует неограниченно часто.
– 4-й уровень – переход разрешен в любой допустимой маркировке.
Задачи сетей Петри
– достижимость – является ли маркировка m1 достижимой из начальной маркировки m0?
– покрываемость – является ли маркировка mn покрывающей для маркировки mk при начальной маркировке m0?
– последовательность запусков – возможна ли другая последовательность запусков переходовв данной сети?
– эквивалентность и подмножества – можно ли изменить послед-ть запусков переходов, не изменяя поведение сети?
Достижимая маркировка – маркировка m1 достижима из m0, если существует послед-ть переходов, переводящая m0 в m1.
Покрывающая маркировка – маркировка m1 покрывает m2, если у m1 в каждой позиции фишек не меньше, чем у m2.

Дерево достижимости представляет все достижимыемаркировки сети Петри, а также все возможные последовательности запусков ее переходов. При построении конечного дерева достижимости для обозначения ∞ множества значений маркировки позиции используется символ w.
Анализ свойств и задач сети Петри на основе дерева достижимости
– ограниченность и безопасность – Сеть Петри ограниченна, когда символ w отсутствует в ее...
tracking img