Referat.me
/ / Математические основы теории систем

Название: Математические основы теории систем

Вид работы: контрольная работа

Рубрика: Математика

Размер файла: 301.07 Kb

Скачать файл: referat.me-218869.docx

Краткое описание работы: Элементы теории графов. Центры и периферийные вершины графов, их радиусы и диаметры. Максимальный поток транспортировки груза и поток минимальной стоимости. Пропускная способность пути. Анализ сетей Петри, их описание аналитическим и матричным способами.

Математические основы теории систем

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

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

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

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

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

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

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

i*j при i ³ j ;

Kij =

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

Найти передачу между вершинами x 1 и 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 = { x 1 , x 2 ,x 3 , x 4 , x 5 , x 6 }, n = 6 k = 2, l = 1 Г xi ={ x | I ± k | ,x | I ± l | }.

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

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

Г x 1 = { x 1 , x 3 , x 2 };

Г x 2 = { x 4 , x 1 , x 3 };

Г x 3 = { x 1 , x 5 , x 2 , x 4 };

Г x 4 = { x 2 , x 6 , x 3 , x 5 };

Г x 5 = { x3 , x 4 , x 6 };

Г x 6 = { x4 ,x 5 }.

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

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

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

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

x1 x2 x3 x4 x5 x6
x1 1* 1 1 0 0 0
x2 1 0 1 1 0 0
x3 1 1 0 1 1 0
x4 0 1 1 0 1 1
x5 0 0 1 1 0 1
x6 0 0 0 1 1 0

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

v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 v17 v18 v19
x1 1* 1 -1 0 0 0 0 0 0 0 0 1 -1 0 0 0 0 0 0
x2 0 -1 1 1 -1 0 0 0 0 0 0 0 0 1 -1 0 0 0 0
x3 0 0 0 -1 1 1 -1 0 0 0 0 -1 1 0 0 1 -1 0 0
x4 0 0 0 0 0 -1 1 1 -1 0 0 0 0 -1 1 0 0 1 -1
x5 0 0 0 0 0 0 0 -1 1 1 -1 0 0 0 0 -1 1 0 0
x6 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 -1 1

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

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

x1 x2 x3 x4 x5 x6
x1 1* 2 2 0 0 0
x2 2 0 2 2 0 0
x3 2 2 0 2 2 0
x4 0 2 2 0 2 2
x5 0 0 2 2 0 2
x6 0 0 0 2 2 0

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

v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 v17 v18 v19
x1 1* 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0
x2 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0
x3 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0
x4 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1
x5 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0
x6 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1

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

- матрица отклонений имеет вид:

x1 x2 x3 x4 x5 x6
x1 1 1 1 2 2 3
x2 1 0 1 1 2 2
x3 1 1 0 1 1 2
x4 2 1 1 0 1 1
x5 2 2 1 1 0 1
x6 3 2 2 1 1 0

- вектор отклонения

=>

х2 , х3 , х4 , х5 - центры графа с наименьшей удаленностью. Радиус ρ (G) = 2.

Периферийными вершинами являются вершины х1 , х6 с наибольшей удаленностью. Диаметр графа D (G) = 3.

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

Выделяем два подграфа: G 1 и G 2

X 1 - { x 1 , x 2 }, Г1х1 = { x 1 , x 2 }, Г1х2 = { x 1 },

X 2 - { x 1 , x 2 , x 3 }, Г2х1 = { x 2 }, Г2х2 = { x 3 }, Г2х3 = { x 2 } .

Объединение ,

,, , .

G

Пересечение

,,, .

G

Разность

,

, , .

G

г) Считая, что передача между вершинами xi и xj

i*j при i ³ j ;

Kij =

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

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

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

x 1 = x 1 +2 x 2 +3 x 3

x 2 = x 1 +6 x 3 +8 x 4

x 3 = x 1 + x 2 +12 x 4 +15 x 5

x 4 = x 2 + x 3 +20 x 5 +24 x 6

x 5 = x 3 + x 4 +30 x 6

x 6 = x 4 + x 5

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

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

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

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

Пути из х1 в х6 и передаточные функции для каждого из них имеют вид:

Контура:

;

;;

;;

;;

;;

