Предисловие ко второму изданию
Вступительное слово к первому изданию
Введение
Множества и отношения
Множества
Элементы и множества
Задание множеств
Парадокс Рассела
Алгебра подмножеств
Сравнение множеств
Равномощные множества
Конечные и бесконечные множества
Добавление и удаление элементов
Мощность конечного множества
Операции над множествами
Разбиения и покрытия
Булеан
Свойства операций над множествами
Представление множеств в компьютере
Реализация операций над подмножествами заданного универсума
Генерация всех подмножеств универсума
Алгоритм построения бинарного кода Грея
Представление множеств упорядоченными списками
Проверка включения слиянием
Вычисление объединения слиянием
Вычисление пересечения слиянием
Представление множеств итераторами
Отношения
Упорядоченные пары
Прямое произведение множеств
Бинарные отношения
Композиция отношений
Степень отношения
Ядро отношения
Свойства отношений
Представление отношений в компьютере
Замыкание отношений
Замыкание отношения относительно свойства
Транзитивное и рефлексивное транзитивное замыкания
Алгоритм Уоршалла
Функции
Функциональные отношения
Инъекция, сюръекция и биекция
Образы и прообразы
Суперпозиция функций
Представление функций в компьютере
Отношения эквивалентности
Определение
Классы эквивалентности
Фактормножества
Ядро функционального отношения и множества уровня
Отношения порядка
Определения
Минимальные элементы
Алгоритм топологической сортировки
Верхние и нижние границы
Монотонные функции
Вполне упорядоченные множества
Индукция
Комментарии
Упражнения
Алгебраические структуры
Алгебры и морфизмы
Операции и носитель
Замыкания и подалгебры
Алгебра термов
Система образующих
Свойства операций
Морфизмы
Гомоморфизмы
Изоморфизмы
Алгебры с одной операцией
Полугруппы
Определяющие соотношения
Моноиды
Группы
Группа перестановок
Алгебры с двумя операциями
Кольца
Области целостности
Поля
Модули и векторные пространства
Векторное пространство
Свойства нуль-вектора
Линейные комбинации
Базис и размерность
Модули
Решётки
Определения
Ограниченные решётки
Решётка с дополнением
Частичный порядок в решётке
Булевы алгебры
Матроиды и жадные алгоритмы
Определения
Максимальные независимые подмножества
Базисы
Жадный алгоритм
Примеры матроидов
Комментарии
Упражнения
Булевы функции
Элементарные булевы функции
Функции алгебры логики
Существенные и несущественные переменные
Булевы функции одной переменной
Булевы функции двух переменных
Формулы
Реализация функций формулами
Равносильные формулы
Подстановка и замена
Алгебра булевых функций
Двойственность
Двойственная функция
Реализация двойственной функции
Принцип двойственности
Нормальные формы
Разложение булевых функций по переменным
Совершенные нормальные формы
Эквивалентные преобразования
Минимальные дизъюнктивные формы
Геометрическая интерпретация
Сокращенные дизъюнктивные формы
Полнота
Замыкание множества булевых функций
Замкнутые классы
Полные системы функций
Полнота двойственной системы
Теорема Поста
Представление булевых функций в~компьютере
Табличные представления
Строковые представления
Алгоритм вычисления значения булевой функции
Деревья решений
Комментарии
Упражнения
Логические исчисления
Логические связки
Высказывания
Формулы
Интерпретация
Логическое следование и логическая эквивалентность
Подстановка и замена
Формальные теории
Определение формальной теории
Выводимость
Интерпретация
Общезначимость и непротиворечивость
Полнота, независимость и разрешимость
Исчисление высказываний
Классическое определение исчисления высказываний
Частный случай формулы
Алгоритм унификации
Конструктивное определение исчисления высказываний
Производные правила вывода
Дедукция
Некоторые теоремы исчисления высказываний
Множество теорем исчисления высказываний
Другие аксиоматизации исчисления высказываний
Исчисление предикатов
Определения
Интерпретация
Общезначимость
Непротиворечивость и полнота чистого~исчисления предикатов
Логическое следование и логическая эквивалентность
Теория равенства
Формальная арифметика
Теория (абелевых) групп
Теоремы Гёделя о неполноте
Автоматическое доказательство теорем
Постановка задачи
Доказательство от противного
Сведение к предложениям
Правило резолюции для исчисления высказываний
Правило резолюции для исчисления предикатов
Опровержение методом резолюций
Алгоритм метода резолюций
Комментарии
Упражнения
Комбинаторика
Комбинаторные задачи
Комбинаторные конфигурации
Размещения
Размещения без повторений
Перестановки
Сочетания
Сочетания с повторениями
Перестановки
Графическое представление перестановок
Циклы
Инверсии
Генерация перестановок
Биномиальные коэффициенты
Элементарные тождества
Бином Ньютона
Свойства биномиальных коэффициентов
Треугольник Паскаля
Генерация подмножеств
Разбиения
Определения
Числа Стирлинга второго рода
Числа Стирлинга первого рода
Число Белла
Принцип включения и исключения
Объединение конфигураций
Принцип включения и исключения
Число булевых функций, существенно зависящих от всех своих переменных
Формулы обращения
Теорема обращения
Формулы обращения для биномиальных коэффициентов
Формулы для чисел Стирлинга
Производящие функции
Основная идея
Метод неопределённых коэффициентов
Числа Фибоначчи
Комментарии
Упражнения
Кодирование
Алфавитное кодирование
Алфавит, слово и язык
Таблица кодов
Разделимые схемы
Префиксные схемы
Неравенство Макмиллана
Кодирование с минимальной избыточностью
Минимизация длины кода сообщения
Цена кодирования
Алгоритм Фано
Оптимальное кодирование
Алгоритм Хаффмена
Помехоустойчивое кодирование
Кодирование с исправлением ошибок
Классификация ошибок
Возможность исправления всех ошибок
Кодовое расстояние
Код Хэмминга для исправления одного замещения
Сжатие данных
Сжатие текстов
Предварительное построение словаря
Алгоритм Лемпела--Зива
Шифрование
Криптография
Шифрование с помощью случайных чисел
Криптостойкость
Модулярная арифметика
Шифрование с открытым ключом
Цифровая подпись
Комментарии
Упражнения
Графы
Определения графов
История теории графов
Основное определение
Смежность
Диаграммы
Орграфы, псевдографы, мультиграфы и~гиперграфы
Изоморфизм графов
Элементы графов
Подграфы
Валентность
Маршруты, цепи, циклы
Связность
Расстояние между вершинами, ярусы и~диаметр~графа
Эксцентриситет и центр
Виды графов и операции над графами
Виды графов
Двудольные графы
Направленные орграфы и сети
Операции над графами
Представление графов в компьютере
Требования к представлению графов
Матрица смежности
Mатрица инциденций
Списки смежности
Mассив дуг
Обходы графов
Орграфы и бинарные отношения
Графы и отношения
Достижимость и частичное упорядочение
Транзитивное замыкание
Комментарии
Упражнения
Связность
Компоненты связности
Объединение графов и компоненты связности
Точки сочленения, мосты и блоки
Вершинная и рёберная связность
Оценка числа рёбер через число вершин и число компонент связности
Теорема Менгера
Непересекающиеся цепи и~разделяющие~множества
Теорема Менгера в >
Варианты теоремы Менгера
Теорема Холла
Задача о свадьбах
Трансверсаль
Совершенное паросочетание
Теорема Холла~--- формулировка и доказательство
Потоки в сетях
Определение потока
Разрезы
Теорема Форда--Фалкерсона
Алгоритм нахождения максимального потока
Связь между теоремой Менгера и теоремой Форда--Фалкерсона
Cвязность в орграфах
Сильная, односторонняя и слабая связность
Компоненты сильной связности
Выделение компонент сильной связности
Кратчайшие пути
Длина дуг
Алгоритм Флойда
Aлгоритм Дейкстры
Дерево кратчайших путей
Кратчайшие пути в бесконтурном орграфе
Комментарии
Упражнения
Деревья
Свободные деревья
Определения
Основные свойства деревьев
Центр дерева
Ориентированные, упорядоченные и~бинарные деревья
Ориентированные деревья
Эквивалентное определение ордерева
Упорядоченные деревья
Бинарные деревья
Представление деревьев в компьютере
Представление свободных деревьев
Представление бинарных деревьев
Обходы бинарных деревьев
Алгоритм симметричного обхода бинарного~дерева
Деревья сортировки
Ассоциативная память
Способы реализации ассоциативной памяти
Алгоритм бинарного (двоичного) поиска
Алгоритм поиска в дереве сортировки
Алгоритм вставки в дерево сортировки
Алгоритм удаления из дерева сортировки
Вспомогательные алгоритмы для~дерева~сортировки
Сравнение представлений ассоциативной памяти
Выровненные и полные деревья
  Сбалансированные деревья
  Балансировка дереьев
