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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
'''Сеть Петри''' (''[[Petri net]]'') - Графическая модель системы с
'''Сеть Петри''' (''[[Petri net]]'') Графическая модель системы с
высокой степенью распараллеливания вычислений, используемая
высокой степенью распараллеливания вычислений, используемая
для анализа определенных ее свойств. Сеть Петри состоит из
для анализа определенных ее свойств. [[Сеть]] Петри состоит из
множества [[узел|узлов]] (мест), множества символов, переходов и
множества [[узел|узлов]] (мест), множества символов, переходов и
множества [[дуга|дуг]]. Каждый переход связывается с соответствующим
множества [[дуга|дуг]]. Каждый переход связывается с соответствующим
Строка 7: Строка 7:
выходных мест. Каждый переход соединяется с каждым из
выходных мест. Каждый переход соединяется с каждым из
входных мест дугой, идущей из узла-места к переходу, и с
входных мест дугой, идущей из узла-места к переходу, и с
каждым выходным местом --- дугой, направленной от перехода к
каждым выходным местом дугой, направленной от перехода к
узлу-месту.
узлу-месту.


Строка 16: Строка 16:
конфигурацией меток. Такое распределение меток между местами
конфигурацией меток. Такое распределение меток между местами
называется ''разметкой''. Узлы обычно изображаются в виде кружков,
называется ''разметкой''. Узлы обычно изображаются в виде кружков,
обозначаемых строчными буквами <math>p \ldots t</math>, переходы --- линиями, а
обозначаемых строчными буквами <math>p \ldots t</math>, переходы линиями, а
исходная разметка --- черными точками. Символы переходов
исходная разметка черными точками. Символы переходов
показывают возможные изменения состояния параллельной
показывают возможные изменения состояния параллельной
системы.
системы.
Строка 29: Строка 29:
изменение состояния, так и влияние этого изменения.
изменение состояния, так и влияние этого изменения.


Срабатывание перехода --- это неделимое событие, и потому
Срабатывание перехода это неделимое событие, и потому
одновременное срабатывание двух или более переходов
одновременное срабатывание двух или более переходов
невозможно. Когда состояние таково, что два или более
невозможно. Когда состояние таково, что два или более
Строка 48: Строка 48:
разметки из заданного исходного состояния, пока не поддается
разметки из заданного исходного состояния, пока не поддается
решению. Неоднократные попытки доказать общепринятую гипотезу о
решению. Неоднократные попытки доказать общепринятую гипотезу о
разрешимости последней, страдали одним общим недостатком --- в
разрешимости последней, страдали одним общим недостатком в
доказательствах были обнаружены ошибки. Вместе с тем многие
доказательствах были обнаружены ошибки. Вместе с тем многие
другие проблемы сетей Петри эквивалентны ей в том смысле, что их
другие проблемы сетей Петри эквивалентны ей в том смысле, что их
Строка 56: Строка 56:
Сеть Петри была изобретена в ФРГ в начале 60-х годов А.А.Петри.
Сеть Петри была изобретена в ФРГ в начале 60-х годов А.А.Петри.
==Литература==
==Литература==
[Котов],  
* Котов В.Е. Сети Петри. — М.: Наука, 1984.


[Словарь]
* Толковый словарь по вычислительным системам. — М.: Машиностроение,
1991.

Версия от 12:14, 2 сентября 2011

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

Petri net.png

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

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

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

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

Литература

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

1991.