Математические основы теории систем: Учебно-методический комплекс

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

МАТЕМАТИЧЕСКИЕ ОСНОВЫ ТЕОРИИ СИСТЕМ

УЧЕБНО-МЕТОДИЧЕСКИЙ КОМЛЕКС

Институт системного анализа, автоматики и управления Специальность 220201 — информатика и управление в технических системах

Санкт-Петербург Издательство СЗТУ 2007

Утверждено редакционно-издательским советом университета УДК 681.3.016 Математические основы теории систем: Учебно-методический комплекс /сост. О. И. Золотов, В.Я Пашкин - СПб:Изд-во СЗТУ, 2007.-15с. Методический комплекс содержит сведения., необходимые студенту для самостоятельного изучении дисциплины, выполнения контрольной работы и курсового проекта. Учебно-методический комплекс (УМК) разработан в соответствии с требованиями государственных образовательных стандартов высшего профессионального образования. УМК предназначен для студентов специальности 220201,изучающих дисциплину “Математические основы теории систем”. Рассмотрено на заседании кафедры процессов управления и информационных систем 21 февраля 2007г.,одобрено методической комиссией института системного анализа, автоматики и управления 22 марта 2007г. Р е ц е н з е н т ы: кафедра процессов управления и информационных систем СЗТУ; Р.Р.Хамидуллин, канд. техн. наук, проф. кафедры ЭВМ, систем и сетей СЗТУ. Составители: О.И. Золотов, канд. техн. наук, проф. В. Я.Пашкин канд. техн. наук, доцент

2

