Учебно-методический комплекс дисциплины (умк-д) " Теория автоматов "
| Вид материала | Учебно-методический комплекс |
- Учебно-методический комплекс умк учебно-методический комплекс теория и методика воспитания, 1435.61kb.
- Учебно-методический комплекс умк учебно-методический комплекс теория языка, 2510kb.
- Учебно-методический комплекс для специальностей: 080507 Менеджмент организации 080504, 347.56kb.
- Учебно-методический комплекс учебной дисциплины «комплексный анализ хозяйственной деятельности», 1158.91kb.
- Назарова Вероника Сергеевна учебно-методический комплекс, 2456.13kb.
- Учебно-методический комплекс умк учебно-методический комплекс общие основы педагогики, 974.02kb.
- Методические рекомендации по составлению учебно-методического комплекса темы (умк), 140.83kb.
- Учебно-методический комплекс дпп. Ф. 01. Теория языка Специальность 050301 Русский, 889.66kb.
- Учебно-методический комплекс по дисциплине Сети ЭВМ и телекоммуникации (наименование, 743.2kb.
- Учебно-методический комплекс дисциплины Бийск бпгу имени В. М. Шукшина, 1049.36kb.
Кафедра Программное обеспечение компьютерных систем и информатики
Вашему вниманию предлагается учебно-методический комплекс дисциплины (УМК-Д)
" Теория автоматов "
Содержание учебно-методический комплекс дисциплины
1. Стандарт дисциплины, утвержденный Министерством образования и науки
Кыргызской Республики.
2. Рабочая программа учебной дисциплины.
3. График самостоятельной работы студентов.
4. Методические указания по выполнению курсовых проектов.
5. Методические указания по выполнению лабораторных работ (могут входить в
состав учебных комплексов).
6. Методические указания, комплект исходных данных и образцы выполнения
самостоятельных работ (домашних заданий).
7. Фонд тестов, тестовых и контрольных вопросов для текущей, промежуточной и
итоговой оценки знаний по дисциплине (может совмещаться с рубрикатором).
8. Комплект образцов экзаменационных билетов.
9. Карта обеспеченности дисциплины основной и дополнительной учебной литературой.
10. Карта обеспеченности студентов учебной литературой по дисциплине.
11. Карта обеспеченности дисциплины кадрами профессорско- преподавательского
состава и техническими средствами обучения.
Кроме перечисленных элементов, УМКД включает дополнительные материалы, такие как:
- учебник или учебное пособие.
- учебно-методическое пособие;
- практикум.
- конспекты лекций;
- рабочие тетради;
- хрестоматии;
- задачники;
- глоссарий;
- примерные темы рефератов, эссе;
- презентации курсов;
- обзорные лекции;
- видеоматериалы;
- дидактические материалы и др.
УМК должно быть оформлено по модульному принципу с использованием гиперссылок ввиде электронных книг.
Содержание учебно-методический комплекс дисциплины
1. Стандарт дисциплины, утвержденный Министерством
образования и науки Кыргызской Республики.
Содержание дисциплины из Государственного образовательного стандарта высшего профессионального образования по направлению подготовки дипломированных специалистов 552801 - "Информатика и вычислительная техника".
| СД.Г.01 | Теория автоматов | 170 |
| | Автоматы и формальные языки; концепция порождения и распознавания; классификация языков по Хомскому; порождающие грамматики; распознаватели: машина Тьюринга, магазинный автомат, сеть Петри, конечный автомат; коллективы автоматов; регулярные языки и конечные автоматы; модель дискретного преобразователя В.М.Глушкова; | |
2. Рабочая программа учебной дисциплины.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ. НАУКИ И МОЛОДЕЖНОЙ ПОЛИТИКИ
Кыргызской республики
КЫРГЫЗСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СТРОИТЕЛЬСТВА. ТРАНСПОРТА И АРХИТЕКТУРЫ
Кафедра «Программное обеспечение вычислительных систем и информатика»
Утверждаю
Директор института(декан факультета)
_____________________М.Дж.Орозалиев
(подпись,расшифровка подписи)
«___»_______________________2009 г.
РАБОЧАЯ ПРОГРАММА
дисциплины «Теория автоматов»
(модульно-рейтинговая система обучения)
Направление подготовки 552801 - "Информатика и вычислительная техника"
Квалификация – ИНЖЕНЕР
Специальность 552 801.4 - Программное обеспечение вычислительной техники и автоматизированных систем
Институт Инновационных Профессий
Форма обучения очно-заочная
| Семестр | 4 |
| Лекции, часов | 36 |
| Практические занятия, часов | 36 |
| Лабораторные занятия, часов | |
| Курсовая работа, часов | 5 |
| Контрольная работа | |
| Самостоятельная работа, часов | 90 |
| Индивидуальная работа, часов | |
| Формы контроля | экзамен |
Рабочая программа обсуждена на заседании кафедры ПОКСиИ,
протокол №___от «__»________20__ года
Разработал:_____________________ и.о.проф. кафедры ПОКСиИ М.А.Шабданов
Проверил : _____________________ и.о.доцента кафедры ПОКСиИ К.К.Талыпов
Бишкек, 2009
Рецензент: к.т.н., доцент К.К.Талыпов
Рабочая программа дисциплины «Теория автоматов»/сост. М.А.Шабданов.- Бишкек:КГУСТА,2009.- 21 стр.
Рабочая программа предназначена для преподавания дисциплины специализации « Теория автоматов» студентам очно-заочной формы обучения специальности «552 801.4 - Программное обеспечение вычислительной техники и автоматизированных систем» в 4 семестре.
Рабочая программа составлена с учетом Государственного образовательного стандарта высшего профессионального образования по направлению подготовки дипломированных специалистов 552801 - "Информатика и вычислительная техника".
Составитель ______________М.А.Шабданов
01.09.2009 г.
©к.т.н. Шабданов М.А..,2009
©ИИП КГУСТА,2009
Цель изучения дисциплины
Целью преподавания данной дисциплины является систематическое изложение общих методов анализа и синтеза цифровых автоматов, и на их основе - методов построения структур операционных и управляющих автоматов.
Методы теории цифровых автоматов, являющихся моделями цифровых устройств, используются в качестве теоретической базы для анализа и синтеза различных цифровых устройств вычислительной техники.
Задачи изучения
Задачи изучения дисциплины состоят в овладении студентами нижеследующих знаний и умений.
- знать методы анализа и синтеза цифровых автоматов, методы построения средства контроля и диагностики цифровых автоматов, стандартную терминологию;
- уметь строить структурные и логические схемы операционных и управляющих автоматов, применять корректирующие коды для обнаружения и исправления ошибок, организовать аппаратный и тестовый контроль;
- иметь представления о современном состоянии и актуальных задачах теории цифровых автоматов.
Формы проведения учебных занятий
Содержание дисциплины реализуется в различных формах организации учебного процесса – лекциях, практических занятиях и самостоятельной работе студентов.
Самостоятельная работа студентов осуществляется как во время аудиторных занятий (выполнение практических заданий), так и во время внеаудиторной работы при подготовке к занятиям.
Формы контроля знаний
В процессе изучения дисциплины целесообразно применять следующие виды контроля: входной рейтинг, текущий рейтинг-контроль, промежуточный рейтинг-контроль, модульный рейтинг, итоговый рейтинг-контроль, итоговый рейтинг по дисциплине.
Текущий контроль осуществляется выборочно на занятиях в любое время в ходе изучения темы. Промежуточный контроль – оценка знаний по освоенному материалу каждого дисциплинарного модуля, одновременно для всех студентов.
В каждом модуле определяется минимальное и максимальное количество баллов. Сумма максимальных баллов по всем модуля равняется 100%-ному освоению материала. Минимальное количество баллов в каждом модуле является обязательным и не может быть заменено набором баллов в других модулях.
Для получения положительной оценки необходимо набрать не мене 60 баллв, предусмотренных по дисциплине (при условии набора всех обязательных минимальных баллов).
Перевод баллов в академическую оценку осуществляется по следующей схеме: оценка «удовлетворительно» - 60-72 баллов, «хорошо» - 73-86 баллов, «отлично» - 67-100 баллов.
Сумма баллов минимальных границ диапазонов всех дисциплинарных модулей должна составлять 60, минимальных -100.
Рейтинговые баллы распределяются по дисциплинарным модулям в зависимости от значимости и трудоемкости модулей.
Структура дисциплины
(содержание лекционных разделов дисциплины)
Структура дисциплины
(содержание лекционных разделов дисциплины)
Модуль I
Общие сведения о цифровых автоматов (ца) (17 часов)
Введение (1 час).
Цель и задачи курса. Структура курса и его связь с другими дисциплинами. Методика изучения курса. Краткий исторический очерк.
Тема 1. Понятие об алгоритмах и конечном ЦА (4 часа).
Алгоритм как алфавитный оператор преобразование дискретной информации. Понятие о нормальных алгоритмах А.А. Маркова. Определение конечного ЦА как преобразователя дискретной информации.
Сигналы – носители цифровой информации. Наиболее распространение формы представления двоичных сигналов. Классификация и характеристика ЦА: по степени абстракции, по функциональному назначению, по аппаратурной реализации.
Тема 2. Переключательные схемы (1 час).
Основные определения. Комбинационные и последовательностные схемы. Задачи анализа и синтеза схем. Понятие системы элементов: базис системы, коэффициенты объединения по входу и выходу. Задержка на логический элемент.
Тема 3. Анализ и синтез комбинационных логических схем (1 час).
Канонический способ синтеза комбинационных схем. Критерии оценки комбинационных схем: сложность, быстродействие, надежность и др. Синтез комбинационных схем с использованием свойств не полностью определенных функций. Эффективность такого синтеза. Риск сбоя в комбинационных схемах. Анализ схем на риск сбоя. Общие сведения о машинных методах анализа и синтеза комбинационных схем.
Тема 4. Абстрактная теория цифровых автоматов (4 часа).
Теория цифровых автоматов как научная абстракция, позволяющая перейти от единичного к общему при синтезе операционных устройств ЭВМ. Конечный автомат как математическая модель последовательностной схемы. Автоматы Милли и Мура. Способы задания автоматов: графы, таблицы переходов и выходов. Классы языков для задания автоматных отображений. Преобразования автоматов. Эквивалентные состояния.
Минимизация числа состояний автомата. Синхронные и асинхронные автоматы.
Тема 5. Структурный автомат с памятью. (6 часов ).
Задачи структурного синтеза автоматов. Канонический метод структурного синтеза цифрового автомата. Элементарные цифровые автоматы с памятью, реализованные в виде интегральных микросхем: D – триггер, JK- триггер, RS – триггер , DY – триггер.
Характеристические функции и матрицы переходов элементарных автоматов.
Пример структурного синтеза цифрового автомата с использование канонического метода. Кодирование внутренних состояний автомата и его влияние на сложность комбинационных схем цифровых автоматов.
Взаимодействие автоматов с внешней средой. Методы организации потактной работы и механизма квантования времени в структурном автомате. Синхронная, асинхронная и согласованная модели взаимодействия автомата с внешней средой.
Особенности реализации синхронного, асинхронного и апериодического автоматов.
Модуль II Управляющие и Операционные Автоматы (17 часов)
Тема 6. Структура цифрового операционного устройства (ОУ) (4 часа).
Операционное устройство в виде композиции операционного и управляющего
автоматов (ОА и УА).
Операторные схемы алгоритмов (ОСА). Определение операторной схемы. Виды ОСА. Преобразование ОСА. Содержательные граф – схемы алгоритмов (ГСА).
Информационные связи в алгоритме. Выделение функций ОА и УА из содержательной ГСА.
Принципы микропрограммного управления. Микропрограммирование.
Тема 7. Управляющие автоматы с жесткой логической (6 часов).
Интерпретация микропрограммы автоматов с памятью. Определение закона функционирования автомата Мили. Определение закона функционирования автомата Мура. Списки переходов автомата. Организация памяти и выделение состояний автомата. Формирование сигналов возбуждения и выходных сигналов. Эффект гонок в автоматах и способы их устранения. Синтез автомата Мили на различных триггерах. Синтез автомата Мура на различных триггерах. Синхронизация работы автоматов.
Управляющие автоматы, построенные на принципе распределения сигналов. Сравнительная оценка управляющих автоматов с жесткой логикой.
Тема 8. Структуры операционных автоматов (4 часа).
Структурный состав операционных автоматов. Каноническая структура операционного автомата как базовой структуры. Эквивалентные операции и обобщенные операторы. Синтез I-автоматов. Структуры M, IM, S-автоматов. Сравнительная оценка различных структур операционных автоматов. Согласование работы ОА и УА.
Тема 9. Контроль и диагностика цифровых автоматов (4 часа).
Понятие о контроле. Повышение помехоустойчивости передач и приема информации. Контроль при передачи информации. Использование помехоустойчивого кодирование для контроля передачи. Обработка информации. Методы контроля. Программные и структурные методы контроля выполнения арифметических и логических операций. Контроль и диагностика работы цифровых автоматов.
Заключение (1 часа).
Современное состояние и актуальные задачи прикладной теории цифровых автоматов. Перспективы развития. Практическое значение полученных знаний в будущем инженерной деятельности.
Перечень практических занятий.
Целью практических занятий является: закрепление знаний полученных в теоретической части и изучение алгоритмов решения задач.
| Наименование занятий, содержание | Количество часов | Примечание |
| Модуль I 1. Канонический синтез комбинационных узлов в различных базисах | 4 часа. | |
| 2. Графы абстрактных автоматов. Преобразования автоматов | 2 часа. | |
| 3. Канонический метод структурного синтеза цифровых автоматов | 2 часа. | |
| 4. Эффект гонок. Противогоночное кодирование состояния ЦА | 2 часа. | |
| Модуль II 1. Помехоустойчивое кодирование. Методы построения двоичных групповых кодов | 2 часа. | |
| 2. Помехоустойчивое кодирование. Методы построения двоичных цикловых кодов | 2 часа. | |
Правила рейтинговой системы оценивания результатов обучения студентов
по дисциплине «Теория автоматов»
на IV семестр 2009/2010 учебного года
| Вид работы | Количество баллов |
| Текущая работа: | 0-25 |
| Устный ответ | 0-6 |
| Домашнее задание | 0-5 |
| Практическая работа | 0-8 |
| Активность на занятиях (дополнения, уточнения, исправления устного ответа товарища) | 0-6 |
| Рубежный контроль 1 (контрольная работа, тестирование, устный опрос, коллоквиум или др.) | 0-5 |
| Выполнение самостоятельной работы | 15 |
| Посещаемость | 0-5 |
| Текущая работа | 0-25 |
| Устный ответ | 0-6 |
| Домашнее задание | 0-5 |
| Практическая работа | 0-8 |
| Активность на занятиях (дополнения, уточнения, исправления устного ответа товарища) | 0-6 |
| Рубежный контроль 1 (контрольная работа, тестирование, устный опрос, коллоквиум или др.) | 0-5 |
| Выполнение самостоятельной работы | 15 |
| Посещаемость | 0-5 |
| Итоговый контроль (зачет, экзамен) | 0-30 |
| Итого | 0-100 |
| Премиальные баллы: | |
| Участие в олимпиаде | 0-5 |
| Выступление на конференциях | 0-5 |
| Участие в конкурсах научных работ | 0-5 |
| Штрафы | |
| Нарушение сроков сдачи работ | Минус0,5-5 |
| Отказ от ответа на семинаре (практике) | Минус0,5-5 |
| Рейтинговая оценка по дисциплине | Максимум 100 баллов |
Модульно-рейтинговая карта дисциплины
«Теория автоматов»
| Наименование модуля, виды работ и формы контроля | Рейтинг-баллы | |
| минимум | максимум | |
| Дисциплинарный модуль №1 | 0 | 40 |
| Текущая работа | 0 | 15 |
| Рубежный контроль 1 | 0 | 5 |
| Выполнение самостоятельной работы | 0 | 15 |
| Посещаемость | 0 | 5 |
| Дисциплинарный модуль №2 | 0 | 40 |
| Текущая работа | 0 | 15 |
| Рубежный контроль 2 | 0 | 5 |
| Выполнение самостоятельной работы | 0 | 15 |
| Посещаемость | 0 | 5 |
| Итоговый модуль | 0 | 20 |
| Дисциплинарный рейтинг | 0 | 100 |
| Шкала перевода дисциплинарного рейтинга в академические оценки | ||
| Дисциплинарный рейтинг | Академическая оценка | |
| 60-72 | 3(удовлетворительно) | |
| 73-86 | 4(хорошо) | |
| 87-100 | 5(отлично) | |
Рейтинг – карта студента ______________________________________
по дисциплине «Теория автоматов»
| Наименование модуля, виды работ и формы контроля | Рейтинг-баллы | Срок сдачи освоенных элементов модуля | Рейтинг-баллы, набранные студентом | Подпись препод. | |||
| минимум | максимум | ||||||
| Дисциплинарный модуль №1 | 0 | 40 | 30.10.09 | | | ||
| Текущая работа | 0 | 15 | | | | ||
| Рубежный контроль 1 | 0 | 5 | | | | ||
| Выполнение самостоятельной работы | 0 | 15 | | | | ||
| Посещаемость | 0 | 5 | | | | ||
| Дисциплинарный модуль №2 | 0 | 40 | 30.12.09 | | | ||
| Текущая работа | 0 | 15 | | | | ||
| Рубежный контроль 2 | 0 | 5 | | | | ||
| Выполнение самостоятельной работы | 0 | 15 | | | | ||
| Посещаемость | 0 | 5 | | | | ||
| Итоговый модуль | 0 | 20 | | | | ||
| Дисциплинарный рейтинг | 0 | 100 | | | | ||
| Шкала перевода дисциплинарного рейтинга в академические оценки | |||||||
| Дисциплинарный рейтинг | Академическая оценка | ||||||
| 60-72 | 3(удовлетворительно) | ||||||
| 73-86 | 4(хорошо) | ||||||
| 87-100 | 5(отлично) | ||||||
Лист регистрации изменений
| Номер изменения | Номер страниц | Номер извещения об изменении | Дата введения изменения | Изменение внесено | |||
| измененных | новых | Аннулир. | дата | подпись | |||
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
3. График самостоятельной работы студентов.
|
4. Методические указания по выполнению курсовых проектов.
1.Разработка функциональных МП нескольких процессорных операций
2.Синтез структурной схемы операционного автомата
3.Разработка структурно-функциональных МП
4.Синтез функциональных схем операционных автоматов
5.Синтез принципиальной схемы узла ОА
6.Разработка структуры МК и синтез схемы управляющего автомата с программируемой логикой
5. Методические указания по выполнению лабораторных работ (могут входить в состав учебных комплексов).
Лабораторных нет
6. Методические указания, комплект исходных данных и образцы выполнения самостоятельных работ (домашних заданий).
7. Фонд тестов, тестовых и контрольных вопросов для текущей, промежуточной и итоговой оценки знаний по дисциплине (может совмещаться с рубрикатором).
Перечень вопросов (текстов) теоретического курса
1 модуль
КОНТРОЛЬНЫЕ ВОПРОСЫ ПО РЕЙТИНГОВОЙ ОЦЕНКЕ ЗНАНИЙ
1.Основные определения, аксиомы, свойства, законы булевой алгебре.
2.Способы представления булевых функций.
3.Элементарные булевы функций.
4.Методы минимизации функций алгебре логики.
5.Неточные методы минимизации функций алгебры логики.
6.Точные методы минимизации функций алгебры логики.
7.Минимизация не полностью определенных функций алгебры логики.
8.Сравнительная оценка различных методов минимизации.
9.Задачи анализа и синтеза переключательных схем.
10.Канонический синтез Комбинационных схем в различных базисах. Оценка схем.
11.Синтез одноразрядных сумматоров (вычитателей). Оценка схем.
12.Синтез преобразовательных кодов. Оценка схем.
13.Синтез схем логической обработки. Оценка смех.
14.Структуры параллельных сумматоров.
15.Структуры умножителей и делителей.
Перечень вопросов (текстов) теоретического курса
2 модуль
КОНТРОЛЬНЫЕ ВОПРОСЫ ПО РЕЙТИНГОВОЙ ОЦЕНКЕ ЗНАНИЙ
1.Концепция микропрограммирования. Язык функционального микропрограммирования.
2.Понятие об абстрактном автомате. Способ задания автоматов. Элементарные
цифровые автоматы.
3.Канонический метод синтеза структурного автомата.
4.Эффект "гонок". Способы его устранений.
5.Как влияет способ кодирования состояний управляющего автомата на его комбинационную часть.
6.Их автоматов.? кции управляющего и операционного автоматов.
7.Операторные схемы алгоритмов (ОСА) и их сравнительная оценка.
8.Структурный синтез управляющего автоматов (Мили, Мура).
9.Сравнительная оценка "жестких" автоматов.
10.Каноническая структура операционных автоматов.
11.Структура 1-автомата и его синтеза.
12.Сравнительная оценка операционных автоматов.
13.Согласование работы операционного и управляющего автомата.
8. Комплект образцов экзаменационных билетов.
(Вставка из прежней УМК или обновленную)
9. Карта обеспеченности дисциплины основной и дополнительной литературой учебной
литературой.
Основная:
| № п/п | Название | Автор | Город,изд-во, год издания | Колич.экз. в библиотеке КГУСТА | Колич.экз. на кафедре ПОКСиИ |
| 1 | Прикладная теория цифровых автоматов | А.Я.Савельев | Москва Высшая школа 1987 | 1 | 1 |
| 2 | Структуры ЭВМ | С.А.Майоров Г.И.Новиков | Ленинград Энергоатомиздат 1987 | 1 | 1 |
| 3 | Архитектура конвейерных ЭВМ | П.М.Коуги | Москва, Радио и связь, 1985 | 1 | 1 |
Дополнительная:
| № п/п | Название | Автор | Город,изд-во, год издания | Колич.экз. в библиотеке КГУСТА | Колич.экз. на кафедре ПОКСиИ |
| 1 | Синтез микропрограммных автоматов | С.И.Баранов | Ленинград Энергия 1979 | | 2 |
| 1 | Теория и проектирование ЭВМ Методические указания | М.А.Шабданов и др. | Фрунзе, «ФПИ 1991 | | 5 |
10. Карта обеспеченности студентов учебной литературой по дисциплине.
(Вставка из прежней УМК))
11. Карта обеспеченности дисциплины кадрами профессорско-преподавательского состава и техническими средствами обучения.
Закреплено за и.о.профессора М.А.Шабдановым
Имеется компьютерный класс и соответствующее ПО