Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Контрольная работа: Математические основы теории систем

Название: Математические основы теории систем
Раздел: Рефераты по математике
Тип: контрольная работа Добавлен 01:36:48 02 сентября 2010 Похожие работы
Просмотров: 975 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Задача 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 } .

Начальная маркировка сети обозначается вектором μ012345 ] , μ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). В результате получим систему логических функций для построения комбинационной части автомата:

.

.

.

.

.

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

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

=

.

.

.

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

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений07:28:56 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
15:54:48 25 ноября 2015

Работы, похожие на Контрольная работа: Математические основы теории систем

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(151391)
Комментарии (1844)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru