Дополнительные главы математики: теория автоматов (стр. 3 )

№ п/п	Наименование обеспечиваемых (последующих) дисциплин	Темы дисциплины необходимые для изучения обеспечиваемых (последующих) дисциплин
1.1	1.2	1.3	2.1	2.2	2.3	3.1	3.2	3.3
1.	Технологии программирования	+	+	+	+
2.	Курсовые и дипломные работы		+	+	+	+	+	+	+	+

5. Содержание дисциплины.

Модуль 1

Тема 1.1. Цифровые устройства обработки информации.

Представление информации физическими сигналами. Два типа цифровых устройств обработки информации – комбинационные схемы и автоматы с памятью. Системы логических элементов, условные графические обозначения. Имена сигналов и активные уровни на выводах схем, логические соглашения.

Тема 1.2. Анализ и синтез комбинационных схем.

Анализ и синтез комбинационных схем (КС). Оценки качества КС. Особенности построения КС в монофункциональном базисе И-НЕ, ИЛИ-НЕ. Синтез КС при наличии ограничений на число входов логических элементов. Особенности синтеза КС со многими выходами. Анализ и синтез основных узлов вычислительных устройств комбинационного типа. Одноразрядный сумматор (ОС). ОС в базисе И-НЕ. Многоразрядные сумматоры с последовательными и параллельными переносами.

Тема 1.3. Абстрактные и структурные автоматы.

Абстрактный автомат. Основные понятия и определения. Конечные автоматы Мура и Мили. Автоматные языки для задания и отображения автоматов: таблицы переходов, графы, матрицы переходов. Синхронные и асинхронные автоматы. Эквивалентные автоматы. Преобразование автомата Мили в автомат Мура и наоборот. Минимизация полностью определённых автоматов на основе выделения классов эквивалентных состояний. Структурный (цифровой) автомат. Теорема Глушкова о структурной полноте. Триггер, как элементарный автомат Мура с двумя состояниями и поной системой переходов и выходов.

Модуль 2

Тема 2.1. Конечные автоматы и машина Тьюринга.

Понятие алгоритма. Алгоритмическая ограниченность конечных автоматов. Машина Тьюринга как мощное средство реализации произвольных алгоритмов. Сравнительная оценка функционирования машины Тьюринга и конечного автомата. Возможные формы реализации машины Тьюринга.

Тема 2.2. Триггерные устройства как элементарные автоматы.

Классификация триггеров. Асинхронный RS-триггер с прямыми входами и формы его описания (таблица переключения, характеристическая таблица и характеристическое уравнение, граф переходов триггера как граф асинхронного автомата с двумя устойчивыми состояниями). Временные диаграммы процесса переключения, Асинхронный RS-триггер с инверсными входами.

Тема 2.3. Структурные автоматы синхронного типа.

Канонический метод синтеза структурного (цифрового) автомата на основе таблицы истинности для выходных сигналов автомата и сигналов возбуждения триггеров. Проблематика кодирования выходных сигналов автомата и его состояний. Соседнее кодирование состояний автомата. Эвристический метод кодирования состояний автомата, минимизирующий суммарное число переключений элементов памяти на всех переходах автомата.

Модуль 3

Тема 3.1. Принцип микропрограммного управления в вычислительных устройствах. Функции операционных и управляющих автоматов.

Общее представление о микропрограммном управлении: микрооперация и управляющие сигналы, логические условия и осведомительные сигналы, микропрограммы и микропрограммирование. Декомпозиция вычислительного устройства на операционный и управляющий автоматы. Язык граф-схем для представления микропрограммы. Граф микропрограммы (содержательная граф - схема алгоритма) и язык микроопераций.

Тема 3.2. Структурная организация и синтез операционных автоматов.

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

Тема 3.3. Синтез управляющих микропрограммных автоматов с жёсткой логикой.

Управляющие автоматы с жесткой логикой. Преобразование граф-схемы алгоритма в граф автомата Мили, автомата Мура. Постановка задачи синтеза управляющих автоматов на основе структурных таблиц. Примеры синтеза автоматов Мили и Мура.

6. Планы семинарских занятий.

Тема 1.1. Цифровые устройства обработки информации.

Представление информации физическими сигналами. Системы логических элементов, условные графические обозначения.

Тема 1.2. Анализ и синтез комбинационных схем.

Анализ и синтез комбинационных схем (КС). Синтез КС при наличии ограничений на число входов логических элементов. Одноразрядный сумматор (ОС). ОС в базисе И-НЕ. Многоразрядные сумматоры с последовательными и параллельными переносами.

Тема 1.3. Абстрактные и структурные автоматы.

Конечные автоматы Мура и Мили. Преобразование автомата Мили в автомат Мура и наоборот. Минимизация полностью определённых автоматов на основе выделения классов эквивалентных состояний.

Тема 2.1. Конечные автоматы и машина Тьюринга.

Машина Тьюринга. Сравнительная оценка функционирования машины Тьюринга и конечного автомата. Возможные формы реализации машины Тьюринга.

Тема 2.2. Триггерные устройства как элементарные автоматы.

Асинхронный RS-триггер с прямыми входами и формы его описания (таблица переключения, характеристическая таблица и характеристическое уравнение, граф переходов триггера как граф асинхронного автомата с двумя устойчивыми состояниями). Временные диаграммы процесса переключения, Асинхронный RS-триггер с инверсными входами.

Тема 2.3. Структурные автоматы синхронного типа.

