Дискретная математика: Учебник для вузов. Стандарт третьего поколения

Description

Предисловие Введение Глава 1. Множества и отношения 1.1. Множества 1.1.1. Элементы и множества 1.1.2. Задание множеств 1.1.3. Парадокс Рассела 1.1.4. Мультимножества 1.2. Алгебра подмножеств 1.2.1. Сравнение множеств 1.2.2. Равномощные множества 1.2.3. Конечные и бесконечные множества 1.2.4. Добавление и удаление элементов 1.2.5. Мощность конечного множества 1.2.6. Операции над множествами 1.2.7. Разбиения и покрытия 1.2.8. Булеан 1.2.9. Свойства операций над множествами 1.3. Представление множеств в программах 1.3.1. Битовые шкалы 1.3.2. Генерация всех подмножеств универсума 1.3.3. Алгоритм построения бинарного кода Грея 1.3.4. Представление множеств упорядоченными списками 1.3.5. Проверка включения слиянием 1.3.6. Вычисление объединения слиянием 1.3.7. Вычисление пересечения слиянием 1.3.8. Представление множеств итераторами 1.4. Отношения 1.4.1. Упорядоченные пары и наборы 1.4.2. Прямое произведение множеств 1.4.3. Бинарные отношения 1.4.4. Композиция отношений 1.4.5. Степень отношения 1.4.6. Свойства отношений 1.4.7. Ядро отношения 1.4.8. Представление отношений в программах 1.5. Замыкание отношений 1.5.1. Транзитивное и рефлексивное замыкание 1.5.2. Алгоритм Уоршалла 1.6. Функции 1.6.1. Функциональные отношения 1.6.2. Инъекция 1.6.3. Образы и прообразы 1.6.4. Суперпозиция функций 1.6.5. Представление функций в программах 1.7. Отношения эквивалентности 1.7.1. Классы эквивалентности 1.7.2. Фактормножества 1.7.3. Ядро функционального отношения и множества уровня 1.8. Отношения порядка 1.8.1. Определения 1.8.2. Минимальные элементы 1.8.3. Алгоритм топологической сортировки 1.8.4. Верхние и нижние границы 1.8.5. Монотонные функции 1.8.6. Вполне упорядоченные множества 1.8.7. Индукция 1.8.8. Алфавит Комментарии Упражнения Глава 2. Алгебраические структуры 2.1. Алгебры и морфизмы 2.1.1. Операции и их носитель 2.1.2. Замыкания и подалгебры 2.1.3. Система образующих 2.1.4. Свойства операций 2.1.5. Гомоморфизмы 2.1.6. Изоморфизмы 2.2. Алгебры с одной операцией 2.2.1. Полугруппы 2.2.2. Определяющие соотношения 2.2.3. Моноиды 2.2.4. Группы 2.2.5. Группа перестановок 2.3. Алгебры с двумя операциями 2.3.1. Кольца 2.3.2. Области целостности 2.3.3. Поля 2.4. Векторные пространства и модули 2.4.1. Векторное пространство 2.4.2. Линейные комбинации 2.4.3. Базис и размерность 2.4.4. Модули 2.5. Решётки 2.5.1. Определения 2.5.2. Ограниченные решётки 2.5.3. Решётка с дополнением 2.5.4. Частичный порядок в решётке 2.5.5. Булевы алгебры 2.6. Матроиды и жадные алгоритмы 2.6.1. Матроиды 2.6.2. Максимальные независимые подмножества 2.6.3. Базисы 2.6.4. Жадный алгоритм 2.6.5. Примеры матроидов Комментарии Упражнения Глава 3. Булевы функции 3.1. Элементарные булевы функции 3.1.1. Функции алгебры логики 3.1.2. Существенные и несущественные переменные 3.1.3. Булевы функции одной переменной 3.1.4. Булевы функции двух переменных 3.2. Формулы 3.2.1. Реализация функций формулами 3.2.2. Равносильные формулы 3.2.3. Подстановка и замена 3.2.4. Алгебра булевых функций 3.3. Двойственность 3.3.1. Двойственная функция 3.3.2. Реализация двойственной функции 3.3.3. Принцип двойственности 3.4. Нормальные формы 3.4.1. Разложение булевых функций по переменным 3.4.2. Совершенные нормальные формы 3.4.3. Эквивалентные преобразования 3.4.4. Минимальные дизъюнктивные формы 3.4.5. Геометрическая интерпретация 3.4.6. Сокращённые дизъюнктивные формы 3.5. Полнота 3.5.1. Замкнутые классы 3.5.2. Полные системы функций 3.5.3. Полнота двойственной системы 3.5.4. Теорема Поста 3.6. Представление булевых функций в программах 3.6.1. Табличные представления 3.6.2. Строковые представления 3.6.3. Алгоритм вычисления значения булевой функции 3.6.4. Деревья решений Комментарии Упражнения Глава 4. Логические исчисления 4.1. Логические связки 4.1.1. Высказывания 4.1.2. Формулы 4.1.3. Интерпретация 4.1.4. Логическое следование и логическая эквивалентность 4.1.5. Подстановка и замена 4.2. Формальные теории 4.2.1. Определение формальной теории 4.2.2. Выводимость 4.2.3. Интерпретация 4.2.4. Общезначимость и непротиворечивость 4.2.5. Полнота 4.3. Исчисление высказываний 4.3.1. Классическое определение исчисления высказываний 4.3.2. Частный случай формулы 4.3.3. Алгоритм унификации 4.3.4. Конструктивное определение исчисления высказываний 4.3.5. Производные правила вывода 4.3.6. Дедукция 4.3.7. Некоторые теоремы исчисления высказываний 4.3.8. Множество теорем исчисления высказываний 4.3.9. Другие аксиоматизации исчисления высказываний 4.4. Исчисление предикатов 4.4.1. Определения 4.4.2. Интерпретация 4.4.3. Общезначимость 4.4.4. Непротиворечивость и полнота чистого исчисления предикатов 4.4.5. Логическое следование и логическая эквивалентность 4.4.6. Теория равенства 4.4.7. Формальная арифметика 4.4.8. Неаксиоматизируемые теории 4.4.9. Теоремы Гёделя о неполноте 4.5. Автоматическое доказательство теорем 4.5.1. Постановка задачи 4.5.2. Доказательство от противного 4.5.3. Сведение к предложениям 4.5.4. Правило резолюции для исчисления высказываний 4.5.5. Правило резолюции для исчисления предикатов 4.5.6. Опровержение методом резолюций 4.5.7. Алгоритм метода резолюций Комментарии Упражнения Глава 5. Комбинаторика 5.1. Комбинаторные задачи 5.1.1. Комбинаторные конфигурации 5.1.2. Размещения 5.1.3. Размещения без повторений 5.1.4. Перестановки 5.1.5. Сочетания 5.1.6. Сочетания с повторениями 5.2. Перестановки 5.2.1. Графическое представление перестановок 5.2.2. Инверсии 5.2.3. Генерация перестановок 5.2.4. Двойные факториалы 5.3. Биномиальные коэффициенты 5.3.1. Элементарные тождества 5.3.2. Бином Ньютона 5.3.3. Свойства биномиальных коэффициентов 5.3.4. Треугольник Паскаля 5.3.5. Генерация подмножеств 5.3.6. Мультимножества и последовательности 5.3.7. Мультиномиальные коэффициенты 5.4. Разбиения 5.4.1. Определения 5.4.2. Числа Стирлинга второго рода 5.4.3. Числа Стирлинга первого рода 5.4.4. Число Белла 5.5. Включения и исключения 5.5.1. Объединение конфигураций 5.5.2. Формула включений и исключений 5.5.3. Число булевых функций 5.6. Формулы обращения 5.6.1. Теорема обращения 5.6.2. Формулы обращения для биномиальных коэффициентов 5.6.3. Формулы для чисел Стирлинга 5.7. Производящие функции 5.7.1. Основная идея 5.7.2. Метод неопределённых коэффициентов 5.7.3. Числа Фибоначчи 5.7.4. Числа Каталана Комментарии Упражнения Глава 6. Кодирование 6.1. Алфавитное кодирование 6.1.1. Таблица кодов 6.1.2. Разделимые схемы 6.1.3. Префиксные схемы 6.1.4. Неравенство Макмиллана 6.2. Кодирование с минимальной избыточностью 6.2.1. Минимизация длины кода сообщения 6.2.2. Цена кодирования 6.2.3. Алгоритм Фано 6.2.4. Оптимальное кодирование 6.2.5. Алгоритм Хаффмена 6.3. Помехоустойчивое кодирование 6.3.1. Кодирование с исправлением ошибок 6.3.2. Возможность исправления всех ошибок 6.3.3. Кодовое расстояние 6.3.4. Код Хэмминга для исправления одного замещения 6.4. Сжатие данных 6.4.1. Сжатие текстов 6.4.2. Предварительное построение словаря 6.4.3. Алгоритм Лемпела-Зива 6.5. Шифрование 6.5.1. Криптография 6.5.2. Шифрование с помощью случайных чисел 6.5.3. Криптостойкость 6.5.4. Модулярная арифметика 6.5.5. Шифрование с открытым ключом 6.5.6. Цифровая подпись Комментарии Упражнения Глава 7. Графы 7.1. Определения графов 7.1.1. История теории графов 7.1.2. Основное определение 7.1.3. Смежность 7.1.4. Диаграммы 7.1.5. Орграфы 7.1.6. Изоморфизм графов 7.2. Элементы графов 7.2.1. Подграфы 7.2.2. Валентность 7.2.3. Маршруты 7.2.4. Связность 7.2.5. Расстояние между вершинами 7.2.6. Эксцентриситет и центр 7.3. Виды графов и операции над графами 7.3.1. Виды графов 7.3.2. Двудольные графы 7.3.3. Направленные орграфы и сети 7.3.4. Операции над графами 7.4. Представление графов в программах 7.4.1. Требования к представлению графов 7.4.2. Матрица смежности 7.4.3. Матрица инциденций 7.4.4. Списки смежности 7.4.5. Массив дуг 7.4.6. Обходы графов 7.5. Орграфы и бинарные отношения 7.5.1. Графы и отношения 7.5.2. Достижимость и частичное упорядочение 7.5.3. Транзитивное замыкание Комментарии Упражнения Глава 8. Связность 8.1. Компоненты связности 8.1.1. Объединение графов и компоненты связности 8.1.2. Точки сочленения 8.1.3. Вершинная и рёберная связность 8.1.4. Оценка числа рёбер 8.2. Теорема Менгера 8.2.1. Непересекающиеся цепи и разделяющие множества 8.2.2. Теорема Менгера в «вершинной форме» 8.2.3. Варианты теоремы Менгера 8.3. Теорема Холла 8.3.1. Задача о свадьбах 8.3.2. Трансверсаль 8.3.3. Совершенное паросочетание 8.3.4. Теорема Холла — формулировка и доказательство 8.4. Потоки в сетях 8.4.1. Определение потока 8.4.2. Разрезы 8.4.3. Теорема Форда-Фалкерсона 8.4.4. Алгоритм нахождения максимального потока 8.4.5. Связь между теоремой Менгера и теоремой Форда-Фалкерсона 8.5. Связность в орграфах 8.5.1. Сильная 8.5.2. Компоненты сильной связности 8.5.3. Выделение компонент сильной связности 8.6. Кратчайшие пути 8.6.1. Длина дуг 8.6.2. Алгоритм Флойда 8.6.3. Алгоритм Дейкстры 8.6.4. Дерево кратчайших путей 8.6.5. Кратчайшие пути в бесконтурном орграфе Комментарии Упражнения Глава 9. Деревья 9.1. Свободные деревья 9.1.1. Определения 9.1.2. Основные свойства деревьев 9.1.3. Центр дерева 9.2. Ориентированные 9.2.1. Ориентированные деревья 9.2.2. Эквивалентное определение ордерева 9.2.3. Упорядоченные деревья 9.2.4. Бинарные деревья 9.3. Представление деревьев в программах 9.3.1. Представление свободных деревьев 9.3.2. Представление упорядоченных ориентированных деревьев 9.3.3. Число упорядоченных ориентированных деревьев 9.3.4. Проверка правильности скобочной структуры 9.3.5. Представление бинарных деревьев 9.3.6. Обходы бинарных деревьев 9.3.7. Алгоритм симметричного обхода бинарного дерева 9.4. Деревья сортировки 9.4.1. Ассоциативная память 9.4.2. Способы реализации ассоциативной памяти 9.4.3. Алгоритм бинарного (двоичного) поиска 9.4.4. Алгоритм поиска в дереве сортировки 9.4.5. Алгоритм вставки в дерево сортировки 9.4.6. Алгоритм удаления из дерева сортировки 9.4.7. Вспомогательные алгоритмы для дерева сортировки 9.4.8. Сравнение представлений ассоциативной памяти 9.4.9. Выровненные и полные деревья 9.4.10. Сбалансированные деревья 9.4.11. Балансировка деревьев 9.5. Кратчайший остов 9.5.1. Определения 9.5.2. Схема алгоритма построения кратчайшего остова 9.5.3. Алгоритм Краскала 9.5.4. Алгоритм Прима Комментарии Упражнения Глава 10. Циклы 10.1. Фундаментальные циклы и разрезы 10.1.1. Циклы и разрезы 10.1.2. Фундаментальная система циклов и циклический ранг 10.1.3. Фундаментальная система разрезов и коциклический ранг 10.1.4. Подпространства циклов и коциклов 10.2. Эйлеровы циклы 10.2.1. Эйлеровы графы 10.2.2. Алгоритм построения эйлерова цикла в эйлеровом графе 10.2.3. Оценка числа эйлеровых графов 10.3. Гамильтоновы циклы 10.3.1. Гамильтоновы графы 10.3.2. Задача коммивояжёра 10.4. Независимые и покрывающие множества 10.4.1. Покрывающие множества вершин и рёбер 10.4.2. Независимые множества вершин и рёбер 10.4.3. Связь чисел независимости и покрытий 10.5. Построение независимых множеств вершин 10.5.1. Постановка задачи отыскания наибольшего независимого множества вершин 10.5.2. Поиск с возвратами 10.5.3. Улучшенный перебор 10.5.4. Алгоритм построения максимальных независимых множеств вершин 10.6. Доминирующие множества 10.6.1. Минимальное и наименьшее доминирующее множество 10.6.2. Доминирование и независимость 10.6.3. Задача о наименьшем покрытии 10.6.4. Связь задачи о наименьшем покрытии с другими задачами 10.7. Раскраска графов 10.7.1. Оценки хроматического числа 10.7.2. Хроматические числа графа и его дополнения 10.7.3. Точный алгоритм раскрашивания 10.7.4. Приближённый алгоритм последовательного раскрашивания 10.7.5. Улучшенный алгоритм последовательного раскрашивания 10.8. Планарность 10.8.1. Укладка графов 10.8.2. Эйлерова характеристика 10.8.3. Теорема о пяти красках Комментарии Упражнения Указатель основных обозначений Список литературы Предметный указатель