Дискретная математика. Алгоритмы: теория и практика

Предисловие
Введение
1. Множество
2. Функция
3. Отношение
4. Отношение эквивалентности
5. Каноническое разложение функции
6. Мощность множества. Счетные и несчетные
множества
7. Мощность континуума
8. Кардинальные числа. Сравнение мощностей
Часть I. ТЕОРИЯ АЛГОРИТМОВ
Глава 1. Частично рекурсивные функции
1.1. Арифметические функции и операции над ними
1.2. Примитивно рекурсивные функции
1.3. Функции, представимые термами
1.4. Конечная сумма и произведение
1.5. Примитивно рекурсивные предикаты
1.6. Ограниченные кванторы
1.7. Ограниченный оператор u
1.8. Подстановка функций в предикат
1.8.1. Кусочное задание функции
1.8.2. Примитивная рекурсивность некоторых
функции и предикатов
1.9. Частично рекурсивные функции
Глава 2. Машины Тьюринга
2.1. Вычисления на машинах Тьюринга
2.2. Синтез машин Тьюринга
2.2.1. Композиция машин
2.2.2. Ветвление машин
2.2.3. Итерация машины
2.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.6. Универсальная частично рекурсивная
функция
2.6.1. Геделева нумерация машин Тьюринга
2.6.2. Функции ситуации машины Тьюринга с
номером k
2.6.3. Построение универсальной функции
2.7. Теорема Клини о неподвижной точке и теорема
Раиса.
2.8. Сложность алгоритмов
Глава 3. Рекурсивная перечислимость и
разрешимость
3.1. Общерекурсивные функции и предикаты
3.2. Нумерации наборов натуральных чисел
3.2.1. Нумерации пар натуральных чисел
3.2.2. Нумерация наборов натуральных чисел
длины k
3.2.3. Нумерация конечных последовательностей
натуральных чисел
3.3. Рекурсивно перечислимые множества
3.4. Рекурсивно перечислимые множества наборов
натуральных чисел
3.5. Общерекурсивные предикаты
3.6. Общерекурсивные множества наборов
натуральных чисел
3.7. Функции с рекурсивно перечислимым графиком
3.8. Примеры алгоритмически неразрешимых
проблем
3.9. Варианты уточнения понятия алгоритма
3.9.1. Ассоциативные исчисления
3.9.2. Системы подстановок Туэ
3.9.3. Алгоритмическая неразрешимость проблемы
тождества полугрупп и логики предикатов
3.9.4. Грамматики
3.9.5. Продукции Поста
3.9.6. Нормальные алгоритмы Маркова
3.9.7. Операторные алгоритмы
Глава 4. Гедель о неполноте формальных систем
4.1. Аксиоматическая арифметика
4.2. Алгоритмическая неразрешимость
содержательной арифметики
4.3. Алгоритмическая неразрешимость логики
предикатов второго порядка
4.4. Нумерическая выразимость
Часть II. АЛГОРИТМЫ НА ГРАФАХ Глава 5. Способы
задания графов
5.1. Графы, мультиграфы, псевдографы
5.2. Задание графов
5.3. Операции над графами
5.4. Маршруты, цепи, циклы, связность
5.4.1. Алгоритм построения кратчайшей цепи в
графе
5.4.2. Алгоритм поиска кратчайшего пути в
ориентированном графе
Глава 6. Обходы графов
6.1. Эйлеровы графы
6.2. Алгоритм построения эйлерова цикла
6.3. Полные циклы и последовательности де
Брюйна
6.4. Гамильтоновы графы
6.5. Коды Грея
Глава 7. Деревья
7.1. Деревья и лес
7.2. Характеристические свойства деревьев
7.3. Каркасы и хорды в связном графе
Глава 8. Циклы в графах
8.1. Линейное пространство двоичных наборов
8.2. Линейное пространство подграфов данного
графа
8.3. Подпространство четных подграфов
8.4. Циклический ранг графа
8.5. Матричная теорема о деревьях
Глава 9. Двудольные графы и паросочетания
9.1. Двудольные графы
9.2. Паросочетания
9.3. Алгоритм построения совершенного
паросочетания
Для двудольного графа
9.4. Системы различных представителей
9.5. Сети Петри
9.5.1. Описание сети Петри
9.5.2. Определение сети Петри
Глава 10. Пленарные графы
10.1. Плоские графы
10.2. Формула Эйлера для плоских графов
Глава 11. Раскраска графов
11.1. Хроматическое число и хроматический класс
11.2. Раскраска вершин
11.3. Верхняя и нижняя оценки хроматического
числа
11.3.1. Внутренне устойчивые множества вершин
графа
11.3.2. Алгоритм вычисления всех наибольших
внутренне устойчивых множеств вершин графа
11.3.3. Внешне устойчивые множества вершин
графа
11.3.4. Алгоритм вычисления всех наименьших
внешне устойчивых множеств вершин графа
11.4. Оптимальная раскраска вершин графа
11.5. Раскрашивание планарных графов
Глава 12. Потоки в транспортных сетях
12.1. Двухполюсные сети
12.2. Дивергенция
12.3. Потоки в сетях
12.4. Сечения в сетях
12.5. Величина потока и пропускная способность
сети
12.6. Максимальный поток
12.6.1. Алгоритм Форда-Фалкерсона
12.6.2. Помечпвающий алгоритм
Форда-Фалкерсона
Глава 13. Перечисление графов
13.1. Число помеченных графов
13.2. Графы и группы подстановок
13.2.1. Группы подстановок и лемма Бернсайда
13.2.2. Теорема Пойа
13.2.3. Раскраска вершин куба
13.2.4. Составление ожерелий
Часть III. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
Глава 14. Порождение комбинаторных
конфигураций и их пересчет
14.1. Размещения, перестановки, сочетания
14.2. Правило суммы и правило произведения
14.3. Подсчет числа размещений, перестановок,
сочетаний
14.3.1. Число размещений и перестановок без
повторений
14.3.2. Число размещений с повторениями
14.3.3. Число сочетаний без повторений
14.3.4. Число сочетаний с повторениями
14.3.5. Число перестановок данной спецификации
14.3.6. Число размещений данной спецификации
Глава 15. Производящие функции для
комбинаторных конфигураций и для их чисел
15.1. Аппарат формальных степенных рядов
15.2. Производящие функции для сочетаний
15.2.1. Сочетания без повторений
15.2.2. Сочетания с повторениями с ограничениями
начисто повторений
15.2.3. Сочетания с повторениями без ограничений
начисто повторений
15.3. Производящие функции для размещений с
повторениями
15.4. Числа Стирлинга, Белла, Каталана
Глава 16. Комбинаторно-логический аппарат
16.1. Включения и исключения
16.2. Приложения формулы включений и
исключений
16.2.1. Задача о беспорядках
16.2.2. Задача о встречах
Глава 17. Рекуррентные последовательности
17.1. Конечные разности
17.2. Рекуррентные уравнения
17.3. Линейные рекуррентные уравнения с
переменными коэффициентами
17.4. Метод Лагранжа вариации произвольных
постоянных вычисления частного решения
неоднородного уравнения
17.5. Линейные рекуррентные уравнения с
постоянными коэффициентами
Глава 18. Частично упорядоченные множества,
решетки, булевы алгебры
18.1. Отношение частичного порядка
18.2. Топологическая сортировка вершин
бесконтурного орграфа
18.3. Решетки
18.4. Изоморфизм решеток
18.5. Булевы алгебры
Приложения
1. Графы
2. Комбинаторика
Литература
Обозначения