1. Понятие дискретной динамической системы

• Название: 1. Понятие дискретной динамической системы
• Дата: 23.11.2018
• Размер: 0.51 Mb.
• Имя файла: tmp_4118-Otvety_k_ekzamenu_po_predmetu_Teoria_vychislitelnykh_pr.docx
• Тип: Документы; #57412
• страница: 15 из 15

44.Лемма 2 для доказательства теоремы о конечности дерева достижимости сети Петри.

Расширенным множеством натуральных чисел будем называть множество натуральных чисел, дополненное символом ω.

Лемма 2. Всякая бесконечная последовательность из расширенного множества натуральных чисел содержит бесконечную неубывающую подпоследовательность.

Доказательство. Возможны два случая:

• 
  Если какой-либо элемент последовательности х₀ встречается бесконечно часто, то последовательность х₀,x₀,x₀,... является бесконечной неубывающей подпоследовательностью. Пусть любой элемент последовательности встречается конечное число раз и х₀ – произвольный элемент последовательности, отличный от ω. Очевидно, что в последовательности имеется не более чем х₀ различных элементов, меньших чем х₀. Каждый из указанных элементов встречается конечное число раз. Тогда общее число элементов, меньших х₀, конечно, а последовательность бесконечна. Следовательно, в последовательности существует элемент x₁,отличный от ω, такой, что x₁ ≥ x₀.
  
• 
  Аналогично должен существовать в последовательности элемент x₂ ≥ x₁ и т.д.
  

Получаем бесконечную неубывающую последовательность x₀≤х₁≤x₂≤x₃≤.... (чтд)

45. Лемма 3 для доказательства теоремы о конечности дерева достижимости сети Петри.

Лемма 3. Всякая бесконечная последовательность n-мерных векторов над расширенным множеством натуральных чисел содержит бесконечную неубывающую подпоследовательность.

Доказательство. Доказываем индукцией по n, где n – размерность векторного пространства.

1. Случай n =1 это лемма 2.

2. Допустим: лемма верна для размерности n, докажем ее справедливость для (n+1).

Сопоставим каждому (n+1)-мерному вектору из последовательности n-мерный вектор, полученный удалением последней координаты. По предположению индукции, из полученной последовательности n-мерных векторов можно извлечь неубывающую подпоследовательность. Добавим к элементам этой подпоследовательности (n+1)-ю координату из исходной последовательности. Выбрав из полученной последовательности [(n+1)–х] координат неубывающую последовательность получим «подподпоследовательность» исходной последовательности с нужными свойствами.

46. Терема о конечности дерева достижимости сети Петри.

Теорема: Усеченное дерево достижимости СП конечно.

Доказательство (от противного).

Допустим, что существует бесконечное усеченное ДД. Число дуг, исходящих из каждой вершины дерева конечно. Все условия леммы 1 выполняются и в дереве существует бесконечный путь, исходящий из корня: х₀, x₁, x₂, ....

Каждой вершине соответствует маркировка, являющаяся n-мерным вектором над расширенным множеством натуральных чисел. По лемме 3 бесконечная последовательность µ[x₀],µ[x₁],µ[x₂],… имеет бесконечную неубывающую последовательность: µ[xi₀]µ[xi₁]≤µ[xi₂]≤…

Обратимся к алгоритму построения усеченного ДД. В соответствии с пунктом 2: если µ[x_ij]= µ[x_ij+1], то µ[x_ij+1], – дублирующая и из соответствующей вершины дуги не строятся. Это позволяет исключить знак равенства. Тогда µ[xi₀]µ[xi₁]µ[xi₂]…

В соответствии с алгоритмом построения УДД, если µ[x] < µ[y] и x и y находятся на одном пути от корня, то в маркировке µ[y] по меньшей мере одна компонента равна ω.

Тогда µ[x_i1] содержит по меньшей мере 1 символ ω; …; µ[x_in] - n символов ω.

Но тогда, так как векторы n-мерные, µ[x_in+1] также содержит n символов ω и является дублирующей к маркировке µ[x_in] и это противоречит тому, что последовательность является бесконечной. Противоречие доказывает справедливость теоремы.

47. Решение задачи безопасности и ограниченности сетей Петри на основе дерева достижимости.

СП ограничена тогда и только тогда, когда символ отсутствует в ее дереве достижимости.

В этом случае покомпонентное исследование вершин усеченного ДД позволяет установить безопасность или ограниченность для каждой отдельной позиции, после чего сделать вывод о сети в целом. Наибольшее значение компоненты маркировки, соответствующей некоторой позиции есть граница числа фишек этой позиции. Если граница для всех позиций не превышает 1, сеть безопасна.

48. Решение задачи сохранения сетей Петри на основе дерева достижимости.

Напомним, что маркированная СП С=(P,T,I,O,μ₀) называется сохраняющей по отношению к вектору взвешивания w=(w₁, w₂,..., w_n), n=|Р|, w_i>0 для i, если для всех μ'R(C, 0)

Строго сохраняющая СП является сохраняющей по отношению к вектору взвешивания w=(1, 1, ..., 1).

Рассмотрим задачу нахождения вектора взвешивания, по отношению к которому сеть будет сохраняющей, используя усеченное ДД. Естественно, что данная задача решается только для деревьев, в которых отсутствует символ .

