rpd000005274 (231000 (09.04.04).М1 Программно-информационные системы)
Описание файла
Файл "rpd000005274" внутри архива находится в следующих папках: 231000 (09.04.04).М1 Программно-информационные системы, 231000.М1. Документ из архива "231000 (09.04.04).М1 Программно-информационные системы", который расположен в категории "". Всё это находится в предмете "вступительные экзамены" из 9 семестр (1 семестр магистратуры), которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "остальное", в предмете "магистратура" в общих файлах.
Онлайн просмотр документа "rpd000005274"
Текст из документа "rpd000005274"
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
Московский авиационный институт
(национальный исследовательский университет)
УТВЕРЖДАЮ
Проректор по учебной работе
______________Куприков М.Ю.
“____“ ___________20__
РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ (000005274)
Дискретная математика и теория автоматов
(указывается наименование дисциплины по учебному плану)
| Направление подготовки | Программная инженерия | |||||
| Квалификация (степень) выпускника | Магистр | |||||
| Программа подготовки | Программно-информационные системы | |||||
| Форма обучения | очная | |||||
| (очная, очно-заочная и др.) | ||||||
| Выпускающая кафедра | 304 | |||||
| Обеспечивающая кафедра | 304 | |||||
| Кафедра-разработчик рабочей программы | 304 | |||||
| Семестр | Трудоем-кость, час. | Лек-ций, час. | Практич. занятий, час. | Лаборат. работ, час. | СРС, час. | Экзаменов, час. | Форма промежуточного контроля |
| 1 | 216 | 18 | 20 | 16 | 162 | 0 | Зо |
| Итого | 216 | 18 | 20 | 16 | 162 | 0 |
Москва
2011
РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Разделы рабочей программы
-
Цели освоения дисциплины
-
Структура и содержание дисциплины
-
Учебно-методическое и информационное обеспечение дисциплины
-
Материально-техническое обеспечение дисциплины
Приложения к рабочей программе дисциплины
Приложение 1. Аннотация рабочей программы
Приложение 2. Cодержание учебных занятий
Приложение 3. Прикрепленные файлы
Программа составлена в соответствии с требованиями ФГОС ВПО по направлению подготовки 231000 Программная инженерия
Авторы программы:
| Корнеенкова А.В. | _________________________ |
| Чугаев Б.Н. | _________________________ |
| Заведующий обеспечивающей кафедрой 304 | _________________________ |
Программа одобрена:
| Заведующий выпускающей кафедрой 304 _________________________ | Декан выпускающего факультета 3 _________________________ |
-
ЦЕЛИ ОСВОЕНИЯ ДИСЦИПЛИНЫ
Целью освоения дисциплины Дискретная математика и теория автоматов является достижение следующих результатов образования (РО):
| N | Шифр | Результат освоения |
| 1 | Знать роль и место дискретной математики и теории автоматов в практическом и теоретическом использовании для решения задач синтеза и анализа цифровых схем | |
| 2 | Знать конечный автомат как модель компонентов аппаратного и программного обеспечения | |
| 3 | Уметь разрабатывать алгоритмы моделирования работы конечных автоматов | |
| 4 | Уметь применять теорию регулярных множеств и регулярных языков в различных системах программного обеспечения | |
| 5 | Владеть навыками реализации синхронных и асинхронных структурных автоматов по заданным критериям оптимизации |
Перечисленные РО являются основой для формирования следующих компетенций: (в соответствии с ФГОС ВПО и требованиями к результатам освоения основной образовательной программы (ООП))
| N | Шифр | Компетенция |
| 1 | ОК-4 | Использование на практике умения и навыки в организации исследовательских и проектных работ, в управлении коллективом |
| 2 | ПК-2 | Умение проводить анализ, синтез, оптимизацию решений с целью обеспечения качества объектов профессиональной деятельности |
| 3 | ПК-16 | Способность организовывать работу коллектива разработчиков порграммного продукта, умение осуществлять взаимодействие со смежниками |
| 4 | ПСК-8 | Способность осуществлять проектирование, разработку и моделирование систем массового обслуживания, применимых в профессиональной сфере, с помощью ЭВМ, применять теорию массового обслуживания для анализа программных продуктов, систем и вычислительных сетей |
-
СТРУКТУРА И СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
Общая трудоемкость дисциплины составляет 6 зачетных(ые) единиц(ы), 216 часа(ов).
| Модуль | Раздел | Лекции | Практич. занятия | Лаборат. работы | СРС | Всего часов | Всего с экзаменами и курсовыми |
| Дискретная математика и теория автоматов | Понятие алгебраической структуры. Теорема Лагранжа. | 4 | 4 | 0 | 24 | 32 | 216 |
| Булевы алгебры. Модели и алгебры, подсистемы, конгруэнции и фактор-системы. | 4 | 2 | 0 | 18 | 24 | ||
| Контекстно-свободные грамматики. Деревья разбора. | 6 | 8 | 8 | 66 | 88 | ||
| Автоматы с магазинной памятью | 4 | 6 | 8 | 54 | 72 | ||
| Всего | 18 | 20 | 16 | 162 | 216 | 216 | |
-
Содержание (дидактика) дисциплины
В разделе приводится полный перечень дидактических единиц, подлежащих усвоению при изучении данной дисциплины.
- 1. Понятие алгебраической структуры
- 2. n-арные операции на множестве, аргументы и результаты применения операции
- 3. Бинарные операции
- 4. Группы, полугруппы, подгруппы и подкольца
- 5. Сигнатура алгебры
- 6. Полукольца
- 7. Замкнутые полукольца
- 8. Области целостности как коммутативное кольцо
- 9. Теорема Лагранжа
- 10. Гомоморфизм колец
- 11. Модели и алгебры
- 12. Понятие подсистемы (подалгебры)
- 13. Замкнутость подмножеств
- 14. Булева алгебра как частный случай идемпотентного полукольца
- 15. Булевы векторы и кубы
- 16. Модель-алгебраическая система с пустым множеством операций
- 17. Подсистема алгебраической системы
- 18. Конгруэнции и фактор-системы
- 19. Фактор-алгебра
- 20. Определение контекстно-свободной грамматики
- 21. Порождения с использованием грамматик, левые и правые порождения
- 22. Язык, задаваемый грамматикой
- 23. Выводимые цепочки
- 24. Построение деревьев разбора
- 25. Крона дерева разбора
- 26. Вывод, порождение и деревья разбора
- 27. Графическое представление автоматов с магазинной памятью
- 28. Допустимость по заключительному состоянию, по пустому магазину
- 29. Языки автоматов с магазинной памятью
- 30. Эквивалентность автоматов с магазинной памятью и контекстно-свободных грамматик
- 31. Автоматы с магазинной памятью и неоднозначные грамматики
-
Лекции
| № п/п | Раздел дисциплины | Объем, часов | Тема лекции | Дидакт. единицы |
| 1 | 1.1.Понятие алгебраической структуры. Теорема Лагранжа. | 2 | Понятие алгебраической структуры. Группы, полугруппы. Подгруппы и подкольца. | 1, 2, 3, 4, 5 |
| 2 | 1.1.Понятие алгебраической структуры. Теорема Лагранжа. | 2 | Полукольца, замкнутые полукольца, теорема Лагранжа | 6, 7, 8, 9, 10 |
| 3 | 1.2.Булевы алгебры. Модели и алгебры, подсистемы, конгруэнции и фактор-системы. | 2 | Булевы алгебры. Конечные булевы алгебры. Булевы векторы и кубы. | 11, 12, 13, 14, 15 |
| 4 | 1.2.Булевы алгебры. Модели и алгебры, подсистемы, конгруэнции и фактор-системы. | 2 | Модель-алгебраическая система с пустым множеством операций. Подсистема алгебраической системы. Конгруэнции и фактор-системы. Фактор-алгебра. | 16, 17, 18, 19 |
| 5 | 1.3.Контекстно-свободные грамматики. Деревья разбора. | 2 | Контекстно-свободные грамматики. Порождения с использованием грамматик. Выводимые цепочки | 20, 21, 22, 23 |
| 6 | 1.3.Контекстно-свободные грамматики. Деревья разбора. | 2 | Деревья разбора. Построение деревьев разбора. | 24, 25 |
| 7 | 1.3.Контекстно-свободные грамматики. Деревья разбора. | 2 | Вывод, порождение и деревья разбора | 26 |
| 8 | 1.4.Автоматы с магазинной памятью | 2 | Автоматы с магазинной памятью. Графическое представление МП-автоматов. | 27, 28 |
| 9 | 1.4.Автоматы с магазинной памятью | 2 | Языки МП-автоматов. Эквивалентность МП-автоматов и КС-грамматик. МП-автоматы и неоднозначные грамматики. | 29, 30, 31 |
| Итого: | 18 | |||
-
Практические занятия
| № п/п | Раздел дисциплины | Объем, часов | Тема практического занятия | Дидакт. единицы |
| 1 | 1.1.Понятие алгебраической структуры. Теорема Лагранжа. | 2 | Нейтральные элементы относительно операции умножения. Определение носителя заданной алгебры. | 1, 17 |
| 2 | 1.1.Понятие алгебраической структуры. Теорема Лагранжа. | 2 | Полукольца. Теорема Лагранжа. Пример решения системы линейных алгебраических уравнений в поле. | 6, 9, 7, 8 |
| 3 | 1.2.Булевы алгебры. Модели и алгебры, подсистемы, конгруэнции и фактор-системы. | 2 | Конечные булевы алгебры. Определение векторов и скаляров заданной группы. Доказательство изоморфизма заданной алгебры прямому произведению двух алгебр | 14, 16, 17 |
| 4 | 1.3.Контекстно-свободные грамматики. Деревья разбора. | 2 | Построение КС-грамматик для различных языков | 20, 21, 22 |
| 5 | 1.3.Контекстно-свободные грамматики. Деревья разбора. | 4 | Построение дерева разбора | 24, 25 |
| 6 | 1.3.Контекстно-свободные грамматики. Деревья разбора. | 2 | От выводов к деревьям разбора. От деревьев к порождениям. | 26 |
| 7 | 1.4.Автоматы с магазинной памятью | 2 | Конгруэнции и фактор-системы | 18 |
| 8 | 1.4.Автоматы с магазинной памятью | 2 | Создание лексического анализатора | 27, 29 |
| 9 | 1.4.Автоматы с магазинной памятью | 2 | Языки описания документов | 29, 30, 31 |
| Итого: | 20 | |||
-
Лабораторные работы
| № п/п | Раздел дисциплины | Наименование лабораторной работы | Наименование лаборатории | Объем, часов | Дидакт. единицы |
| 1 | 1.3.Контекстно-свободные грамматики. Деревья разбора. | Алгоритм порождения по заданной грамматике | 4 | 21 | |
| 2 | 1.3.Контекстно-свободные грамматики. Деревья разбора. | Построение дерева разбора | 4 | 24 | |
| 3 | 1.4.Автоматы с магазинной памятью | Моделирование автомата с магазинной памятью | 4 | 27, 29 | |
| 4 | 1.4.Автоматы с магазинной памятью | Трансляция языка вещественных констант | 4 | 29 | |
| Итого: | 16 | ||||
-
Типовые задания
| № п/п | Раздел дисциплины | Объем, часов | Наименование типового задания |
| Итого: | |||
-
Курсовые работы и проекты по дисциплине
-
Рубежный контроль
-
Промежуточная аттестация
1. Зачет с оценкой (1 семестр)
