Конспект установочных лекций по комплексному курсу Информатика, Теория информации



         

Сети Петри


Одной из первых концепций, которые были предложены для описания распределенных систем и процессов, являются сети Петри, представляющие собой графическое описание таких систем.

Сеть Петри, или сеть условий/событий, есть направленный граф, состоящий из узлов двух типов - так называемых вентилей

(еще используются термины: переходы, барьеры) и ячеек (места, площадки). Ребра по мере надобности ведут от вентилей к ячейкам или от ячеек к вентилям. Ячейки загружаются логическими значениями или натуральными числами. Содержимое ячеек определяет состояние сети. В каком-либо заданном состоянии определенные вентили (множество вентилей) готовы к передаче (они могут «открываться» - путем открытия такого множества вентилей изменяется загрузка сети, т.е. содержимое ее ячеек).

Пусть дано множество T вентилей и множество Р ячеек (с Р ? Т = Ø ). Сеть Петри есть тройка (Т0, Р0, R), такая, что справедливо

Т0

Т                                                                         вентили,

Р0

 Р                                                                        ячейки,

 (Т0

х Р0) U (Р0 х Т0)                                           отношения потока.

Множества Т0

и  Р0  конечны. В таком случае сеть Петри есть бичастичный направленный граф. Граф называется бичастичным, если множество его узлов разбито на два класса и ребра могут соединять только узлы из различных классов.

Для сети Петри (Т0, Р0, R) каждое отображение

b: Р0

> N, которое ячейкам предписывает числа, означает целочисленную конкретизацию (занесение в ячейки конкретных чисел). Сети с целочисленными конкретизациями называются также сетями ячейки-вентили. Часто для некоторых ячеек устанавливаются дополнительно определенные наибольшие значения («мощность ячейки»), которые могут иметь заносимые в эти ячейки значения.

В некоторых случаях можно ограничиться сетями Петри с конкретизациями, использующими только значения 0 и 1, или соответственно false

и true. При этом рассматриваются только конкретизации вида b: Р0 > В.




Содержание  Назад  Вперед