Дискретная математика. Теория и практика решения задач по информатике

Предисловие
Глава 1. Основные методы дискретной математики
(счет и перебор)
1.1. Счет и перебор
1.2. Асимптотические обозначения и основная
теорема
1.3. Эффект "комбинаторного взрыва"
Упражнения и задачи
Комментарии
Глава 2. Основные комбинаторные принципы и
понятия в примерах
2.1. Принципы сложения и умножения
2.2. Подмножества
2.3. Принцип включения и исключения
2.4. Выборки
2.5. Размещения с повторениями
2.6. Размещения без повторений
2.7. Сочетания без повторений
2.8. Бином Ньютона и полиномиальная
формула (комбинаторный смысл)
2.9. Сочетания с повторениями
2.10. Перестановки без повторений
2.11. Перестановки с повторениями
2.12. Задача о размещениях
2.13. Разбиения
2.14. Разбиения на циклы
2.15. Разбиение числа на слагаемые
Упражнения и задачи
Комментарии
Глава 3. Перечисление комбинаторных объектов
3.1. Общая схема генерации комбинаторных
объектов . .
3.2. Генерация перестановок без повторений
3.3. Генерация сочетаний без повторений
3.4. Генерация размещений без повторений
3.5. Генерация перестановок с повторениями
3.6. Генерация сочетаний с повторениями
3.7. Генерация размещений с повторениями
3.8. Генерация подмножеств
3.9. Генерация разбиений
3.10. Генерация разбиений на циклы
3.11. Генерация разбиений числа на слагаемые
Упражнения и задачи
Комментарии
Глава 4. Рекуррентные и нерекуррентные формулы
4.1. Простые примеры
4.2. Числа Фибоначчи
4.3. Числа Каталана
4.4. Схема нахождения общего решения
линейных рекуррентных уравнений
4.5. Производящие функции
4.6. Ладейные полиномы
4.7. Аддитивность задач, или динамическое
программирование
Упражнения и задачи
Комментарии
Глава 5. Понятие графа, основные методы
просмотра вершин графа
5.1. Терминология
5.2. Способы представления графа
5.3. Поиск в глубину
5.4. Поиск в ширину
5.5. Основные понятия
Упражнения и задачи
Комментарии
Глава 6. Деревья
6.1. Определение дерева
6.2. Перечисление остовных деревьев
связного помеченного графа
6.3. Матричная формула Кирхгофа
6.4. Алгоритм представления дерева в виде
последовательности чисел
6.5. Остовные деревья минимального веса
6.6. Задача Штейнера
Упражнения и задачи
Комментарии
Глава 7. Связность
7.1. Вершинная и реберная связность
7.2. Метод нахождения блоков графа
7.3. Теорема Менгера
7.4. Связность в орграфе
Упражнения и задачи
Комментарии
Глава 8. Циклы
8.1. Эйлеровы графы
8.2. Гамильтоновы графы
8.3. Фундаментальное множество циклов
8.4. Матроиды
Упражнения и задачи
Комментарии
Глава 9. Покрытия и независимость
9.1. Основные понятия
9.2. Метод генерации всех максимальных
независимых множеств вершин графа
9.3. Клики
9.4. Доминирующие множества
9.5. Паросочетания
9.6. Матроиды трансверсалей
9.7. Диаграмма взаимосвязей между задачами
Упражнения и задачи
Комментарии
Глава 10. Планарные графы
10.1. Основные понятия
10.2. Формула Эйлера
10.3. Алгоритм укладки графа на плоскости
Упражнения и задачи
Комментарии
Глава И. Раскраска вершин графа
11.1. Хроматическое число
11.2. Метод правильной раскраски
11.3. Методы поиска минимальной раскраски
Упражнения и задачи
Комментарии
Глава 12. Кратчайшие пути в графе
12.1. Постановка задачи. Вывод пути
12.2. Алгоритмы поиска кратчайших путей
Упражнения и задачи
Комментарии
Глава 13. Потоки в сетях
13.1. Основные понятия и постановка задачи
13.2. Алгоритм К. Эдмондса-Р. Карпа
13.3. Введение в метод блокирующих потоков
или алгоритм Е. А. Диница
13.4. Модификация алгоритма Е. А. Диница
Упражнения и задачи
Комментарии
Ответы и решения
Задачи для самостоятельного решения
Приложение 1. Математические факты и
доказательства
отдельных теорем
Приложение 2. Описание основных элементов
языков программирования Паскаль, визуального
Бейсика и C++
Литература
Предметный указатель