;;

;

;.

;.

Пары несоприкасающихся контуров

L 1 L 3 , L 1 L 4 , L 1 L 5 , L 1 L 6 , L 1 L 8 , L 1 L 9 , L 1 L 10 , L 1 L 13 , L 1 L 14 , L 1 L 15 , L 1 L 16 , L 1 L 17 , L 1 L 18 ;

L 2 L 4 , L 2 L 5 , L 2 L 6 , L 2 L 8 , L 2 L 9 , L 2 L 10 , L 2 L 15 , L 2 L 16 , L 2 L 17 , L 2 L 18 ;

L 3 L 5 , L 3 L 6 , L 3 L 10 , L 3 L 17 , L 3 L 18 ;

L 4 L 6 , L 5 L 7 ; L 5 L 11 , L 5 L 12 , L 6 L 7 , L 6 L 8 , L 6 L 11 , L 6 L 12 , L 6 L 13 , L 6 L 14 ;

L 7 L 8 , L 7 L 10 , L 7 L 17 , L 7 L 18 ;

L 8 L 9 , L 9 L 10 , L 10 L 11 , L 10 L 12 , L 11 L 17 , L 11 L 18 , L 12 L 17 , L 12 L 18 .

Независимые тройки

L 1 L 3 L 5 ,L 1 L 3 L 6 ,L 1 L 3 L 10 ,L 1 L 3 L 17 ,L 1 L 3 L 18 ,L 1 L 4 L 6 ,L 1 L 6 L 8 ,L 1 L 6 L 13 ,L 1 L 6 L 14 ,L 1 L 8 L 9, L 1 L9 L10 ,L2 L 4 L6 ,L2 L9 L10 ,L6 L7 L 8 .

Отсюда

D = 1 - ( L 1 +L 2 +L 3 +L 4 +L 5 + L 6 +L 7 +L 8 +L 9 +L 10 +L 11 +L 12 +

+ L 13 +L 14 + L 15 +L 16 + L 17 +L 18 )+ ( L 1 L 3 +L 1 L 4 +L 1 L 5 +L 1 L 6 +L 1 L 8 +L 1 L 9 +L 1 L 10 +L 1 L 13 +L 1 L 14 +L 1 L 15 +L 1 L 16 +L 1 L 17 +L 1 L 18 +L 2 L 4 +L 2 L 5 +L 2 L 6 +L 2 L 8 +L 2 L 9 +L 2 L 10 +L 2 L 15 +L 2 L 16 +L 2 L 17 +L 2 L 18 + L 3 L 5 +L 3 L 6 +L 3 L 10 +L 3 L 17 +L 3 L 18 L 4 L 6 +L 5 L 7 +L 5 L 11 +L 5 L 12 +L 6 L 7 +L 6 L 8 +L 6 L 11 +L 6 L 12 +L 6 L 13 +L 6 L 14 +L 7 L 8 +L 7 L 10 +L 7 L 17 +L 7 L 18 +L 8 L 9 +L 9 L 10 +L 10 L 11 +L 10 L 12 +L 11 L 17 +L 11 L 18 +L 12 L 17 +L 12 L 18 ) -

( L 1 L 3 L 5 +L 1 L 3 L 6 +L 1 L 3 L 10 +L 1 L 3 L 17 +L 1 L 3 L 18 +L 1 L 4 L 6 +L 1 L 6 L 8 +L 1 L 6 L 13 +L 1 L 6 L 14 +L 1 L 8 L 9 +L 1 L 9 L 10 +L 2 L 4 L 6 +L 2 L 9 L 10 +L 6 L 7 L 8 ) .

D 1 = 1- L 8 ;

D 2 = 1;

D 3 = 1;

D 4 = 1 - L 9 ;

D 5 = 1;

D 6 = 1.

.

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


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

Транспортная сеть задана в виде ориентированного графа, приведенного на рисунке.

На каждом из ребер проставлены значения пропускной способности С (n ) ребра n .

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

Решение:

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

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

Tаблица 1.

