Дискретная математика. Алгоритмы и программы
ОглавлениеПредисловиеГлава 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. Функция Мебиуса. Формула обращения Мёбиуса |
