Программа дисциплины Математическая логика и теория автоматов
Работа добавлена на сайт samzan.net: 2016-03-13
Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Программа дисциплины
“Математическая логика и теория автоматов”
для заочного курса
(осень 2013/2014 учебного года)
Преподаватель: Фураев Илья Александрович
E-mail: iljya.furaev@yandex.ru
Староста: Филатов Дмитрий 8(911)242-76-66
dimaspb@me.com
Курс - 108 часов:
- Лекций: 6 часов
- Лабораторные работы: 6 часов
- Практические занятия (курсовой проект): 4 часа
- Самостоятельная подготовка: 92 часа
Отчетность:
- Зачет по лабораторным занятиям (контрольные работы).
- Курсовой проект.
- Экзамен.
Темы занятий:
- Определение абстрактного автомата. Модели Мура и Мили. Способы задания абстрактных автоматов. Эквивалентность автоматов. Эквивалентные преобразования автоматов Мили и Мура. Частично определенный автомат. Алфавитный оператор. Автоматный оператор. Переход от алфавитного оператора к абстрактному автомату.
- Обобщенная модель дискретного устройства. Задание автоматного отображения операторной схемой алгоритма. Языки операторных схем алгоритма. Синтез абстрактного автомата по операторной схеме алгоритма.
- Минимизация числа состояний полностью определенного автомата. Отношение эквивалентности, классы эквивалентности. Минимизация числа состояний полностью определенного автомата. Построение множества классов эквивалентности и минимального автомата.
- Минимизация частичных автоматов. Определение частичного автомата. Свойства частичного отображения. Преобразование частичных автоматов Мили и Мура. Учет взаимодействия управляющего и операционного автоматов. Построение частичного автомата. Совместимость состояний, классы совместимости. Построение множества максимальных классов совместимости. Построение замкнутого покрытия и минимального частичного автомата.
- Модель структурного автомата. Структурный базис. Типы триггеров. Канонический метод структурного синтеза конечного автомата. Асинхронные автоматы. Гонки в автоматах. Устойчивость структурного автомата. Противогоночное кодирование состояний автомата. Методы кодирования, ориентированные на упрощение автомата. Кодирование, учитывающие частоту переходов. Унитарное кодирование. Кодирование, использующее понятие «соседства" состояний. Кодирование, минимизирующее число переключений элементов памяти.
- Структурные методы обеспечения устойчивости структурного автомата. Одноступенчатые синхронизируемые триггеры. "Двойная память". Двухступенчатые триггеры. Явление риска в логических схемах. Условия возникновения риска. Построение логических схем без риска.
Лабораторные работы:
- Минимизация числа состояний полностью/не полностью определенного автомата с помощью треугольной матрицы.
- Кодирование состояний автомата.
- Построение функций возбуждения для заданного синхронного/асинхронного автомата при заданном способе кодирования и заданном элементе памяти.
- Построение комбинационной схемы автомата.
- Синтез элементов памяти.
- Построение схем без риска.
Практические занятия:
Подготовка к выполнению курсового проекта – синтез цифрового автомата с памятью.
Литература
Угрюмов Е.П. Цифровая схемотехника. - СПб.: БХВ-Санкт-Петербург 2004. – 800с. Третье изд. (БХВ-СПб), 2011, 812 с.
Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы). – 2-е изд., перераб. И доп. –Л.:Энергия, Ленингр. отделение, 1979. – 232 с, ил.