Указатель обозначений
Предисловие
Глава 1. Введение
1.1. Моделирование
1.2. Псевдокод
Набор упражнений 1
Краткое содержание главы
Глава 2. Логика и доказательство
2.1. Высказывания и логика
2.2. Предикаты и кванторы
2.3. Методы доказательств
2.4. Математическая индукция
Набор упражнений 2
Краткое содержание главы
Приложение. Корректность алгоритмов
Глава 3. Теория множеств
3.1. Множества и операции над ними
3.2. Алгебра множеств
3.3. Дальнейшие свойства множеств
Набор упражнений 3
Краткое содержание главы
Приложение. Система с базой знаний
Глава 4. Отношения
4.1. Бинарные отношения
4.2. Свойства отношений
4.3. Отношения эквивалентности и частичного порядка
Набор упражнений 4
Краткое содержание главы
Приложение. Системы управления базами данных
Глава 5. Функции
5.1. Обратные отношения и композиция отношений
5.2. Функции
5.3. Обратные функции и композиция функций
5.4. Принцип Дирихле
Набор упражнений 5
Краткое содержание главы
Приложение. Языки функционального программирования
Глава 6. Комбинаторика
6.1. Правила суммы и произведения
6.2. Комбинаторные формулы
6.3. Бином Ньютона
Набор упражнений 6
Краткое содержание главы
Приложение. Эффективность алгоритмов
Глава 7. Графы
7.1. Графы и терминология
7.2. Гамильтоновы графы
7.3. Деревья
Набор упражнений 7
Краткое содержание главы
Приложение. Сортировка и поиск
Глава 8. Ориентированные графы
8.1. Ориентированные графы
8.2. Пути в орграфах
8.3. Кратчайший путь
Набор упражнений 8
Краткое содержание главы
Приложение. Коммуникационные сети
Глава 9. Булева алгебра
9.1. Булева алгебра
9.2. Карта Карно
9.3. Функциональные схемы
Набор упражнений 9
Краткое содержание главы
Приложение. Проектирование 2-битного сумматора
Решения упражнений
Дополнение к первому изданию
Д. 1. Генератор случайных графов
Д.1.1. Алгоритм построения случайного неориентированного графа
Д.1.2. Алгоритм построения случайного ориентированного графа
Д.1.3. Алгоритм построения случайного ориентированного бесконтурного графа
Д.2. Связность в графах
Д.2.1. Алгоритм Уоршелла, вычисляющий матрицу связности
Д.2.2. Выделение компонент связности
Д.3. Эйлеровы циклы
Д.3.1. Алгоритм построения эйлерова цикла в графе
Д.3.2. Алгоритм Терри
Д.4. Операции над множествами
Д.4.1. Объединение множеств
Дополнение ко второму изданию
Предисловие
Д.5. Дополнительные главы дискретной математики
Введение
Д.5.1. Исчисление и оценка конечных сумм
Набор упражнений Д.5.1
Д.5.2. Элементы теории рекурсии
Набор упражнений Д.5.2
Д.5.3. Конечные разности. Разностный и суммирующий операторы
Набор упражнений Д.5.3
Д.5.4. Производящие функции и комбинаторные подсчеты
Набор упражнений Д.5.4
Д.6. Общая проблема перебора и некоторые точные методы решения задач целочисленного программирования
Введение
Д.6.1. Понятие m-мериого евклидова целочисленного пространства
Д.6.2. Общая постановка, типизация и примеры задач целочисленного программирования
Д.6.3. NP-полные задачи и проблема перебора
Д.6.4. Обзор точных методов решения задач целочисленного программирования
Д.6.5. Точное решение задачи одномерной упаковки методом динамического программирования
Д.6.6. Метод ветвей и границ и задача коммивояжера
Набор упражнений Д.6
Литература
Предметный указатель