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