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

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

рабочая программа дисциплины
Закреплена за кафедройКафедра вычислительной техники и электроники
Направление подготовки09.03.01. Информатика и вычислительная техника
ПрофильИнформатика и вычислительная техника
Форма обученияОчная
Общая трудоемкость3 ЗЕТ
Учебный план09_03_01_ИиВТ-2-2020
Часов по учебному плану 108
в том числе:
аудиторные занятия 42
самостоятельная работа 66
Виды контроля по семестрам
диф. зачеты: 4

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

Курс (семестр) 2 (4) Итого
Недель 19
Вид занятий УПРПДУПРПД
Лекции 18 18 18 18
Практические 24 24 24 24
Сам. работа 66 66 66 66
Итого 108 108 108 108

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

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

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

разработана в соответствии с ФГОС:
Федеральный государственный образовательный стандарт высшего образования по направлению подготовки 09.03.01 Информатика и вычислительная техника (уровень бакалавриата) (приказ Минобрнауки России от 19.09.2017 г. № 929)

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

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

Протокол от 08.06.2020 г. № 79/19-20
Срок действия программы: 2020-2021 уч. г.

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


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

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

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

Протокол от 08.06.2020 г. № 79/19-20
Заведующий кафедрой к.ф.-м.н., Пашнев Владимир Валентинович, доц., зав. кафедрой "Вычислительной техники и электроники" Николаевич, проф., зав. кафедрой "Вычислительной техники и электроники"


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

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

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

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

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

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

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

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

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

Код занятия Наименование разделов и тем Вид занятия Семестр Часов Компетенции Литература
Раздел 1. Тема 1. Введение в теорию автоматов.
1.1. Становления теории автоматов. Понятие «автомат» и «конечный автомат». Классическими задачами теории конечных автоматов. Определение абстрактного автомата. Функциональная схема абстрактного ав-томата. Примеры задания абстрактного автомата. Классификация автоматов. Автоматы Мили и Мура. Функциональная схема С-автомата. Функциональная схема порождающего автомата. Функциональная схема распознающего авто-мата. Лекции 4 2 Л1.2, Л2.2
1.2. Классификация способов задания автоматов. Таблич-ный способ задания автоматов. . Матричный способ задания автоматов. Гра-фический способ задания автоматов. Примеры автоматных моделей: простей-шая ячейка памяти , модель простейшего трехразрядного счетчика, модель ав-томата по продаже напитков. Лекции 4 2 Л1.1, Л2.2
Раздел 2. Основной раздел
2.1. Эквивалентность внутренних состояний абстрактного автомата. Минимизация абстрактного автомата. Алгоритмы минимизации ав-томата Мили и автомата Мура. Эквивалентность автоматов Мура и Мили. Пе-реход от автомата Мура к автомату Мили. Переход от автомата Мили к авто-мату Мура. Лекции 4 2 Л1.2, Л2.2
2.2. Связность и достижимость автоматов. Понятие ком-позиции автоматов. Последовательное и параллельное соединение автоматов. Формы параллельного соединения автоматов. Лекции 4 2 Л1.1, Л2.2
2.3. Понятие алфавитного оператора. Признаки автомат-ности алфавитного оператора. Процедура преобразования алфавитного опера-тора в автоматный. Построение автоматов по автоматному оператору. Пример построение автоматов типа Мили по автоматному оператору. Пример по-строения автомата типа Мура по автоматному оператору. Лекции 4 0 Л1.2, Л2.2
2.4. Функции алгебры логики (ФАЛ). Способы задания ФАЛ: табличный, аналитический, числовой. геометрический. Минимизация функций алгебры-логики : карты Карно, метод неопределенных коэффициен-тов, метод Квайна, метод Квайна-Мак-Класки. Функции алгебры логики (ФАЛ). Способы задания ФАЛ: табличный, аналитический, числовой. геометрический. Минимизация функций алгебры-логики : карты Карно, метод неопределенных коэффициен-тов, метод Квайна, метод Квайна-Мак-Класки. Лекции 4 0 Л1.1, Л2.2
2.5. Комбинационные логические схемы (КЛС). Характе-ристики КЛС. Построение элементарных автоматов на базе триггеров. Лекции 4 1 Л1.2, Л2.2
2.6. Каноническая модель структурного автомата. Кано-ническая модель для автомата Мили. Алгоритм структурного синтеза автомата в рамках канонической модели. Гонки в автоматах. Лекции 4 1 Л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 2 Л2.1, Л1.2
2.18. Композиция автоматов. Используя данные элементарных автоматов строятся последовательны и параллельные композиции различных форм. Практические 4 2 Л1.1, Л2.2
2.19. Функции алгебры логики и способы их задания. Практические 4 2 Л2.1, Л1.2
2.20. Канонический метод структурного синтеза конечных автоматов. Практические 4 2 Л1.1, Л2.2
2.21. Автоматы-распознаватели. Автомат-ные языки. Примеры автоматов-распознавателей. Практические 4 2 Л2.1, Л1.2
2.22. Недетерминированные автоматы-распознаватели Практические 4 2 Л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 6 Л1.1, Л2.2
Раздел 4. Подготовительный этап
4.1. Подготовка к лекции, подготовка к практическому занятию Сам. работа 4 7 Л2.1, Л1.2
4.2. Подготовка к лекции, подготовка к практическому занятию Сам. работа 4 5 Л1.1, Л2.2
Раздел 5. Основной раздел

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. Перечень ресурсов информационно-телекоммуникационной сети "Интернет"
Название Эл. адрес
Э1 Курс в Мудл. Теория автоматов portal.edu.asu.ru
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. Методические указания для обучающихся по освоению дисциплины

Не требуются