МОТС 30 вариант Первая часть

		0	1			0	0
	7			5	0		4
	3					5
		4					9	1
	2		3				3		0
	6	3
					4
						5	6

		0	1	8		0	0
	7			5	0		4
	3					5
	1	0					1
		4					9	1
	2		3				3		0
	6	3		1	0	0		0	0
					4		4		0
						5	6	8

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

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

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

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

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

μ₁ = 2 ; μ₂ =1; μ₃ =3

μ⁰ = [2 1 3]

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

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

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

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

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

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

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

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

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

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

- переход t₁:

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

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

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

переход t₂:

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

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

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

- переход t₃ :

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

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

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

- переход t₄ :

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

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

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

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

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

t₁

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

[0 0 4] = [(– x₂ -2x₄)(x₂)(x₁ + x₃)]

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

одно из решений x₁ = 4; x₂=0; x₃ =0; x₄=0

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

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 = 7. Определим количество входов СА: p ≥ log2 4, принимаем р = 2. Количество выходов СА: e ≥ log2 3, принимаем е =2. Количество элементов памяти, т.е. необходимое количество D-триггеров: z ≥ log2 7, принимаем z = 3.

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

	1
	0

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

	0	0
	0	1
	1	0
	1	1