МИНОБРНАУКИ РОССИИ
федеральное государственное бюджетное образовательное учреждение высшего образования
«Алтайский государственный университет»

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

рабочая программа дисциплины
Закреплена за кафедройКафедра вычислительной техники и электроники
Направление подготовки09.03.01. Информатика и вычислительная техника
Форма обученияОчная
Общая трудоемкость5 ЗЕТ
Учебный план09_03_01_ИиВТ-4-2019
Часов по учебному плану 180
в том числе:
аудиторные занятия 72
самостоятельная работа 81
контроль 27
Виды контроля по семестрам
экзамены: 4

Распределение часов по семестрам

Курс (семестр) 2 (4) Итого
Недель 17
Вид занятий УПРПДУПРПД
Лекции 36 36 36 36
Лабораторные 36 36 36 36
Сам. работа 81 81 81 81
Часы на контроль 27 27 27 27
Итого 180 180 180 180

Программу составил(и):
к.ф.-м.н., доцент, Калачев А.В.

Рецензент(ы):
к.ф.-м.н., доцент, Рудер Д.Д.

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

разработана в соответствии с ФГОС:
Федеральный государственный образовательный стандарт высшего образования по направлению подготовки 09.03.01 ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА (уровень бакалавриата) (приказ Минобрнауки России от 12.01.2016г. №5)

составлена на основании учебного плана:
09.03.01 Информатика и вычислительная техника
утвержденного учёным советом вуза от 25.06.2019 протокол № 9.

Рабочая программа одобрена на заседании кафедры
Кафедра вычислительной техники и электроники

Протокол от 26.06.2019 г. № 69/18-19
Срок действия программы: 2019-2020 уч. г.

Заведующий кафедрой
д.т.н., Седалищев Виктор Николаевич, проф., зав. кафедрой "Вычислительной техники и электроники"


Визирование РПД для исполнения в очередном учебном году

Рабочая программа пересмотрена, обсуждена и одобрена для
исполнения в 2019-2020 учебном году на заседании кафедры

Кафедра вычислительной техники и электроники

Протокол от 26.06.2019 г. № 69/18-19
Заведующий кафедрой д.т.н., Седалищев Виктор Николаевич, проф., зав. кафедрой "Вычислительной техники и электроники"


1. Цели освоения дисциплины

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

Задачами дисциплины является изучение понятийного аппарата дисци-плины, основных теоретических положений и методов, привитие навыков применения теоретических знаний для решения практических задач.

2. Место дисциплины в структуре ООП

Цикл (раздел) ООП: Б1.В.ДВ.04

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

СПК-3 способностью осознавать сущность и значение информации в развитии современного общества; владеть основными методами, способами и средствами получения, хранения, переработки информации
В результате освоения дисциплины обучающийся должен
3.1.Знать:
3.1.1.- основные исторические вехи развития теории автоматов;
- основные классы автоматов и их свойства;
- способы задания цифровых автоматов, в том числе на языках регуляр-ных выражений алгебры событий и операторных схем алгоритмов;

3.2.Уметь:
3.2.1.- выбирать требуемые для решения конкретной задачи классы автоматов
с учетом их свойств;
- строить и минимизировать конечный автомат по условиям предлагае-мой задачи;
- использовать методы синтеза цифровых автоматов для построения распознавателей и преобразователей и систем логического управления;
- разрабатывать автоматы для решения прикладных задач.
3.3.Иметь навыки и (или) опыт деятельности (владеть):
3.3.1.- навыками по применению различных методов построения автоматов;
- навыками по применению различных методов минимизации автоматов;
- навыками по синтезу и анализу структурных схем автоматов;
- навыками по организации и проведению экспериментов с автоматами.

4. Структура и содержание дисциплины

