TVPS_posobie_13_06_2013

1.11.Упражнения

Упражнение 1

Орграф G=(S, V), где S-множество вершин, а V-множество дуг, задан списком дуг. Орграф G=(S, V) интерпретирует асинхронный процесс P=<S, F, I, R>.

Указать два способа назначения множества инициаторов I и множества результантов R. В одном из случаев, если возможно, получить простой асинхронный процесс. Установить в каждом случае, является ли процесс простым, эффективным, управляемым; ответ пояснить. Информация о дугах (Vi, Vj) графа G содержится в таблице, представленной ниже (по столбцам).

Вариант

1	2	3	4	5	6	7	8	9	10
1,3	1,3	1,4	1,4	1,2	1,3	1,2	1,4	1,4	1,3
1,4	2,3	2,4	2,4	2,3	2,4	1,3	1,5	2,4	1,4
2,4	2,4	2,5	3,5	3,1	3,5	2,4	2,3	2,7	2,5
2,5	3,6	4,3	3,6	3,4	3,6	3,4	2,4	3,5	2,6
3,8	3,8	4,6	4,5	4,5	4,7	4,5	2,6	3,6	4,7
4,6	4,5	5,6	4,1	6,5	5,1	5,6	3,6	3,9	5,8
5,7	4,6	5,7	5,7	5,7	6,5	5,8	5,1	4,7	5,9
6,8	6,7	6,9	6,9	5,8	6,7	7,8	6,5	5,7	6,9
6,1	6,8	6,1	7,8	7,1	6,9	7,9	6,8	6,9	6,1
7,1	7,1	7,1	8,9	8,6	7,8	8,9	7,6	7,8	7,5
8,9	8,9	8,6	8,1	8,9	8,6	9,1	8,9	8,1	8,7
9,6	9,6	9,8	9,7	8,1	8,1	10,7	8,1	10,7	9,1
				Вариант
11	12	13	14	15	16	17	18	19	20
1,3	1,4	1,4	1,2	1,3	1,2	1,3	1,3	1,5	1,3
1,4	2,4	1,5	1,3	2,4	2,7	1,6	2,4	1,6	2,3
2,4	3,6	2,4	2,4	3,6	3,4	2,3	3,6	2,5	3,6
2,5	3,7	3,6	3,6	4,5	4,5	3,6	4,6	3,4	3,9
3,1	4,5	4,5	4,5	5,7	4,6	4,5	5,4	4,1	4,5
4,9	4,6	4,7	4,6	5,1	5,6	5,7	5,8	5,6	4,8
5,6	5,8	5,8	4,7	6,5	6,9	5,8	63	6,7	5,3
5.7	5,9	6,9	6,8	6,9	7,6	6,7	6,9	7,8	6,8
6,7	6,1	7,8	7,9	1,9	7,8	7,9	7,9	7,1	7,6
6,9	8,9	7,9	7,1	8,6	8,9	7,1	8,7	8,9	7,1
7,8	9,1	8,1	8,3	9,8	9,1	8,9	9,1	9,6	9,7
9,1	10,8	10,7	9,1	9,1	10,8	10,6	10,7	10,9	10,9

31

Вариант

21	22	23	24	25	26	27	28	29	30
1,2	1,2	1,2	1,2	1,3	1,2	1,2	1,3	1,2	1,2
1,5	2,3	1,3	2,3	2,3	2,3	1,3	2,4	1,5	2,5
2,3	2,4	2,5	3,4	3,4	3,5	2,4	3,5	2,3	3,6
3,4	3,5	3,2	3,6	4,8	3,7	3,5	3,6	3,8	3,7
4,5	4,5	3,4	4,8	4,9	3,8	4,6	4,7	4,9	4,2
4,6	4,7	5,6	5,6	5,6	4,3	5,7	5,6	5,6	4,3
6,7	4,8	5,7	6,3	6,4	5,4	6,7	5,8	6,7	5,3
6,9	5,6	6,7	7,4	7,6	6,2	6,8	7,1	7,3	5,8
7,8	5,9	7,8	7,1	8,6	6,7	7,8	8,9	7,1	6,8
7,9	6,1	7,9	8,7	8,9	7,8	8,1	9,7	8,4	7,9
7,1	9,6	8,1	8,9	8,1	8,9	9,8	9,1	8,1	9,1
9,1	10,9	9,6	9,7	10,9	8,1	10,9	10,8	9,8	10,7
				Вариант
