Постройте граф достижимости для рассмотренной в п. 3.1 Сети Петри.

Министерство образования и науки РФ

Федеральное государственное бюджетное образовательное учреждение высшего образования

Уфимский государственный авиационный технический университет

ПРАКТИКУМ ПО СИСТЕМНОМУ АНАЛИЗУ

Методические указания

К практическим работам по дисциплине

«Теория систем и системный анализ»

Практическое занятие № 1 Представление модели объекта в виде семантической сети

1 Цель занятия

Научиться рассматривать сложные объекты в виде семантических сетей и изучить их на примере Сетей Петри.

2 Общие теоретические сведения

Сети Петри являются примером семантических сетей, представленных разновидностью ориентированных двудольных графов. Двудольный граф включает вершины двух типов: позиции (обозначаются кружками) и переходы (обозначаются планками). Сеть Петри может быть формально представлена как совокупность множеств:

N = (P, T, G, W),

где P = {p₁, p₂… p_n} – множество всех позиций (n – количество позиций),

Т = {t₁, t₂… t_m} – множество переходов (m – количество переходов),

G = (G_p_-_t, G_t_-_p) – множество дуг сети:

G_p_-_t = (p ´ t), G_t_-_p = (t ´ p) – множества дуг, ведущих соответственно от переходов к позициям и от позиций к переходам (дуг, соединяющих однородные вершины, не существует),

W = {w₁, w₂… w _k} – множество весов дуг (k – количество дуг).

Каждая позиция может быть маркирована, т.е. содержать некоторое число фишек. Если обозначить числа фишек, находящихся в i-й позиции p_i, как m_i, то маркировка всей сети: M = {m₁, m₂… m_n}. Тогда полное определение сети Петри, включая данные о начальной маркировке, можно записать в виде

PN = (N, M₀),

где М₀ – начальная маркировка сети.

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

Пример. Схема принятия решений при попытке получить деньги из банкомата (см. рис. 1).

t₆

Р₆

t₄

Рис. 1. Пример Сети Петри

Смысл позиций: Р₁ – карта (ее наличие); Р₂ – исправность банкомата; Р₃ – введенный код; Р₄ – код набран правильно, запрашивается сумма; Р₅ – код набран неправильно; Р₆ – сумма доступна; Р₇ – сумма недоступна (нет такого количества денег на карте); Р₈ – деньги (получены). Смысл переходов: t₁ – банкомат принимает карту и делает запрос в банк, ввод кода; t₂ – запрос суммы; t₃ – повторный ввод кода; t₄ – выдача сообщения о доступности суммы; t₅ – выдача сообщения о недоступности суммы; t₆ – выдача денег; t₇ – повторный набор суммы; t₈ – забрать карту из банкомата (другой исход: имеется другая карта, с которой также нужно снять деньги – см. дуги, обозначенные пунктиром); t₉ – выдача сообщения, что код неверный.

Роль указателей мощности потоков выполняют фишки или метки (●). Формально метка – это знак выполнения соответствующего условия. Переход срабатывает только в том случае, если во всех входных позициях имеется достаточное количество меток (по меньшей мере, по одной). При срабатывании перехода из входных позиций изымаются метки (в случае взвешенной СП изымается количество меток, соответствующее весам дуг, связывающих входные позиции с данным переходом), а во входные – добавляются (для взвешенной СП – также соответственно весам дуг). Начальная маркировка СП есть начальное состояние системы.

Таким образом, если осуществить начальную маркировку СП, то с использованием формальных правил можно описать логику работы системы и произвести анализ ее работоспособности. Переходы меток описываются графом достижимости (ГД), у которого каждой вершине соответствует определенная маркировка, а каждой дуге – переход, который срабатывает при данной маркировке.

Таким образом, граф достижимости представляется как

GD = (V, E),

где V – массив вершин (маркировок, соответствующих вершинам):

V = {М₁, М₂… М_q},

М_i – i-я маркировка, q – количество маркировок;

Е = {e₁, e₂… e_p} – массив дуг, связывающих вершины (р – количество дуг).

Каждая дуга представляется как совокупность e_i = {a₁, a₂, Т}, где a₁ и a₂ – номера начальной и конечной вершин графа; Т = {t₁, t₂, … t_k} – массив переходов, соответствующий дуге; k – количество одновременно срабатывающих переходов при переходе от одной маркировки к другой.