ПРЕДИСЛОВИЕ Цель дисциплины — обучить студентов методам решения задач дискретной математики, необходимым для проектирования систем управления различных классов. Дисциплина связана с предшествующими ей дисциплинами «Высшая математика», «Информатика», «Программирование» и со всеми последующими дисциплинами специальности. РАБОЧАЯ ПРОГРАММА (150 часов) Введение (1 час) [21, с. 12... 25 Цель и основные разделы курса. Примеры использования методов дискретной математики при разработке информационного, программного и технического обеспечения научно-технических и экономических задач. 1. Элементы и средства теоретико-множественного описания систем (24 часа) [1], с. 5... 79; [2],с.24…67 Множества. задания множеств. Операции над множествами. Упорядочение элементов и прямое произведение множеств. Соответствия множеств. Отображения и их свойства. Функция, функционал. Отношения на множествах. Свойства отношений. Операции над отношениями. Элементы общей алгебры. Алгебраическая система. Фундаментальные алгебры. Типы алгебр. 2. Теория графов (25 часов) [1]. с. 119.. . 148;[2],с.76…96 Основные понятия и определения: Граф, отмеченный граф, ориентированный граф, инцидентность, связность, путь, цикл. Способы задания графов: матрицы смежности и инциденций, списки. Алгебра графов. Базисные свойства графов. Основные характеристики графов. Алгебраическая система графов. Задача на графах .Классические задачи с разбиением графов. Задачи о кратчайшем и критическом путях на графе. Задача о наибольшем потоке. Транспортные сети и графы. Транспортная задача. Задача декомпозиции на графах. Методы разложения графа. Понятие о сетях Петри. 3.Теория автоматов(25 часов). [3], с. 28…49, [4],4…10, 30…43,55…73,78…82 Абстрактные автоматы. Понятие абстрактного автомата. Преобразование абстрактных автоматов. Структурный синтез автоматов и кодирование информации. Кодирование состояний, входных и выходных символов. Математический аппарат синтеза комбинационных автоматов. Элементная база для построения комбинационных автоматов. Переключательные функции. Минимизация переключательных функций. Метод Квайна. Структурный синтез комбинационных автоматов. Синтез на основе минимальных нормальных форм. Синтез с учётом коэффициентов объединения по входу. Структурный синтез автоматов с памятью, асинхронные автоматы. . 4. Математическое программирование (44 часов) [2], с. 282… 306, 328…339, 460…464 Общая задача математического программирования. Классификация задач математического программирования. Линейное программирование. Геометрическая интерпретация. Симплекс-метод. Нахождение опорного решения. Теория двойственности. Анализ чувствительности. Декомпозиция линейных задач. Динамическое программирование. Основное рекуррентное соотношение. Принцип Беллмана. Алгоритм решения дискретных задач методом динамического программирования. Задача с несколькими ограничениями. Целочисленное программирование. Метод ветвей и границ. Ветвление. Вычисление границ. Понятие рекорда. Алгоритм решения задачи целочисленного линейного программирования методом ветвей и границ. Оценка точности решения. Задача коммивояжера и алгоритм Литтла. 3

5. Теория игр (30 часов) [2], с, 343. . . 3 7 9 ; [ 5 ] , с . 5 4 7 … 5 6 1 . Игра как математическая модель конфликта. Примеры игровых ситуаций. Основные понятия теории игр. Классификация игр. Матричные игры. Теорема о минимаксах. Смешанные стратегии. Основная теорема матричных игр. Графический метод решения матричных игр. Метод Брауна — Робинса. Сведение матричной игры к задачам линейного программирования. Бескоалиционные игры. Характеристические функции. Методы решения кооперативных игр. Определение С-ядра.. Связь между С-ядром и решением кооперативной игры. Заключение (1 час) [5], с. 17 . . . 19 Методология построения математических моделей для решения прикладных задач. ЛИТЕРАТУРА Основная: 1.Николаев В.И., Золотов О.И., Петухов О.А., Хамидуллин Р.Р. Математические основы теории систем: Учебное пособие.-СПб.:СЗТУ,2001. 2.Коршунов Ю. М. Математические основы кибернетики: Учеб. пособие для вузов. 3-е изд. Перераб. и доп. — М.: Энергоатомиздат, 1987. Дополнительная: 3.Николаев В.И., Пашкин В.Я. Основы дискретной математики: Учебное пособие. СПб.: СЗПИ, 1999. 4.Анкудинов Г.И., Иванова И.В., Пашкин В.Я., Шумова Е.О. Теория автоматов: Учебное пособие. - СПб.: СЗПИ,1997. 5.Хэмди А Taxa . Введение в исследование операций. - М.: Издательский дом Вильямс”,2001. Тематический план лекций (32часа) 1. Введение. Множества. Способы задания множеств. 4 часа. 2. Основные понятия графов. Задачи на графах.. 4 часа. 3. Транспортные сети и графы. 4 часа. 4. Абстрактные автоматы. Структурный синтез автоматов с памятью 4 часа 5. Линейное программирование. Симплекс метод. 4 часа. 6. Динамическое программирование. 4 часа. 7. Метод ветвей и границ. 4 часа. 8. Основные понятия теории игр. Заключение. 4 часа.

Задание на контрольную работу: Студент выполняет вариант задания в соответствии с последними тремя цифрами зачётной книжки: a, b, c. 1. Решить симплекс-методом следующую задачу линейного программирования: z = cx1 + bx2+ax3 + 6x:4→ max; 2x1 + 3x2 +b x 3 +cx4 ≤ 8; x1 + 2х2+схя+5х4≤ 10: xi ≥0, i = 1,4 . 2. Методом динамического программирования решить задачу целочисленного программирования: 4

z = (а+1) x12+ x22→ max; 2х1+х2(b+с)/3≤10; х 1, х 2 = 0, 1, 2, … 3. Методом ветвей и границ решить задачу целочисленного линейного программирования: z = (a+1) x1 + (b+3) x2 → max; xl + (2+c) x2≤ 7 + с; (2+с) х1+х2≤ 7 + b; х1, х2, = 0, 1 , 2 , . . . 4.Графическим методом решить антагонистическую игру, заданную матрицей выигрыша первого игрока φ=

a2cb abbc

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ Выполняя контрольную работу, студент должен продемонстрировать умение грамотно, четко и кратко излагать суть процедур решения предложенных ему задач, давать необходимые пояснения и анализировать полученные результаты. Контрольная работа должна быть аккуратно оформлена, смысл всех используемых обозначений должен быть понятен, расчеты следует приводить, не опуская промежуточные выкладки. Ниже кратко рассмотрены основные этапы решения задач, составляющих контрольную работу. Задача 1. Решим симплекс-методом задачу линейного программирования z = 2x1 + 3x2→ max; x 1 + x2 ≤ 5; 2x1 - х2 ≤ 4: х 1, х 2 ≥ 0. Прежде всего, введя дополнительные переменные х3 и х4, перепишем исходную задачу в нормальной форме, не содержащей неравенств: z = 2x1+3x2+0x3+0x4→max; (1) x1+x2+x3+0x4=5; (2) 2x1 - x2+0x3+x4=4; (3) х 1, х 2 ≥ 0. В качестве опорного плана x*=(x1*,x2*,x3*,x4*) возьмем начало координат исходной задачи, т. е. положим x1*=x2*= 0. Тогда из (2) и (3) получим , x3*=5, x4*= 4. Дли этого опорного плана запишем симплекс-таблицу (см. табл. 1 приложения), в которой С — строка коэффициентов при переменных в целевой функции ( 1 ) , Вx — столбец базисных переменных, A0 — столбец свободных членов, А 1, ..., A4 -столбцы коэффициентов в (2) и (3) соответственно при переменных x1,….,x4. Элементы строки ∆ в табл. 2 вычисляются по формуле ∆j = ∑ CiAij - Cj (4) i∈Bx

где i, j — номера переменных и, соответственно, строк и столбцов в симплекс-таблице, Aij — элемент таблицы, стоящий на пересечении i-ой строки и j-го столбца. Согласно (4) имеем: ∆0 = С3A30 + С4А40-С0 =0*5 + 0*4 - 0 = 0, ∆1 = С3A31 + С4А41-С1 =0*1 + 0*2 - 2 = -2, ∆2 = С3A32 + С4А42-С2 =0*1 + 0*1 - 3 = -3, 5

∆3 = С3A33 + С4А43-С3 =0*1 + 0*0 - 0 = 0, ∆4 = С3A34 + С4А44-С4 =0*0 + 0*1 - 0 = 0. Поскольку строка ∆ симплекс-таблицы содержит отрицательные элементы ∆1 и ∆2, то решение х* =(0, 0, 5, 4) не является оптимальным. Кроме того, столбцы j =1 и j = 2 симплекс-т а б л и ц ы содержат положительные элементы. Последнее означает, что оптимальное решение существует и для его нахождения следует перейти к новой симплекс-таблице. Сначала по формуле ∆k = min ∆j j

отыскивается разрешающий столбец k, а затем по формуле θг = min θi, i∈Bx

где величина θi= Ai0 / Aik и вычисляется только для тех i, для которых Aik>0, находится разрешающая строка r. Согласно табл. 2,' ∆k = ∆2=--3, т. е. k = 2, а θг =θз = = 5/1=5, т. е. r=3. Следовательно, разрешающий элемент (в табл. 1 он заключен в квадрат) A rk =1. Зная разрешающий элемент, вычисляем элементы Aнij новой симплекс-таблицы по формуле: ⎧Aij/Ark, если i = r; ⎫ Aнij = ⎨ ⎬ ⎩Aij - ArkAik/Ark, если i ≠ k ⎭ При этом новые элементы для i = 3 равны A30н = A30 / A32 = 5/1 = 5, A31н = A31 / A32 = 1/1 = 1, A32н = A32 / A32 = 1/1 = 1, A33н = A33 / A32 = 1/1 = 1, A34н = A34 / A32 = 0/1 = 0, а новые элементы строки i=4 равны: A40н = A40 - A30 A42 / A32 = 4 – 5(-1)/1 = 9, A41н = A41 - A31 A42 / A32 = 2 – 1(-1)/1 = 3, A42н = A42 - A32 A42 / A32 = -1 – 1(-1)/1 = 0, A43н = A43 - A33 A42 / A32 = 0 – 1(-1)/1 = 1, A44н = A44 - A34 A42 / A32 = -1 – 0(-1)/1 = 1, Введя в базис переменную х2 вместо х3 и заново вычислив строку ∆, получим новую симплекс-таблицу (см. табл. 2 приложения), которая соответствует оптимальному решению х0 = (0, 5, 0, 9). Следовательно, х10 = 0, х10 = 5 (дополнительные переменные х3, х4 не входили в формулировку исходной задачи и потому не должны указываться в ее решении). При этом целевая функция имеет значение z = ∆0 = 15. Задача 2. Методом динамического программирования найдем z = х12 +3х2 →max 3 х1 +2 х22≤ 10, х 1, х 2 =0, 1 , 2 , . . .

(5)

Поскольку задача содержит две переменные, решение будет найдено за два шага. Шаг /. На этом шаге основное рекуррентное соотношение динамического программирования для нашей задачи запишется в виде: x1€X1(ξ) ∆1(ξ) = max f 1 (х 1 ), x1∈X1(ξ )

6

(6)

причем f 1 (х 1 )= х 1 2, X1(ξ) = {0, I, . . . , [ξ /А 1]}, где [X] означает «целая часть числа , X», a A1 = 3 — коэффициент при переменной х 1 в неравенстве (5). Воспользовавшись (6), вычислим ∆1(ξ) для всех возможных состояний вычислительного процесса ξ≤ В, где В — правая часть неравенства (5). Результаты сведем в табл. 4 приложения. Шаг 2. На этом шаге основное рекуррентное соотношение динамического программирования имеет вид: ∆2(ξ) = max [f 2 (х 2 ) + ∆1(ξ – A2 х 2 2)] x1∈X1(ξ )

(7)

где f 2 (х 2 ) =3х 2 , A2 = 2, a ξ = В, так как данный шаг последний. Результаты расчетов по формуле (7) сведем в табл. 4 приложения, в которой графа ∆1 заполнена на основании данных табл. 3. Из табл. 4 ясно, что ∆2 (В)=9. Следовательно, z=9. Поскольку величина ∆2(В)=9 достигается при х 2 = 0, то для переменной х2 оптимальное значение х 2 0 = 0. При этом ∆1(10-2х 2 2) = ∆1(10) = 9, причем это значение, согласно табл. 3, достигается при х 1 =3. Следовательно, для переменной х 1 оптимальным является значение х 1 0=3. Задача 3. Методом ветвей и границ найти: z = 2х 1 +3х 2 →max;

(8)

х1 + х 2 ≤5;

(9)

2 х1 - х2< 4 ;

(10)

l,5 х 1 - х 2 ≥—4;

(11)

х1, х 2 = 0, 1 , 2 , . . .

(12)

Шаг 1. Вычисление границы. Пусть G — множество допустимых решений исходной задачи. Заменим в этой задаче условие целочисленности ( 1 2 ) на условие неотрицательности х 1 , х 2 ≥0. В новой задаче множество допустимых решений обозначим через G*. Очевидно, что G G*. Поэтому максимум целевой функции (8) на множестве G* есть верхняя граница λ(G) этой функции на множестве G. Решив графически задачу линейного программирования (см. рис. 3), получим, что х 1 * = 0,5, х 2 * = 4,5, и потому λ(G) = 2 х 1 *+3 х 2 * -= 14,5.

Шаг 2. Ветвление. Поскольку в векторе х*=( х 1 *, х 2 *) обе компоненты не являются целочисленными, то ветвление можно осуществить по любой из них. Произведем ветвление по переменной х 2 . Тогда множество G* будет разбито на непересекающиеся подмножества 7

G 1*= {( х 1 , х 2 ) | ( х 1 , х 2 ) € G*, х 2 ≤ [х 2 *] = 4}, G 2*= {( х 1 , х 2 ) | ( х 1 , х 2 ) € G*, х 2 ≥ [х 2 *] +1 = 4} Из рис. .3 ясно, что G 2*=0 и потому верхнюю границу следует вычислять только для множества G 1 = G∩G1*. Шаг 3. Вычисление границы. Из рис. 4 видно, что максимум целевой функции (8) на множестве G1* достигается в точке х*=(1,4) с целочисленными координатами. При этом величина z* = 2 х 1 *+3 х 2 *= 14 является рекордом для множества G 1 и, следовательно, для множества G = G 1 U G2, где G2 = G ∩G2*. Поскольку найден рекорд для исходного множества допустимых решений G, то задача решена: z=z*=14, х10 = х 1 *=l, x 2 0 = x 2 *=4.

Задача 4. Решим графическим методом антагонистическую игру, заданную матрицей выигрыша первого игрока 205 φ= 431 'Ожидаемые выигрыши первого игрока в ситуациях (х, j), где х= (х 1 , l-х 1 ) - смешанная стратегия первого игрока, а j — чистая стратегия второго игрока, определяются выражениями: M φ(х,1 ) = х 1 φ11 + (1- х 1 ) φ11 = 2 х 1 + 4(1- х 1 )=4-2 х 1 , M φ(х,2 ) = х 1 φ12 + (1- х 1 ) φ12 = 0 х 1 + 3(1- х 1 )=3-3 х 1 , M φ(х,3 ) = х 1 φ13 + (1- х 1 ) φ13 = 5 х 1 + 1(1- х 1 )=1+4 х 1 , которым на рис. 5 соответствуют три прямые. Нижняя огибающая этих прямых выделена жирной ломаной. Верхней точке этой огибающей соответствует абсцисса 0,29 и ордината 2,14. Поэтому оптимальная стратегия первого игрока х 0 = (0,29, 0,71), а цена игры V = Mφ(х 0 , 2) = 2,14.

Для оптимальной стратегии второго игрока y0=( y1°, y2°, y3°) величина y1°=0, так как высшая точка нижней огибающей на рис. 5 образована прямыми, соответствующими j = 2 и j=3. Поэтому y3°= 1— y2° и для определения y° достаточно найти точку пересечения прямых, описываемых уравнениями M φ(1,y) = y 2 φ12 + (1- y 2 ) φ13 = 0 y 2 + 5(1- y 2 )=5-5 y 2 , M φ(2,y) = y 2 φ22 + (1- y 2 ) φ23 = 3 y 2 + 1(1- y 2 )=1+2 y 2 , 8

.Абсцисса этой точки у2° определится из условия 5 — 5 y2° = — l+2 y2°, что дает y2° = 0,57. Следовательно, y0=(0, 0,57, 0,43). ПРИЛОЖЕНИЕ Таблица 1 C

C0=0

C1=0

C2=0

C3=0

C4=0

Bx

A0

A1

A2

A3

A4

→x3

5

1

1

1

0

x4

4

2

-1

0

1

∆

9

-2

0

0

B

-3 ↑

Таблица 2 C

C0=0

C1=0

C2=0

C3=0

C4=0

Bx

A0

A1

A2

A3

A4

x2

5

1

1

1

0

x4

9

3

0

1

1

∆

15

1

0

3

0

B

Таблица 3 ξ

х1

f 1 (х 1 )

∆1(ξ)

ξ

х1

f 1 (х 1 )

0

0

0

0

7

0

0

1

0

0

0

1

1

2

0

0

0

2

4

4

3

о 1 0 1 0

0 1 0 1 0

0 1 2 0 1

0 1 4 0 1

4

1

1

2

4

0 1 2

0 1 4

3 0 1 2

9 0 1 4

9

3

9

9

4 5 6

8 1 1

9

1 10 4

9

∆1(ξ)

Таблица 4 х2

10-2х 2 2

∆1(10-2х 2 2)

f 2 (х 2 )

f 2 (х 2 )+ ∆1(10-2х 2 2)

∆2

0

10

9

0

9

9

1

8

4

3

7

2

2

0

6

6

Номер варианта Входы

Задание на курсовой проект. Абстрактный автомат Мили задан таблицей переходов/выходов. Требуется а) Минимизировать число состояний абстрактного автомата; б) Построить графы исходного минимизированного автомата; в) Произвести структурный синтез автомата на элементах памяти (для предпоследней цифры студента 0, 2, 4, 6, 8 – Т-триггеры, для цифр 1, 3, 5, 7, 9 – Д-триггеры); г) Вычертить логическую схему минимизированного автомата. Значения таблиц переходов/выходов выбираются из таблицы «А» по вариантам, соответствующим последней цифре шифра. Таблица А Состояния Функция переходов Функция выходов 1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8 11 3 1 1

