Элементы теории графов. Сеть Петри. Конечный автомат

Определение исходного графа графическим, матричным и аналитическим способами. Установление центров и периферийных вершин. Задача о максимальном потоке и потоке минимальной стоимости. Анализ сетей Петри. Элементы математической логики и теории автоматов.

Рубрика Программирование, компьютеры и кибернетика
Вид контрольная работа
Язык русский
Дата добавления 11.10.2013
Размер файла 991,7 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru

Вариант №8

Задача 1. Элементы теории графов

Связный ориентированный граф G(Х, Г) задан множеством вершин X={x1, x2, …, xn} и отображением Гxi={x|Ik|, x|Il|}, i =1, 2,…, n. Здесь i - текущий номер вершины, n- количество вершин графа. Значение индексов n, k и l взять из табл. 1 в соответствии с номером варианта. Индексы k и l формируют значения индексов , , … переменной x в отображении Гxi = {x , x , x,…}. Если значения индексов , , … переменной x не соответствуют ни одному из номеров вершин графа, то эта переменная не учитывается во множестве Гxi.

Выполнить следующие действия:

а) определить исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами;

б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов;

в) выделить в ориентированном графе два подграфа. Найти объединение, пересечение и разность подграфов;

г) описать систему уравнений, соответствующую сигнальному графу, считая, что передача между вершинами xi и xj

i*j при i j;

Kij =

1/(p+1) при i<j .

Найти передачу между вершинами x1 и xn, используя правило Мезона. Построить структуру кибернетической системы, определяемой топологией графа.

Таблица 1


варианта

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

N

5

5

5

5

5

5

5

5

5

6

6

6

6

6

6

K

2

3

4

1

1

1

3

5

2

4

2

3

4

5

6

L

1

1

1

2

3

4

2

1

3

3

1

1

1

1

1


варианта

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

N

6

6

6

6

6

6

6

6

6

7

7

7

7

7

7

K

1

1

1

1

3

2

5

5

2

3

4

5

6

5

3

L

2

3

4

5

2

3

2

3

3

2

3

2

1

3

5

Решение:

Множество вершин X = {x1, x2, x3, x4, x5}, n = 5, k = 5, l = 1. Гxi={x|Ik|, x|Il|}.

а) определим исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами:

Определим граф аналитическим способом:

Гx1 = { x4, x2 };

Гx2 = { x3, x1 };

Гx3 = { x2, x4 };

Гx4 = { x1, x5, x3};

Гx5 = {x4}.

Ориентированный граф графическим способом:

Неориентированный граф графическим способом:

Ориентированный граф матричным способом:

RG - матрица смежности

x1

x2

x3

x4

x5

x1

0

1

0

1

0

x2

1

0

1

0

0

x3

0

1

0

1

0

x4

1

0

1

0

1

x5

0

0

0

1

0

AG - матрица инцидентности

v1

v2

v3

v4

v5

v6

v7

v8

v9

v10

x1

1

-1

0

0

0

0

0

0

1

-1

x2

-1

1

1

-1

0

0

0

0

0

0

x3

0

0

-1

1

1

-1

0

0

0

0

x4

0

0

0

0

-1

1

1

-1

-1

1

x5

0

0

0

0

0

0

-1

1

0

0

Неориентированный граф матричным способом:

RD - матрица смежности

x1

x2

x3

x4

x5

x1

0

2

0

2

0

x2

2

0

2

0

0

x3

0

2

0

2

0

x4

2

0

2

0

2

x5

0

0

0

2

0

AD - матрица инцидентности

v1

v2

v3

v4

v5

v6

v7

v8

v9

v10

x1

1

1

0

0

0

0

0

0

1

1

x2

1

1

1

1

0

0

0

0

0

0

x3

0

0

1

1

1

1

0

0

0

0

x4

0

0

0

0

1

1

1

1

1

1

x5

0

0

0

0

0

0

1

1

0

0

б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов:

- матрица отклонений; - вектор отклонения.

x1

x2

x3

x4

x5

x1

0

1

2

1

2

x2

1

0

1

2

3

x3

2

1

0

1

2

x4

1

2

1

0

1

x5

2

3

2

1

0

=>

Центры графа - это вершины с наименьшей удаленностью. Периферийные вершины - вершины с наибольшей удаленностью. В данном случае периферийными вершинами являются две вершины x2, x4, а центрами графа являются три вершины x1, x3, x5. Тогда радиус с(G) =2, а диаметр графа D(G) = 3.

в) выделим в ориентированном графе два подграфа и найдем объединение, пересечение и разность подграфов:

Выделяем два подграфа: G1 и G2

