1303
правки
Сеть Петри: различия между версиями
Материал из WikiGrapp
→Литература
KEV (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) |
||
| (не показано 13 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
Сеть Петри ([[Petri net|''Petri net'']]) —– одна из наиболее популярных моделей параллельных систем, используемая как для теоретических исследований, так и практических применений в различных областях. Она используется для моделирования распределенных баз данных и операционных систем, архитектур вычислительных машин, систем и сетей, систем программного обеспечения, протоколов коммуникаций, семантики параллельных языков, систем с элементами искусственного интеллекта и т. д. | |||
для | |||
Состояние параллельной системы представляется наличием определенных | Сети Петри ориентированы на моделирование «неалгоритмических» параллельных систем в виде причинно–следственных связей между событиями их недетерминированного поведения на основе [[Сеть|''сети'']] с двумя типами вершин: места и переходы. Каждый переход связывается с соответствующим множеством входных мест и соответствующим множеством выходных мест. Обычно вершины-места изображаются кружками, а вершины-переходы — барьерами (а также прямоугольниками или квадратами, если переходы являются неэлементарными объектами). Каждый переход соединяется с каждым из входных мест дугой, идущей из вершины-места к переходу, и с каждым выходным местом — дугой, направленной от перехода к вершине-месту.[[Файл:Petri net.png|350px|right]] | ||
конфигурацией меток. Такое распределение меток между местами | Состояние параллельной системы представляется наличием определенных меток у вершин, а конкретное состояние отображается конкретной конфигурацией меток. Такое распределение меток между местами называется ''[[Разметка сети|разметкой]],'' которая обычно изображается в виде черных точек (фишек) внутри соответствующих кружков. | ||
называется ''разметкой'' | |||
Функционирование сети Петри описывается формально с помощью множества последовательностей срабатываний переходов, меняющих разметки, и множества достижимых в сети разметок. Эти понятия определяются через правила срабатывания переходов сети. | |||
Переход может срабатывать (отображая смену состояния) только тогда, когда | Переход может срабатывать (отображая смену состояния) только тогда, когда | ||
| Строка 27: | Строка 15: | ||
изменение состояния, так и влияние этого изменения. | изменение состояния, так и влияние этого изменения. | ||
Срабатывание перехода | Срабатывание перехода — это неделимое событие, и потому | ||
одновременное срабатывание двух или более переходов | одновременное срабатывание двух или более переходов | ||
невозможно. Когда состояние таково, что два или более | невозможно. Когда состояние таково, что два или более | ||
переходов претендуют на срабатывание, каждый из них должен | переходов претендуют на срабатывание, каждый из них должен | ||
рассматриваться отдельно. Начиная с | рассматриваться отдельно. | ||
которая соответствует исходному состоянию системы, и | |||
Начиная с ''начальной'' разметки, | |||
которая соответствует исходному (начальному) состоянию системы, и | |||
выполняя очевидную процедуру генерирования другой разметки, | выполняя очевидную процедуру генерирования другой разметки, | ||
достижимой из | достижимой из текущей за счет срабатывания некоторого перехода, можно исследовать возможные | ||
состояния системы и пути их достижения. Например, могут быть | состояния системы и пути их достижения. Например, могут быть | ||
легко обнаружены тупиковые состояния и непродуктивные | легко обнаружены тупиковые состояния и непродуктивные | ||
| Строка 46: | Строка 36: | ||
разметки из заданного исходного состояния, пока не поддается | разметки из заданного исходного состояния, пока не поддается | ||
решению. Неоднократные попытки доказать общепринятую гипотезу о | решению. Неоднократные попытки доказать общепринятую гипотезу о | ||
разрешимости последней, страдали одним общим недостатком | разрешимости последней, страдали одним общим недостатком — в | ||
доказательствах были обнаружены ошибки. Вместе с тем многие | доказательствах были обнаружены ошибки. Вместе с тем многие | ||
другие проблемы сетей Петри эквивалентны ей в том смысле, что их | другие проблемы сетей Петри эквивалентны ей в том смысле, что их | ||
| Строка 53: | Строка 43: | ||
Сеть Петри была изобретена в ФРГ в начале 60-х годов А.А.Петри. | Сеть Петри была изобретена в ФРГ в начале 60-х годов А.А.Петри. | ||
==Литература== | ==Литература== | ||
[ | * Котов В.Е. Сети Петри. — М.: Наука, 1984. | ||
* Касьянов В.Н., Касьянова Е.В. Теория вычислений. — Новосибирск: ИНЦ НГУ, 2018. | |||
* Питерсон Дж. Теория сетей Петри и моделирование систем.— М.: Мир, 1984. | |||
* Толковый словарь по вычислительным системам. — М.: Машиностроение,1991. | |||
[[Категория:Сети Петри]] | |||
[[Категория:Теория вычислений]] | |||
[[Категория:Граф-модели]] | |||
[[Категория:Основные термины]] | |||
