Закреплена за кафедрой | Кафедра вычислительной техники и электроники |
---|---|
Направление подготовки | 09.03.01. Информатика и вычислительная техника |
Профиль | Информатика и вычислительная техника |
Форма обучения | Очная |
Общая трудоемкость | 3 ЗЕТ |
Учебный план | 09_03_01_ИиВТ-1-2019 |
|
|
Распределение часов по семестрам
Курс (семестр) | 2 (4) | Итого | ||
---|---|---|---|---|
Недель | 19 | |||
Вид занятий | УП | РПД | УП | РПД |
Лекции | 18 | 18 | 18 | 18 |
Практические | 18 | 18 | 18 | 18 |
Сам. работа | 72 | 72 | 72 | 72 |
Итого | 108 | 108 | 108 | 108 |
Визирование РПД для исполнения в очередном учебном году
Рабочая программа пересмотрена, обсуждена и одобрена для
исполнения в 2019-2020 учебном году на заседании
кафедры
Кафедра вычислительной техники и электроники
Протокол от 26.06.2019 г. № 69/18-19
Заведующий кафедрой д.т.н., Седалищев Виктор Николаевич, проф., зав. кафедрой "Вычислительной техники и электроники"
1.1. | Цели освоения дисциплины – дать студенту систематические знания и навыки в области теории автоматов, теории формальных языков и грамматик. Задачами дисциплины является изучение понятийного аппарата дисци-плины, основных теоретических положений и методов, привитие навыков применения теоретических знаний для решения практических задач. |
---|
Цикл (раздел) ООП: Б1.В.01 |
ПК-2 | Способен осуществлять концептуальное, функциональное и логическое проектирование систем среднего и крупного масштаба и сложности; |
В результате освоения дисциплины обучающийся должен | |
3.1. | Знать: |
---|---|
3.1.1. | - основные исторические вехи развития теории автоматов; - основные классы автоматов и их свойства; - способы задания цифровых автоматов, в том числе на языках регуляр-ных выражений алгебры событий и операторных схем алгоритмов; |
3.2. | Уметь: |
3.2.1. | - выбирать требуемые для решения конкретной задачи классы автоматов с учетом их свойств; - строить и минимизировать конечный автомат по условиям предлагае-мой задачи; - использовать методы синтеза цифровых автоматов для построения распознавателей и преобразователей и систем логического управления; - разрабатывать автоматы для решения прикладных задач. |
3.3. | Иметь навыки и (или) опыт деятельности (владеть): |
3.3.1. | - навыками по применению различных методов построения автоматов; - навыками по применению различных методов минимизации автоматов; - навыками по синтезу и анализу структурных схем автоматов; - навыками по организации и проведению экспериментов с автоматами. |
Код занятия | Наименование разделов и тем | Вид занятия | Семестр | Часов | Компетенции | Литература |
---|---|---|---|---|---|---|
Раздел 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 | 2 | Л2.1, Л1.2 | |
2.24. | Грамматики Хомского. | Практические | 4 | 2 | Л1.1, Л2.2 | |
2.25. | Синтаксический анализатор . | Практические | 4 | 2 | Л2.1, Л1.2 | |
2.26. | Подготовка к лекции, под-готовка к практическому занятию | Сам. работа | 4 | 3 | Л1.1, Л2.2 | |
2.27. | Подготовка к лекции, под-готовка к практическому занятию | Сам. работа | 4 | 3 | Л2.1, Л1.2 | |
2.28. | Подготовка к лекции, подготовка к практическому занятию | Сам. работа | 4 | 3 | Л1.1, Л2.2 | |
2.29. | Подготовка к лекции, подготовка к практическому занятию | Сам. работа | 4 | 3 | Л2.1, Л1.2 | |
2.30. | Сам. работа | 4 | 12 | Л1.1, Л2.2 | ||
Раздел 3. Заключительный этап | ||||||
3.1. | Подготовка к лекции, подготовка к практическому занятию | Сам. работа | 4 | 12 | Л2.1, Л1.2 | |
3.2. | Подготовка к лекции, подготовка к практическому занятию | Сам. работа | 4 | 12 | Л1.1, Л2.2 | |
Раздел 4. Подготовительный этап | ||||||
4.1. | Подготовка к лекции, подготовка к практическому занятию | Сам. работа | 4 | 12 | Л2.1, Л1.2 | |
4.2. | Подготовка к лекции, подготовка к практическому занятию | Сам. работа | 4 | 12 | Л1.1, Л2.2 | |
Раздел 5. Основной раздел | ||||||
Раздел 6. Заключительный этап |
5.1. Контрольные вопросы и задания для проведения текущего контроля и промежуточной аттестации по итогам освоения дисциплины |
Процедуры оценивания знаний, умений, навыков, характеризующих этапы формирования компетенций, изложены в методических рекомендациях по изучению дисциплины «Теория автоматов», в которые входят методические указания для обучающихся по освоению дисциплины, методические рекомендации для самостоятельной работы студентов. |
5.2. Темы письменных работ для проведения текущего контроля (эссе, рефераты, курсовые работы и др.) |
Не требуется |
5.3. Фонд оценочных средств для проведения промежуточной аттестации |
ФОС приведен в Приложении |
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/) |
Аудитория | Назначение | Оборудование |
---|---|---|
Помещение для самостоятельной работы | помещение для самостоятельной работы обучающихся | Компьютеры, ноутбуки с подключением к информационно-телекоммуникационной сети «Интернет», доступом в электронную информационно-образовательную среду АлтГУ |
Учебная аудитория | для проведения занятий лекционного типа, занятий семинарского типа (лабораторных и(или) практических), групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации, курсового проектирования (выполнения курсовых работ), проведения практик | Стандартное оборудование (учебная мебель для обучающихся, рабочее место преподавателя, доска) |
202С | библиотека (читальный зал) - помещение для самостоятельной работы | Учебная мебель на 53 посадочных места; компьютеры с подключением к информационно-телекоммуникационной сети «Интернет», доступом к электронной информационно-образовательной среде АлтГУ; ноутбуки (по запросу) |
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 |
Не требуются |