Сеть Петри: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 17: Строка 17:
называется ''разметкой''. Узлы обычно изображаются в виде кружков,
называется ''разметкой''. Узлы обычно изображаются в виде кружков,
обозначаемых строчными буквами <math>p \ldots t</math>, переходы — линиями, а
обозначаемых строчными буквами <math>p \ldots t</math>, переходы — линиями, а
исходная разметка — черными точками (фишками). Символы переходов
текущая разметка — черными точками (фишками). Символы переходов
показывают возможные изменения состояния параллельной
показывают возможные изменения состояния параллельной
системы.
системы.
Строка 35: Строка 35:
рассматриваться отдельно.  
рассматриваться отдельно.  


Начиная с начальной разметки,
Начиная с ''начальной'' разметки,
которая соответствует исходному (начальному) состоянию системы, и
которая соответствует исходному (начальному) состоянию системы, и
выполняя очевидную процедуру генерирования другой разметки,
выполняя очевидную процедуру генерирования другой разметки,
достижимой из текущей, можно исследовать возможные
достижимой из текущей за счет срабатывания некоторого перехода, можно исследовать возможные
состояния системы и пути их достижения. Например, могут быть
состояния системы и пути их достижения. Например, могут быть
легко обнаружены тупиковые состояния и непродуктивные
легко обнаружены тупиковые состояния и непродуктивные

Версия от 10:35, 16 сентября 2018

Сеть Петри (Petri net) — Графическая модель системы с высокой степенью распараллеливания вычислений, используемая для анализа определенных ее свойств. Сеть Петри состоит из множества узлов (мест), множества символов, переходов и множества дуг. Каждый переход связывается с соответствующим множеством входных мест и соответствующим множеством выходных мест. Каждый переход соединяется с каждым из входных мест дугой, идущей из узла-места к переходу, и с каждым выходным местом — дугой, направленной от перехода к узлу-месту.

Petri net.png

Состояние параллельной системы представляется наличием определенных меток у узлов, а конкретное состояние отображается конкретной конфигурацией меток. Такое распределение меток между местами называется разметкой. Узлы обычно изображаются в виде кружков, обозначаемых строчными буквами [math]\displaystyle{ p \ldots t }[/math], переходы — линиями, а текущая разметка — черными точками (фишками). Символы переходов показывают возможные изменения состояния параллельной системы.

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

Срабатывание перехода — это неделимое событие, и потому одновременное срабатывание двух или более переходов невозможно. Когда состояние таково, что два или более переходов претендуют на срабатывание, каждый из них должен рассматриваться отдельно.

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

Сеть Петри была изобретена в ФРГ в начале 60-х годов А.А.Петри.

Литература

  • Котов В.Е. Сети Петри. — М.: Наука, 1984.
  • Толковый словарь по вычислительным системам. — М.: Машиностроение,1991.
  • Касьянов В.Н., Касьянова Е.В. Теория вычислений. — Новосибирск: ИНЦ НГУ, 2018.