Пусть усеченное ДД имеет k вершин: _x1, x₂, …, x_k. Для набора вершин составляется система, имеющая k равенств, n неравенств и (n+1) неизвестных (w₁, w₂, …, w_n, С).

49.Решение задачи покрываемости и достижимости сетей Петри на основе дерева достижимости. Проблемы, возникающие в случае наличия неограниченной позиции. Пример.

В задаче покрываемости мы хотим для данной маркировки μ' определить, достижима ли маркировка μ''μ'. Строим для начальной маркировки усеченное ДД. Затем ищем любую вершину х с μ[xμ'. Если такой вершины не существует, маркировка μ' не покрывается никакой достижимой маркировкой; если она найдена, μ[х] дает достижимую маркировку, покрывающую μ'.

Задача достижимости маркировки μ'' из начальной маркировки μ' решается поиском вершины усеченного ДД с маркировкой μ''

Усеченное ДД не всегда можно использовать для решения задач покрываемости и достижимости. Ранее уже обсуждалось, что решение указанных задач затруднено в случае, когда ДД содержит символ . Если дерево не содержит символ , то эти за

дачи успешно решаются. Пример: рисунок

Если проанализировать функционирование СП, то можно увидеть, что для получения маркировки (0, 14, 1, 7), необходимо выполнить следующую последовательность запусков: =(t1t1…t1) t2 (t3t3…t3). 21 раз 7 раз Таким образом =(0, 14, 1, 7) достижима из начальной маркировки, однако она не покрывается, так как после получения переход t1 запустить уже нельзя и фишки после дальнейшего запуска t3 лишь перераспределяются между p2и p4. Обе задачи решить по усеченному ДД затруднительно, так как оно не дает информации о соотношении фишек в p2 и p4.

50. Анализ свойств сетей на основе использования матричного подхода: матрицы D-, D+, пример построения матриц для сети Петри.

Один из подходов к анализу свойств СП основан на матричном представлении сетей, в соответствии с которым сеть представляется четверкой:
С=(P, T, D–,D+), где Р – множество позиций , |P| = п; T – множество переходов, |T|=т; D–– матрица, описывающая входную функцию, D–[j,i]=#(pi, I(tj)); D+– матрица, описывающая выходную функцию, D+[j,i]=#(pi, O(tj)).

D^–: Первая строка отвечает за переход t₁. Первые три элемента в строке равны 1, так как из позиций p₁, p₂, p₃ идут дуги к переходу t₁.

51.Составная матрица изменений (матрица инцидентности). Пример. Замечания по применению матричного подхода.

Рассмотрим m-мерный булев вектор е[j].Например, для перехода t2, если m=5, то e[j]=(0, 1, 0, 0, 0). Переход tjв маркировке μ разрешен, если μе[j]D–. Результат запуска tj в μ: δ(μ, tj)= μ'=μ-е[j]D–+е[j]D+. Вынесем е[j] за скобку: δ(μ, tj)=μ'=μ+е[j]D, где D=-D–+D+
Замечания по применению матричного подхода 1) Переходы, имеющие как входы, так и выходы из одной позиции (петли), представляются соответствующими элементами матриц D- и D+, но затем взаимно уничтожаются в матрице D=D+-D-. 2) При вычислении матрицы D, если СП содержит петли, теряется информация о кратности дуг.

52.Решение задачи достижимости с помощью матричного подхода. Замечание. Пример.

Для данной СП С=(P, T, D^-, D⁺) требуется определить, достижима ли маркировка μ' из маркировки μ.

Если маркировка μ' достижима из μ, то существует последовательность (возможно пустая) запусков переходов σ, которая приводит из μ к μ'. Следовательно, f(σ) является целым неотрицательным решением следующего матричного уравнения относительно х: μ'=μ+xD,где x=f(σ)=(x₁, x₂, …, x_m), m=|T|.

Пример. Для D=ребуется определить, достижима ли маркировка μ'=(0, 1, 0) из μ=(0, 0, 2).

Для решения данной задачи воспользуемся уравнением μ'=μ+xD:

(0, 1, 0)=(0, 0, 2)+(x1, x2, x3)→→

Пусть x₁=x₃=1, тогда x₂=0. Таким образом, для получения μ' из μ требуется запустить по одному разу переходы t₁ и t₃, если это возможно.

Замечание. Существование целого неотрицательного решения уравнения μ'=μ+xD является необходимым, но не достаточным условиемnдля достижимости μ'.

В сети Петри (С, 0) допустима бесконечная последовательность запусков σ* тогда и только тогда, когда из μ₀ достижима маркировка μ, из которой допустима повторяющаяся последовательность σ*.

53.Решение задачи сохранения с помощью матричного подхода. Пример

СП является сохраняющей тогда и только тогда, когда существует такой положительный вектор W, что выполняется DW=0.

Пример: Дана СП. D=. Определить, является ли сеть сохраняющей по отношению к вектору.

Решим систему уравнений DW=0.

→→

Система имеет множество решений. Пусть w₂=3, тогда w₁=1, w₃=3/2. Таким образом, сеть является сохраняющей по отношению к вектору взвешивания W=(1, 3, 3/2).