x1 x2 (1) x3 (1) x4 (1) x5 ( 2) x6 ( 3) x7 ( 3) x8 (2) x9 (6)
x1 7 9- 4
x2 0 8 3 6
x3 0+ 5 8- 4
x4 0 0 0 9 2
x5 0 2
x6 0+ 5 3-
x7 0 0 0 7 6
x8 0 0 0 0 8
x9 0+ 0 0

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

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

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

Tаблица 2

x1 x2 (1) x3 (1) x4 (1) x5 ( 2) x6 ( 3) x7 ( 3) x8 (2) x9 (7)
x1 7 6- 4
x2 0 8 3 6
x3 3+ 5 5 4-
x4 0 0 0 9 2
x5 0 2
x6 3 5 0
x7 0+ 0 0 7 6-
x8 0 0 0 0 8
x9 3 0+ 0

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

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

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

Tаблица 3

x1 x2 (1) x3 (1) x4 (1) x5 ( 2) x6 ( 3) x7 ( 4) x8 (2) x9 (7)
x1 7 2 4-
x2 0 8 3 6
x3 7 5 5 0
x4 0+ 0 0 9- 2
x5 0 2
x6 3 5 0
x7 4 0+ 0 7 2-
x8 0 0 0 0 8
x9 3 4+ 0

Третий шаг.1. Пометив столбцы, находим l3 = (x1 , х4 , х7 ,x9 ) .

Величина потока по пути l3

Вычислив новые пропускные способности дуг, приходим к табл.4.

Таблица 4

x1 x2 (1) x3 (1) x4 (1) x5 ( 2) x6 ( 3) x7 ( 4) x8 (2) x9 (8)
x1 7- 2 2
x2 0+ 8 3 6-
x3 7 5 5 0
x4 2 0 0 7 2
x5 0 2
x6 3 5 0
x7 4 2 0 7 0
x8 0+ 0 0 0 8-
x9 3 6 0+

Четвертый шаг.1. Помечаем столбцы табл.4, находим четвертый путь l4 = (x1 , х2 , х8 , х9 ) и расставляем знаки.

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

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

Таблица 5

x1 x2 (1) x3 (1) x4 (1) x5 ( 2) x6 ( 3) x7 ( 4) x8 (4) x9 (8)
x1 1 2 2-
x2 6 8 3 0
x3 7 5 5 0
x4 2+ 0 0 7 2-
x5 0 2
x6 3 5 0
x7 4 2 0 7 0
x8 6 0+ 0 0 2-
x9 3 6 6+

Пятый шаг.1. Помечаем столбцы табл.5, находим четвертый путь l5 = (x1 , х4 , х8 , х9 ) и расставляем знаки.

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

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


Таблица 6

x1 x2 (1) x3 (1) x4 (1) x5 ( 2) x6 ( 3) x7 ( 4) x8 (5) x9
x1 1 2 0
x2 6 8 3 0
x3 7 5 5 0
x4 4 0 0 7 0
x5 0 2
x6 3 5 0
x7 4 2 0 7 0
x8 6 2 0 0 0
x9 3 6 8

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

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

Таблица 7.

x1 x2 x3 x4 x5 x6 x7 x8 x9
x1 6 7 4
x2 -6 0 0 6
x3 -7 0 3 4
x4 -4 0 0 2 2
x5 0 0
x6 -3 0 3
x7 4 2 0 0 6
x8 -6 -2 0 0 8
x9 -3 -6 -8

Величина максимального потока равна сумме элементов x 1 -й строки табл.7 или сумме элементов x 9 -го столбца.

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

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

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

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

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

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

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

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

Таблица 1

№

варианта

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
m1 0 1 0 1 1 1 1 2 2 0 1 3 0 1 1
m2 1 2 2 2 3 1 2 2 1 2 3 1 1 2 0
m3 2 3 1 0 1 1 1 3 2 1 0 1 2 3 3
m4 3 1 3 4 0 2 1 1 0 1 1 2 1 1 2
m5 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 } .

Начальная маркировка сети обозначается вектором μ0 [μ1 ,μ2 ,μ3 ,μ4 ,μ5 ] , μ0 [1 3 0 1 2]. Отсюда получим:

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

Через F (t j ) обозначается множество входных позиций, а через H (t j ) - множество выходных позиций перехода t j ; μ 0 - начальная маркировка сети.

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

