Сети Петри

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Пример сети Петри. Белыми кружками обозначены позиции, полосками — переходы, чёрными кружками — метки.

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

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

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

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

История[править | править исходный текст]

Сети Петри разрабатывались для моделирования систем с параллельными взаимодействующими компонентами. Сети Петри впервые предложил Карл Адам Петри. В докторской диссертации "Связь автоматов" он сформулировал основные понятия теории связи асинхронных компонент вычислительной системы[1].

Динамика сети Петри[править | править исходный текст]

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

Виды сетей Петри[править | править исходный текст]

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

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

Анализ сетей Петри[править | править исходный текст]

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

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

В основе исследования перечисленных свойств лежит анализ достижимости. Методы анализа свойств сетей Петри основаны на использовании графов достижимых (покрывающих) маркировок, решении уравнения состояний сети и вычислении линейных инвариантов позиций и переходов. Применяются также вспомогательные методы редукции, позволяющие уменьшить размер сети Петри с сохранением ее свойств, и декомпозиции [2], разделяющие исходную сеть на подсети.

Универсальная сеть Петри[править | править исходный текст]

В 1974 году Тилак Аджервала показал, что ингибиторная сеть Петри является универсальной алгоритмической системой. В монографии Котова В.Е. приведен набросок доказательства, указывающий правила кодирования ингибиторной сетью программы счетчикового автомата Минского. Питерсон Дж. приводит примеры других расширенных классов сетей Петри, являющихся универсальной алгоритмической системой: синхронных и приоритетных. Построенная в явном виде универсальная сеть Петри [3] насчитывала несколько тысяч вершин и недавно была уменьшена до 56 вершин [4].

Бесконечные сети Петри[править | править исходный текст]

Бесконечные сети Петри были введены для верификации вычислительных решеток и позволяют определять свойства сетей Петри для регулярных структур (линейная, древовидная, квадратная, треугольная, шестиугольная и гиперкуб [5]) произвольного размера, полученных путем композиции типовых фрагментов.

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

Ссылки[править | править исходный текст]

  • Учебный курс МГТУ им. Баумана «Основы САПР. Моделирование». Сети Петри. Анализ сетей Петри
  • Сети Петри на сайте Института автоматики и процессов управления.
  • Исходные тексты примеров программ, реализующих сети Петри и строго иерархические сети.
  • Питерсон Дж. Теория сетей Петри и моделирование систем.- М.: Мир, 1984.- 264с.
  • Котов В.Е. Сети Петри.- М.: Наука, 1984.- 160с.
  • Слепцов А.И., Юрасов А.А. Автоматизация проектирования управляющих систем гибких автоматизированных производств / Под ред. Б.Н.Малиновского. – К.: Технiка, 1986. – 160 с.
  • Ачасова С.М., Бандман О.Л. Корректность параллельных вычислительных процессов. – Н.: Наука, 1990. – 253 с.