Кратчайший остов
Определения
Схема алгоритма построения кратчайшего остова
Алгоритм Краскала
Алгоритм Прима
Комментарии
Упражнения
Циклы, независимость и раскраска
Фундаментальные циклы и разрезы
Циклы и разрезы
Фундаментальная система циклов и~циклический~ранг
Фундаментальная система разрезов и~коциклический ранг
Подпространства циклов и коциклов
Эйлеровы циклы
Эйлеровы графы
Алгоритм построения эйлерова цикла в~эйлеровом графе
Оценка числа эйлеровых графов
Гамильтоновы циклы
Гамильтоновы графы
Задача коммивояжёра
Независимые и покрывающие множества
Покрывающие множества вершин и рёбер
Независимые множества вершин и рёбер
Связь чисел независимости и покрытий
Построение независимых множеств вершин
Постановка задачи отыскания наибольшего независимого множества вершин
Поиск с возвратами
Улучшенный перебор
Алгоритм построения максимальных независимых множеств вершин
Доминирующие множества
Минимальное и наименьшее доминирующее множество
Доминирование и независимость
Задача о наименьшем покрытии
Связь задачи о наименьшем покрытии с другими задачами
Раскраска графов
Хроматическое число
Хроматическое число графа и его дополнения
Точный алгоритм раскрашивания
Приближённый алгоритм последовательного раскрашивания
Улучшенный алгоритм последовательного раскрашивания
Планарность
Укладка графов
Эйлерова характеристика
Теорема о пяти красках
Комментарии
Упражнения
Указатель обозначений
Метаобозначения
Числовые множества
Совокупности
Операции с множествами
Логические обозначения
Отношения
Функции
Групповые операции