683
правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Сеть Петри''' (''Petri net'') - Графическая модель системы с высокой степенью расп...) |
KVN (обсуждение | вклад) |
||
(не показано 9 промежуточных версий 2 участников) | |||
Строка 1: | Строка 1: | ||
'''Сеть Петри''' (''Petri net'') | '''Сеть Петри''' (''[[Petri net]]'') — Графическая модель системы с | ||
высокой степенью распараллеливания вычислений, используемая | высокой степенью распараллеливания вычислений, используемая | ||
для анализа определенных ее свойств. Сеть Петри состоит из | для анализа определенных ее свойств. [[Сеть]] Петри состоит из | ||
множества узлов (мест), множества символов, переходов и | множества [[узел|узлов]] (мест), множества символов, переходов и | ||
множества дуг. Каждый переход связывается с соответствующим | множества [[дуга|дуг]]. Каждый переход связывается с соответствующим | ||
множеством входных мест и соответствующим множеством | множеством входных мест и соответствующим множеством | ||
выходных мест. Каждый переход соединяется с каждым из | выходных мест. Каждый переход соединяется с каждым из | ||
входных мест дугой, идущей из узла-места к переходу, и с | входных мест дугой, идущей из узла-места к переходу, и с | ||
каждым выходным местом | каждым выходным местом — дугой, направленной от перехода к | ||
узлу-месту. | узлу-месту. | ||
[[Файл:Petri net.png|350px|right]] | |||
Состояние параллельной системы представляется наличием определенных | Состояние параллельной системы представляется наличием определенных | ||
меток у узлов, а конкретное состояние отображается конкретной | [[метка|меток]] у узлов, а конкретное состояние отображается конкретной | ||
конфигурацией меток. Такое распределение меток между местами | конфигурацией меток. Такое распределение меток между местами | ||
называется ''разметкой''. Узлы обычно изображаются в виде кружков, | называется ''разметкой''. Узлы обычно изображаются в виде кружков, | ||
обозначаемых строчными буквами <math>p \ldots t</math>, переходы | обозначаемых строчными буквами <math>p \ldots t</math>, переходы — линиями, а | ||
текущая разметка — черными точками (фишками). Символы переходов | |||
показывают возможные изменения состояния параллельной | показывают возможные изменения состояния параллельной | ||
системы. | системы. | ||
Строка 27: | Строка 29: | ||
изменение состояния, так и влияние этого изменения. | изменение состояния, так и влияние этого изменения. | ||
Срабатывание перехода | Срабатывание перехода — это неделимое событие, и потому | ||
одновременное срабатывание двух или более переходов | одновременное срабатывание двух или более переходов | ||
невозможно. Когда состояние таково, что два или более | невозможно. Когда состояние таково, что два или более | ||
переходов претендуют на срабатывание, каждый из них должен | переходов претендуют на срабатывание, каждый из них должен | ||
рассматриваться отдельно. Начиная с | рассматриваться отдельно. | ||
которая соответствует исходному состоянию системы, и | |||
Начиная с ''начальной'' разметки, | |||
которая соответствует исходному (начальному) состоянию системы, и | |||
выполняя очевидную процедуру генерирования другой разметки, | выполняя очевидную процедуру генерирования другой разметки, | ||
достижимой из | достижимой из текущей за счет срабатывания некоторого перехода, можно исследовать возможные | ||
состояния системы и пути их достижения. Например, могут быть | состояния системы и пути их достижения. Например, могут быть | ||
легко обнаружены тупиковые состояния и непродуктивные | легко обнаружены тупиковые состояния и непродуктивные | ||
Строка 46: | Строка 50: | ||
разметки из заданного исходного состояния, пока не поддается | разметки из заданного исходного состояния, пока не поддается | ||
решению. Неоднократные попытки доказать общепринятую гипотезу о | решению. Неоднократные попытки доказать общепринятую гипотезу о | ||
разрешимости последней, страдали одним общим недостатком | разрешимости последней, страдали одним общим недостатком — в | ||
доказательствах были обнаружены ошибки. Вместе с тем многие | доказательствах были обнаружены ошибки. Вместе с тем многие | ||
другие проблемы сетей Петри эквивалентны ей в том смысле, что их | другие проблемы сетей Петри эквивалентны ей в том смысле, что их | ||
Строка 54: | Строка 58: | ||
Сеть Петри была изобретена в ФРГ в начале 60-х годов А.А.Петри. | Сеть Петри была изобретена в ФРГ в начале 60-х годов А.А.Петри. | ||
==Литература== | ==Литература== | ||
[ | * Котов В.Е. Сети Петри. — М.: Наука, 1984. | ||
* Толковый словарь по вычислительным системам. — М.: Машиностроение,1991. | |||
* Касьянов В.Н., Касьянова Е.В. Теория вычислений. — Новосибирск: ИНЦ НГУ, 2018. | |||
[[Категория:Теория вычислений]] |