1 0

2 1 2 3

3 1 2 3

4 2 3 4

5 2 5 8

6 7 5 8

7 5 1 6

8 2 5 8

9 2 3 4

10 7 4 5

12 1 2 2

13 1 1 3

14 3 1 1

15 2 2 3

1

1 2 3

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

2 1 1 1 3 1 1 3 2 2 2 2 1 2 1 1 3 3 2 3 1 2 3 1

2

1 2 3

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

1 3 2 1 1 1 3 1 1 1 2 2 2 2 1 2 3 1 3 3 2 3 1 2

3

1 2 3

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

1 1 1 3 1 1 3 2 2 2 2 1 2 1 1 2 3 2 3 1 2 3 1 3

4

1 2 3

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

1 3 1 1 3 2 1 1 2 1 2 1 1 2 2 2 3 1 2 3 1 3 3 2

5

1 2 3

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

1 1 3 1 1 1 2 3 1 2 1 2 2 2 2 1 3 2 1 3 2 3 3 1 10

16 1 2 3

17 1 2 2

18 1 2 3

1

2

Продолжение Таблицы А 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

6

1 2 3

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

1 1 1 2 3 1 1 3 2 2 2 2 1 1 2 1 3 2 3 3 1 3 2 1

7

1 2 3

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

3 1 1 3 1 1 1 2 1 1 2 1 2 2 2 2 1 3 2 1 3 2 3 3

