Дискретная математика. Алгоритмы и программы

  

Иванов Б. Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие. — М.: Лаборатория Базовых Знаний, 2001 — 288 с.

Книга посвящена современному курсу дискретной математики. Теоретические основы курса сопровождаются практически значимыми алгоритмами, реализованными в конкретных компьютерных программах. Книгу можно рассматривать в качестве хорошего справочника методов и алгоритмов дискретной математики, широко применяемых в практическом программировании.

Пособие рассчитано на студентов специальностей, учебные планы которых предполагают изучение каких-либо разделов курса дискретной математики, в первую очередь на математиков-прикладников, а также программистов, занятых разработкой прикладного программного обеспечения.



Оглавление

Предисловие
Глава 1. Комбинаторные схемы
1.1. Правило суммы
1.2. Правило прямого произведения
1.3. Размещения с повторениями
1.4. Размещения без повторений
1.5. Перестановки
1.6. Сочетания
1.7. Сочетания с повторениями
1.8. Перестановки с повторениями, мультимножества
1.9. Упорядоченные разбиения множества
1.10. Неупорядоченные разбиения множества
1.11. Полиномиальная формула
1.12. Бином Ньютона
1.13. Инверсии
1.14. Обратные перестановки
Глава 2. Представление абстрактных объектов
2.1. Представление последовательностей
2.2. Представление деревьев
2.3. Представление множеств
Глава 3. Методы подсчета и оценивания
3.1. Производящие функции
3.2. Линейные рекуррентные соотношения
3.3. Неоднородные линейные рекуррентные соотношения
3.4. Обобщенное правило произведения
3.5. Принцип включения и исключения
3.6. Ладейные многочлены и многочлены попаданий
Глава 4. Генерация комбинаторных объектов
4.2. Перестановки различных элементов
4.3. Эффективное порождение перестановок
4.4. Порождение подмножеств множества
4.5. Генерация размещений с повторениями
4.6. Порождение сочетаний
4.7. Порождение композиций и разбиений
4.8. Генерация случайных перестановок
Глава 5. Сортировка и поиск
5.1. Сортировка вставками
5.2. Пузырьковая сортировка
5.3. Сортировка перечислением
5.4. Сортировка всплытием Флойда
5.5. Последовательный поиск
5.6. Логарифмический поиск
5.7. Сортировка с вычисляемыми адресами
Глава 6. Введение в теорию графов. Алгоритмы на графах
6.2. Представления графов
6.3. Метод поиска в глубину
6.4. Отношение эквивалентности
6.5. Связные компоненты
6.6. Выделение компонент связности
6.7. Эйлеровы графы
6.8. Остовные деревья
6.8.1. Жадный алгоритм построения минимального остовного дерева
6.8.2. Алгоритм ближайшего соседа построения остовного дерева
6.9. Кратчайшие пути на графе
6.10. Потоки в сетях
6.11. Клики, независимые множества
6.12. Циклы, фундаментальные множества циклов
6.13. Листы и блоки
6.14. Двудольные графы
6.15. Хроматические графы
6.16. Диаметр, радиус и центры графа
Глава 7. Введение в теорию групп. Приложения
7.2. Гомоморфизм групп
7.3. Смежные классы
7.4. Строение коммутативных (абелевых) групп
7.5. Строение некоммутативных групп
7.6. Симметрическая группа подстановок
7.7. Действие групп на множестве
7.8. Цикловой индекс группы
7.9. Теория перечисления Пойа
7.10. Цикловая структура групп подстановок
Глава 8. Элементы теории чисел
8.1. Наибольший общий делитель
8.2. Наименьшее общее кратное
8.3. Простые числа
8.4. Сравнения, свойства сравнений
8.5. Полная система вычетов
8.6. Приведенная система вычетов
8.7. Функция Эйлера
8.8. Функция Мебиуса. Формула обращения Мёбиуса