31	32	33	34	35	36	37	38	39	40
1,2	1,2	1,2	1,4	1,3	1,4	1,3	1,3	1,2	1,4
2,4	2,3	1,7	2,3	2,4	2,5	2,4	2,3	2,3	2,4
2,5	3,6	2,5	2,6	3,7	3,5	3,4	3,4	2,5	3,5
2,6	3,7	3,5	3,4	4,6	3,1	3,5	3,8	3,4	4,6
3,4	3,1	4,6	4,5	5,6	4,2	3,1	3,9	4,5	4,1
4,2	4,5	4,1	5,6	5,1	4,6	4,5	4,5	5,6	5,7
5,6	5,3	5,6	6,7	6,9	5,6	5,8	5,1	6,1	6,1
6,7	5,9	6,7	6,8	7,6	6,7	6,7	6,7	7,8	7,1
6,1	6,7	6,8	7,8	7,1	6,8	7,5	7,1	8,3	3,9
7,8	7,8	7,8	7,9	8,6	8,9	7,1	8,9	9,3	9,7
7,1	8,6	8,9	8,9	9,8	9,6	8,9	9,5	9,4	10,8
10,6	8,1	9,7	9,6	9,1	10,9	9,5	10,6	10,5	10,9

Упражнение 2

Построить полумодулярную диаграмму переходов с числом вершин n (каждую ситуацию описывает булев набор длины k).

a) 2< n <5, k=2; б) 6< n <9, k=3; в) 9< n <17, k=4.

Упражнение 3

Построить полумодулярную диаграмму переходов с числом вершин 6 (каждую ситуацию описывает булев набор длины 3) и выполнить редукцию по входному множеству X*={00, 01}.

32

Вопросы для самоконтроля

1.Дайте определение динамической системы, используя термины «ситуация» и «процесс».

2.В чем особенность дискретных динамических систем (ДДС)? Приведите примеры ДДС.

3.Что такое такт для ДДС?

4.Дайте определение дискретной информации.

5.Что такое асинхронный процесс?

6.Поясните термины «инициаторы» и «результанты».

7.Понятие асинхронного процесса задается с помощью отношения непосредственного следования F. Поясните смысл слова «непосредственного».

8.Что такое траектория АП?

9.Чем отличается от F отношение M?

10.Дайте определение отношения эквивалентности E.

11.Какой АП называется эффективным? Изобразите с помощью графа такой процесс.

12.Какой АП называется управляемым? Изобразите с помощью графа управляемый и неуправляемый АП.

13.Дайте определение перехода.

14.Какой АП называется простым?

15.Для чего используется репозиция АП?

16.Какой класс АП используется для моделирования конвейерной обработки информации?

17.Для чего используется редукция АП?

18.Какими способами можно выполнить структурирование ситуаций АП?

19.Дайте определение ДП.

20.В каком случае компонента ситуации АП называется возбужденной, а в каком устойчивой?

33

21.В чем смысл функционирования ДП?

22.Когда ситуация ДП является конфликтной? Приведите пример.

23.Постройте ДП, ситуации которой представлены в виде векторов размерности 4. Выделите возбужденные компоненты ситуаций с помощью символа «*». Проверьте полученную ДП на полумодулярность.

24.В чем суть редукции ДП?

34

2.Сети Петри

В основу данного раздела положены материалы из книг Дж. Питерсона «Теория сетей Петри и моделирование систем» [5] и В. Е. Котова «Сети Петри» [3], дополненные и переработанные авторами.

2.1.Введение в теорию комплектов

Втеории сетей Петри, моделирующих динамические свойства параллельных вычислительных систем, используется понятие комплекта. Теория комплектов является естественным расширением теории множеств; комплект, подобно множеству, есть набор элементов из некоторой конечной области D, но, в отличие от множества, комплекты допускают присутствие нескольких экземпляров одного и того же элемента.

Втеории множеств основным понятием является отношение включения . Это отношение связывает элементы и множества и определяет, какие элементы являются членами каких множеств. В теории комплектов основным понятием является функция числа экземпляров. Обозначим число экземпляров элемента х в комплекте #(x, B) (читается «число x в комплекте B»).

Синонимом термина «комплект» является термин «мультимножество».

Если мы ограничим число экземпляров каждого элемента в комплекте так, что 0 #(x, B) 1, то комплект совпадает с множеством.

Свойства комплектов

Определим область D как конечное множество элементов, из которых составляются комплекты.

Пусть х некоторый элемент из области D, B комплект, все элементы которого принадлежат области D.

Очевидно, что для всех х и B: #(х, В) 0.

35

Если #(х, В)>0, то есть элемент х является членом комплекта В, то это обозначается так: х B.

Если #(х, В)=0, то есть элемент х не является членом комплекта В, то это обозначается так: х В.

Пустой комплект обозначается так: .

Мощность |B| комплекта В есть общее число экземпляров в комплекте:

Комплект A есть подкомплект комплекта В (обозначение: A B), если #(х, A) #(х, В) для всех х B. Из A B следует: |A| |B|. Комплект А строго включен в комплект В (обозначение: А В), если А В и А В.

