Kursovaja_po_MOTS_19

		7	4	3
	-7		5		2
	-4	-5		0		3	1			5
	-3		0				1	2
		-2				1			1
			-3		-1				0	4
			-1	-1				0		2
				-2			0			2
					-1	0				1
			-5			-4	-2	-2	-1

Дуговые потоки:

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

d=7*5+4*6+3*3+5*2+2*7+3*5+1*1+5*4+1*7+2*2+1*5+1*6+4*3+2*6+2*8+1*5=195

ЗАДАНИЕ 3. АНАЛИЗ СЕТЕЙ ПЕТРИ

μ₁ = 0 ; μ₂ =3; μ₃ =1; μ₄ = 2; μ₅ = 1;

μ⁰ = [0 3 1 2 1]

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

Аналитический способ

P= {p₁ p₂ p₃ p₄ p₅} – множество позиций

T = {t₁ t₂ t₃ } – множество переходов

F(t₁) = {p₄} H(t₁) = { p₁ p₂ }

F(t₂) = {p₁ p₅} H(t₂) = { p₃ }

F(t₃) = {p₂ p₃} H(t₃) = {p₄ p₅}

Матричный способ

2. Проверим условия срабатывания переходов

- переход t₁:

Переход разрешен.

Новая маркировка:

µ ^{/ Т}= [0 3 1 2 1 ]+[1 0 0 ]D=[0 3 1 2 1 ]+[1 1 0 -1 0 ]=[1 4 1 1 1 ]

переход t₂:

Переход запрещён.

- переход t₃ :

Переход разрешен.

Новая маркировка:

µ ^{/ Т}= [0 3 1 2 1 ]+[0 0 1 ]D=[0 3 1 2 1 ]+[0 -1 -1 1 1 ]=[0 2 0 3 2 ];

3. Построим дерево достижимости:

t₁

4. Исследуем задачу достижимости для сети Петри, с начальной маркировкой [03121] для маркировки [14111]

Уравнение µ^/T = µ₀^T + x^T D принимает вид:

[110-10] = [(x₁ –x₂)(x₁ –x₃)(x₂ –x₃) (-x₁ +x₃) (-x₂ +x₃)]

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

одно из решений x₁ = 2; x₂=1; x₃ =1;

Маркировка достижима и для ее достижения необходимо чтобы переход t₁ сработал 2 раза; переход t_{2 ,} - 1 раз ; t₃- 1 раз.

ЗАДАНИЕ 4. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ И ТЕОРИИ АВТОМАТОВ.

Конечный автомат задан графом, определенным в задаче 1 контрольной работы № 1. Вершины графа отожествляются с состояниями автомата таким образом, что множество состояний Q = {q₁, q₂ ,…, q_n}. Переход автомата из одного состояния в другое осуществляется под воздействием множества входных сигналов X={x₁, x₂, x₃, x₄}. Переходы определяются законом отображения Г вершин графа, причем каждому переходу соответствует только одна из букв множества X. При задании графа эти буквы расставим произвольно.

Автомат позволяет вырабатывать выходные сигналы Y={y₁, y₂, y₃}:

y₁ – переход из состояния q_i в состояние q_i (петля);

y₂ – переход из состояния q_i в q_j при i<j;

y₃ – переход из состояния q_i в q_j при i>j.

Таблица переходов:

	-	-
			-	-	-	-
		-	-	-	-	-
	-					-

Количество букв входного алфавита АА п=4, количество букв выходного алфавита m = 3, количество состояний r = 5. Определим количество входов СА: p ≥ log2 4, принимаем р = 2. Количество выходов СА: e ≥ log2 2, принимаем е =1. Количество элементов памяти, т.е. необходимое количество T-триггеров: z ≥ log2 6, принимаем z = 3.

Осуществим кодирование входного и выходного алфавитов структурного автомата:

	1	0	1
	0	0	0
	0	0	1
	0	1	0
	1	0	0
	0	1	1

	0
	1

	0	0
	0	1
	1	0
	1	1

Обобщенная таблица переходов и выходов абстрактного автомата:

	101	000	001	010	100	011
00	-	-	000/01	001/01	011/00	100/01
01	000/00	001/00	-	-	-	-
10	011/00	-	-	-	-	-
11	-	101/01	010/00	100/00	010/01	-

Обобщенная таблица функционирования СА:

0	0	1	0	1	*	*	*	*	*	*	*
0	1	1	0	1	0	1	1	0	1	1	1
1	0	1	0	1	*	*	*	*	*	*	*
1	1	1	0	1	0	0	0	0	1	0	0
0	0	0	0	0	1	0	1	1	1	0	1
0	1	0	0	0	0	0	1	0	0	0	1
1	0	0	0	0	*	*	*	*	*	*	*
1	1	0	0	0	*	*	*	*	*	*	*
0	0	0	0	1	*	*	*	*	*	*	*
0	1	0	0	1	*	*	*	*	*	*	*
1	0	0	0	1	0	1	0	0	0	1	0
1	1	0	0	1	0	0	0	1	0	0	0
0	0	0	1	0	1	0	0	0	1	1	0
0	1	0	1	0	0	0	1	1	0	1	1
1	0	0	1	0	*	*	*	*	*	*	*
1	1	0	1	0	*	*	*	*	*	*	*
0	0	1	0	0	0	1	1	0	1	1	1
0	1	1	0	0	*	*	*	*	*	*	*
1	0	1	0	0	0	1	0	1	1	1	0
1	1	1	0	0	*	*	*	*	*	*	*
0	0	0	1	1	*	*	*	*	*	*	*
0	1	0	1	1	*	*	*	*	*	*	*
1	0	0	1	1	1	0	0	1	1	1	0
1	1	0	1	1	*	*	*	*	*	*	*