Канонический метод синтеза структурного (цифрового) автомата на основе таблицы истинности для выходных сигналов автомата и сигналов возбуждения триггеров. Соседнее кодирование состояний автомата. Эвристический метод кодирования состояний автомата, минимизирующий суммарное число переключений элементов памяти на всех переходах автомата.

Тема 3.1. Принцип микропрограммного управления в вычислительных устройствах. Функции операционных и управляющих автоматов.

Декомпозиция вычислительного устройства на операционный и управляющий автоматы. Граф микропрограммы (содержательная граф - схема алгоритма) и язык микроопераций.

Тема 3.2. Структурная организация и синтез операционных автоматов.

Синтез логико-суммирующего устройства для выполнения поразрядных логических операций.

Тема 3.3. Синтез управляющих микропрограммных автоматов с жёсткой логикой.

Преобразование граф-схемы алгоритма в граф автомата Мили, автомата Мура. Примеры синтеза автоматов Мили и Мура.

7. Темы лабораторных работ (Лабораторный практикум).

Не планируются.

8. Примерная тематика курсовых работ.

Не планируются.

9. Учебно - методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины (модуля).

1. Текущая аттестация:

· контрольные работы. В семестре проводятся контрольные работы (на семинарах);

· тестирование (письменное или компьютерное) по разделам дисциплины.

2. Промежуточная аттестация:

· тестирование по дисциплине;

· зачёт (письменно-устная форма). Зачёт выставляется после решения всех задач контрольных работ и выполнения самостоятельной работы.

Текущий и промежуточный контроль освоения и усвоения материала дисциплины осуществляется в рамках рейтинговой (100-бальной) системы оценок.

Контрольная работа по теме «Абстрактные и структурные автоматы»

Задание 1.

Для данного конечного автомата, заданного таблично, со множеством внутренних состояний {1,2,3,4,5,6,7,8,9}, входным алфавитом {а, Ь} и выходным алфавитом {х, у}:

1. Выяснить, является ли автомат сильно связным.

2. Построить эквивалентный минимальный автомат.

3. Проверить работу исходного и минимального автоматов над

словом "bbabaab".

Задание 2.

1. Построить таблицу состояний данного автомата.

2. Считая автомат неинициальным, построить зквивалентный автомат Мура. 3. Проверить работу данного и построенного автоматов над одним и тем же словом.

Вопросы к зачёту

1. Комбинационные схемы (КС) и цифровые автоматы. Системы логических элементов. Логические соглашения.

2. Этапы синтеза КС. Оценки качества КС (быстродействие, сложность).

3. Особенности синтеза КС в монофункциональном базисе И-НЕ и ИЛИ-НЕ. Учёт ограничений на число входов логических элементов.

4. Особенности синтеза КС со многими выходами.

5. Синтез одноразрядного сумматора. Многоразрядный сумматор с последовательным переносом.

6. Абстрактный автомат. Основные определения.

7. Автоматные языки для задания и отображения абстрактных автоматов

8. Связь между моделями автоматов Мили и Мура. Взаимные преобразования.

9. Минимизация полностью определённых автоматов.

10. Постановка задачи синтеза структурного автомата синхронного типа.

11. Сравнительная оценка функционирования машины Тьюринга и конечного автомата.

12. Триггеры и их классификация. RS - триггер с прямыми входами. Таблица состояний, граф состояний, характеристическое уравнение и словарь.

13. Канонический метод синтеза структурного автомата синхронного типа. Пример.

14. Эвристический метод кодирования состояний автомата, минимизирующий суммарное число переключений триггеров на всех переходах автомата.

15. Микропрограммное управление. Декомпозиция вычислительного устройства на управляющий (УА) и операционный автоматы (ОА).

16. Граф микропрограммы МП. Пример. Вычленение функции УА (кодированный граф МП) и ОА (множество микрокоманд и логических условий) из графа микропрограммы.

17. Преобразование кодированного графа МП в граф автомата Мили. Функционирование автомата Мили в течение машинного такта.

18. Преобразование кодированного графа МП в граф автомата Мура. Функционирование автомата Мура в течение машинного такта.

19. Синтез управляющего автомата Мили на основе структурной таблицы.

20. Синтез управляющего автомата Мура на основе структурной таблицы.

10. Образовательные технологии.

Сочетание традиционных образовательных технологий в форме лекций, практических работ и проведение контрольных мероприятий (контрольных работ, промежуточного тестирования, экзамена).

аудиторные занятия:

лекционные и практические занятия; на практических занятиях контроль осуществляется при сдаче набора заданий. В течение семестра студенты выполняют задачи, указанные преподавателем к каждому занятию.

внеаудиторные занятия:

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

11. Учебно-методическое и информационное обеспечение дисциплины (модуля).

11.1. Основная литература:

1. Карпов автоматов. СПб.: Питер, 2002.

2. Чирков общей теории конечных автоматов. - Ленинград: Изд-во ЛГУ, 1975. 

11.2. Дополнительная литература:

1., Вашкевич автоматы и их использование для синтеза систем управления. Часть 1. Эквивалентные преобразования едетерминированных автоматов. Изд. Пенз. Гос. Техн. Ун-та, 1996.

2.Рейуолд- Дж. Теория формальных языков. М., Радио и связь, 1988.

3. и др. Прикладная теория цифровых автоматов. Киев: Виша школа, 1987.

12. Технические средства и материально-техническое обеспечение дисциплины (модуля).

При освоении дисциплины для проведения лекционных занятий нужны учебные аудитории, оснащённые мультимедийным оборудованием, для проведения практических занятий необходимы обычные классы.