Министерство науки и высшего образования РФ

Федеральное государственное бюджетное образовательное

учреждение высшего образования

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

ОТЧЕТ
Контрольная работа № 2

по дисциплине «Математические основы теории систем»

Выполнил студент:
группы з-511П2-4
направление подготовки 27.03.04

(ФИО) Проверил:
доцент кафедры КСУП ТУСУР

(ученая степень, звание)
Карпов А. Г.
(ФИО)

Томск 2022

Вопрос 1: Перечислите операции над автоматными отображениями.
Ответ:

Теоретико-множественные операции:

a) Объединение: S_C = S_AS_B

Автоматное отображение S_C(q₁, x), индуцированное автоматом C, есть продолжение автоматных отображений S_A(q₁,x) и S_B(q1,x) на множество X^*.

b) Пересечение: S_C = S_AS_B

Алгебраические операции :

a) Произведение: S_K = S_AS_B

S_K(z) = S_K(xu) = S_A(x)  S_B(u) = y v = s,

xX^*, uU^*, yY^*, vV^*, sS^* - слова в соответствующих алфавитах,

xu - декартово произведение слов.

b) Сплетение: S_M = S_AS_B

S_M(z) = S_M(xu) = S_A(x)  S_B(u) = y  v = s,

xu – сплетение слов.

c) Суперпозиция: S_N = S_AS_B

S_N(x) = S_B(y) = S_B(S_A(x).


Вопрос 2: Понятие вероятностного автомата. Как задать вероятностный

---

автомат?
Ответ:

Если состояния переходов и/или состояния выходов являются случайными, то автомат называют вероятностным (стохастическим).

Задать вероятностный автомат можно совокупностью объектов:

A = (X, Q, q₁Q, (q, x)),

где X = {x₁…x_m} – входной алфавит, Q = {q₁…q_n} – алфавит состояний, q₁ – начальное состояние автомата, (q, x) – двуместная функция, задающая отображение множества QX в множество матриц P = {P_i}, i = {1… m}. Эта функция (q, x) называется таблицей переходных вероятностей.

Другой способ, можно задать графами переходов, только у каждого ребра, связывающие вершины q_i c q_j, ставят еще и соответствующую вероятность перехода p_ij(x). Этот способ больно громоздкий и неудобен. Поэтому , обычно задают системой стохастических матриц.
Вопрос 3: Что такое комбинационный автомат?
Ответ:

Комбинационным (логическим) автоматом называется такой автомат, у которого для любого входного символа xX и любых состояний q_i, q_jQ выполняется равенство:

(q_i, x) = (q_j, x),

то есть выход автомата не зависит от его состояния и определяется только его входом. В таком автомате все состояния эквивалентны и минимальный комбинационный автомат имеет только одно состояние. Функция переходов в нём вырождена, а поведение такого автомата задаётся функцией выходов с одним аргументом (x_i) = y_i.

Вопрос 4: Что необходимо для структурного синтеза автомата?
Ответ:

Для структурного синтеза необходимо:

a) Описывают функциальную модель;

b) Задаётся элементарный базис;

c) Определение правил соединений элементов.
Вопрос 5: Что входит в состав элементного базиса?
Ответ:

Состоит базис из следующих элементов:

a) Элемента памяти (сюда входят задержки и триггера);

b) Логический элемент (конъюнкция, дизъюнкция, отрицание, штрих Шеффера, стрелка Пирса).
Вопрос 6: Понятие правильной синхронной сети.
Ответ:

Правильная синхронная сеть- это сеть состоящая из логических элементов и элементов задержки, если:

a) к каждому входному полюсу блока присоединён не более, чем один выходной полюс (однако

---

допускается присоединение выходного полюса

блока к нескольким входным полюсам, то есть разветвление выходов);

b) в каждом контуре обратной связи, то есть в каждом цикле, есть хотя бы один элемент задержки.
Вопрос 7: Канонические уравнения сети.
Ответ:

Возьмём произвольную правильную синхронную логическую сеть (ПЛС) G. Удалив из неё элементы задержки, получим линейно – упорядоченную сеть (ЛУС) G₀ без задержек, которая является логическим комбинационным автоматом. Входами G₀ являются: во-первых, входы G, а во-вторых, выходы z₁…z_k элементов задержки G, выходы G₀ – это выходы G м входы z₁^',…,z_k элементов задержки G. Таким образом, входной набор G₀ имеет вид (x₁,…x_m, z₁,…z_k), а выходной набор – (y₁,…y_n, z₁^’,…,z_k^’). Если теперь набор (x₁(t),…x_m(t)) считать входным сигналом x(t) сети G, набор (y₁(t),…y_n(t)) – выходным сигналом y(t) сети G, а набор (z₁(t),…z_k(t)) – состоянием q(t) сети G и учесть, что (z₁^’(t),…z_k^’(t)) = (z₁(t+1),…z_k(t+1)) = q(t+1), то получим, что сеть G₀ вычисляет две системы логических функций от набора x(t) q(t) – систему (z₁^’(t),…z_k^’(t)) = q(t+1), то есть функцию переходов , и систему (y₁(t),…y_n(t)), то есть функцию выхода . Эти две системы называются каноническими уравнениями сети G.(из доказательства теоремы)

Вопрос 8: Проблемы кодирования состояний в асинхронных автоматах.
Ответ:

При кодировании асинхронных автоматов возникают проблемы, связанные с практической реализацией и конструктивными особенностями элементов памяти (триггеров).Каждый из реальных элементов памяти обладает инерционностью (ненулевое время срабатывания), причём эта инерционность не является постоянной и одинаковой для всех элементов. Это не учитывается в абстрактной модели автомата. Вследствие этого при переходе автомата из одного состояния в другое может реализоваться некоторая последовательность элементарных переходов (соответствующих изменениям состояния отдельных элементов памяти), при которой автомат проходит через некоторое множество промежуточных состояний и которая в общем случае непредсказуема. Последующие действия автомата будут определяться уже значениями функции переходов на достигнутых промежуточных состояниях.

---

Таким образом, дальнейшее поведение автомата может оказаться в зависимости от того, какой из элементов памяти быстрее среагирует на прикладываемое к нему воздействие. Элементы как бы состязаются в быстроте реакции, чем и обусловлено название соответствующего явления – состязание между элементами памяти. Если, в конце концов, автомат приходит в намеченное матрицей переходов состояние, то состязания можно считать не опасными, в противном случае их следует рассматривать как опасные. Чтобы поведение автомата не отличалось от заданного матрицей переходов, необходимо устранить все опасные состязания между элементами.
Вопрос 9: Какая из программ, предназначенных для реализации комбинацион-

ного автомата, лучше - бинарная или операторная?
Ответ:

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

Вопрос 10: Какие недостатки и преимущества у канонического метода синтеза

автоматов по сравнению с декомпозиционным методом синтеза?
Ответ:

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

a)не требуется строить сложные кодированные таблицы переходов;

b)решается проблема оптимального кодирования внутренних состояний автомата, приводящего к минимальной комбинационной части автомата;

c) декомпозиционный метод позволяет строить оптимальную или близкую к ней функциональную схему автомата при использовании элементарных автоматов со многими устойчивыми состояниями и логическими элементами в недвоичной логике. То есть, этой метод позволяет осуществлять синтез автоматов при использовании элементарного базиса, использующего логику более высокого порядка по сравнению с двоичной.

---

Смотрите также файлы

• Информатика пні бойынша кнтізбелік таырыпты жоспар 6 сынып.docx

• азастан республикасы білім жне ылым министрлігі шыыс азастан облысы тарбаатай ауданы.docx

• Тсінік хат. Информатика пні. 59 сыныптар.docx

• Информатика. ОулыCD. Р. А.адырлов, А. Д. Рыслбекова, Г. Нрмханбетова Алматы Алматы кітап баспасы, 2021.doc

• Оу масаты 2 1ртрліапараттрлерінімысалдарынкелтіружнеапараттыртрлінысандардасыну 2 2байланысарналары, апараткздеріжнеабылдаыштарынымысалынкелтіру 2 3мтіндікапараттыкодтаужнедекодтау Баалау критерийі.doc