Два комплекта A	и	В равны	(обозначение: А=В),	если
#(х, А)=#(х, В) для всех х	D.
Нетрудно видеть, что A=B тогда и только тогда, когда A				B и
В А. Из A=B следует: |A|=|B|.
Операции над комплектами
Пусть А и В – комплекты. Определим для них операции:
объединение комплектов А		В: #(х, А	В)=max(#(х, А), #(х, B));
пересечение комплектов А		В: #(х, А	В)=min(#(х, А), #(х, B));

сумма комплектов А+В: #(х, А+В)=#(х, А)+#(х, B);

разность комплектов А-В:

#(х, A)-#(х, В), если #(х, А) #(х, В),

#(x, A-B)=

0, если #(х, А)<#(х, В)

Нетрудно видеть, что

А ВА В; А-ВА+В

36

Различие между объединением и суммой комплектов очевидно. В частности,

|А В| |A|+|B|; |А+В|=|A|+|B|.

Пример 15. Для комплектов А={а, а, с} и В={а, b, b, с, с, с} имеем:

|А| = 3; |B| = 6;

A B={а, a, b, b, c, с, с}; А+B={a, a, a, b, b, c, c, c, c}; A B={a, c}; А-В={а}; В-А={b, b, с, с}.

Пространство комплектов

Определение. Пространство комплектов Dn есть множество всех таких комплектов, что элементы их принадлежат D, и ни один элемент не входит в комплект более п раз.

Таким образом, для любого комплекта В Dn имеем: 1) если х В, то х D,

2) для х В: #(х, В) n.

Множество D есть множество всех комплектов над областью D без каких-либо ограничений на число экземпляров элемента в комплекте.

Если D={d1, d2, ..., dm}, то существует естественное соответствие между каждым комплектом B над D и m-мерным вектором f=(f1, f2, ..., fm) по правилу fi=#(di, B). Это соответствие называется

отображением Париха.

Пример 16. Пусть D={d1, d2, ..., d7}. B={d1, d2, d2, d2, d2, d7}, то есть #(d1, B)=1; #(d2, B)=4; #(d3, B)=0;…; #(d7, B)=1; тогда

отображение Париха: YB=(1, 4, 0, 0, 0, 0, 1).

37

2.2.Основные понятия теории сетей Петри

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

Далее будут рассмотрены сети Петри (СП) как модельная интерпретация АП.

Основы теории СП были опубликованы в 1962 году в диссертационной работе Карла Адама Петри. Он предложил модель описания потоков событий. Событие в данном случае может быть интерпретировано как изменение какой-либо компоненты ситуации АП.

Итак, СП – это модель описания потоков событий. Связь между событиями выражается с помощью некоторого числа условий, каждое из которых может принимать два значения «условие выполнено» и «условие не выполнено». Согласно Петри, событие может наступить, если выполнены все условия, от которых зависит его наступление, а если событие наступило, то изменяются значения некоторого числа условий.

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

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

38

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

маркировано или размечено.

Рис. 19. Пример сети Петри

Кратные входы в переход указываются кратными дугами из входных позиций в этот переход. Кратные выходы для перехода также указываются кратными дугами.

2.3.Структура сети Петри

Определение. Сеть Петри это четверка С=(P, T, I, O),

где Р={p1, p2, ..., pn} – конечное множество условий (позиций), |P|=n, n≥0;

Т={t1, t2, ..., tm} – конечное множество событий (переходов), |Т|=m, m≥0;

I: T Р– входная функция – отображение переходов в комплекты входных позиций, I(tj) интерпретируется как комплект входных позиций для перехода tj;

О: T Р – выходная функция – отображение переходов в комплекты выходных позиций, О(tj) интерпретируется аналогично.

39

Пример 17. Для СП, изображенной на рис. 19, структура имеет следующий вид:

P={p1, p2, p3}, T={t1, t2, t3, t4},

I(t1)={p1}, I(t2)={p1}, I(t3)={p1},

I(t4)={ p2, p2, p2, p3},

O(t1)={p2}, O(t2)={p2}, O(t3)={p3},

O(t4)=Ø.

Кратность входной позиции pi для перехода tj есть число появлений позиции во входном комплекте перехода #(pi, I(tj)). Аналогично кратность выходной позиции рi для перехода tj есть число появлений позиции в выходном комплекте перехода

#(рi, О(tj)). Если входная и выходная функции являются множествами (а не комплектами), то кратность каждой позиции есть либо 0, либо 1.

Для описания функционирования сети Петри необходимо уточнение понятия сети Петри в частности, требуется понятие маркировки, о котором говорилось выше.

Определение. Маркировкой сети Петри С=(P, T, I, O)

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

: P N0.

Если (pi)=0 (нет фишек), то говорят, что условие pi не выполнено; если (pi)=1, то условие выполнено; если (pi)=n>1 (n фишек), то условие выполнено с n-кратным запасом.

40