Элементы теории графов. Сеть Петри. Конечный автомат
Вариант №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 с.
Похожие статьи
-
Сеть Петри это двудольный направленный граф с маркировкой, ребра которого задают причинно-следственные отношения "события-условия" и именуются дугами....
-
Граф переходов конечного автомата лексического анализатора Исходная КС-грамматика G({prog, end., if, else, then, begin, end, while, do, or, and, not,...
-
Некоторые сведения из теории графов - Алгоритмы нескольких махов
Приведенные ниже определения взяты из [1,2,7-9], теоремы из [6]. Граф, или обыкновенный граф G -- это упорядоченная пара G := (V, E), где V -- это...
-
Рассмотрим замкнутую сеть массового обслуживания с разнотипными заявками, которая является вероятностной моделью обслуживания заявок в УП "Проектный...
-
Теоретические аспекты поставленной задачи В этой части проекта будут объяснены этапы применения МКЭ для плоской фермы. В первой главе было рассмотрено...
-
Элементы самодвойственных сетей - Функциональные модели универсального нейрокомпьютера
Если при обратном функционировании самодвойственной сети на ее выход подать производные некоторой функции F по выходным сигналам сети, то в ходе...
-
Впервые последовательное описание конструирования нейронных с Етей из элементов было предложено в книге А. Н. Горбаня [65]. Однако за прошедшее время...
-
Наиболее распространенной реализацией МКЭ является метод прямой жесткости, применяемый для компьютерного моделирования сложных структур. Это матричный...
-
СЕТЬ ПЕТРИ, ТЕКСТ ПРОГРАММЫ - Теория вычислительных процессов
Начальная разметка сети: одна фишка в позиции S1. После завершения функционирования сети фишка будет в позиции S2 Расшифровка переходов: 1. T1 - push f...
-
Реализация программного обеспечения управляющего автомата
Реализация программного обеспечения управляющего автомата Задание По заданной граф-схеме алгоритма (рис. 1), реализовать на языке высокого уровня,...
-
Нахождение ожидаемых доходов в центральной системе Рассмотрим замкнутую сеть массового обслуживания с разнотипными заявками, которая является...
-
Ферменная конструкция представляет собой стержневую систему. При замене жестких узлов шарнирами, она остается геометрически неизменяемой и удовлетворяет...
-
Упорядоченное множество Наряду с понятием множества как совокупности элементов важным понятием является понятие упорядоченного множества или кортежа....
-
Графическое отображение нелокальной нейронной сети в системе "Эйдос" Математический метод СК-анализа в свете идей интервальной бутстрепной робастной...
-
Конечно-элементный анализ широко применяется при решении задач механики деформируемого твердого тела, теплообмена, гидро - и газодинамики, электро - и...
-
Для решения трехмерной задачи упругости с помощью метода конечных элементов были заданы следующие основные параметры: [1]. Количество секций. [2]....
-
Метод конечных элементов является численным методом для нахождения приближенных решений физических задач. В основе этого метода лежит разделение...
-
Итерационные алгоритмы разрезания графа на куски
Лекция Итерационные алгоритмы разрезания графа на куски Суть Итерационных Алгоритмов Разрезания Графов заключается в выборе первого случайного разрезания...
-
Расчет диаметра сети - Проектирование учебной локальной вычислительной сети
Методика определения диаметра сети может быть оформлена в виде таблицы. Номера строк и столбцов в ней соответствуют индиентификаторам рабочих станций на...
-
Фактически это означает, что в СТИ множество возможных состояний объекта рассматривается не как совокупность несвязанных друг с другом состояний, как в...
-
ЛВС должна обеспечивать скорость передачи данных при одновременной передаче всех узлов сети не менее 100 Мб/с. Техническое обеспечение сети должно иметь...
-
Из рисунка 2.1.2 и технического задания видно, что: Требуется обеспечить выходом в сеть все квартиры, в том числе беспроводным. Логичнее всего установить...
-
Для обеспечения функционирования локальной сети часто выделяется специальный компьютер - сервер, или несколько таких компьютеров. На дисках серверов...
-
Исходя из рисунка 2.1.1 и технического задания видно, что: - Требуется подключить три компьютера на три рабочих места в приемной; - Один компьютер...
-
С помощью диалоговых окон были отображены задания, их выбор, поля для ввода входных данных, заполняемые по умолчанию, полученный результат и визуализация...
-
Для реализации поставленной задачи методом конечных элементов будут использованы следующие программные обеспечения (ПО): - MATLAB - ПО и одноименный язык...
-
Известные в литературе нейронные сети, в отличие от предлагаемой семантической информационной модели и нелокальных нейронных сетей, не обеспечивают...
-
Рассмотрим особенности программирования под Android. Класс Activity - самый важный класс, из которого строится приложение Android. Этот класс...
-
Метод конечных элементов (МКЭ) жесткости возник в аэрокосмической отрасли. Исследователи рассматривали различные подходы к анализу сложных частей...
-
Дерево досяжності ССП - це граф, вершинами якого є реальні стани (маркування) мережі, які можуть бути досягнуті з кожного чергового реального стану...
-
Множество D с двумя заданными на нем операциями (плюс) и (умножение) называется диоидом, если выполнены следующие аксиомы: § Ассоциативность. §...
-
Конфиденциальность очень важна для некоторых организаций, так как то, что обычно считается безобидной информацией, может на самом деле содержать полезные...
-
Глоссарий - Поиск информации в сети Интернет
№ п/п Понятие Определение 1 Интернет Это глобальная компьютерная сеть, которая связывает между собой как пользователей компьютерных сетей, так и...
-
Основные требования к поиску - Поиск информации в сети Интернет
Поисковый система файл яндекс К результатам поиска предъявляются требования полноты охвата ресурсов, достоверности полученной информации, минимальных...
-
Рисунок 17. Cisco SB WAP121-E-K9-G5 1. Назначение 1. Точка доступа Cisco SB WAP121-E-K9-G5, предназначен для применения на сети связи общего пользования...
-
Требования к программному обеспечению системы На сетевом оборудовании должна функционировать межсетевая операционная система, причем ее версия должна...
-
Все IP-адреса в автономных системах имеют "серый" адрес, то есть адрес, которым нельзя воспользоваться для выхода в Интернет (классы таких адресов были...
-
Плановый срок начала работ по модернизации локальной вычислительной сети административного здания (корпус II) НГУ им. Н. И. Лобачевского - 7 февраля 2013...
-
Объектно-ориентированные СУБД Несмотря на большую популярность реляционных СУБД, развитие технологии появления данными на них не остановилось. Развитие...
-
Заключение - Исследование и модернизация локальной вычислительной сети
Осуществляя данный проект, удалось модернизировать и повысить эффективность существующей распределенной системы. Оптимальная архитектура ЛВС позволила...
Элементы теории графов. Сеть Петри. Конечный автомат