МТУСИ
Методы анализа и синтеза сетей Петри
Дизайн И.. Гайдель 2007
Лекция 9
Дизайн И. Гайдель 2007
Тензорные методы анализа и синтеза СП-моделей сложных систем
Этап 4. Синтез СП-моделей. Программы синтеза СП-моделей
В качестве исходных данных для выполнения процедуры синтеза СП- моделей выберем примитивную систему NPR, состоящую из m переходов, а
также операции объединения вершин.
Поставим в соответствие примитивной системе |
NPR |
некоторую |
последовательность V (VT + VP), состоящую из (m + n) элементов. Данная последовательность будет задавать некоторую программу построения (синтеза) новой СП-модели.
1 2 |
m 1 2 |
|
|
|
n |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
VT VP
Дизайн И. Гайдель 2007
Тензорные методы анализа и синтеза СП-моделей сложных систем
Этап 4. Синтез СП-моделей. Программы синтеза СП-моделей
При выполнении операции объединения вершин элементы последовательности V должны содержать следующую информацию:
во-первых, участвует ли данная вершина в процессе объединения; во-вторых, какому объединяемому подмножеству должна принадлежать
данная вершина.
Пусть каждый элемент последовательности меняется в пределах от 1 до r, где
r - определяет максимальное число |
|
подмножеств объединяемых вершин, на |
|||||||
которое может быть разделено множество переходов или множество позиций. |
|||||||||
Определим величину r |
следующим образом: |
||||||||
для множества позиций: |
|
|
|
|
|
||||
rp = │P│/2 ; |
|
|
|
|
|
|
|
|
|
для множества переходов: |
− |
|
|||||||
( T│−│1)/2если, |
│ |
|
T |
|
нечетно |
||||
rt = │ │ |
T /2 , |
если │ │ |
|
|
|||||
|
|
|
T |
|
− |
четно |
|||
|
|
|
|
│ |
|
|
|||
Дизайн И. Гайдель 2007
Тензорные методы анализа и синтеза СП-моделей сложных систем
Этап 4. Синтез СП-моделей. Программы синтеза СП-моделей
Пусть части VT или VP последовательности V представляют собой числа разрядности m = │T│ и n = │P│ в системах счисления rt и rp, соответственно. Тогда разряды данных чисел будут содержать информацию как об участии вершины СП NPR в процессе объединения (значение соответствующего разряда больше нуля), так и о том, какому объединяемому подмножеству данная вершина принадлежит (элементы частей VT или VP , которым соответствуют вершины, входящие в одно объединяемое подмножество, имеют одинаковые значения).
Дизайн И. Гайдель 2007
Тензорные методы анализа и синтеза СП-моделей сложных систем
Этап 4. Синтез СП-моделей. Программы синтеза СП-моделей
В итоге значения элементов последовательности V задают комбинацию, определяющую программу синтеза СП-модели. Отсюда алгоритм, генерирующий подмножества объединяемых вершин на множестве переходов и множестве позиций, представляет собой алгоритм синтеза комбинаций V , состоящих из двух чисел:
VT - имеющее разрядность m в системе счисления rt, VP - имеющее разрядность n в системе счисления rp.
Иначе: алгоритм генерации программ синтеза СП-моделей можно представить как работу счетчика V, состоящего из двух частей VT и VP , каждая их которых считает в своей системе счисления (rt для VT и rp для VP ).
Дизайн И. Гайдель 2007
Тензорные методы анализа и синтеза СП-моделей сложных систем
Этап 4. Синтез СП-моделей. Программы синтеза СП-моделей. Пример.
Пусть m = 4, тогда rt = 2.
Все возможные комбинации объединения переходов можно описать двумя символами (rt = 2) 1 и 2.
Учитывая наличие значения 0, мы получаем троичную систему счисления.
В этом случае для описания объединяемых переходов (объединяемых подмножеств) требуется три символа 1, 2 и 3. Учитывая 0, получаем четырехичную систему счисления.
Дизайн И. Гайдель 2007
Тензорные методы анализа и синтеза СП-моделей сложных систем
Этап 4. Синтез СП-моделей. Эквивалентные СП-модели
Среди комбинаций, генерируемых описанным алгоритмом, существуют такие, которые задают программы синтеза эквивалентных СП-моделей. Для определения таких комбинаций рассмотрим следующие свойства последовательности V .
Свойство 1. Комбинация V , содержащая лишь |
один |
положительный элемент отличный от остальных в части VT |
или в |
части VP, описывает эквивалентную СП-модель. |
|
Свойство 2. Если существует некоторая подстановка X с областью определения {1,2,..., rt} или некоторая подстановка Y с областью определения {1,2,...,rp}, которые переводят комбинацию V в комбинацию V' : VT VT' или VP VP' ,
то комбинация V описывает программу синтеза эквивалентной СП- модели. 
Дизайн И. Гайдель 2007
Тензорные методы анализа и синтеза СП-моделей сложных систем
Этап 4. Синтез СП-моделей.
Множество СП-моделей при m=2
Дизайн И. Гайдель 2007
а)
б)
Тензорные методы анализа и синтеза СП-моделей сложных систем
Этап 4. Синтез СП-моделей. Примеры
в) |
|
t1 |
t2 |
p1 |
p2 |
p3 |
p4 |
|
|
|
|
|
|
|
|
|
а) |
1 |
1 |
1 |
0 |
1 |
0 |
|
б) |
0 |
0 |
1 |
0 |
1 |
0 |
|
в) |
0 |
0 |
0 |
1 |
1 |
1 |
г) |
г) |
1 |
1 |
1 |
1 |
1 |
1 |
Дизайн И. Гайдель 2007
Тензорные методы анализа и синтеза СП-моделей сложных систем
Этап 4. Синтез СП-моделей. Редукция СП-моделей
Алгоритмы оценки интерпретирующих СП имеют экспоненциальную сложность от числа вершин СП-модели. Поэтому при анализе СП-моделей актуальным является вопрос сокращения числа вершин.
Сокращение числа вершин СП-моделей (редукция) должно проводиться таким
образом, |
чтобы язык, порождаемый |
измененной |
СП-моделью, |
являлся |
изоморфным языку исходной СП-модели. |
|
|
|
|
Изоморфизм (от др.-греч. ἴσος — «равный, |
одинаковый, |
подобный» |
и μορφή — |
|
|
́ |
|
|
|
«форма») — это очень общее понятие, которое определяется по-разному в различных
разделах математики. Изоморфизм определяется для |
множеств, наделённых |
некоторой структурой (например, для групп, колец, линейных |
пространств и т. п.). В |
общих чертах изоморфизм можно описать так: это обратимое отображение (биекция) между двумя множествами, наделёнными структурой, с сохранением этой структуры. Если между такими структурами существует изоморфизм, то они называются изоморфными. Изоморфизм всегда задаёт отношение эквивалентности на классе таких структур.