X1 - {x1, x2}, Г1х1 = { x2 }, Г1х2 = {x1},

X2 - {x1, x2, x3}, Г2х1 = {x2}, Г2х2 = {x3}, Г2х3 = {x2}.

Объединение графов:

,

, , , .

G

Пересечение ,

, , .

G

Разностью графов G1(X1, Г1) и G2(X2, Г2) называется граф , где - дополнение по отображению графа G2 до насыщенного.

, где

.

Он имеет вид

;, .

Граф имеет вид:

G

г) i*j при i j;

Kij = 1/(p+1) при i<j .

Сигнальный граф имеет вид

Система уравнений, соответствующая сигнальному графу имеет вид

x1 = 2 x2 + 4x4

x2 = x1 +6x3

x3 =x2 +12 x4

x4 = x1 +x3 +20x5

x5 =x4.

Определить передачу k15 по правилу Мезона. Формула Мезона имеет вид

PS - передача пути,

DS - алгебраическое дополнение,

D - определитель.

Пути из х1 в х5:

.

Контура:

;

; ;

; .

;

Пары несоприкасающихся контуров L1L3, L1L4, L2L4, L2L5.

Отсюда

(L1L3+ L1L4+ L2L4+ L2L5).

D1 = 1- L2

D2 = 1.

.

Структура кинематической системы представлена на рисунке

Задача 2. Задача о максимальном потоке и потоке минимальной стоимости

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

максимальный поток max транспортировки груза между указанной парой вершин, считая одну из них источником, а другую -- стоком.

стоимость доставки груза по путям, формирующим максимальный поток в сети.

Решение:

найдем максимальный поток max транспортировки груза между вершинами х1 и х8.

Первый шаг. 1. Находим какой-либо путь из х1 в х8 с положительной пропускной способностью.

Таблица 1

x1

x2(1)

x3(2)

x4(2)

x5(1)

x6(2)

x7(6)

x8(2)

x1

3-

15

x2

0+

4

7

18

2

9-

x3

0

5

x4

0

15

x5

0

0

10

4

x6

0

0

0

11

11

x7

0

3

x8

0+

0

0

0

В результате получен путь l1 = (x1,x2,x8). Элементы этого пути Cij помечаем знаком минус, а симметричные элементы Cji - знаком плюс.

Определяем пропускную способность найденного пути, которая равна наименьшей из пропускных способностей дуг:

Определяем остаточные пропускные способности дуг найденного пути и симметричных ему дуг. Для этого из элементов табл. 1 вычитаем C1, а к элементам прибавляем C1. В результате получим новую табл. 2 с измененными пропускными способностями.

Tаблица 2

x1

x2

x3

x4

x5(1)

x6(5)

x7(6)

x8(5)

x1

0

15-

x2

3

4

7

18

2

6

x3

0

5

x4

0

15

x5

0+

0

10

4-

x6

0

0

0

11

11

x7

0

3

x8

3

0+

0

0

Второй шаг. 1. Помечаем столбцы табл. 2, находим второй путь l2 = (x1, x5, x8) и расставляем знаки.

2. Пропускная способность пути l2

Изменим пропускные способности помеченных дуг на С2 в табл. 3.

Tаблица 3

x1

x2

x3

x4

x5(1)

x6(5)

x7(6)

x8(6)

x1

0

11-

x2

3

4

7

18

2

6

x3

0

5

x4

0

15

x5

4+

0

10-

0

x6

0

0

0+

11

11-

x7

0

3

x8

3

4

0+

0

Третий шаг. 1. Помечаем столбцы табл. 3, находим третий путь l3 = (x1, x5, x6, x8) и расставляем знаки.

2. Пропускная способность пути l2

Изменим пропускные способности помеченных дуг на С3 в табл. 4.

Tаблица 4

x1

x2

x3

x4

x5(1)

x6

x7

x8

x1

0

1

x2

3

4

7

18

2

6

x3

0

5

x4

0

15

x5

14

0

0

0

x6

0

0

10

11

1

x7

0

3

x8

3

4

10

0

Четвертый шаг. Просматривая строки, убеждаемся в том, что больше не существует ни одного пути с положительной пропускной способностью из вершины x1 в вершину x8. Подмножество R образуют помеченные вершины х1, х5, а подмножество - остальные непомеченные вершины х2, х3, х4, х6, х7, х8. Разрез с минимальной пропускной способностью образуют дуги, начальные вершины которых принадлежат подмножеству R, а конечные - . Таким образом, разрез с минимальной пропускной способностью . Удалив дуги этого разреза, блокируем все пути из источника в сток. Пропускная способность разреза

