Контрольная работа №2

Федеральное Агентство по образованию

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

Кафедра компьютерных систем в управлении и проектировании (КСУП)

КОНТРОЛЬНАЯ РАБОТА №2

2011

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

В алгебре абстрактных автоматов выделяют две группы бинарных операций: теоретико-множественные и алгебраические.

К теоретико-множественным относятся:

- объединение:

Автоматное отображение , индуцированное автоматом , есть продолжение автоматных отображений и на множество .

- пересечение:

К алгебраическим относятся:

- произведение:

,

- слова в соответствующих алфавитах,

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

- суммирование:

- суперпозиция:

.

- композиция:

Это наиболее общий случай работы автоматов, все предыдущие операции являются

частным случаем этой.

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

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

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

,

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

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

Что такое комбинационный автомат?

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

,

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

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

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

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

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

Вторая исходная предпосылка структурного синтеза – выбор из множества элементарных автоматов того набора, который гарантирует возможность построения нужного автомата (условие полноты). При этом должна обеспечиваться возможность построить наилучшую (или близкую к этому) в каком-либо смысле структуру - наилучшую в смысле простоты, цены, доступности, скорости разработки и т. п. Такой набор называется базисом синтеза или элементным базисом, и выбор его во многом определяет успех разработки.

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

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

- задан абстрактный автомат (функциональная модель),

- выбран элементный базис,

- известны правила соединения элементов базиса в структуру.

5. Что входит в состав элементного базиса?

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

Базис состоит из логических элементов и элементов памяти :

- логические элементы представляют собой элементарные комбинационные логические автоматы, составляющие полную систему булевых функций, а функциональные свойства которых представляются достаточно полными логическими функциями: дизъюнкция, конъюнкция, отрицание, функция Шеффера, импликация, стрелка Пирса, и т. д.

- элементы памяти - элементарные логические автоматы. Наиболее простые и распространённые – элемент задержки и триггер. Элемент задержки – элементарный синхронный автомат, функции которого сводятся к задержке на один такт значения одной логической переменной. То есть значение выхода в момент времени t равно значению входа в момент времени t-1.Триггер – асинхронный автомат с двумя внутренними состояниями, которые могут фиксироваться и в каждое из которых при определённых условиях автомат можно перевести.

6. Понятие правильной синхронной сети.

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

1) к каждому входному полюсу блока присоединён не более, чем один выходной полюс (однако допускается присоединение выходного полюса блока к нескольким входным полюсам, то есть разветвление выходов);

2) в каждом контуре обратной связи, то есть в каждом цикле, есть хотя бы один элемент задержки.

Входными полюсами правильной синхронной сети будут полюса, не присоединенные ни к каким выходным полюсам блоков, а выходными полюсами те, которые не подсоединены ни к каким входным полюсам.

7. Канонические уравнения сети.

Возьмём произвольную правильную синхронную логическую сеть (ПЛС), обозначив её . Удалим из неё элементы задержки и получим линейно – упорядоченную сеть (ЛУС) без задержек, которая является логическим комбинационным автоматом. Входами являются: во-первых, входы , а во-вторых, выходы элементов задержки . Выходы – это выходы и входы элементов задержки . Таким образом, входной набор имеет вид , а выходной набор –. Если теперь набор считать входным сигналом сети , набор – выходным сигналом сети , а набор – состоянием сети и учесть, что , то получим, что сеть вычисляет две системы логических функций от набора – систему , то есть функцию переходов , и систему , то есть функцию выхода . Эти две системы называются каноническими уравнениями сети .

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

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

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

9. Какая из программ, предназначенных для реализации комбинационного автомата, лучше – бинарная или операторная?

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

10. Какие недостатки и преимущества у канонического метода синтеза автоматов по сравнению с декомпозиционным методом синтеза?

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

Преимущества декомпозиционного метода синтеза автоматов по сравнению с каноническим следующие:

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

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

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