Дискретная математика. Курс лекций и практических занятий

Рассмотрены вопросы трех разделов, изучаемых в курсе дискретной математики: теории множеств, комбинаторики и теории графов. Изложены основные теоретические сведения и приведены многочисленные примеры решения задач по всем разделам. Для теории множеств обсуждена основная система аксиом, ее модификации и перспективы дальнейшего развития теории на основе аксиоматического метода. Рассмотрены основные типы задач комбинаторики, основанные на 4-х схемах выбора элементов множеств. Приведены основные наиболее употребительные оптимизационные алгоритмы теории графов, алгоритмы сетевого планирования и варианты заданий для выполнения контрольных и расчетно-графических работ.
Для студентов, аспирантов и преподавателей технических вузов
ЧАСТЬ I. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ КУРСА
Глава 1. Элементы теории множеств
1.1. Множества и действия над ними
1.2. Отношения и функции. Специальные бинарные отношения
1.3. Практическое занятие 1. Операции над множествами. Отношения и функции
1.4. Эквивалентные, конечные и бесконечные множества
1.5. Практическое занятие 2. Кардинальные числа
1.6. Аксиомы теории множеств
Глава 2. Комбинаторика
2.1. Основные определения комбинаторного анализа
2.2. Правило суммы и правило произведения
2.3. Формулы для расчета перестановок и сочетаний без повторений и с повторениями
2.4. Бином Ньютона и полиномиальная теорема
2.4.1. Бином Ньютона
2.4.2. Полиномиальная теорема
2.5. Практическое занятие 3. Правила суммы и произведения. Перестановки и сочетания. Свойства биномиальных коэффициентов
2.6. Метод рекуррентных соотношений
2.7. Метод производящих функций
2.8. Производящие функции для некоторых схем выбора
2.8.1. Производящая функция для (л,г)-сочетаний с ограниченным числом повторений
2.8.2. Производящая функция для (я,г)-сочетаний с неограниченным числом повторений
2.9. Применение производящих функций для получения комбинаторных чисел !
2.10. Однородные и неоднородные линейные рекуррентные соотношения
2.11. Экспоненциальные производящие функции
2.12. О приложениях теории производящих функций к теории вероятностей
2.13. Практическое занятие 4. Производящие функции и рекуррентные соотношения
2.14. Метод включений и исключений
2.15. Учет весов элементов в формуле включений и исключений
2.16. Функция Эйлера
2.17. Функция Мебиуса
2.18. Практическое занятие 5. Формула включений и исключений
Глава 3. Теория графов
3.1. Основные понятия и определения
3.2. Операции над графами
3.3. Маршруты, цепи, циклы
3.4. Способы задания графов
3.5. Метрические характеристики графа
3.6. Упорядочивание дуг и вершин орграфа
3.7. Выявление маршрутов с заданным количеством ребер
3.8. Определение экстремальных путей на графах. Метод Шимбелла
3.9. Практическое занятие 6. Способы задания графов.
Операции над графами. Метрические характеристики графов.
Упорядочивание элементов орграфов
3.10. Нахождение кратчайших путей. Алгоритм Дейкстры
3.11. Нахождение кратчайших путей. Алгоритм Веллмана—Мура
3.12. Алгоритм нахождения максимального пути
3.13. Особенности алгоритмов теории графов
3.14. Практическое занятие 7. Нахождение минимальных и максимальных путей на орграфах
3.15. Деревья (основные определения)
3.16. Задача об остове экстремального веса
3.17. Обходы графов. Фундаментальные циклы
3.18. Клики, независимые множества
3.19. Практическое занятие 8. Остовы графов, фундаментальные циклы.
Эйлеровы и гамильтоновы графы. Доминирующие множества и клики
3.20. Планарность графов
3.21. Алгоритм укладки графа на плоскости
3.22. Хроматические графы. Раскраски графов
3.23. Практическое занятие 9. Планарные и хроматические графы
3.24. Потоки в сетях
3.25. Теорема Форда-Фалкерсона
3.26. Поток минимальной стоимости
3.27. Элементы сетевого планирования.
Критические пути, работы, резервы
3.28. Линейные графики
3.29. Практическое занятие 10. Потоки в сетях.
Сетевые и линейные графики
ЧАСТЬ И. ОТВЕТЫ, РЕШЕНИЯ, УКАЗАНИЯ
Глава 4. Теория множеств
4.1. Ответы и решения задач практического занятия 1
4.2. Ответы и решения задач практического занятия 2
Глава 5. Комбинаторика
5.1. Ответы и решения задач практического занятия 3
5.2. Ответы и решения задач практического занятия 4
5.3. Ответы и решения задач практического занятия 5
Глава 6. Теория графов
6.1. Ответы и решения задач практического занятия 6
6.2. Ответы задач практического занятия 7
6.3. Ответы и решения задач практического занятия 8
6.4. Ответы и решения задач практического занятия 9
Ответы и решения задач практического занятия 10
Предметный указатель