анализ (Раздаточные материалы)

Система дистанционного обучения betaСтр. 1Новосибирский Государственный Технический УниверситетСистема Дистанционного Обучения.:Меню:.ГлавнаяКниги/УчебникиЛабораторные работыОбратная связь.:Поиск:.ИскатьРасширенный поиск.:Часы:.Оглавление » СЕТИ ПЕТРИ » Анализ сетей Петри »Методы анализаМетоды анализаОсобыйинтересвызываютметодыанализасвойств сетейПетри, которыеобеспечиваютавтоматический анализ моделируемых систем. Сначаларассмотрим метод анализа сетей Петри, которыйоснован на использовании дерева достижимости.ДдостижимостиСтраница создана за 0.01 с.]------------------GZip сжатие:До сжатия:51 кб .После сжатия:10 кб.Всего:81% .Ваш IP:213.79.

8.71Дереводостижимостипредставляетвседостижимые маркировки сети Петри, а также – всевозможные последовательности запусков ее переходов.Пример 4.4. Частичное дерево достижимостимаркированной сети Петри изображено на рисунке4.11, а, а частичное дерево достижимости для трёхшагов построения имеет вид (рис.

4.11, б).Для сети Петри с бесконечным множествомдостижимых маркировокдерево достижимостиявляется бесконечным. Сеть Петри с конечныммножеством достижимых маркировок также можетиметь бесконечное дерево достижимости (см. пример4.4). Для превращения бесконечного дерева вполезный инструмент анализа строится его конечноеhttp://tvp.iconix.ru/index.php?do=bk&b_id=1&gl=5&cat=26&hd=64&tt=406.06.2011 10:26:19Система дистанционного обучения betaСтр. 2представление.

При построении конечного деревадостижимостидляобозначениябесконечногомножества значений маркировки позиции используетсясимвол  . Также используются следующие нижеоперации над  , определяемые для любогопостоянного a. -- а =  ;  + а =  ; а <  ;.Алгоритм построенияконечногодеревадостижимости. Каждая вершина дерева достижимостиклассифицируется алгоритмом или как граничнаявершина, терминальная вершина, дублирующаявершина, или как внутренняя вершина.

Алгоритмначинает работу с определения начальной маркировкикорнем дерева, и граничной вершиной. Один шагалгоритма состоит в обработке граничной вершины.Пусть х — граничная вершина, тогда её обработказаключается в следующем:1. Если в дереве имеется другая вершина y, неявляющаяся граничной, и с ней связана та жемаркировка,  [x]= [y], то вершина х становитсядублирующей.2. Если для маркировки  [х] ни один из переходовне разрешен , то x становится терминальной.T,3. В противном случае, для всякого перехода tразрешенного в  [х], создаётся новая вершина zдеревадостижимости.Маркировка [z],связанная с этой вершиной, определяется дляP следующим образом:каждой позиции p3.1.

Если  [х](p) =  , то  [z](p) =  .3.2. Если на пути от корневой вершины к xсуществует вершина y с  [y] <  ’ (где  ’ –маркировка, непосредственно достижимая из [х] посредством запуска перехода t) и  [y](p) <http://tvp.iconix.ru/index.php?do=bk&b_id=1&gl=5&cat=26&hd=64&tt=406.06.2011 10:26:19Система дистанционного обучения betaСтр. 3 ’(p), то  [z](p) =  .

(В этом случаепоследовательность запусков переходов, ведущаяиз маркировки  [y] в маркировку  ’, можетнеограниченно повторяться и неограниченноувеличивать значение маркировки в позиции p.)В противном случае  [z](p) =  ’(p).4. Строится дуга с пометкой t, направленная отвершины x к вершине z. Вершина х становитсявнутренней, а вершина z – граничной.Такая обработка алгоритмом граничных вершинпродолжается до тех пор, пока все вершины дерева нестануттерминальными,дублирующимииливнутренними. Затем алгоритм останавливается.Важнейшим свойством алгоритма построенияконечного дерева достижимости является то, что он законечное число шагов заканчивает работу.Пример4.5.КонечноеНавигацияВверх<НазадВперед>Вниздереводостижимости сети Петри.Сеть Петри и ее конечное дерево достижимостиизображены на рис.

