Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Рыбинская государственная авиационная технологическая академия им.
Факультет радиоэлектроники и информатики
Кафедра ²Вычислительные системы²
²УТВЕРЖДАЮ²
Декан факультета РЭИ
__________
РАБОЧАЯ ПРОГРАММА
По дисциплине ²Теория автоматов²
для направления 230100 – Информатика и вычислительная техника
для специальности 230101 – Вычислительные машины, комплексы,
системы и сети
Распределение часов
Форма обучения | Очная | Очно-заочная | Заочная | ||
на базе ПСО | на базе СПО | на базе ПСО | на базе СПО | ||
Лекции | 54 | 51 | – | 12 | |
Практические занятия | – | – | – | 4 | |
Лабораторные занятия | 36 | 34 | – | – | |
Индивидуальные занятия | 10 | 10 | – | – | |
Самостоятельная работа в т. ч. курсовая работа | 70 | 75 | – | 154 | |
Всего часов | 170 | 170 | – | 170 | |
Форма контроля | экзамен | экзамен | – | экзамен |
Программу составил к. т.н. доцент _____________________
Рабочая программа рассмотрена на заседании кафедры ²Вычислительные системы² 12 октября 2005 г.
Заведующий кафедрой к. т.н. профессор ____________________
Согласовано Декан ФЗО _________________________________
Рыбинск 2005
Настоящая программа составлена в соответствии с Государственным стандартом высшего профессионального образования и Учебным планом подготовки специалиста по направлению 220100 (230100).
Цели и задачи изучения дисциплины
Дисциплина преподается с целью дать студентам комплекс знаний о теоретических основах проектирования цифровых конечных автоматов и методах практической реализации схем конечных автоматов. Основные задачи изучения дисциплины:
– изучение вопросов абстрактного и структурного синтеза конечных автоматов;
– овладение навыками разработки электронных устройств, построенных на базе конечных автоматов;
– овладение навыками практической реализации конечных автоматов с использованием универсальных и уникальных лабораторных стендов.
1. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
Введение. Общие сведения о предмете.
1. Абстрактная теория автоматов.
1.1. Математическая модель абстрактного автомата. Проблема отражения времени при проектировании: синхронные, асинхронные и апериодические схемы.
1.2. Классы абстрактных автоматов. Получение не полностью определенного автомата. 1.2.1. Основные классы абстрактных автоматов. 1.2.2. Структурно-ориентированные автоматы. 1.2.3. Декомпозиция абстрактного автомата. Модель дискретного преобразователя .
1.3. Автоматы и формальные языки для описания конечных автоматов. 1.3.1. Начальные автоматные языки. 1.3.2. Стандартные автоматные языки. 1.3.3. Структурно-ориентированные автоматные языки: язык ГСА, формулы перехода, прямая и обратная таблица переходов.1.3.4. Концепция порождения и распознавания. Классификация языков по Хомскому. Порождающие грамматики, распознаватели: машина Тьюринга, магазинный автомат, сеть Петри, конечный автомат.
1.4. Минимизация абстрактных автоматов. 1.4.1. Минимизация полностью определенных автоматов. 1.4.1.1. Алгоритм Полла и Ангера. 1.4.1.2. Алгоритм Аутенкампа и Кона. 1.4.2. Минимизация частичных автоматов.
1.5. Связь между моделями автоматов Мура и Мили. 1.5.1. Взаимообратный переход от автомата Мили к автомату Мура при графическом способе задания автомата. 1.5.2. Взаимообратный переход от автомата Мили к автомату Мура при табличном способе задания автомата.
1.6. Коллективы автоматов. 1.6.1. Параллельное соединение автоматов. 1.6.2. Последовательное соединение автоматов. 1.6.3. Соединение с обратной связью.
1.7. Сети Петри. 1.7.1. Оригинальная сеть Петри. Способы задания. Получение правильного управляющего процесса. 1.7.2. Разновидности сетей Петри.
1.9. Абстрактный синтез автоматов. 1.10. Синтез автоматов по ГСА. 1.10.1. Последовательность синтеза автомата по ГСА. 1.10.2. Переход от ГСА к графу автомата.
1.11. Регулярные языки и конечные автоматы. Синтез автоматов по регулярным выражениям. 1.11.1. Основной алгоритм синтеза автоматов по регулярным выражениям. Правила разметки мест. 1.11.2. Получение таблицы переходов автомата однократного и многократного действия.
1.12. Структурный синтез автоматов с "жесткой" логикой.
1.12.1. Структурный синтез управляющих автоматов. Построение комбинационной схемы автомата. 1.12.1.1. Канонический метод структурного синтеза управляющих автоматов. Состояния элементов памяти. Кодирование состояний синхронного и асинхронного автомата. 1.12.1.2. Проблемы обеспечения функциональной устойчивости структурного автомата. 1.12.1.3. Проектирование переключательной функции комбинационной схемы автомата на ЛЭ. 1.12.1.4. Методика синтеза комбинационной части автомата на ПЛМ и ПЗУ.
1.12.2. Проектирование операционных автоматов.
1.13. Методы обеспечения функциональной устойчивости структурного автомата. Явление риска логических схем. 1.13.1. Противогоночное кодирование состояний управляющего автомата. 1.13.2.Схемотехнические методы обеспечения устойчивости автомата.
1.14. Синтез автомата Мили на ПЛМ.
1.15. Синтез автомата Мура на ПЛМ.
1.16. Синтез управляющих автоматов с программируемой логикой. Микропрограммирование.
1.17. Проблемы и перспективы автоматизации проектирования.
2. ПЕРЕЧЕНЬ лабораторных РАБОТ (36 час.)
2.1. Структурный синтез автомата Мура.
2.2. Структурный синтез автомата Мили.
2.3. Структурный синтез совмещенного автомата.
2.4. Изучение взаимного преобразования моделей Мура и Мили.
2.5. Синтез автомата однократного действия по регулярным выражениям.
2.6. Синтез автомата многократного действия по регулярным выражениям
2.7. Структурный синтез микропрограммного автомата Мура.
2.8. Синтез автомата для формирования заданной последовательности импульсов.
2.9. Синтез композиции автоматов.
2.10. Синтез автомата Мура и Мили на ПЛМ.
3. ПЕРЕЧЕНЬ ТЕМ КУРСОВОЙ РАБОТЫ
3.1. Синтез автомата для управления техническими объектами, режим работы которых не является периодическим (шлюзы, железнодорожные переезды, турникеты и пр.).
3.2. Синтез автомата для управления бытовой техникой.
3.3. Синтез автомата для управления техническими объектами, режим работы которых является периодическим (светофоры, конвейеры, формирователи импульсов и пр.).
3.4. Синтез автомата для управления кодовым замком.
3.5. Синтез автомата для управления вычислительным процессом.
3.6. Синтез автомата, имитирующего работу микропроцессора, микроконтроллера, программируемого контроллера.
3.7. Синтез автомата для связи удаленного объекта с персональным компьютером по последовательному каналу.
4. СПИСОК ЛИТЕРАТУРЫ И ПЕРЕЧЕНЬ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ
Основной
4.1. Баранов микропрограммных автоматов (граф-схемы и автоматы). – 2-е изд., перераб. и доп. – Л.: Энергия, 1979. – 232с.: ил. (см. также первое изд. данной книги, 1974 г. в библиотеке РГАТА).
4.2. , Портной схем электронных цифровых машин. – М.: Сов. радио, 1963. – 440с.: ил.
4.3. Схемотехника ЭВМ/ Под ред. . – М.: Высшая школа, 1985. – 391с.: ил.
4.4. Справочник по интегральным микросхемам /, , и др.; Под ред. .–2-е изд., перераб. и доп. –М.: Энергия, 1990.– 810с.: ил.
4.5. Логические ИС КР1533, КР1554: Справочник в 2-х ч.: ТОО "БИНОМ", 1993. ч. 1. – 254 с.
4.6. Нефедов микросхемы и их зарубежные аналоги: Справочник. Т. 5. – М.: ИП РадиоСофт, 1999. – 608 с.: ил.
4.7. Гусаров конечных автоматов: Лабораторный практикум. – Рыбинск: РГАТА, 2005. – 76 с.
4.8. Савельев теория цифровых автоматов: Учеб. для вузов по спец. ЭВМ. М. – Высш. шк., 1987. – 272 с., ил.
4.9. Сидоркин цифровых автоматов на микросхемах: Лабораторный практикум / Под ред. . – Рыбинск: РГАТА, 2003. – 103 с., ч.1.
4.10. Сидоркин цифровых автоматов на микросхемах: Лабораторный практикум / Под ред. . – Рыбинск: РГАТА, 2003. – 107 с., ч. 2.
Дополнительный
4.11. еория и проектирование переключательных схем. Пер. с англ. – М.: Мир, 1978. – 584с.: ил.
4.12. Шоломов теории дискретных логических и вычислительных устройств. – М.: Наука, 1980. – 400с.: ил.
4.13. Поспелов методы анализа и синтеза схем. – М.: Энергия, 1974. – 368 с.: ил.
4.14. , Шубарев цифровых микроэлектронных устройств. – М.: Радио и связь, 1983. – 216 с.: ил.
4.15. Глушков цифровых автоматов. – М.: Физматгиз, 1962. – 476с.: ил.
4.16. , Пийль управляющих автоматов. – М.: Энергия, 1970.– 400с.: ил.
4.17. , Новиков организации цифровых машин. – Л.: Машиностроение, 1974. – 432с.: ил.
4.18. , , Тарасенко цифровые вычислительные машины. – Киев: Вища школа, 1976. – 480с.: ил.
Программное обеспечение: программа для минимизации переключательных функций МПФ. exe (автор ) – позволяет минимизировать переключательные функции, имеющие от 3 до 7 аргументов.
5. Методические указания студентам по изучению дисциплины
5.1. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ ЛАБОРАТОРНЫХ РАБОТ
При подготовке к лабораторным работам следует изучить методические указания к лабораторным работам, рекомендуемую литературу, конспект лекций. При синтезе схем автоматов следует использовать программу для минимизации переключательных функций МПФ. exe, которая находится на сервере кафедры в папке Student\ВС 3-й курс\Теория автоматов\Минимизация переключательных функций. Все вопросы, связанные с выполнением лабораторных работ, подробно рассмотрены в методических указаниях, которые размещены на сервере кафедры в папке Student\ВС 3-й курс\Теория автоматов\Лабораторные работы.
5.2. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ИЗУЧЕНИЮ ТЕОРЕТИЧЕСКОГО КУРСА
Теоретический курс изучается студентом в процессе работы на лекциях, при этом студент конспектирует излагаемый преподавателем материал, отвечает на вопросы, которые ставит преподаватель в процессе чтения лекций, а также в процессе самостоятельной работы с рекомендуемой литературой в библиотеке академии, а также при выполнении курсовой работы.
Перед лекцией следует просмотреть материалы предыдущих лекций по данной дисциплине.
Перед лекцией по материалам пункта 1.12, 1.14 и 1.15 следует просмотреть конспекты лекций и литературу по дисциплине "Схемотехника ЭВМ", например [4.3 – 4.7] из основного списка литературы.
Перед лекцией по материалам пункта 1.13 следует просмотреть конспекты лекций и литературу по дисциплине "Дискретная математика", например [4.8] из основного списка литературы и [4.9] из дополнительного списка литературы.
5.3. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КУРСОВОЙ РАБОТЫ
Методические указания по выполнению курсовой работы приведены на сервере кафедры ВС в папке Student\ВС 3-й курс\Теория автоматов\Курсовая работа.
6. Список экзаменационных вопросов
6.1. Общие сведения о предмете.
6.2. Математическая модель абстрактного автомата.
6.3. Основные классы абстрактных автоматов.
6.4. Структурно-ориентированные автоматы.
6.5. Декомпозиция абстрактного автомата.
6.6. Начальные автоматные языки.
6.7. Стандартные автоматные языки.
6.8. Структурно-ориентированные автоматные языки: язык ГСА, формулы перехода, прямая и обратная таблица переходов.
6.9. Алгоритм Полла и Ангера.
6.10. Алгоритм Аутенкампа и Кона.
6.11. Минимизация частичных автоматов.
6.12. Взаимообратный переход от автомата Мили к автомату Мура при графическом способе задания автомата.
6.13. Взаимообратный переход от автомата Мили к автомату Мура при табличном способе задания автомата.
6.14. Параллельное соединение автоматов.
6.15. Последовательное соединение автоматов.
6.16. Соединение с обратной связью.
6.17. Оригинальная сеть Петри. Способы задания. Получение правильного управляющего процесса.
6.18. Разновидности сетей Петри.
6.19. Последовательность синтеза автомата по ГСА.
6.20. Переход от ГСА к графу автомата.
6.21. Основной алгоритм синтеза автоматов по регулярным выражениям. Правила разметки мест.
6.22. Получение таблицы переходов автомата однократного и многократного действия.
6.23. Структурный синтез автоматов с "жесткой" логикой.
6.24. Канонический метод структурного синтеза управляющих автоматов.
6.25. Проблемы обеспечения функциональной устойчивости структурного автомата.
6.26. Проектирование переключательной функции комбинационной части автомата на ЛЭ.
6.27. Методика синтеза комбинационной части автомата на ПЛМ и ПЗУ.
6.28. Проектирование операционных автоматов.
6.29. Противогоночное кодирование состояний управляющего автомата.
6.30.Схемотехнические методы обеспечения устойчивости автомата.
6.31. Синтез автомата Мили на ПЛМ.
6.32. Синтез автомата Мура на ПЛМ.
6.33. Синтез управляющих автоматов с программируемой логикой.
7. Контрольные вопросы (тесты самопроверки)
1. При задании автомата в виде "черного ящика" считаются заданными:
1) алфавит состояний и входной алфавит;
2) алфавит состояний и выходной алфавит;
3) входной и выходной алфавит;
4) только алфавит состояний.
2. Кортежем из 6 элементов задается
1) инициальный автомат;
2) неинициальный автомат;
3) совмещенный автомат;
4) комбинационная схема.
3. Кортежем из 5 элементов задается
1) инициальный автомат;
2) неинициальный автомат;
3) совмещенный автомат;
4) комбинационная схема.
4. Кортежем из 3 элементов задается
1) инициальный автомат;
2) неинициальный автомат;
3) совмещенный автомат;
4) комбинационная схема.
5. Кортежем из 8 элементов задается
1) инициальный автомат;
2) неинициальный автомат;
3) совмещенный автомат;
4) комбинационная схема.
6. Запрещенные слова имеются в алфавите
1) частичного автомата;
2) полностью определенного автомата;
3) совмещенного автомата;
4) комбинационной схемы.
(в задании 6 возможен более чем 1 правильный вариант ответа)
7. Кортежем из 6 элементов задается
1) автомат Мура;
2) автомат Мили;
3) совмещенный автомат;
4) комбинационная схема.
(в задании 7 возможен более чем 1 правильный вариант ответа)
8. Кортежем из 5 элементов задается
1) автомат Мура;
2) автомат Мили;
3) совмещенный автомат;
4) комбинационная схема.
(в задании 8 возможен более чем 1 правильный вариант ответа)
9. Состояние выхода возникает одновременно с вызывающим его состоянием входа в
1) автомате Мура;
2) автомате Мили;
3) совмещенном автомате;
4) комбинационной схеме.
(в задании 9 возможен более чем 1 правильный вариант ответа)
10. Состояние выхода возникает с задержкой на 1 такт по сравнению с вызывающим его состоянием входа в
1) автомате Мура;
2) автомате Мили;
3) совмещенном автомате;
4) комбинационной схеме.
(в задании 10 возможен более чем 1 правильный вариант ответа)
11. Выходной сигнал в начальный момент времени не зависит от того, какая буква подана на вход автомат, в
1) автомате Мура;
2) автомате Мили;
3) совмещенном автомате;
4) комбинационной схеме.
(в задании 11 возможен более чем 1 правильный вариант ответа)
12. Выходной сигнал в начальный момент времени зависит от того, какая буква подана на вход автомат, в
1) автомате Мура;
2) автомате Мили;
3) совмещенном автомате;
4) комбинационной схеме.
(в задании 12 возможен более чем 1 правильный вариант ответа)
13. В соответствии со структурой дискретного преобразователя по наибольшее число состояний имеет
1) операционный автомат;
2) управляющий автомат;
3) комбинационная схема.
14. Наличие пустой микрокоманды в управляющем автомате означает, что
1) не выполняется ни одна микрооперация;
2) выполняются все возможные микрооперации;
3) выполняется предыдущая микрокоманда;
4) выполняется текущая микрокоманда.
15. Таблица выходов относится к
1) начальным автоматным языкам;
2) конечным автоматным языкам;
3) стандартным автоматным языкам;
4) структурно-ориентированным автоматным языкам.
16. Ориентированные графы относятся к
1) начальным автоматным языкам;
2) конечным автоматным языкам;
3) стандартным автоматным языкам;
4) структурно-ориентированным автоматным языкам.
17. Граф-схемы алгоритмов (ГСА) относятся к
1) начальным автоматным языкам;
2) конечным автоматным языкам;
3) стандартным автоматным языкам;
4) структурно-ориентированным автоматным языкам.
18. Язык регулярных выражений относится к
1) начальным автоматным языкам;
2) конечным автоматным языкам;
3) стандартным автоматным языкам;
4) структурно-ориентированным автоматным языкам.
19. Матричный способ задания относится к
1) начальным автоматным языкам;
2) конечным автоматным языкам;
3) стандартным автоматным языкам;
4) структурно-ориентированным автоматным языкам.
20. Обратная таблица переходов относится к
1) начальным автоматным языкам;
2) конечным автоматным языкам;
3) стандартным автоматным языкам;
4) структурно-ориентированным автоматным языкам.
21. При переходе от автомата Мура, имеющего 3 состояния и 4 входных сигнала, к эквивалентному ему автомату Мили, максимальное число состояний автомата Мили может равняться
1) 12;
2) 3;
3) 4;
4) 13.
22. При переходе от автомата Мили, имеющего 3 состояния и 4 входных сигнала, к эквивалентному ему автомату Мура, максимальное число состояний автомата Мура может равняться
1) 12;
2) 3;
3) 4;
4) 13.
23. При переходе от автомата Мили, имеющего 3 состояния и 4 входных сигнала, к эквивалентному ему автомату Мура, максимальное число состояний автомата Мура может равняться
1) 12;
2) 3;
3) 4;
4) 13.
24. Автомат однократного действия характерен тем, что
1) из конечного состояния его можно вывести любым сигналом из входного алфавита;
2) из конечного состояния его можно вывести определенным сигналом из входного алфавита;
3) из конечного состояния его нельзя вывести никаким сигналом из входного алфавита;
4) в конечное состояние нельзя попасть ни при какой комбинации входных сигналов.
25. Автомат многократного действия характерен тем, что
1) из конечного состояния его можно вывести любым сигналом из входного алфавита;
2) из конечного состояния его можно вывести определенным сигналом из входного алфавита;
3) из конечного состояния его нельзя вывести никаким сигналом из входного алфавита;
4) в конечное состояние нельзя попасть ни при какой комбинации входных сигналов.
26. Реализация перехода как мгновенного события рассматривается в
1) сети Петри с раскрашенными позициями;
2) временной сети Петри;
3) оригинальной сети Петри;
4) тайм-аутной сети Петри.
27. Каждому переходу ставится в соответствие определенный интервал времени
1) в сети Петри с раскрашенными позициями;
2) во временной сети Петри;
3) в оригинальной сети Петри;
4) в тайм-аутной сети Петри.
28. Соседнее кодирование состояний невозможно, если орграф автомата
1) содержит цикл с нечетным числом вершин;
2) содержит цикл с четным числом вершин;
3) содержит 2 пары дуг между вершинами, путь между которыми проходит по одной из пар дуг графа;
4) содержит 2 вершины.
29. Соседнее кодирование состояний возможно, если орграф автомата
1) содержит цикл с нечетным числом вершин;
2) содержит цикл с четным числом вершин;
3) содержит 4 пары дуг между вершинами, путь между которыми проходит по одной из пар дуг графа;
4) содержит 3 пары дуг между вершинами, путь между которыми проходит по одной из пар дуг графа.
30. Минимизация ПФ, основанная на нахождении минимального покрытия, выполняется
1) с использованием карт Вейча;
2) с использованием карт Карно;
3) с использованием метода Квайна-Мак-Класки;
4) с использованием метода Уилкса-Стринжера.
31. При соединении двух автоматов с обратной связью
1) один из них должен быть автоматом Мили;
2) один из них должен быть автоматом Мура;
3) оба должны быть автоматами Мура;
4) оба должны быть автоматами Мили.
