Модуль 1: Множества, отношения, алгебры




Скачать 64.66 Kb.
Дата04.08.2016
Размер64.66 Kb.

Дискретная математика


3-й семестр 2013–2014, спец. ИУ-7

МОДУЛЬ 1: Множества, отношения, алгебры


Виды аудиторных занятий
и самостоятельной работы


Сроки проведения или выполнения,
недели

Трудоемкость, часы

Примечание

Лекции

1-10

20




Практические занятия

1-6

12




Домашние задания текущие

1-6

12




Рубежный контроль по модулю

9

2



МОДУЛЬ 2: Элементы теории графов. Регулярные языки и конечные автоматы


Виды аудиторных занятий
и самостоятельной работы


Сроки проведения или выполнения,
недели

Трудоемкость, часы

Примечание

Лекции

11-20

20




Практические занятия

7-13

14




Домашние задания текущие

1-9

30




Дом. задание «Регулярные языки и конечные автоматы»

8–14

8




Рубежный контроль по модулю

14

2



МОДУЛЬ 3: Элементы комбинаторики


Виды аудиторных занятий
и самостоятельной работы


Сроки проведения или выполнения,
недели

Трудоемкость, часы

Примечание

Лекции

21-25

11




Практические занятия

14-17

8




Домашние задания текущие

14-17

8




Дом. задание «Элементы комбинаторики»

14–17

6




Рубежный контроль по модулю

17

2



Лекции

МОДУЛЬ 1: Множества, отношения, алгебры


Лекция 1. Предмет и метод дискретной математики. Множества. Кортеж. Декартово произведение.

ОЛ-1 1.1, 1.2; ОЛ-2 1.1.

ДЛ-4 1.6; МРК, конспект лекций.

Лекция 2. Отношение арности . Отображения и их классификация. Операции и предикаты.

ОЛ-1 1.3, 2.2; ОЛ-2 1.3.



Лекции 3–4. Отношения эквивалентности и фактор-множества. Частично упорядоченные (ч.у.) множества. Теорема о неподвижной точке.

ОЛ-1 1.5–1.8, 1.9.



Лекция 5. Алгебраические структуры. Группоиды, полугруппы, группы.

ОЛ-1 2.1–2.2; ОЛ-2 2.1, 2.2.



Лекция 6. Циклические группы. Подгруппы. Теорема Лагранжа.

ОЛ1 2.6, 2.7, ОЛ-2 2.1, 2.2.



Лекции 7–8. Кольца, тела, поля.

ОЛ1 2.3, 2.4, ОЛ-2 2.1, 2.2.



Лекции 9–10. Полукольца. Решение систем линейных уравнений в замкнутых полукольцах.

ОЛ1 3.1–3.3.


МОДУЛЬ 2: Элементы теории графов. Регулярные языки и конечные автоматы


Лекция 11. Основные понятия теории графов: неориентированные и ориентированные графы, цепи, пути, циклы, контуры. Подграфы. Компоненты и бикомпоненты.

ОЛ-1 5.1; ДЛ-2 гл.2 §2, 3; ДЛ-7 гл. 1.



Лекция 12. Деревья и их классификация. Теорема о числе листьев в полном бинарном дереве. Дерево решений и задача сортировки.

ОЛ-1 5.3; ДЛ-2 3.4.



Лекции 13-14. Методы систематического обхода вершин графа: поиск в глубину и поиск в ширину.

ОЛ-1 5.5; ДЛ-2 5.2, 5.4.



Лекция 15. Гомоморфизм и изоморфизм графов. Группа автоморфизмов графа и ее вычисление.

ОЛ-1 5.7; ДЛ-7 гл. 1, §11.



Лекция 16. Задача о путях во взвешенном ориентированном графе и ее решение с помощью алгоритма Флойда — Уоршелла — Клини. Задача о достижимости и поиске кратчайших расстояний между двумя узлами графа.

ОЛ-1 5.6; ДЛ-2 5.6–5.10; ДЛ-4 гл. 3 §1.



Лекция 17. Алфавит, слово, язык. Операции над языками, регулярные языки.

ОЛ-1 7.1, 7.4.



Лекция 18. Понятие конечного автомата (КА). Анализ и синтез КА. Теорема Клини о совпадении класса языков, допускаемых КА и класса регулярных языков.

ОЛ-1 7.5.



Лекция 19. Детерминизация и минимизация КА. Регулярность дополнения регулярного языка и пересечения двух регулярных языков. Проблемы пустоты и эквивалентности.

ОЛ-1 7.6, 7.7.



Лекция 20. Лемма о разрастании для регулярных языков.

ОЛ-1 7.8.


МОДУЛЬ 3: Элементы комбинаторики


Лекция 21. Основные комбинации. Формулы включения и исключения.

ОЛ-2 часть 2, §3; ОЛ-4 12.3, 11.1, 11.2; ОЛ-5 1.1, 1.2; ДЛ-9 2.14, 2.15.



Лекция 22. Ладейные полиномы. Подстановки с запрещенными позициями. Сюръекции и разбиения.

ОЛ-4 12.3, 12.4.

Лекция 23. Линейные рекуррентные соотношения.

ОЛ-4 11.1–11.2; ОЛ-5 2.1–2.4, ДЛ-9 2.7–2.9, 2.11.



