Рабочая программа учебной дисциплины теория автоматов



Скачать 129.12 Kb.
Дата20.12.2012
Размер129.12 Kb.
ТипРабочая программа
Санкт-Петербургский государственный политехнический университет









УТВЕРЖДАЮ
Декан факультета разработчика
_______________В.А. Лопота
"____" ________ 2009 г.



Вводится в действие с "____" ________ 2009 г.



РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ



теория автоматов





Составлена кафедрой “Телематика ”



для студентов специальности

230101.65 – Вычислительные машины, комплексы, системы и сети





Форма обучения - очная


Автор:








Профессор, к.т.н.

_______________

Курочкин М.А.



"____" ________ 2009 г

Санкт-Петербург

2009 г.


Цели и задачи изучения дисциплины


  1. Знание основ формальных языков и типовых моделей, используемых для описания управляющих автоматов.

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

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




  1. Место дисциплины в рабочем учебном плане


Дисциплина изучается в течение шестого и седьмогосеместров и относится к специальным дисциплинам федерального компонента (СД.07).
Изучение дисциплины базируется на знаниях, получаемых студентами из курсов "Информатика", "Схемотехника ЭВМ", «Дискретная математика».

Готовит студентов к изучению последующих общепрофессиональных и специальных дисциплин: “Организация ЭВМ и систем”, “Микропроцессорные системы”, “Периферийные устройства” “Архитектура вычислительных систем”.
3. Распределение объема учебной дисциплины по видам учебных занятий и формы контроля
Форма обучения - очная



Виды занятий и формы контроля

Объем по семестрам




6-й сем.

7-й сем.

Лекции (Л), час.

34




Лабораторные занятия (ЛЗ), час.

34

34

Курсовые проекты (КП), шт.




1

Самостоятельная работа (СР), час.

17

34

Зачеты, (З), шт.

1

1

Экзамены, (Э), шт.

1




Общая трудоемкость дисциплины составляет по ГОС ВПО /РПД: 200 / 204 часов.



4. Содержание дисциплины
4.1. Разделы дисциплины и виды занятий




Разделы дисциплины по ГОС

(дидактические единицы ГОС)

Раздел дисциплины по РПД

Объемы занятий, часов

Л

ЛЗ


СР

1


Автоматы и формальные языки; концепция порождения и распознавания; классификация языков по Хомскому;

Автоматы и формальные языки; концепция порождения и распознавания; классификация языков по Хомскому;

6

4

4

2

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

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

8

16

12

3

Модель дискретного преобразователя В.М.Глушкова; абстрактный синтез; получение не полностью определенного автомата.

Модель дискретного преобразователя В.М.Глушкова; абстрактный синтез; получение не полностью определенного автомата.

8

6

14

4

Структурный синтез; состояния элементов памяти; кодирование состояний синхронного и асинхронного автомата.

Структурный синтез; состояния элементов памяти; кодирование состояний синхронного и асинхронного автомата.

8

12

12

5

Явление риска логических схем; построение комбинационной схемы автомата; микропрограммирование.

Явление риска логических схем; построение комбинационной схемы автомата; микропрограммирование.

7

8

8

6

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

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

6

12

10

7

Проблемы и перспективы автоматизации проектирования.

Проблемы и перспективы автоматизации проектирования.

8

10

8

Итого


Трудоемкость по ГОС 170 час.


Трудоемкость РПД 187 час.


51 час.

68 час.

68 час.


4.2 Содержание разделов дисциплины
1. Автоматы и формальные языки; концепция порождения и распознавания; классификация языков по Хомскому.

Введение. Цели и задачи курса. рассмотрены основные понятия теории алгоритмов, формальных языков, грамматик и автоматов; рассмотрены формальные модели алгоритмов, дается классификация формальных грамматик, описаны используемые в практике программирования алгоритмы преобразования грамматик и синтеза автоматов. Классификация формальных грамматик. Иерархия Хомского формальных языков.
2. Порождающие грамматики; распознаватели: машина Тьюринга, магазинный автомат, сеть Петри, конечный автомат; коллективы автоматов; регулярные языки и конечные автоматы.