Заключительный шаг. Вычитая из элементов табл.1 соответствующие элементы табл.4, получим табл.5

Tаблица 5

x1

x2

x3

x4

x5

x6

x7

x8

x1

3

14

x2

-3

0

0

0

0

3

x3

0

0

x4

0

0

x5

-14

0

10

4

x6

0

0

-10

0

10

x7

0

0

x8

-3

-4

-10

0

Величина максимального потока равна сумме элементов x1-й строки табл. 5 или сумме элементов x8-го столбца

Максимальный поток равен .

положительные элементы табл.5 характеризуют величины дуговых потоков:

; ;; ; ;.

Стоимость доставки груза определяется по формуле:

.

.

.

Задача 3. Анализ сетей Петри

Сеть Петри задана графически (рис. 23…30). В табл. 1 в соответствии с вариантом и указанным номером рисунка приведены различные начальные маркировки сети.

Выполнить следующие действия:

Описать сеть аналитическим и матричным способами.

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

Построить дерево достижимости заданной сети.

Проверить, является ли достижимой одна из маркировок, получаемых на четвертом шаге построения дерева, составив и решив матричные уравнения.

Таблица 1

варианта

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

0

1

0

1

1

1

1

2

2

0

1

3

0

1

1

2

1

2

2

2

3

1

2

2

1

2

3

1

1

2

0

3

2

3

1

0

1

1

1

3

2

1

0

1

2

3

3

4

3

1

3

4

0

2

1

1

0

1

1

2

1

1

2

5

1

2

5

1

2

2

3

0

3

3

2

0

3

2

1

№ рисунка

Рис. 23

Рис. 27

Рис. 28

Рис. 29

Решение:

Опишем сеть аналитическим и матричным способами. Приведем графическое представление сети Петри, в которой позиции P = {p1, p2, p3, p4, p5} и переходы T = {t1, t2, t3, t4, t5}. Начальная маркировка сети обозначается вектором м0 [м1,м2,м3,м4,м5], м0 [2 2 3 1 0]. Отсюда получим:

При аналитическом способе задания сеть Петри задается как C = (P,T,F,H,м0), где, кроме множеств позиций Р и переходов Т, задаются входная F и выходная Н функции. Через F(tj) обозначается множество входных позиций, а через H(tj) - множество выходных позиций перехода tj; м0 - начальная маркировка сети.

F(t1) = {p1}, H(t1) = {p2, p3 },

F(t2) = {p2}, H(t2) = {p4},

F(t3) = {p3}, H(t3) = {p5 },

F(t4) = {p4, p5}, H(t4) = {p1},

F(t5) = {p4, p5}, H(t5) = {p2, p3}.

м0 [2 2 3 1 0]

Матричная форма определения сети Петри эквивалентна аналитическому способу задания C = (P,T,D-,D+,м0). Здесь D- и D+ - матрицы входных и выходных инциденций соответственно размером m Ч n, где m - число переходов и n - число позиций.

Элемент dij- матрицы D- равен кратности дуг, входящих в i-й переход из j-й позиции.

Элемент dij+ матрицы D+ равен кратности дуг, выходящих из i-ro перехода в j-ю позицию.

Для рассматриваемой сети Петри

Матрица D = D+ - D - называется матрицей инцидентности сети Петри,

2. Найдем переходы, которые разрешены при начальной маркировке м0 [2 2 3 1 0] сети Петри.

Переход t1

[м0] ? [10000]* D- = [10000] · ; [2 2 3 1 0] ? [1 0 0 0 0] - условие выполняется, переход разрешен.

Новая маркировка при срабатывании перехода t1 определяется следующим образом:

.

Переход t2

[м0] ? [01000]* D- = [01000] ; [2 2 3 1 0] ? [0 1 0 0 0] - условие выполняется, переход разрешен.

Новая маркировка при срабатывании перехода t2 определяется следующим образом:

.

Переход t3

[м0] ? [00100]* D- = [00100] ; [2 2 3 1 0] ? [0 0 1 0 0] - условие выполняется, переход разрешен.

Новая маркировка при срабатывании перехода t3 равна:

.

Переход t4

[м0] ? [00010]* D- = [00010] ; [2 2 3 1 0] ? [0 0 0 1 1] - условие не выполняется, переход запрещен.

Переход t5

[м0] ? [00001]* D- = [00001] ; [2 2 3 1 0] ? [0 0 0 1 1] - условие не выполняется, переход запрещен.

Построим дерево достижимости заданной сети.

Проверим, является ли достижимой одна из маркировок, полученных на пятом шаге построения дерева, составив и решив матричные уравнения.

Уравнение принимает вид