Код занятия Наименование разделов и тем Вид занятия Семестр Часов Компетенции Литература
Раздел 1. Тема 1. Введение в теорию автоматов.
1.1. Становления теории автоматов. Понятие «автомат» и «конечный автомат». Классическими задачами теории конечных автоматов. Определение абстрактного автомата. Функциональная схема абстрактного ав-томата. Примеры задания абстрактного автомата. Классификация автоматов. Автоматы Мили и Мура. Функциональная схема С-автомата. Функциональная схема порождающего автомата. Функциональная схема распознающего авто-мата. Лекции 4 4 Л1.2, Л2.2
1.2. Классификация способов задания автоматов. Таблич-ный способ задания автоматов. . Матричный способ задания автоматов. Гра-фический способ задания автоматов. Примеры автоматных моделей: простей-шая ячейка памяти , модель простейшего трехразрядного счетчика, модель ав-томата по продаже напитков. Лекции 4 4 Л1.1, Л2.2
Раздел 2. Основной раздел
2.1. Эквивалентность внутренних состояний абстрактного автомата. Минимизация абстрактного автомата. Алгоритмы минимизации ав-томата Мили и автомата Мура. Эквивалентность автоматов Мура и Мили. Пе-реход от автомата Мура к автомату Мили. Переход от автомата Мили к авто-мату Мура. Лекции 4 4 Л1.2, Л2.2
2.2. Связность и достижимость автоматов. Понятие ком-позиции автоматов. Последовательное и параллельное соединение автоматов. Формы параллельного соединения автоматов. Лекции 4 4 Л1.1, Л2.2
2.3. Понятие алфавитного оператора. Признаки автомат-ности алфавитного оператора. Процедура преобразования алфавитного опера-тора в автоматный. Построение автоматов по автоматному оператору. Пример построение автоматов типа Мили по автоматному оператору. Пример по-строения автомата типа Мура по автоматному оператору. Лекции 4 4 Л1.2, Л2.2
2.4. Функции алгебры логики (ФАЛ). Способы задания ФАЛ: табличный, аналитический, числовой. геометрический. Минимизация функций алгебры-логики : карты Карно, метод неопределенных коэффициен-тов, метод Квайна, метод Квайна-Мак-Класки. Функции алгебры логики (ФАЛ). Способы задания ФАЛ: табличный, аналитический, числовой. геометрический. Минимизация функций алгебры-логики : карты Карно, метод неопределенных коэффициен-тов, метод Квайна, метод Квайна-Мак-Класки. Лекции 4 4 Л1.1, Л2.2
2.5. Комбинационные логические схемы (КЛС). Характе-ристики КЛС. Построение элементарных автоматов на базе триггеров. Лекции 4 2 Л1.2, Л2.2
2.6. Каноническая модель структурного автомата. Кано-ническая модель для автомата Мили. Алгоритм структурного синтеза автомата в рамках канонической модели. Гонки в автоматах. Лекции 4 2 Л1.1, Л2.2
2.7. Декомпозиция устройств обработки цифровой ин-формации. Управляющие автоматы. Принцип действия управляющего автома-та с хранимой в памяти логикой и микропрограммное управление. Управляющие автоматы с «жёсткой логикой». Граф - схемы микропрограммных автоматов. Синтез микропрограммных автоматов по граф - схеме алгоритма. Декомпозиция устройств обработки цифровой ин-формации. Управляющие автоматы. Принцип действия управляющего автома-та с хранимой в памяти логикой и микропрограммное управление. Управляющие автоматы с «жёсткой логикой». Граф - схемы микропрограммных автоматов. Синтез микропрограммных автоматов по граф - схеме алгоритма. Лекции 4 0 Л1.2, Л2.2
2.8. Определение формального языка. Типа грамматик: порождающие и распознающие. Определение автомата-распознавателя. Авто-матные и неавтоматные языки. Примеры автоматов-распознавателей. Лекции 4 1 Л1.1, Л2.2
2.9. Понятие эквивалентности автоматов- распознавателей. Общая структура синхронной композиции двух конечных автоматов. Проверка с помощью синхронной композиции двух конечных ав-томатов распознавателей на их эквивалентность. Алгоритм минимизация автоматов-распознавателей. Лекции 4 1 Л1.2, Л2.2
2.10. Определение недетерминированного автомата-распознавателя. Отличия детерминированного автомата-распознавателя от не-детерминированного автомата-распознавателя. Переход от недетерминиро-ванного автомата к детерминированному. Лемма о накачке (лемма о разраста-нии). Лекции 4 1 Л2.1, Л1.1
2.11. Регулярные множества. Операции над регулярными множествами: объединение, конкатенация, итерация. Задание регулярных множеств. Понятие регулярного языка. Понятие регулярного выражения. Задание регулярного выражения. Примеры регулярных выражения. Теорема Клини. Построение регулярного выражении, описывающего язык, допускае-мым автоматом-распознавателем. Посторенние автомата-распознавателя, допускающий язык, описываемый заданным регулярным выражением. Лекции 4 0 Л1.2, Л2.2
2.12. Назначение лексического анализатора. Понятие лек-семы. Грамматики и распознавателя лексического анализа. Основные методы лексического анализа. Взаимодействие лексического и синтаксического ана-лизаторов. Понятие токена, шаблона и лексемы. Лексические ошибки. Архи-тектура лексического анализатора. Лекции 4 1 Л1.1, Л2.2
2.13. Определение формальной грамматики. Задание формального языка. Порождающая и распознающая грамматики. Виды поро-ждающих грамматик. Примеры грамматик. Лекции 4 1 Л2.1, Л1.2
2.14. Задание Грамматики Хомского . Классификация грамматик Хомского. Грамматики общего вида – тип 0. Контекстно-зависимые грамматики – тип 1. Контекстно-свободные грамматики – тип 2. Регулярные грамматики – тип 3. Соотношения между типами грамматик. Рас-познающие устройства для грамматик Хомского Лекции 4 1 Л1.1, Л2.2
2.15. Организация автомата с магазинной памятью. Опе-рации автомата с магазинной памятью. Связь между грамматиками и автома-тами с магазинной памятью. LL(1) – грамматики. Лекции 4 1 Л1.2, Л2.2
2.16. Синтаксический разбор и синтаксический анализа-тор. Классификация методов синтаксического разбора. Последовательность разбора. Нисходящий и восходящий разборы. Лекции 4 1 Л1.1, Л2.2
2.17. Способы задания абстрактных конеч-ных автоматов. Составить таблицу переходов и выходов, матрицу переходов и граф автомата для автомата с одним входом и одним выходом. Лабораторные 4 4 Л2.1, Л1.2
2.18. Композиция автоматов. Используя данные элементарных автоматов строятся последовательны и параллельные композиции различных форм. Лабораторные 4 4 Л1.1, Л2.2
2.19. Функции алгебры логики и способы их задания. Лабораторные 4 4 Л2.1, Л1.2
2.20. Канонический метод структурного синтеза конечных автоматов. Лабораторные 4 4 Л1.1, Л2.2
2.21. Автоматы-распознаватели. Автомат-ные языки. Примеры автоматов-распознавателей. Лабораторные 4 4 Л2.1, Л1.2
2.22. Недетерминированные автоматы-распознаватели Лабораторные 4 4 Л1.1, Л2.2
2.23. Лексический анализатор. Лабораторные 4 4 Л2.1, Л1.2
2.24. Грамматики Хомского. Лабораторные 4 4 Л1.1, Л2.2
2.25. Синтаксический анализатор . Лабораторные 4 4 Л2.1, Л1.2
2.26. Подготовка к лекции, под-готовка к практическому занятию Сам. работа 4 8 Л1.1, Л2.2
2.27. Подготовка к лекции, под-готовка к практическому занятию Сам. работа 4 8 Л2.1, Л1.2
2.28. Подготовка к лекции, подготовка к практическому занятию Сам. работа 4 8 Л1.1, Л2.2
2.29. Подготовка к лекции, подготовка к практическому занятию Сам. работа 4 8 Л2.1, Л1.2
2.30. Сам. работа 4 8 Л1.1, Л2.2
Раздел 3. Заключительный этап
3.1. Подготовка к лекции, подготовка к практическому занятию Сам. работа 4 8 Л2.1, Л1.2
3.2. Подготовка к лекции, подготовка к практическому занятию Сам. работа 4 8 Л1.1, Л2.2
Раздел 4. Подготовительный этап
4.1. Подготовка к лекции, подготовка к практическому занятию Сам. работа 4 12 Л2.1, Л1.2
4.2. Подготовка к лекции, подготовка к практическому занятию Сам. работа 4 13 Л1.1, Л2.2
Раздел 5. Основной раздел
Раздел 6. Заключительный этап
6.1. Аттестация Экзамен 4 27 Л2.1, Л1.2, Л1.1, Л2.2

