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

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

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

ЛИТЕРАТУРА

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лекции

МОДУЛЬ 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.

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

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

ОЛ-1 7.1, 7.4.

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

ОЛ-1 7.5.

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

ОЛ-1 7.6, 7.7.

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

ОЛ-1 7.8.

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

Лекция 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.

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

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

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

ЛИТЕРАТУРА

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лекции

МОДУЛЬ 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.