Операторы регулярных выражений. Регулярные выражения и шаблоны. Использование шаблонов VHDL. Языки регулярных выражений и шаблонов. Построение регулярных выражений по шаблонам. Построение регулярного выражения по ДКА. Алгоритм преобразования регулярных выражений в ДКА. Теорема Клини. Лексический анализ. Применение регулярных выражений для решения задач лексического анализа. Алгебра Клини регулярных выражений. Основные законы алгебры Клини. Определение автомата с магазинной памятью (МПА). Вычисления МПА. Языки МПА. Допустимость по заключительному состоянию и по пустому магазину. Эквивалентность двух определений допустимости МПА. Преобразование кс-грамматики в МПА. Построение кс-грамматики по МПА. Детерминированные МПА (ДМПА). Соотношение между регулярными языками, кс-языками и языками ДМПА. Синтаксис языка VHDL.
3. Модель дискретного преобразователя В.М.Глушкова; абстрактный синтез; получение не полностью определенного автомата.

Детерминированные конечные автоматы (ДКА). Диаграммы Мура (системы переходов). Вычисления ДКА. Язык ДКА. Недетерминированные конечные автоматы (НКА). Язык НКА. Теорема о детерминизации НКА. Пример экспоненциального увеличения размеров автомата при детерминизации. Конечные автоматы с пустыми переходами. Операции над конечными автоматами. Эквивалентность и минимизация конечных автоматов. Проверка эквивалентности состояний. Алгоритмы минимизации ДКА.
4. Структурный синтез; состояния элементов памяти; кодирование состояний синхронного и асинхронного автомата.

Классификация триггеров. Логическая структура триггера, синхронизируемого перепадом. Таблица режимов, анализ работы. Триггерные устройства RS, D,T, JK типа. Таблицы управления триггерами различного типа. Обоснование приоритетности асинхронных установок. Временные характеристики переключения, метастабильность триггеров. Дается понятие совмещенного автомата и способы его представления. Рассматриваются методы канонического синтеза структурных автоматов. Приводятся примеры синтеза памяти структурного автомата на базе RS-, Т- и D-триггеров.
5. Явление риска сбоев логических схем; построение комбинационной схемы автомата; микропрограммирование.

способы представления автоматов: теоретико-множественное, графовое, табличное и матричное, понятия реакции автомата и эквивалентных автоматов. Приводятся методы взаимного эквивалентного преобразования автоматов. Приводятся общие сведения о микропрограммном управлении, понятия микрокоманды, микрооперации, микропрограммы, способы представления микропрограмм в виде граф-схем алгоритмов (ГСА) , формул переходов, матричных и логическим схем алгоритмов. Приводятся методы разметки ГСА и правила построения по ним автоматов Мили и Мура.
6. Проблема отражения времени при проектировании: синхронные, асинхронные и апериодические схемы.

Тактирование в цифровых устройствах. Требования к цепям синхронизации. Определение максимальной производительности устройства. Введение конвейеризации. Устройства PLL. Организация обмена данными в различных тактовых доменах. Правила проектирования.

7. Проблемы и перспективы автоматизации проектирования.

Средства автоматизации проектирования цифровых управляющих автоматов. Редактор State Machine Editor. Оптимизация автоматов.

5. Лабораторный практикум


  1. Синтез и исследование автомата без памяти на физической и имитационной моделях (разделы 1, 2,);

  2. Исследование элементной базы построения автоматов с памятью (раздел 2);

  3. Синтез и исследование конечного автомата на физической и имитационной моделях (раздел 3);

  4. Использование языка VHDL для описания конечного автомата (раздел 2);

  5. Разработка управляющих автоматов для арифметических преобразователей (умножающих и делительных устройств) (раздел 3, 4);

  6. Разработка и исследование управляющего автомата ШИМ (разделы 4);

  7. Разработка управляющего автомата контроллера клавиатуры и устройства динамической индикации (разделы 5, 6);

  8. Разработка управляющего автомата устройства уплотнения данных на базе FIFO с различными тактовыми доменами (раздел 6);

  9. Разработка и исследование битового процессора (раздел 5);