Алгоритм построения графа по исходной СП:

1 За исходную берется маркировка М₀ и ей присваивается метка «новая».

2 Для каждой «новой» маркировки выполнять следующие операции:

a. Для «новой» маркировки М_нов определяются все переходы, которые могут быть запущены, а также все возможные комбинации этих переходов.

b. Для каждого разрешенного перехода или комбинации переходов производятся следующие действия:

- Определяется маркировка М’, которая образуется при срабатывании данного перехода (комбинации переходов).

- Просматриваются все маркировки на пути от М’ к начальной М₀. Если на пути находится маркировка М”, элементы которой больше либо равны соответствующим элементам новой и которая не равна М’, то вместо элементов m’_i, которые больше, чем элементы m_i маркировки М₀, записывается символ «w» (бесконечность). В массив Е записывается дуга с соответствующими a₁, a₂ и Т.

- Просматриваются все маркировки графа. Если находится маркировка, равная новой, то в массив Е записывается новая дуга, у которой a₁ = a₂ и равны номеру найденной маркировки.

- Если в п.п. а и б маркировки не найдены, то создается новая вершина графа, в которую записывается новая маркировка, в массив Е записывается дуга, у которой a₁ равна номеру исходной маркировки, a₂ – номеру новой маркировки, Т – набор переходов, срабатывание которых привело к переходу от одной маркировки к другой. Далее определяется массив всех разрешенных переходов и расчет продолжается, начиная с п. а.

Рис. 2. Граф достижимости Сети Петри

Для рассмотренного выше примера СП граф ГД имеет вид (см. рис. 2), список маркировок приведен в таблице к рисунку. С помощью ГД могут быть определены свойства СП и, в конечном счете, моделируемой системы. К ним относятся:

- живость (отсутствие тупиковых состояний);

- ограниченность (сеть ограниченна, если символ «w» не входит ни в одну вершину графа);

- безопасность (сеть безопасна, если в метки вершин входят только «0» и «1») – физически безопасность означает отсутствие зацикливаний;

- правильность (если сеть безопасная и живая, то она правильная);

- обратимость (сеть обратима, если в графе имеется хотя бы одна дуга, направленная к начальной маркировке М₀);

- пассивность переходов (переход t_i пассивен, если он не соответствует ни одной дуге графа);

- число возможных состояний N_сост.

Сеть Петри называется k-ограниченной, если в любом состоянии в любой позиции скапливается не более k фишек.

Любая система должна представляться правильной сетью.

Для рассмотренного примера можно сделать вывод, что сеть правильная, обратимая и без пассивных переходов.

3 Задачи для самостоятельного решения студентами

3.1. Постройте в виде Сети Петри схему принятия решения об обеде в столовой УГАТУ, используя при этом примерно следующие позиции: осознание голода, выбор зала, занятие очереди, выбор блюда, проверка наличия блюда (блюдо есть), проверка наличия денег, переход к другому блюду, переход в другой зал, отказ от обеда, расчёт с кассиром, выбор столовых приборов, выбор свободного стола и занятие стола, потребление пищи, принятие решения о покупке дополнительных блюд, принятие решения о передачи грязной посуды на мойку, передача грязной посуды на мойку, выход из столовой.

Постройте граф достижимости для рассмотренной в п. 3.1 Сети Петри.

4 Контрольные вопросы

1) Какие примеры семантических сетей Вы знаете?

2) Что интерпретируют собой переходы в Сети Петри?

3) Что такое граф достижимости?

4) Когда Сеть Петри безопасна?

Список литературы

1 INTEGRATION DEFINITION FOR FUNCTION MODELING (IDEF0). Draft Federal Information Processing Standards Publication 183, 1993, December 2. www.idef.com.

2 Куликов Г.Г., Набатов А.Н., Речкалов А.В. Автоматизированное проектирование информационно-управляющих систем. Системное моделирование предметной области. – Уфа: УГАТУ, 1998.

3 Прангишвили И.В. Системный подход и общесистемные закономерности. // М.: СИНТЕГ, 2000.

4 Рекомендации Р 1.1.26-2002. Система менеджмента качества. Методология функционального моделирования. Основные положения и порядок проведения работ. М.: НИИСУ, 2002

Дата добавления: 2019-03-09; просмотров: 433; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!