4. 12.:Важнейшим свойством алгоритма построенияконечного дерева достижимости является то, что он законечноечислошаговзаканчиваетработу.Доказательство основано на трёх леммах.Лемма 4.1. В любом бесконечном направленномдереве, в котором каждая вершина имеет толькоконечное число непосредственнопоследующихhttp://tvp.iconix.ru/index.php?do=bk&b_id=1&gl=5&cat=26&hd=64&tt=406.06.2011 10:26:19Система дистанционного обучения betaСтр. 4вершин, существует бесконечный путь, исходящий изкорня.Доказательство. Пусть x0 корневая вершина.Посколькуимеетсятолькоконечноечислонепосредственно следующих за x0 вершин, но общеечисло вершин в дереве бесконечно, по крайней мере,одна из непосредственно следующих за x0 вершиндолжна быть корнем бесконечного поддерева.

Выберемвершину x1 непосредственно следующую за x0 иявляющуюся корнем бесконечного поддерева. Теперьодна из непосредственно следующих за ней вершинтакже является корнем бесконечного поддерева,выберем в качестве такой вершины x 2. Еслипродолжать этот процесс бесконечно, то получимбесконечный путь в дереве – x0,x 1,x2 ,…,xn,… .Лемма4.2.Всякаябесконечнаяпоследовательность неотрицательных целых содержитбесконечную неубывающую последовательность.Доказательство.

Возможны два случая:1. Если какой-либо элемент последовательностивстречается бесконечно часто, то пусть x 0является таким элементом. Тогда бесконечнаяподпоследовательностьбесконечнойx0 ,x0,…,x0,…являетсянеубывающейподпоследовательностью.2. Если никакой элемент не встречается бесконечночасто, тогда каждый элемент встречается толькоконечное число раз. Пусть x0 — произвольныйэлемент последовательности. Существует самоебольшее x0 целых, неотрицательных и меньших,чем x0 (0,..., x 0 - 1), причем каждый из нихhttp://tvp.iconix.ru/index.php?do=bk&b_id=1&gl=5&cat=26&hd=64&tt=406.06.2011 10:26:19Система дистанционного обучения betaСтр.

5присутствуетвпоследовательноститолькоконечное число раз. Следовательно, продвигаясьдостаточно долго по последовательности, мыдолжны встретить элемент x 1, x1x 0.Аналогичнодолженсуществоватьвпоследовательности x2, x2x1, и т. д. Этоопределяетбесконечнуюнеубывающуюпоследовательность x0,x 1,x2 ,…,xn ,… .Таким образом, в обоих случаях бесконечнаянеубывающая подпоследовательность существует.Лемма4.3.Всякаябесконечнаяпоследовательность n-векторов над расширеннымисимволом  неотрицательными целыми содержитбесконечную неубывающую подпоследовательность.Доказательство. Доказываем индукцией по n, где n— размерность векторного пространства .1. Базовыйслучай (n= 1).Есливпоследовательности имеется бесконечное числовекторов вида < >, то они образуютбесконечную неубывающую последовательность(так как справедливо случаебесконечная ).

В противномпоследовательность,образованная удалением конечногочислаэкземпляров < >, имеет по лемме 4.2бесконечнуюнеубывающуюподпоследовательность.2. Индуктивное предположение. (Допустим, чтолемма верна для n докажем её справедливостьдля n+1.) Рассмотрим первую координату. Еслисуществуетбесконечномноговекторов,имеющих.

в качестве первой координаты  ,тогдавыберемэтубесконечнуюподпоследовательность,http://tvp.iconix.ru/index.php?do=bk&b_id=1&gl=5&cat=26&hd=64&tt=4котораянеубывает06.06.2011 10:26:19Система дистанционного обучения betaСтр. 6(постоянна) по первой координате. Если толькоконечное число векторов имеют  в качествепервой координаты, то рассмотрим бесконечнуюпоследовательностьцелых,являющихсязначениями первых координат.