F (t2 ) = {p1 },H (t2 ) = {p3 , p4 },

F (t3 ) = {p3 , p4 }H (t3 ) = {p1 },

F ( t 4 ) = { p 2 , p 3 , p 4 } H ( t 4 ) = { p 5 }.

μ0 [1 3 0 1 2]

Матричная форма определения сети Петри эквивалентна аналитическому способу задания 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 [1 3 0 1 2] сети Петри разрешенными являются переходы t 1 и t 2 .

Условия срабатывания для перехода t 3 и t 4 не выполняется.

Переход t 1

[μ0 ] ≥ [1000]*D - = [1000] · ; [1 3 0 1 2] ≥ [00001] –

условие выполняется, переход разрешен.

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

.

Переход t 2

[μ0 ] ≥ [0100]* D - = [0100] ·; [1 3 0 1 2] ≥ [10000] –

условие выполняется, переход разрешен.

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

.

Переход t 3

[μ0 ] ≥ [0010]* D - = [0010] ·; [1 3 0 1 2] ≥ [00110] - условие не

выполняется, переход запрещен.

Переход t 4

[μ0 ] ≥ [0001]* D - = [0001] ·; [1 3 0 1 2] ≥ [01110] –

условие не выполняется, переход запрещен.

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

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

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

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

.

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

Система имеет решение x 1 = 1; x 2 = 2; x 3 = 0; x 4 = 2.

Это значит, что исследуемая маркировка достижима и в последовательности срабатываний переход t 1 срабатывает один раз, переходы t 2 и t 4 - по два раза, переход t 3 не срабатывает.

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

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

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

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

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

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

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

Таблица 1

№

варианта

 11 12 13 14 15 16 17 18 19 20

Тип

элементов

И

НЕ

И

ИЛИ

НЕ

И

НЕ

ИЛИ

НЕ

И

НЕ

И

ИЛИ

НЕ

И

НЕ

ИЛИ

НЕ

И

ИЛИ

НЕ

И

НЕ

Тип

триггера

 D JK T D RS RSD D JK T D

Решение:

Множество вершин X = { x 1 , x 2 ,x 3 , x 4 , x 5 , x 6 },

Вершины графа отожествляются с состояниями автомата таким образом, что множество состояний Q= {q 1 ,q 2 , q 3 , q 4 , q 5 , q 6 }. Переход автомата из одного состояния в другое осуществляется под воздействием множества входных сигналов X = {x 1 ,x 2 ,x 3 ,x 4 }.

Автомат позволяет вырабатывать выходные сигналы Y = {y 1 , y 2 ,y 3 }.

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

Г q1 = {q1 (x1 /y1 ), q3 (x2 /y2 ), q2 (x3 /y2 )},

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

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

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

Г q5 = {q3 (x4 /y3 ), q4 (x1 /y3 ), q6 (x2 /y2 )},Г q 6 = {q 4 (x 3 / y 3 ),q 5 (x 4 / y 3 )}.

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

Таблица 2

X Q q1 q2 q3 q4 q5 q6
X1 q1 /y1 q3 /y2 q1 /y3 q2 /y3 q4 /y3 ─
X2 q3 /y2 ─ q5 /y2 q6 /y2 q6 /y2 ─
X3 q2 /y2 q4 /y2 q2 /y3 q3 /y3 ─ q4 /y3
X4 ─ q1 /y3 q4 /y2 q5 /y2 q3 /y3 q5 /y3

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

Количество букв входного алфавита n = 4

Количество входовp ≥ log2 n = log2 4 = 2;

Количество букв выходного алфавита m = 2

Количество выходовe ≥ log2 m = log2 3 = 2;

Количество состояний r = 6

Количество триггеровz ≥ log2 r = log2 6 = 3.

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


x

 u u1 u2
x1 1 0 5
x2 1 1 4
x3 0 0 5
x4 0 1 5
v1 v2
y1 1 0 1
y2 0 1 9
y3 0 0 9

q

w

 w1 w2 w3
q1 0 0 1 3
q2 0 1 0 3
q3 0 0 0 4
q4 1 0 0 4
q5 0 1 1 3
q6 1 1 0 2

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

Таблица 3

u1 u2

