Рабочая программа дисциплины «Теория автоматов и формальных языков» Направление подготовки
| Вид материала | Рабочая программа |
- Рабочая программа дисциплины теория автоматов и формальных языков направление подготовки, 146.98kb.
- Теория автоматов и формальных языков составил доцент А. А. Мальцев, 38.01kb.
- Программа дисциплины Формальные языки и автоматы Семестр, 9.45kb.
- Рабочая программа Дисциплины «Теория автоматов» Для студентов специальности 23010065, 57.28kb.
- Рабочая программа дисциплины «Математическая логика и теория алгоритмов» Направление, 175.54kb.
- Рабочая программа учебной дисциплины методология преподавания иностранных языков, 119.54kb.
- Рабочая программа учебной дисциплины «Теория телетрафика» Направление подготовки, 175.5kb.
- Рабочая программа дисциплины «Теория государства и права» пц. Б б. 1 Направление подготовки, 903.23kb.
- Рабочая программа дисциплины «теоретические основы теплотехники» Направление подготовки, 554.69kb.
- Рабочая программа дисциплины «Техническая термодинамитка» Направление подготовки, 804.99kb.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное образовательное учреждение
высшего профессионального образования
«Чувашский государственный университет имени И.Н.Ульянова»
Факультет дизайна и компьютерных технологий
«УТВЕРЖДАЮ»
Проректор по учебной работе
______________ А.Ю. Александров
«______»______________ 20__ г.
РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
«Теория автоматов и формальных языков»
Направление подготовки
231000 Программная инженерия
Профиль подготовки
Разработка программно-информационных систем
Квалификация (степень) выпускника
Бакалавр
Форма обучения
очная
Чебоксары
2011
Рабочая программа основана на требованиях Федерального государственного стандарта высшего профессионального образования по направлению подготовки 231000 Программная инженерия, утвержденного Приказом Минобрнауки 09.11.2009 г. № 542.
Составитель: доцент Желтов П.В. __________________
Рабочая программа рассмотрена и одобрена на заседании обеспечивающей кафедры – компьютерных технологий (протокол № _____ от ___________2010 г.).
Зав. кафедрой: профессор Желтов В.П. ___________________
Рабочая программа согласована с Методической комиссией выпускающего факультета Дизайна и компьютерных технологий.
Председатель комиссии, декан: профессор Желтов В.П. ___________________
СОГЛАСОВАНО:
Зам. начальника УМУ: доцент Харитонов М.Ю. __________________
- Цели освоения дисциплины
Настоящий курс ставит своей целью ознакомление обучаемых с устройством теории формальных языков, а также с основными принципами, методами и алгоритмами синтаксического анализа формальных языков (в т.ч. языков программирования).
В рамках программы приводятся сведения о способах описания формальных языков, моделях вычислений, используемых для представления формальных языков, о задаче синтаксического анализа и методах ее решения и иных приложениях. Рассматриваются проблемы сложности преобразований и неразрешимости ряда задач, связанных с грамматиками и языками.
2. Место дисциплины в структуре ООП бакалавриата
Дисциплина входит в базовую часть математического и естественнонаучного цикла образовательной программы бакалавра. Студент должен уметь использовать основные законы естественно-научных дисциплин для понимания преподаваемой дисциплины, иметь навыки работы с компьютером как средством управления информацией.
Дисциплина является предшествующей для изучения дисциплины «Разработка программирования».
3. Компетенции обучающегося, формируемые в результате освоения дисциплины
Процесс изучения дисциплины направлен на формирование следующих компетенций:
- способность к формализации в своей предметной области с учетом ограничений используемых методов исследования (ПК-2);
- готовность к использованию методов и инструментальных средств исследования объектов профессиональной деятельности (ПК-3);
- умение готовить презентации, оформлять научно-технические отчеты по результатам выполненной работы, публиковать результаты исследований в виде статей и докладов на научно-технических конференциях (ПК-5);
- способность формализовать предметную область программного проекта и разработать спецификации для компонентов программного продукта (ПК-6).
В результате освоения дисциплины обучающийся должен:
- Знать:
- методы синтеза комбинационных схем на логических элементах различной степени интеграции;
- способы задания цифровых автоматов, в том числе на языках регулярных выражений алгебры событий и операторных схем алгоритмов и методы абстрактного синтеза цифровых автоматов на их основе;
- общие методы структурного синтеза автоматов на основе теоремы В.М. Глушкова о структурной полноте;
- методы синтеза операционных и управляющих микропрограммных автоматов с жесткой и программируемой логикой, в том числе на основе использования моделей недетерминированных автоматов;
- Уметь:
- использовать методы синтеза цифровых автоматов для построения распознавателей и преобразователей и систем логического управления;
4. Структура и содержание дисциплины
4.1. Структура дисциплины
Общая трудоемкость дисциплины составляет 6 зачетных единиц, 216 часов.
| № п/п | Раздел дисциплины | Семестр | Неделя семестра | Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах) | Формы текущего контроля успеваемости (по неделям семестра) Форма промежуточной аттестации (по семестрам) | ||||||
| Лекции | Практ. зан. | Лабор. зан. | КСР * | СРС ** | Всего | Из ауд. зан. в интер. форме | |||||
| 1 | Введение. Общие сведения о цифровых автоматах. Классификация и характеристики автоматов | 5 | | 6 | | | | 7 | | | |
| 2 | Абстрактные автоматы и их связь с формальными языками и грамматиками | 5 | | 2 | | | | 7 | | | |
| 3 | Синтез цифровых автоматов без памяти. Синтез комбинационных схем на логических элементах (ЛЭ) разной степени интеграции | 5 | | 2 | | 4 | | 7 | | | |
| 4 | Общая теория конечных цифровых автоматов с памятью. Способы задания автоматов | 5 | | 2 | | 4 | | 7 | | | |
| 5 | Абстрактный синтез конечных цифровых автоматов | 5 | | 2 | | 4 | | 7 | | | |
| 6 | Канонический метод структурного синтеза цифровых автоматов | 5 | | 6 | | 8 | | 8 | | | |
| 7 | Взаимодействие автомата с внешней средой | 5 | | 2 | | | | 8 | | | |
| 8 | Синтез операционных и управляющих микропрограммных автоматов. Принцип микропрограммного управления и обобщенная структура операционных устройств | 5 | | 2 | | | | 8 | | | |
| 9 | Структурная организация и синтез операционных автоматов | 5 | | 2 | | 4 | | 8 | | | |
| 10 | Структурная организация и синтез управляющих микропрограммных автоматов. Заключение | 5 | | 6 | | 8 | | 9 | | | |
| | Итого | | | 32 | | 32 | 4 | 76 | 216 | | Курсовой проект. Экзамен. |
* Контроль самостоятельной работы: аудиторные занятия для проверки самостоятельной работы студентов, приема зачета, проведения текущих консультаций.
** Самостоятельная работа студента, включая курсовой проект, курсовую работу, расчетно-графические работы.
4.2. Содержание лекционных занятий
1. Введение. Общие сведения о цифровых автоматах. Классификация и характеристики автоматов
Автоматы абстрактные и структурные. Автоматы комбинационного действия и автоматы с памятью. Автоматы Мили и Мура. Недетерминированные автоматы. Модель дискретного преобразования В.М. Глушкова, автоматы операционные и управляющие. Микропрограммные автоматы. Автономные автоматы, автоматы без выхода и др. Направление использования моделей конечных цифровых автоматов.
2. Абстрактные автоматы и их связь с формальными языками и грамматиками
Основные понятия формальных языков и грамматик и их классификация по Хомскому. Регулярные языки и автоматные грамматики. Автоматы распознаватели и преобразователи. Машины Тьюринга, магазинные автоматы, конечные автоматы. Автоматы как язык описания законов взаимодействия сложных систем, коллективы автоматов. Сеть Петри как средство моделирования автоматов.
3. Синтез цифровых автоматов без памяти. Синтез комбинационных схем на логических элементах (ЛЭ) разной степени интеграции
Общая задача структурного синтеза комбинационных схем. Синтез комбинационных схем на ЛЭ малой степени интеграции. Синтез комбинационных схем на интегральных схемах средней степени интеграции: на мультиплексорах и дешифраторах. Синтез комбинационных схем на интегральных схемах большой степени интеграции: на программированных логических матрицах и постоянных запоминающих устройствах.
4. Общая теория конечных цифровых автоматов с памятью. Способы задания автоматов
Начальные языки: язык регулярных выражений алгебры событий, язык операторных схем алгоритмов. Автоматные или стандартные языки: таблицы и матрицы переходов и выходов и их аналитическая интерпретация – система канонических уравнений (СКУ) и система выходных функций (СВФ).
5. Абстрактный синтез конечных цифровых автоматов
Абстрактный синтез цифровых автоматов – представление автоматов на стандартном языке на основе задания его на начальном языке. Минимизация автоматов, заданных на стандартном языке.
6. Канонический метод структурного синтеза цифровых автоматов
Основные этапы структурного синтеза цифровых автоматов с памятью. Теорема В.М. Глушкова о структурной полноте. Обобщенные структурные схемы цифровых автоматов с памятью. Представление функционирования цифрового автомата в виде прямой таблицы переходов и выходов. Кодирование внутренних состояний автомата для синхронных и асинхронных автоматов с учетом сложности комбинационных схем и состязаний элементов памяти, учет неиспользованных кодовых групп. Выбор элементов памяти. Построение функций возбуждения элементов памяти и функций выходов цифрового автомата.
7. Взаимодействие автомата с внешней средой
Формирование такта работы автомата. Синхронные, асинхронные и согласованные модели взаимодействия в системе среда-автомат.
8. Синтез операционных и управляющих микропрограммных автоматов. Принцип микропрограммного управления и обобщенная структура операционных устройств
Представление структуры операционных устройств в виде двух взаимодействующих автоматов – операционного и управляющего. Основные понятия микропрограммного управления: микрооперация и управляющие сигналы; логические условия и осведомительные сигналы; микропрограммы и микропрограммирование. Выделение функций операционного и управляющего автоматов. Задача синтеза операционных устройств. ßзык функционального микропрограммирования. Оценка времени выполнения микропрограмм.
9. Структурная организация и синтез операционных автоматов
Структурные элементы операционных автоматов, реализующих его основные функции. Каноническая структура операционного автомата. Функционирование операционных автоматов и обеспечение его устойчивого функционирования. Примеры типовых блоков операционных автоматов на БИС.
10. Структурная организация и синтез управляющих микропрограммных автоматов
Недетерминированные автоматы (НдА) – общий случай конечных цифровых автоматов. Основные понятия и определения НдА. Иерархия входных сигналов и событий, реализуемых в НдА. Основные эквивалентные преобразования НдА: детерминизация, кодирование и минимизация. ßзык операторных схем алгоритмов с параллельными ветвями (ОСАП). Методы формализации алгоритмов управления с параллельными взаимодействующими ветвями. Структурный синтез микропрограммных управляющих автоматов (МПА) с жесткой логикой на основе использования СКУ для детерминированных и недетерминированных автоматов. Структурный синтез МПА с программируемой логикой. Обобщенная структура МПА. Базовые функции управления. Способы адресации и кодирования микрокоманд. Методы реализации многоальтернативных переходов в МПА. Принципы построения систем микропрограммного управления на основе управляющей памяти и нанопамяти. Примеры типового блока микропрограммного управления на БИС.
11. Заключение
Перспективы использования основных положений теории автоматов для построения системного программного обеспечения и систем логического управления.
4.4. Содержание лабораторных занятий
- Синтез комбинационных схем на логических элементах разной степени интеграции.
- Стандартные способы задания цифровых автоматов с памятью.
- Способы построения СКУ и СВФ по ГСА и регулярным выражениям алгебры событий.
- Минимизация автоматов, заданных на стандартном языке.
- Структурный синтез цифровых автоматов, заданных на языке ГСА и таблицах переходов и выходов автомата.
- Структурный синтез операционного автомата для заданного набора операций.
- Детерминизация НдА по модели автомата, заданного на языке ОСАП.
- Построение микропрограмм для МПА с программируемой логикой для структур МПА с естественной и принудительной адресацией.
5. Образовательные технологии
В процессе изучения дисциплины используются:
-раздаточный материал для изучения лекционного материала;
-учебный материал в электронном виде;
-контрольные программы по курсу для подготовки к сдаче семестровой аттестации и экзамена;
-программное обеспечение в соответствии с содержанием дисциплины;
6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины.
6.1. Перечень заданий для самостоятельной работы и проведения текущего контроля.
- Общие сведения о цифровых автоматах. Классификация и характеристики автоматов.
- Абстрактные автоматы и их связь с формальными языками и грамматиками.
- Синтез цифровых автоматов без памяти. Синтез комбинационных схем на логических элементах (ЛЭ) разной степени интеграции.
- Общая теория конечных цифровых автоматов с памятью. Способы задания автоматов.
- Абстрактный синтез конечных цифровых автоматов.
- Канонический метод структурного синтеза цифровых автоматов.
- Взаимодействие автомата с внешней средой.
- Синтез операционных и управляющих микропрограммных автоматов. Принцип микропрограммного управления и обобщенная структура операционных устройств.
- Структурная организация и синтез операционных автоматов.
- Структурная организация и синтез управляющих микропрограммных автоматов.
6. 2. Перечень примерных тем курсовых работ.
- Алгебра композиции автоматов
- Классификация конечных автоматов по свойствам комбинационных частей
- Полная система для однородных автоматов
- Применение модели универсального автомата для решения задач технической диагностики
- Функционирование автомата с изменениями состояний в циклах
6.3. Перечень вопросов к промежуточной аттестации.
1. Понятие конечного автомата, основные определения. Обобщения понятия конечного автомата. Примеры автоматов, описывающих сложение n-разрядных чисел и деление n-разрядных чисел на фиксированное число. Способы задания автомата, канонические уравнения, диаграмма Мура.
2. Автоматная функция. Детерминированная функция, понятие о.д.-функции. Эквивалентность состояний автомата, сильная и слабая эквивалентность автоматов. Пример несовпадения сильной и слабой эквивалентности. Изоморфизм автоматов, приведенный автомат. Теорема о единственности приведенного автомата, эквивалентного данному.
3. Абстрактные автоматы. Проверка эквивалентности состояний автомата, теорема Мура о длине слова, проверяющего эквивалентность состояний автомата и ее следствия. Проверка эквивалентности конечных автоматов. Теорема Мура о длине слова, отличающего конечные автоматы. Достижимость оценки длины слова отличающего конечные автоматы.
4. Эксперименты с автоматами. Простые, кратные и условные эксперименты. Невозможность определения с помощью экспериментов числа состояний автомата и начального состояния автомата. Установочный эксперимент. Теорема об оценке длины установочного эксперимента.
5. Конечные автоматы как акцепторы. Регулярные множества и регулярные выражения. Теорема Клини.
6. Конечные автоматы как сверхакцепторы. Теорема Мак-Нотона.
7. Структурные автоматы, операции суперпозиции и композиции. Схемы в базисе из булевых функций и задержки. Оператор замыкания. Проблема полноты и выразимости. Мощность полных систем автоматов. Класс автоматов с безусловными переходами, полные системы в этом классе.
8. Системы автоматов с операцией суперпозиции, имеющих ограниченное число входов. Полнота системы одноместных автоматов и булевых функций. Полугруппа автомата, связь операций над автоматами с операциями над их полугруппами. Вербальные операции над автоматами. Неполнота системы одноместных групповых автоматов и булевых функций в классе групповых автоматов.
9. Линейные автоматы. Проблема полноты для линейных автоматов относительно суперпозиции.
10. Алгоритмическая неразрешимость проблемы полноты конечных систем автоматов относительно композиции.
11. О мощности множества предполных классов автоматов.
12. Системы автоматов с операцией композиции, содержащие истинностные функции. Разрешимость проблемы полноты таких систем.
7. Учебно-методическое и информационное обеспечение дисциплины
а) основная литература:
1. Автоматы, Сборник статей под редакцией Маккарти и Шеннона, ИЛ, Москва, 1956
2. Бабин Д.Н., Разрешимый случай задачи о полноте автоматных функций, Дискретная математика, том 4, 1992, выпуск 4, с.41-56, Наука, Москва.
3. Бабин Д.Н. О полноте двухместных о.д.-функций относительно суперпозиции, Дискретная
4. Бабин Д.Н., Вербальные подавтоматы и задача полноты, Вестник МГУ, Математика и механика, 1985, N 3, с.82-85.
5. Брауэр В. Введение в теорию конечных автоматов. Перевод с английского под редакцией Ю.И. Журавлева-М. Радио и связь, 1987, 392с.
6. Кудрявцев В.Б., Алешин С.В.,Подколзин А.С. "Введение в теорию конечных автоматов".- М.: Наука, 1985 г.
7. Кудрявцев В.Б., О мощностях множеств предполных классов некоторых функциональных
8. Летичевский А.А., Условия полноты для конечных автоматов, Вычислительная математика и математическая физика, N 4,1961, с.702-710.
математика, том 1, 1989, вып. 4, с. 86-91, Наука, Москва.
9. Савельев А.Я. Прикладная теория цифровых автоматов. Учебник для вузов-М. Высшая школа, 1987, 272с.
10. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1985 г.
систем, связанных с автоматами, ДАН СССР т.151,N3,1963, c.493-496.
б) дополнительная литература:
1. Киносита К., Асада К., Карашу О. Логическое проектирование СБИС – М. Мир, 1988, 309с.
2. Савельев Н.В., Коняхин В.В. Функционально-логическое проектирование БИС.-М. Высшая школа, 1990, 156с.
3. А. Фридман, П.Менон. Теория и проектирование переключательных схем. Москва. Мир. 1978
4. С.З. Кузьмин. Основы теории цифровой обработки радиолокационной информации. Москва. Советское радио. 1974
5. Д.А. Поспелов. Логические методы анализа и синтеза схем. Москва. Энергия. Издание третье, переработанное и дополненное. 1974.
6. Киносита К., Асада К., Карашу О. Логическое проектирование СБИС – М. Мир, 1988, 309с.
7. В. А. Горбатов, А. В. Горбатов, М. В. Горбатова. Теория автоматов: учебник для студентов втузов. Высшая школа. Издательство «АСТ», 2008. 559 с.
8. Нефедов В.Н., Осипова В.А. Курс дискретной математики. М.: Издательство МАИ, 1992.
9. Поликарпова Н.И., Шалыто А.А. Автоматное программирование. СПб.: Питер, 2008. 167 с. УДК 681.3.06.
10. Салпре И. Программирование мобильных устройств на платформе .Net Compact Framework. М.:Вильямс. 2006. – 550 с.
11. Круковский М.Ю. Автоматно-Графовая модель композитного документооборота// Математические машины и системы. – 2005. – № 3. – С. 149с – 163с
12. Казаков М.А., Столяр С.Е. Визуализаторы алгоритмов как элемент технологии преподавания дискретной математики и программирования //Тезисы докладов международной научно-методической конференции "Телематика-2000". СПб.: СПбГИТМО (ТУ), 2000.
13. Г. А. Корнеев, Н. Н. Шамгунов, А. А. Шалыто. Обход деревьев на основе автоматного подхода. Компьютерные инструменты в образовании, 2004, № 3, с 32-37.
14. Новиков Ф.А. Методические рекомендации и указания по разработке, базирующиеся на принципах автоматного программирования. Часть 3. Мобильные системы, 2006
15. Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков, вычислений, 2-е изд.: Пер. с англ. М.: Издательский дом «Вильямс», 2008. 528 с.
8. Материально-техническое обеспечение дисциплины
Для обеспечения данной дисциплины необходимо: лекционная аудитория и компьютерный класс, соответствующие действующим санитарным и противопожарным нормам, оборудованный вычислительными средствами (ПЭВМ).