6. Практические занятия
Не предусмотрены.
7. Курсовой проект (работа)
Разработка специализированного вычислительного устройства со сложным управляющим автоматом. Получение знаний по возможностям и особенностям использования систем автоматизации проектирования сложных цифровых устройств и систем и умения использовать специализированные языки Hardware Description Language для формального синтеза. Получение навыков работы по программированию внутренней логической структуры.
8. Учебно-методическое обеспечение дисциплины
8.1. Рекомендуемая литература

Основная:



1. Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. Изд. дом "Вильямс", 2002, 527 с.

2. Немудров В. Мартин Г. Системы на кристалле. Проблемы проектирования и развития. «Мир», 2007.

3. Антонов А.П. Язык описания цифровых устройств AlteraHDL, М.:, Радио-Софт, 2003- 224 с.

Дополнительная:





  1. Антонов А.П. и др. Структурный синтез цифровых устройств. Учебное пособие - СПб.: СПбГТУ, 1997.

8.2. Технические средства освоения дисциплины


  1. Комплект презентаций по темам, общим объемом 432 слайда..

  2. Комплект слайдов по работе со средствами автоматизации проектирования.


9. Материально-техническое обеспечение дисциплины

Работы проводятся в лабораториях:

  • микросхемотехники на стендах, обеспечивающих возможность оперативной реализации исследуемых устройств на базе СПИС ПЛ семейства Cyclone II при использовании в качестве средств наблюдения и контроля осциллографов и встроенных средств отладки;

  • автоматизации проектирования цифровых устройств при использовании САПР Quartus II и лабораторных отладочных плат UP1 и Altera Nios II Cyclone II Development Kit.


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

Выполнение требований ГОС ВПО в рабочей программе учебной дисциплины подтверждаю:



Разработчик РПД

Заведующий кафедрой “Телематика”

___________ Заборовский В.С.

"____" ________ 2009 г.


Похожие:

Рабочая программа учебной дисциплины теория автоматов iconРабочая программа дисциплины теория автоматов для подготовки дипломированных специалистов по направлению
Рабочая программа обсуждена на заседании кафедры Вычислительной техники “ ” 2002г., протокол №
Рабочая программа учебной дисциплины теория автоматов iconРабочая программа учебной дисциплины «История и теория адвокатуры» «History and Theory of the Bar»
Требования к подготовленности обучающегося к освоению содержания учебной дисциплины
Рабочая программа учебной дисциплины теория автоматов iconУчебная программа Дисциплины б6 «Теория автоматов и формальных языков»
Целью преподавания дисциплины «Теория автоматов и формальных языков» является подготовка специалистов к деятельности в сфере разработки,...
Рабочая программа учебной дисциплины теория автоматов iconРабочая программа Дисциплины «Теория автоматов»
Целью данной дисциплины является ознакомление студентов технических специальностей с арифметическими и логическими основами проектирования...
Рабочая программа учебной дисциплины теория автоматов iconРабочая программа Дисциплины «Теория автоматов»
Целью данной дисциплины является ознакомление студентов технических специальностей с арифметическими и логическими основами проектирования...
Рабочая программа учебной дисциплины теория автоматов iconРабочая программа учебной дисциплины «теория систем и системный анализ» Направление 080800 Прикладная информатика
Рабочая программа предназначена для преподавания дисциплины блока ен студентам очной формы обучения специальности 080801 прикладная...
Рабочая программа учебной дисциплины теория автоматов iconРабочая программа учебной дисциплины б в. 10 Теория и история искусств трудоемкость

Рабочая программа учебной дисциплины теория автоматов iconРабочая Программа учебной дисциплины б в. 01 Теория языка (часть I) Трудоемкость (в зачетных единицах) 3

Рабочая программа учебной дисциплины теория автоматов iconРабочая программа учебной дисциплины «информатика» очная Форма обучения (очная, очно-заочная)
Рабочая программа учебной дисциплины «Информатика» предназначена для подготовки инженеров по специальности 250900 «Химическая технология...
Рабочая программа учебной дисциплины теория автоматов iconРабочая программа дисциплины теория автоматов и формальных языков направление подготовки
Уметь: строить формальные грамматики, деревья вывода, распознающие автоматы; анализировать формальные языки
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org