Рабочая программа

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

Ульяновский государственный технический университет

Утверждаю

Декан ФИСТ

______________

“___” ________ 2007.

Р а б о ч а я п р о г р а м м а

Дисциплины «Теория автоматов»

Для студентов специальности «Вычислительные машины, системы, комплексы и сети»

Факультет - Информационные системы и технологии

Кафедра - Вычислительная техника

Курс - 2

Семестр -3

Лекций - 51 час

Лабораторных работ - ВСЕГО- 130

Практических занятий -аудиторных

Самостоятельных работ -самостоятельных

Курсовой проект -

Экзамен - 3 семестр

Ульяновск, 2007

Рабочая программа составлена на основании решения кафедры «Вычислительная техника» УлГТУ для специальности «Вычислительные машины, системы, комплексы и сети».

Составил: доцент

Рабочая программа обсуждена на заседании кафедры «ВТ»

________________2005г.

Заведующий кафедрой

«Вычислительная техника»

Одобрена методической комиссией ФИСТ

Цели и задачи дисциплины “Теория автоматов”

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

Основные требования

В результате изучения курса студент должен знать:

o  Основные системы счисления, применяемые в ЭВМ и компьютерах, способы перевода из одной системы в другую, кодирование положительных и отрицательных чисел, а также способы представления чисел в ЭВМ и компьютерах,

o  Представление и типы абстрактных автоматов,

o  Синтез структурных автоматов на различных цифровых элементах,

o  Описание функционирования цифровых устройств.

В результате изучения дисциплины студент должен уметь:

o  Переводить числа из одной системы счисления в другую,

o  Составлять таблицы переходов для автоматов Мили, Мура и других типов, представлять графы автоматов,

o  Осуществлять преобразование автоматов и минимизацию абстрактных автоматов,

o  Выполнять канонический синтез структурных автоматов на различных цифровых элементах,

o  Оценивать сложность комбинационной схемы автомата,

o  Разрабатывать алгоритм функционирования цифрового устройства.

Дисциплина “Теория автоматов” является одной из принципиальных в процессе подготовки специалистов специальности «Вычислительные машины, системы, комплексы и сети».

Темы лекционных занятий

Лекция 1. Определение абстрактного автомата, способы задания автоматов: табличный, графический, матричный. Определение синхронного и асинхронного автоматов. 2 часа.

Лекция 2. Автоматы Мили и Мура. Связь между моделями автоматов Мили и Мура. . 2 часа.

Лекция 3. Минимизация полностью определенных автоматов. Алгоритм минимизации. Пример минимизации автоматов Мили и Мура. 2 часа.

Лекция 4. Совмещенная модель автомата (С-автомат). 2 часа.

Лекция 5. Структурный автомат. Композиция элементарных автоматов. Структурный алфавит автомата и автоматное время. Соотношение абстрактного и структурного алфавитов. 2 часа.

Лекция 6. Основы канонического синтеза структурного автомата. Память и комбинационный блок. Теорема о структурной полноте, ограничения в работе схем. 2 часа.

Лекция 7. Представление структурного автомата. Работа структурных автоматов. Синтез комбинационной схемы. 2 часа.

Лекция 8. Абстрактный автомат памяти. Пример функционирования автомата памяти. 2 часа.

Лекция 9. Пример канонического метода структурного синтеза автомата. Функции возбуждения и выходов. Построение логической схемы структурного автомата. 2 часа.

Лекция 10. Синтез автоматов на элементах задержки, триггерах со счетным входом и триггерах с раздельными входами. 4 часа.

Лекция 11. Табличный метод структурного синтеза автомата. Пример синтеза автомата на элементах задержки. 4 часа.

Лекция 12. Графический метод структурного синтеза автомата. Пример синтеза автомата на триггерах со счетным входом. 4 часа.

Лекция 13. Структурный синтез автомата на триггерах с раздельными входами. 4 часа.

Лекция 14. Кодирование состояний автомата. Гонки в автомате. Противогоночное кодирование состояний. Алгоритм развязывания состояний. Пример противогоночного кодирования. 4 часа.

Лекция 15. Кодирование состояний и сложность комбинационной схемы. Оценка сложности схемы. Пример кодирования состояний автомата. 2 часа.

Лекция 16. Алгоритмы функционирования цифровых автоматов. Микропрограммы работы дискретных устройств. Граф-Схемы алгоритмов. Содержательные ГСА. 2 часа.

Лекция 17. Логические схемы алгоритмов функционирования цифровых устройств. Матричные схемы алгоритмов. 2 часа.

Лекция 18. Алгоритмы выполнения арифметических операций на цифровых устройствах. 2 часа.

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

Темы семинарских занятий

Занятие 1. Перевод целых, дробных и совместных чисел из одной системы счисления в другую. 2 часа.

Занятие 2. Автоматное (машинное, компьютерное) представление чисел. . 2 часа.

Занятие 3. Кодирование положительных и отрицательных чисел. Виды кодов, сложение чисел на двоичных сумматорах. 2 часа.

Занятие 4. Построение графов автоматов по таблицам переходов и выходов автоматов Мили и Мура. 2 часа.

Занятие 5. Преобразование автомата Мили в автомат Мура и обратно. Минимизация автоматов. 4 часа.

Занятие 6. Синтез структурного автомата на элементах задержки табличным методом и графическим методом. 4 часа.

Занятие 7. Синтез структурного автомата на триггерах со счетным входом табличным методом и графическим методом. 4 часа.

Занятие 8. Синтез структурного автомата на триггерах с раздельными входами табличным методом и графическим методом. 4 часа.

Занятие 9. Построение содержательной граф-схемы алгоритма выполнения операции деления на цифровом устройстве. 4 часа.

Занятие 10. Преобразование граф-схемы алгоритма операции деления в логическую схему и матричную схему алгоритма. 4 часа.

Литература

1.  Баранов микропрограммных автоматов. «Энергия», Ленинградское отделение, 1974

2.  , Скляров устройства на программируемых БИС с матричной структурой. М. Радио и связь, 1986

3.  Иванов автоматов. Программно-информационный продукт. Свидетельство N874 ОФАП при УОЦ НИТ УлГТУ, 2005.