w1 w2 w3

001 010 000 100 011 110
10 001/10 000/01 001/00 010/00 100/00 ─
11 000/01 ─ 011/01 110/01 110/01 ─
00 010/01 100/01 010/00 000/00 ─ 100/00
01 ─ 001/00 100/01 011/01 000/00 011/00

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

Таблица 4

u1 u2 w1 (t) w2 (t) w3 (t)

w1

( t+1)

w2

( t+1)

w3

( t+1)

 v1 v2 D1 D2 D3
1 0 0 0 1 0 0 1 1 0 0 0 1
1 1 0 0 1 0 0 0 0 1 0 0 0
0 0 0 0 1 0 1 0 0 1 0 1 0
0 1 0 0 1 * * * * * * * *
1 0 0 1 0 0 0 0 0 1 0 0 0
1 1 0 1 0 * * * * * * * *
0 0 0 1 0 1 0 0 0 1 1 0 0
0 1 0 1 0 0 0 1 0 0 0 0 1
1 0 0 0 0 0 0 1 0 0 0 0 1
1 1 0 0 0 0 1 1 0 1 0 1 1
0 0 0 0 0 0 1 0 0 0 0 1 0
0 1 0 0 0 1 0 0 0 1 1 0 0
1 0 1 0 0 0 1 0 0 0 0 1 0
1 1 1 0 0 1 1 0 0 1 1 1 0
0 0 1 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 1 0 1 0 1 1
1 0 0 1 1 1 0 0 0 0 1 0 0
1 1 0 1 1 1 1 0 0 1 1 1 0
0 0 0 1 1 * * * * * * * *
0 1 0 1 1 0 0 0 0 0 0 0 0
1 0 1 1 0 * * * * * * * *
1 1 1 1 0 * * * * * * * *
0 0 1 1 0 1 0 0 0 0 1 0 0
0 1 1 1 0 0 1 1 0 0 0 1 1

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

.

.

.

.

.

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

После минимизации имеем набор функций в базисе И-НЕ

=

.

.

.

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

Похожие работы

  • Типовой расчет графов

    Данная работа является типовым расчетом по курсу "Дискретная математика" по теме "Графы", предлагаемая студентам МГТУ им. Баумана.

  • Графы

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

  • Использование математических методов и моделей в управлении микроэкономическими системами

    ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ОТКРЫТЫЙ УНИВЕРСИТЕТ

  • СМО с отказами

    СМО с отказами (задача Эрланга) Рассматривается N-канальная СМО с отказами: λпотерь λобслуживания υ υ υ λ Любая заявка может быть обслужена любым свободным каналом. Если все каналы заняты, заявка немедленно получает отказ в обслуживании и покидает систему (теряется).

  • Теория графов 2

    Содержание Введение………………………………………………………………………..……………………………………3 1 Теоретическая часть. 4 1.1 Основные понятия теории графов. 4 1.2 Порядок и правила построения сетевых графиков. 6

  • Поиск оптимального пути в ненагруженном орграфе

    Понятия теории графов. Понятия смежности, инцидентности и степени. Маршруты и пути. Матрицы смежности и инцедентности. Алгоритм поиска минимального пути в ненагруженном ориентированном орграфе на любом языке программирования, алгоритм фронта волны.

  • Операции на графах

    Операции на графах позволяют образовывать новые графы из нескольких более простых. Операции на графах без параллельных ребер. Объединение графов. Свойства операции объединения т, которые следуют из определения операции и свойств операций на множествах.

  • Матрицы графов

    БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ Кафедра информатики РЕФЕРАТ На тему: «Матрицы графов» МИНСК, 2008 В теоретико-множественной и геометрической форм определения (задания) графов, часто используется матричная форма их представления. Существуют различные виды матриц графов, однако все они, как правило, полностью передают основные свойства графов.

  • Свойства операций над множествами

    Содержание Свойства операций над множествами Смежность и инцидентность. Степени вершины графа Определение транспортной сети 1.Свойства операций над множествами

  • Графы Основные понятия

    Министерство образования и науки Российской Федерации Курский государственный технический университет Кафедра ПО ВТ и АС Лабораторная работа № 1 Графы. Основные понятия