По лемме 4.2 этапоследовательностьимеетбесконечнуюнеубывающуюподпоследовательность.Онаопределяет бесконечную последовательностьвекторов, которые не убывают по своей первойкоординате.В любом случае мы имеем последовательностьвекторов, неубывающих по первой координате.Примениминдуктивноепредположениекпоследовательности n-векторов, которая получается врезультате отбрасывания первой компоненты n+1векторов.Полученнаяподпоследовательность являетсябесконечнаянеубывающей покаждой координате.Докажем следующую теорему.Теорема 4.1.

Дерево достижимости сети Петриконечно.Доказательство. Докажем методом от противного.Допустим, что дерево достижимости бесконечно.Тогда по лемме 4.1 (и так как число вершин,следующих за каждой вершиной в дереве, ограниченочислом переходов m) в нём имеется бесконечный путьx 0,x1 ,x2,… , исходящий из корня x 0. Тогда  [x0 ],  [x1 ],  [x2],… — бесконечная последовательность n{ }, а по лемме 4.3 она имеетнеубывающую подпоследовательность… . Но по [xk1] [xk2]векторов. над Natбесконечную [xk0]построению дерева достижимости  [xi ] [xj] (для ij), поскольку тогда одна из вершин была быhttp://tvp.iconix.ru/index.php?do=bk&b_id=1&gl=5&cat=26&hd=64&tt=406.06.2011 10:26:19Система дистанционного обучения betaСтр.

7дублирующей и не имела следующих за собой вершин.Следовательно, это бесконечная строго возрастающаяпоследовательность  [xk0] <  [xk1] <  [xk2] …. Но попостроению, так как  [xi] <  [xj] нам следовало бызаменить по крайней мере одну компоненту  [x j], неявляющуюся  , на  в  [xj]. Таким образом,  [xk1]имеет по крайней мере одну компоненту, являющуюся ,  [xk2] имеет по крайней мере двекомпоненты, а  [xkn] имеет по крайней мере n  компонент.

Поскольку маркировки n-мерные,  [xkn]имеет во всех компонентах  . Но тогда у  [xkn+1 ] неможет быть больше  [xkn ]. Пришли к противоречию,что доказывает теорему.Анализ свойств сетей Петри на основе деревадостижимостиАнализ безопасности и ограниченности. СетьПетри ограниченна тогда и только тогда, когда символ отсутствует в ее дереве достижимости.Присутствие символа  в дереве достижимости(  [х](p) =  для некоторой вершины x и позиции p)означает, что для произвольного положительногоцелого k существует достижимая маркировка созначением в позиции p, большим, чем k.

Это, в своюочередь, означает неограниченность позиции p, аследовательно, и самой сети Петри.Отсутствие символа  в дереве достижимостиозначает, что множество достижимых маркировокконечно. Следовательно, простым перебором можнонайти верхнюю границу, как для каждой позиции вотдельности, так и общую верхнюю границу для всехпозиций.

Последнее означает ограниченность сетиhttp://tvp.iconix.ru/index.php?do=bk&b_id=1&gl=5&cat=26&hd=64&tt=406.06.2011 10:26:19Система дистанционного обучения betaСтр. 8Петри. Если граница для всех позиций равна 1, то сетьПетри безопасна.Анализсохранения.Таккакдереводостижимости конечно, для каждой маркировки можновычислить сумму начальной маркировки. Если этасумма одинакова для каждой достижимой маркировки,то сеть Петри является сохраняющей. Если суммы неравны, сеть не является сохраняющей.

Еслимаркировка некоторой позиции совпадает с  , то этапозиция должна был исключена из рассмотрения.Анализ покрываемости. Задача покрываемоститребуется для заданной маркировки  ' определить,достижима ли маркировка  " '. Такая задачарешается путём простого перебора вершин деревадостижимости. При этом ищется такая вершина х, что [x]  '. Если такой вершины не существует, томаркировка  ' не является покрываемой. Если онанайдена,тоопределяетпокрывающую [x]маркировку для  ' Если компонента маркировки  [x],соответствующая некоторой позиции p совпадает с  ,то конкретное её значение может быть вычислено.