Перенесем в левую часть и выполним умножение, тогда

Приравняем составляющие векторов

Система имеет решение x1 = 0; x2 = 1; x3 = 2; x4 = 1; x5 = 1.

Это значит, что исследуемая маркировка достижима и в последовательности срабатываний переходы t2, t4, t5 срабатывают по одному разу, переход t3 срабатывает два раза, переход t1 не срабатывает ни разу.

Задача 4. Элементы математической логики и теории автоматов

граф сеть петри конечный

Конечный автомат задан графом, определенным в задаче 1 контрольной работы № 1. Вершины графа отождествляются с состояниями автомата таким образом, что множество состояний Q = {q1, q2 ,…, qn}. Переход автомата из одного состояния в другое осуществляется под воздействием множества входных сигналов X={x1, x2, x3, x4}. Переходы определяются законом отображения Г вершин графа, причем каждому переходу соответствует только одна из букв множества X. При задании графа эти буквы расставить произвольно.

Автомат позволяет вырабатывать выходные сигналы Y={y1, y2, y3}:

y1 - переход из состояния qi в состояние qi (петля);

y2 - переход из состояния qi в qj при i<j;

y3 - переход из состояния qi в qj при i>j.

Осуществить структурный синтез конечного автомата. Реализацию осуществить на элементах, указанных в табл. 1, в соответствии с номером варианта. Обязательной является минимизация реализуемых функций.

Таблица 1

№ варианта

1

2

3

4

5

6

7

8

9

10

Тип
элементов

И

НЕ

И

ИЛИ

НЕ

ИЛИ

НЕ

И

ИЛИ

НЕ

И

НЕ

ИЛИ

НЕ

ИЛИ

НЕ

И

ИЛИ

НЕ

И

НЕ

ИЛИ

НЕ

Тип
триггера

RS

JK

T

RS

JK

D

RS

T

D

RS

Решение:

Множество вершин X = {x1, x2, x3, x4, x5}.

Вершины графа отожествляются с состояниями автомата таким образом, что множество состояний Q = {q1, q2, q3, q4, q5}. Переход автомата из одного состояния в другое осуществляется под воздействием множества входных сигналов X={x1, x2, x3, x4}. Автомат позволяет вырабатывать выходные сигналы Y={y1, y2, y3}. Так как в графе нет петель, выходной сигнал y1 будет отсутствовать.

На основании аналитического описания ориентированного графа из задания № 1 запишем закон отображения состояний автомата:

Гq1 = { q2(x1/y2), q4(x2/y2)},

Гq2 = {q1(x3/y3), q3(x4/y2)},

Гq3 = {q2(x1/y3), q4(x2/y2)},

Гq4 = {q1(x3/y3), q5(x4/y2), q3(x1/y3)},

Гq5 = {q4(x2/y3)}.

Обобщенная таблица переходов и выходов соответствующего конечного автомата представлена в табл. 2.

Таблица 2

X

Q

q1

q2

q3

q4

q5

X1

q2/y2

-

q2/y3

q3/y3

-

X2

q4/y2

-

q4/y2

-

q4/y3

X3

-

q1/y3

-

q1/y3

-

X4

-

q3/y2

-

q5/y2

-

Осуществим структурный синтез автомата, заданного табл. 1. В качестве элементов памяти используем T-триггеры, в качестве элементной базы используем логические элементы И ИЛИ НЕ.

n = 4 p ? log2 n = log2 4 = 2;

m = 3 e ? log2 m = log2 3 = 2;

r = 5 z ? log2 r = log2 5 = 3.

Приступаем к кодированию:

u

u1

u2

x1

0

0

3

x2

0

1

3

x3

1

0

2

x4

1

1

2

v

y2

1

5

y3

0

5

q

w

w1

w2

w3

q1

1

0

0

2

q2

0

0

1

2

q3

0

1

0

2

q4

0

0

0

3

q5

1

1

0

1

На основании результатов кодирования строим обобщенную таблицу переходов и выходов структурного автомата (табл.3), заменяя состояния, входные и выходные переменные их кодами.

Таблица 3

u1u2

w1w2w3

100

001

010

000

110

00

001/1

-

001/0

010/0

-

01

000/1

-

000/1

-

000/0

10

-

100/0

-

100/0

-

11

-

010/1

-

110/1

-

Используя таблицу переходов T-триггера и данные предыдущей таблицы, составим обобщенную таблицу функционирования структурного автомата (табл.4). Функции возбуждения трех триггеров обозначены через T1, T2, T3 соответственно.

Таблица 4

u1

u2

w1(t)

w2(t)

w3(t)

w1

(t+1)