8

1 2 3

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

3 1 1 1 2 3 1 1 1 2 2 2 2 1 1 2 1 3 2 3 3 1 3 2

9

1 2 3

1 8 8 3 5 8 8 3 8 7 5 5 2 5 7 6 7 6 3 2 8 2 6 5

2 3 1 1 3 1 1 1 2 1 1 2 1 2 2 2 3 1 3 2 1 3 2 3

Методические указания СИНТЕЗ АВТОМАТА С ПАМЯТЬЮ ОБЩИЕ ПОЛОЖЕНИЯ Абстрактным конечным автоматом Мили называется математическая модель, поведение которой описывается уравнениями: S(t+1)=δ(s(t), x(t)); Y(t)=λ(s(t), x(t)); S(0)=s 1 , где s(t)€S, x(t)€X, y(t)€Y, t€{0, 1, 2, . . .} (t — дискретное автоматное время; S X, Y— алфавиты (конечные множества) состояний, входных сигналов и выходных сигналов соответственно); s(t), x(t), y(t)—соответственно состояние, входной сигнал и выходной сигнал автомата в момент времени t; s1 — начальное состояние автомата; δ — функция переходов автомата; λ — функция выходов автомата. Для автоматов Мура функция выходов имеет более простой вид: Y(t)= λ(s((t)) Поведение многих реальных устройств автоматики и вычислительной техники характеризуется способностью запоминать воздействия внешней среды и вырабатывать реакцию на текущие воздействия с учетом воздействий среды на устройство в предыдущие моменты времени. Абстрактные конечные автоматы являются достаточно точной моделью таких устройств. Абстрактный конечный автомат Мили может быть задан в виде таблицы переходов и таблицы выходов (иногда используется совмещенная таблица) или ориентированного графа, вершины которого соответствуют состояниям, а дуги помечены парами символов «входной сигнал/выходной сигнал». Состояния автомата реализуются с помощью элементов памяти. Если требуемое число состояний синтезируемого автомата равно M, а число состояний элемента памяти θ, то требуется 11

N=] log θ M [ элементов памяти, причем ]х [ функция, равная ближайшему большему или равному х целому числу. При использовании двоичных элементов памяти N=]log 2M[. На этапе абстрактного синтеза число состоянии, л следовательно, число элементов памяти может быть уменьшено с помощью проведенной ниже процедуры минимизации. МИНИМИЗАЦИЯ АБСТРАКТНЫХ АВТОМАТОВ Рассмотрим минимизацию автоматов Мили. Сначала выявим тождественные состояния автомата и в таблицах переходов и выходов оставим только по одному представителю из каждого класса тождественных состояний. Два состояния автомата называются тождественными, если значения функций переходов и выходов для этих состояний совпадают при всех значениях входных сигналов. Затем выявим 1эквивалентные состояния. Два состояния автомата называются 1-эквивалентными, если значения функций выходов для этих состояний совпадают при всех значениях входных сигналов. Объединение всех 1-эквивалентных состояний автомата образует 1-класс эквивалентности. Два 1-эквивалентных состояния автомата называются 2-эквивалентными, если значения функции переходов для этих состояний принадлежат общему 1-классу для каждого значения входного сигнала; i-эквивалентные состояния и i-классы определяются по индукции. Следует обратить внимание на то, что необходимым условием (i+1)-эквивалентности состояний автомата является их i-эквивалентность (i=1,2, 3, . . . ) . Если разбиение на (i+1) -классы совпадает с разбиением на i -классы, то оно одновременно является разбиением на ∞-классы. Оставляя в каждом ∞-классе по одному представителю, получаем минимальное число состояний автомата Мили. Пример. Автомат Мили задан таблицами переходов и выходов (табл. 6 а и б). Состояния s1 и s8 тождественны, поэтому заменяем везде s8 на s1 и столбец для s8 отбрасываем. Из табл. 6 б находим 1-классы: π1 = { А 1 А 2}, где А 1= = {Sl, S2, S4, S5}, A2={S3, S 6, S 7}. Таблица 6а Входные Состояния символы Sl S2 S3 S4 S5 S6 X1 S2 S5 S1 S5 S4 S8 X2 Sl S6 S2 S7 S6 S5 Входные символы X1 X2 1-классы

Sl Y2 Y1 А1

Входные символы

Sl X1 А1 X2 А1 2-классы B1

Состояния S4 S5 S6 S7 Y2 Y2 Y1 Y1 Y1 Y1 Y2 Y2 А1 А1 А2 А2 Таблица 7 1-классы А1 А2 S2 S3 S4 S5 S6 S7 А 1 А 1 А1 А1 А 1 А 1 А2 А2 А2 А1 А1 А1 B2 B2 B2 B3 B3 B3

S2 Y2 Y1 А1

Входные символы

B1 Sl X1 B2 X2 B1 3-классы C1

S7 S8 S1 S2 S4 S2 Таблица 6б

S3 Y1 Y2 А2

2-классы

S2 B2 B3 C2

B2 S3 B2 B3 C2

S4 B2 B3 C2

S5 B1 B2 C3

Таблица 8 B3 S6 B1 B2 C3

S7 B1 B2 C3

12

S8 Y2 Y1 -

С помощью табл. 7 находим разбиением на 2-классы: π2 = { B1 B2 B3 }где B1={ Sl }, B2 = {s2, s4, s5}, B3 = {s3, s6, s7}. Далее с помощью табл. 8 определяем разбиением на 3-классы: π3 = {С1 С2, С3}, причем оказывается, что С1 = B1, С2 = B2 и С3 = B3,, т. е. мы получим ∞-классы, которым соответствует автомат Мили, описываемый табл. 9, а и б. Граф минимизированного автомата приведен на рис. 7.

Рис. 7. СТРУКТУРНЫЙ СИНТЕЗ КОНЕЧНЫХ АВТОМАТОВ Целью структурного синтеза конечного автомата является схемная реализация минимизированного абстрактного автомата. В состав структурного автомата входят логические элементы и элементы памяти, образующие функционально полную систему. В качестве запоминающих элементов используются автоматы Мура, обладающие полными системами переходов и выходов. Полнота системы переходов автомата заключается в том, что для любой упорядоченной пары состояний автомата существует входной сигнал, переводящий первый элемент этой пары во второй. Полнота системы выходов означает, что каждому состоянию автомата соответствует свой особый сигнал, позволяющий однозначно определить это состояние. Таким образом, в автомате Мура с полной системой выходов состояния автомата можно отождествить с соответствующими выходными сигналами. Функции переходов элементарных двоичных автоматов Мура, которые будут использоваться при синтезе конечного автомата, приведены в табл. 10, а, б и в (и — входной двоичный сигнал автомата, v — выходной двоичный сигнал, совпадающий с состоянием автомата). Таблица 9а Входные Состояния символы Sl S2 S3 X1 S2 S2 S1 X2 Sl S3 S2 Таблица 9б Входные Состояния символы Sl S2 S3 X1 Y2 Y2 Y1 X2 Y1 Y1 Y2 Таблица 10а и v 0 1 0 0 0 1 1 1 Таблица 10б и v 0 1 0 0 1 1 1 0 Табл. 10 а соответствует элементу задержки, осуществляющему задержку входного сигнала на один такт. Элемент задержки может быть выполнен в виде D-триггера. Табл. 10 б соответствует триггеру (Т-триггеру) со счетным входом. Канонический метод структурного синтеза конечных автоматов сводится к синтезу 'комбинационных схем, реализующих логические функции возбуждения элементов памяти и логические функции структурного представления выхода автомата. На рис. 8 приведены обобщенные структурные схемы конечных автоматов на элементах задержки, триггерах со счетным входом и триггерах с раздельными входами. Для обеспечения устойчивости работы автоматов в этих схемах используется удвоение памяти (рис. 9) и синхронизация работы автомата. 13

На первом этапе структурного синтеза конечного автомата осуществляется двоичное кодирование алфавитов состояний, входных и выходных символов автомата; на втором — синтез комбинационной части автомата, обеспечивающей получение требуемых функций переходов и выходов. Кодирование состояний синхронного автомата влияет только на сложность комбинационной части автомата. Пример. Осуществим структурный синтез минимизированного абстрактного автомата Мили, полученного в предыдущем примере. Разрядность кода входного символа равна ]log22[=l, разрядность кода выходного символа — ]log22[=l, число элементов памяти ]log2 3 [=2. Закодируем входные и выходные символы и состояния автомата так, как показано в табл. 11 а, и б. Используя эти коды, построим закодированные таблицы переходов и выходов структурного автомата (табл. 12, а, б). Их удобно строить в форме карт Карно Вейча. Табл. 10 а соответствует элементу задержки, осуществляющему задержку входного сигнала на один такт. Элемент задержки может быть выполнен в виде D-триггера. Табл. 10 б соответствует триггеру (Т-триггеру) со счетным входом. Канонический метод структурного синтеза конечных автоматов сводится к синтезу комбинационных схем, реализующих логические функции возбуждения элементов памяти и логические функции структурного представления выхода автомата. На рис. 8 приведены обобщенные структурные схемы конечных автоматов на элементах задержки, триггерах со счетным входом и триггерах с раздельными входами. Для обеспечения устойчивости работы автоматов в этих схемах используется удвоение памяти (рис. 9) и синхронизация работы автомата. На первом этапе структурного синтеза конечного автомата осуществляется двоичное кодирование алфавитов состояний, входных и выходных символов автомата; на втором— синтез комбинационной части автомата, обеспечивающей получение требуемых функций переходов и выходов. Кодирование состояний синхронного автомата влияет только на сложность комбинационной части автомата. Пример. Осуществим структурный синтез минимизированного абстрактного автомата Мили, полученного в предыдущем примере. Разрядность кода входного символа равна ]log22[=l, разрядность кода выходного символа — ]log22[=l, число элементов памяти ]log2 3 [=2. Закодируем входные и выходные символы и состояния автомата так, как показано в табл. 11 а, и б. Используя эти коды, построим закодированные таблицы переходов и выходов структурного автомата (табл. 12, а, б). Их удобно строить в форме карт Карно Вейча. в) б) а)