5. Фонд оценочных средств

5.1. Контрольные вопросы и задания для проведения текущего контроля и промежуточной аттестации по итогам освоения дисциплины
Процедуры оценивания знаний, умений, навыков, характеризующих этапы формирования компетенций, изложены в методических рекомендациях по изучению дисциплины «Теория автоматов», в которые входят методические указания для обучающихся по освоению дисциплины, методические рекомендации для самостоятельной работы студентов.
5.2. Темы письменных работ для проведения текущего контроля (эссе, рефераты, курсовые работы и др.)
Не требуется
5.3. Фонд оценочных средств для проведения промежуточной аттестации
ФОС приведен в Приложении

6. Учебно-методическое и информационное обеспечение дисциплины

6.1. Рекомендуемая литература
6.1.1. Основная литература
Авторы Заглавие Издательство, год Эл. адрес
Л1.1 Ю. Г. Карпов Теория автоматов: учеб. для вузов: СПб. : Питер, 2002
Л1.2 Хопкрофт, Джон Введение в теорию автоматов, языков и вычислений: 2-е изд.- М. : [Издат. дом] Вильямс,, 2002
6.1.2. Дополнительная литература
Авторы Заглавие Издательство, год Эл. адрес
Л2.1 Шевелев Ю.П. Дискретная математика: учеб. пособие для вузов СПб.: Лань // ЭБС "Лань", 2008 e.lanbook.com
Л2.2 Р. Г. Бухараев Вероятностные автоматы: Казань : Изд-во Казан. ун-та,, 1977
6.2. Перечень ресурсов информационно-телекоммуникационной сети "Интернет"
6.3. Перечень программного обеспечения
Open Office – Условия использования по ссылке http://www.openoffice.org/license.html
LibreOffice
Условия использования: https://ru.libreoffice.org/about-us/license/
7-zip
Условия использования: https://www.7-zip.org/license.txt
Acrobat Reader
Условия использования: http://wwwimages.adobe.com/content/dam/Adobe/en/legal/servicetou/Acrobat_com_Additional_TOU-en_US-20140618_1200.pdf
Mozila FireFox
Условия использования: https://www.mozilla.org/en-US/about/legal/eula/
Chrome
Условия использования: http://www.chromium.org/chromium-os/licenses
Microsoft Windows
6.4. Перечень информационных справочных систем
1 Федеральная служба государственной статистики РФ [Электронный ресурс]. - Электронные данные. - Режим доступа: http://www.gks.ru/.
2 Федеральный портал по научной и инновационной деятельности [Электронный ресурс]. -Электронные данные. - Режим доступа: http://www.sci-innov.ru/.
3 Научная и учебно-методическая литература [Электронный ресурс]. - Электронные данные. - Режим доступа: http://www.intuit.ru.
4 Научный журнал «Вестник Российской академии естественных наук» [Электрон-ный ресурс]. - Электронные данные. - Режим доступа: http://www.ras.ru/publishing/rasherald/rasherald_archive.aspx.
5 Научный журнал «Интеграл» [Электронный ресурс]. - Электронные
данные. – Режим доступа: http://www.portalnano.ru/read/databases/publication/journal_integral.
6 Научный журнал «Инновации» [Электронный ресурс]. - Электронные данные. – Режим доступа: http://ojs.innovjoum.ru/index.php/innov
7 Научный журнал «Информатика и системы управления» [Электронный ресурс]. – Электронные данные. - Режим доступа: http://ics.khstu.ru/
8 Научный журнал «Информационные системы и технологии» [Электронный ре-сурс]. - Электронные данные. - Режим доступа: http://gu-unpk.ru/science/joumal/isit
9 Научный журнал «Информационные технологии» [Электронный ресурс]. - Элек-тронные данные. - Режим доступа: http://novtex.ru/IT/
10 Научный журнал «Нейрокомпьютеры: разработка, применение» [Электронный ре-сурс]. - Электронные данные. – Режим доступа: http://www.radiotec.ru/catalog.php?cat=jr7
11 Научный журнал «Программные продукты и системы» [Электронный ресурс]. - Электронные данные. – Режим доступа: http://www.swsys.ru/
Электронная библиотечная система Алтайского государственного университета (http://elibrary.asu.ru/)

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

Аудитория Назначение Оборудование
Помещение для самостоятельной работы помещение для самостоятельной работы обучающихся Компьютеры, ноутбуки с подключением к информационно-телекоммуникационной сети «Интернет», доступом в электронную информационно-образовательную среду АлтГУ
Учебная аудитория для проведения занятий лекционного типа, занятий семинарского типа (лабораторных и(или) практических), групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации, курсового проектирования (выполнения курсовых работ), проведения практик Стандартное оборудование (учебная мебель для обучающихся, рабочее место преподавателя, доска)
001вК склад экспериментальной мастерской - помещение для хранения и профилактического обслуживания учебного оборудования Акустический прибор 01021; виброизмеритель 00032; вольтметр Q1202 Э-500; вольтметр универсальный В7-34А; камера ВФУ -1; компьютер Турбо 86М; масспектрометр МРС -1; осциллограф ЕО -213- 2 ед.; осциллограф С1-91; осциллограф С7-19; программатор С-815; самописец 02060 – 2 ед.; стабилизатор 3218; терц-октавный фильтр 01023; шкаф вытяжной; шумомер 00026; анализатор АС-817; блок 23 Г-51; блок питания "Статрон" – 2 ед.; блок питания Ф 5075; вакуумный агрегат; весы; вольтметр VM -70; вольтметр В7-15; вольтметр В7-16; вольтметр ВУ-15; генератор Г-5-6А; генератор Г4-76А; генератор Г4-79; генератор Г5-48; датчик колебаний КВ -11/01; датчик колебаний КР -45/01; делитель Ф5093; измеритель ИМП -2; измеритель параметров Л2-12; интерферометр ИТ 51-30; источник "Агат" – 3 ед.; источник питания; источник питания 3222; источник питания ЭСВ -4; лабораторная установка для настройки газовых лазеров; лазер ЛГИ -21; М-кальк-р МК-44; М-калькул-р "Электроника"; магазин сопротивления Р4075; магазин сопротивления Р4077; микроскоп МБС -9; модулятор МДЕ; монохроматор СДМС -97; мост переменного тока Р5066; набор цветных стекол; насос вакумный; насос вакуумный ВН-01; осциллограф С1-31; осциллограф С1-67; осциллограф С1-70; осциллограф С1-81; осциллоскоп ЕО -174В – 2 ед.; пентакта L-100; пирометр "Промень"; пистонфон 05001; преобразователь В9-1; прибор УЗДН -2Т; скамья оптическая СО 1м; спектограф ДФС -452; спектограф ИСП -51; стабилизатор 1202; стабилизатор 3217 – 4 ед.; стабилизатор 3218; стабилизатор 3222 – 3 ед.; станок токарный ТВ-4; усилитель мощности ЛВ -103 – 4 ед.; усилитель У5-9; центрифуга ВЛ-15; частотомер Ч3-54А; шкаф металлический; эл.двигатель; электродинамический калибратор 11032
202С библиотека (читальный зал) - помещение для самостоятельной работы Учебная мебель на 53 посадочных места; компьютеры с подключением к информационно-телекоммуникационной сети «Интернет», доступом к электронной информационно-образовательной среде АлтГУ; ноутбуки (по запросу)

8. Методические указания для обучающихся по освоению дисциплины

Не требуются