w2

(t+1)

w3

(t+1)

v

T1

T2

T3

0

0

1

0

0

0

0

1

1

1

0

1

0

1

1

0

0

0

0

0

1

1

0

0

1

0

1

0

0

*

*

*

*

*

*

*

1

1

1

0

0

*

*

*

*

*

*

*

0

0

0

0

1

*

*

*

*

*

*

*

0

1

0

0

1

*

*

*

*

*

*

*

1

0

0

0

1

1

0

0

0

1

0

1

1

1

0

0

1

0

1

0

1

0

1

1

0

0

0

1

0

0

0

1

0

0

1

1

0

1

0

1

0

0

0

0

1

0

1

0

1

0

0

1

0

*

*

*

*

*

*

*

1

1

0

1

0

*

*

*

*

*

*

*

0

0

0

0

0

0

1

0

0

0

1

0

0

1

0

0

0

*

*

*

*

*

*

*

1

0

0

0

0

1

0

0

0

1

0

0

1

1

0

0

0

1

1

0

1

1

1

0

0

0

1

1

0

*

*

*

*

*

*

*

0

1

1

1

0

0

0

0

0

1

1

0

1

0

1

1

0

*

*

*

*

*

*

*

1

1

1

1

0

*

*

*

*

*

*

*

По этой таблице запишем СДНФ выходной функции V и функций возбуждения триггеров T1, T2, T3, зависящих от набора переменных u1, u2, w1(t), w2(t), w3(t). В результате получим систему логических функций для построения комбинационной части автомата:

.

.

.

.

Минимизируем функции согласно картам Карно:

Функциональная схема структурного автомата:

Список используемой литературы

А.В. Павлова Контрольные задания по курсу “Математические основы теории систем”, для студентов специальности «Информационные технологии и управление в технических системах». Часть 1.- Мн.: 2006. - 17 с.

А.В. Павлова Математические основы теории систем: Конспект лекций для студентов специальности «Информационные технологии и управление в технических системах». Часть 1.- Мн.:БГУИР, 2004. - 84 с.

Размещено на Allbest.ru


Подобные документы

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

    курсовая работа [1,0 M], добавлен 17.11.2009

  • Методы разработки вычислительной структуры. Изучение методов использования иерархических сетей Петри, пути их практического применения при проектировании и анализе систем. Анализ полученной модели на активность, обратимость, конечность функционирования.

    лабораторная работа [36,8 K], добавлен 03.12.2009

  • Методы моделирования, отличные от инструментария "сети Петри". Пример моделирования стандартом IDEF0 процесса получения запроса браузером. Раскрашенные (цветные) сети Петри. Моделирование процессов игры стандартными средствами сетей Петри, ее программа.

    курсовая работа [1,6 M], добавлен 11.12.2012

  • Исследование методов моделирования, отличных от сетей Петри. Моделирование при помощи инструментария IDEF. Пример простейшей байесовской сети доверия. Анализ младшего разряда множителя. Сложение на сумматорах. Заполнение и анализ редактора сетей Петри.

    курсовая работа [2,6 M], добавлен 28.10.2013

  • Специфика построения и минимизации детерминированного автомата методом разбиения. Построение детерминированной сети Петри, моделирующей работу распознающего автомата. Особенности программной реализации праволинейной грамматики, построение ее графа.

    курсовая работа [615,1 K], добавлен 19.06.2012

  • Разработка и реализация графического редактора сетей Петри. Описание программы, которая позволяет создавать новые сети путем добавления позиций и переходов, соединяя их определенным образом. Основы построения систем автоматизационного проектирования.

    курсовая работа [2,6 M], добавлен 21.06.2011

  • Построение математической модели программы, одноленточного автомата над алфавитом, допускающего различные множества слов. Алфавит терминальных символов, множество состояний и переходов. Определение начального и конечного состояний. Понятие сети Петри.

    контрольная работа [294,8 K], добавлен 17.09.2013

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

    контрольная работа [268,5 K], добавлен 06.09.2011

  • Анализ инцидентов информационной безопасности. Структура и классификация систем обнаружения вторжений. Разработка и описание сетей Петри, моделирующих СОВ. Расчет времени реакции на атакующее воздействие. Верификация динамической модели обнаружения атак.

    дипломная работа [885,3 K], добавлен 17.07.2016

  • Алгоритмы, использующие решение дополнительных подзадач. Основные определения теории графов. Поиск пути между парой вершин невзвешенного графа. Пути минимальной длины во взвешенном графе. Понятие кратчайшего пути для графов с помощью алгоритма Флойда.

    реферат [39,6 K], добавлен 06.03.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.