Рис. 8

Рис. 9

14

Входной символ X1 X2

Таблица 11а Двоичный код z 0 1

Выходной символ Y1 Y2

Таблица 11б Двоичный код w 0 1

Функцию выхода w строим по табл. 12 б: w = zv1 V zv1 Входной ход (z) 0 1 Входной ход (z) 0 1

Таблица 12а. Код состояния (v1 v2) 00 01 11 10 01 01 -01 00 10 -01 Таблица 12б. Код состояния (v1 v2) 00 01 11 10 1 1 0 0 0 1

Если в качестве элементов памяти использовать элементы задержки (см. функцию переходов в табл. 10 а), то функция возбуждения и 1 и 2 совпадает с табл. 12 а. Если в качестве элементов памяти использовать триггеры со счетным входом, то при построении таблицы возбуждения элементов памяти необходимо учитывать, что сигнал 1 подается на вход счетного триггера тогда и только тогда, когда необходимо изменить его состояние (перейти из состояния 0 в состояние 1 или наоборот). Предположим, что структурный автомат, рассмотренный выше, находится в состоянии v1 v2 = 00. При подаче входного сигнала z = 0 он должен перейти в состояние 01. В соответствии с табл. 10 6 на вход и1 надо подать 0, а на вход и2 — 1, т. е. и 1 и 2 = 01 Пусть исходное состояние автомата v1 v2 = 01, входной сигнал z =1. Тогда автомат должен перейти в состояние 10. Для этого на оба счетных триггера надо подать 1, т. е. и 1 и 2 = 11, и т. д. Результирующие значения кодов возбуждения и 1 и 2 приведены в табл. 13.

Входной код (z)

Таблица 13 Код состояния (v1

0

00 01

01 00

1 --

10 10

1

00

11

--

11

Из табл. 13 находим функции возбуждения для Т-триггеров: и 1 = v1\/ z v2, и 2 = zv1 v2\/ zv2 \/ zv1.

15