Лекция 24–25. Теория перечисления Пойя. Производящие функции.

ОЛ-4 19.1, 19.2, 13.1, 13.2, 13.5; ОЛ-5 3.1–3.4; ДЛ-10, с. 61–107.


Практические занятия

МОДУЛЬ 1: Множества, отношения, алгебры


Занятие 1. Доказательство теоретико-множественных тождеств.

ОЛ-1 Д.1.2, задачи 1.1–1.6.



Занятие 2. Операции над соответствиями. Исследование свойств бинарных отношений.

ОЛ-1 задачи 1.7–1.20.



Занятие 3. Отношения эквивалентности и порядка.

ОЛ-1 задачи 1.21–1.31.



Занятие 4. Группоиды, полугруппы, группы

ОЛ-1 задачи 2.1–2.8.



Занятие 5. Кольца, тела, поля. Полукольца.

ОЛ- 1 задачи 2.10–2.19; 3.1–3.4.



Занятие 6. Рубежный контроль по модулю 1.

МОДУЛЬ 2: Элементы теории графов. Регулярные языки и конечные автоматы


Занятие 7. Основные понятия теории графов. Некоторые комбинаторные задачи на графах .

ОЛ-1 задачи 5.1–5.19.



Занятие 8. Поиск в глубину и поиск в ширину.

ОЛ-1 задачи 5.25–5.31.



Занятие 9. Распознавание изоморфизма графов. Группа автоморфизмов графа и ее вычисление.

ОЛ-1 задачи 5.6, 5.8; ОЛ-5 3.1.



Занятие 10. Задача о путях во взвешенном ориентированном графе и ее решение с помощью алгоритма Флойда — Уоршелла — Клини. Задача о достижимости и поиске кратчайших расстояний между двумя узлами графа.

ОЛ-1 задачи 5.32–5.34.



Занятие 11. Анализ и синтез конечных автоматов. Детерминизация и минимизация конечных автоматов.

ОЛ-1 задачи 7.9–7.21.

ОЛ-1 задачи 7.29–7.33; задача 7.34.

Занятие 12. Лемма о разрастании для регулярных языков.

Занятие 13. Рубежный контроль по модулю 2.

ОЛ-1 задача 7.35.


МОДУЛЬ 3: Элементы комбинаторики


Занятие 14. Элементы комбинаторики: формулы включения и исключения.

ОЛ-5 1.3.



Занятие 15. Рекуррентные соотношения.

ОЛ-4 задачи к разд. 11.2; ОЛ-5 2.4.



Занятие 16. Производящие функции. Элементы теории Пойя.

ОЛ-4 задачи к разд. 13.3, 19.1 и 19.2; ОЛ-5 3.5.



Занятие 17. Рубежный контроль по модулю 3.

Контрольные мероприятия

МОДУЛЬ 1: Множества, отношения, алгебры


1.Рубежный контроль по модулю (8 неделя).

МОДУЛЬ 2: Элементы теории графов. Регулярные языки и конечные автоматы


2.Домашнее задание «Регулярные языки и конечные автоматы» (14 неделя).

3.Рубежный контроль по модулю (14 неделя).


МОДУЛЬ 3: Элементы комбинаторики


4.Домашнее задание «Элементы комбинаторики» (17 неделя).

5.Рубежный контроль по модулю (17 неделя).


ЛИТЕРАТУРА

Основная литература (ОЛ)


6.Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб. для вузов / Под ред. В.С. Зарубина и А.П. Крищенко. – 4-е изд. - М. Изд-во МГТУ им. Н.Э. Баумана, 2006, – 743 с.

7.Яблонский С.В. Введение в дискретную математику. – 3-е изд.. – М: Высшая школа, 2001. – 384 с.

8.Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. – 2-е изд. – М: Наука, 1992, – 368 с.

9.Дж. Андерсон. Дискретная математика и комбинаторика. – М., СПб, Киев: Изд. Дом. «Вильямс», 2003. – 960 с.

10.Белоусов А.И., Власов П.А. Элементы комбинаторики: метод. указания к выполнению домашнего задания. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2012. – 53 с.

Дополнительная литература (ДЛ)


  1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. В 2 т. – М.: Мир, 1978.

11.Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979. – 536 с.

12.Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений, 2-е изд.. – М.: Издательский дом «Вильямс», 2002. – 528 с.

13.Евстигнеев В.А. Применение теории графов в программировании. – М.: Наука, 1985. – 352 с.

14.Блюменфельд В.К., Котов В.Е. Теория схем программ. – М.: Наука, 1991. – 248 с.

15.Зыков А.А. Основы теории графов. – М.: «Вузовская книга», 2004. – 664 с.

16.Лекции по теории графов / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. – М: Наука, 1990. – 383 с.

17.Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М: Наука, 1975, – 240 с.

18.Шапорев С.Д. Дискретная математика: курс лекций и практических занятий. – СПб, БХВ-Петербург, 2006. – 400 с.

19.Прикладная комбинаторная математика (сб. статей). – М.: Мир, 1968.- 362 с.

Кафедра ФН-12


Ответственный по кафедре А.Н. Канатников
Автор документа А.И. Белоусов

Телефон (499) 263-62-88




База данных защищена авторским правом ©uverenniy.ru 2016
обратиться к администрации

    Главная страница