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

Вид материала

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

Содержание Цели и задачи дисциплины “Теория автоматов” Основные требования Темы лекционных занятий

Подобный материал:

• Программа сквозной практической подготовки для студентов направления 654600 специальности, 176.46kb.
• Методические указания и контрольные задания для студентов заочников Специальности 230101, 135.39kb.
• Курс лабораторных работ для студентов специальностей 230101 "Вычислительные машины,, 318.37kb.
• Программа-минимум кандидатского экзамена по специальности 05. 13. 15 «Вычислительные, 126.11kb.
• Рабочая программа по дисциплине технические средства информатизации для студентов специальности, 320.99kb.
• Рабочая программа учебной дисциплины микропроцессоры и микропроцессорные системы для, 378.72kb.
• Программа дисциплины ен. Ф. 07. Информатика для студентов специальности 230101 «Вычислительные, 162.52kb.
• Методические указания к лабораторной работе по дисциплине "Сети ЭВМ и средства телекоммуникаций", 315.14kb.
• Рабочая программа, 258.96kb.
• Рабочая программа и общие методические указания для студентов II и III курсов специальности, 212kb.

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

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


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


Утверждаю


Декан ФИСТ

______________В.В.Шишкин


“___” ________ 2007.


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


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

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


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

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

Курс - 2

Семестр -3


Лекций - 34 час

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

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

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

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

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


Ульяновск, 2007


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


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


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

________________2005г.


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

«Вычислительная техника» П.И.Соснин


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


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


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


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


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

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

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

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

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


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


Лекция 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.