Содержание
Предисловие.............................................................................................................................9
Введение................................................................................................................................... 11
1. Множество ................................................................................................................................ 11
2. Функция .................................................................................................................................... 12
3. Отношение ................................................................................................................................ 14
4. Отношение эквивалентности ............................................................................................. 15
5. Каноническое разложение функции................................................................................ 16
6. Мощность множества. Счетные и несчетные множества......................................... 17
7. Мощность континуума ......................................................................................................... 18
8. Кардинальные числа. Сравнение мощностей............................................................... 19
Часть I. ТЕОРИЯ АЛГОРИТМОВ............................................................................... 23
Глава 1. Частично рекурсивные функции...................................................... 24
1.1. Арифметические функции и операции над ними.................................................... 24
1.2. Примитивно рекурсивные функции ............................................................................ 25
1.3. Функции, представимые термами................................................................................. 27
1.4. Конечная сумма и произведение.................................................................................... 29
1.5. Примитивно рекурсивные предикаты......................................................................... 31
1.6. Ограниченные кванторы................................................................................................... 31
1.7. Ограниченный оператор µ ............................................................................................... 32
1.8. Подстановка функций в предикат................................................................................. 33
1.8.1. Кусочное задание функции...................................................................................... 34
1.8.2. Примитивная рекурсивность некоторых функций и предикатов ............. 35
1.9. Частично рекурсивные функции................................................................................... 36
Глава 2. Машины Тьюринга ....................................................................................... 38
2.1. Вычисления на машинах Тьюринга.............................................................................. 38
2.2. Синтез машин Тьюринга................................................................................................... 40
2.2.1. Композиция машин.................................................................................................... 40
2.2.2. Ветвление машин........................................................................................................ 41
2.2.3. Итерация машины ...................................................................................................... 43
2.3. Машины Тьюринга в однобуквенном алфавите....................................................... 45
2.4. Правильно вычислимые функции................................................................................. 49
2.4.1. Суперпозиция правильно вычислимых функций........................................... 49
2.4.2. Примитивная рекурсия правильно вычислимых функций......................... 50
4 Содержание
2.4.3. Минимизация правильно вычислимых функций ........................................... 50
2.4.4. Правильная вычислимость частично рекурсивных функций..................... 51
2.5. Частичная рекурсивность правильно вычислимых функций............................. 51
2.5.1. Геделева нумерация ситуаций машины Тьюринга .......................................... 52
2.5.2. Функции программы машины Тьюринга........................................................... 53
2.5.3. Функции вычисления по программе машины Тьюринга ............................. 53
2.5.4. Функция ситуаций машины Тьюринга............................................................... 55
2.6. Универсальная частично рекурсивная функция...................................................... 57
2.6.1. Геделева нумерация машин Тьюринга................................................................. 57
2.6.2. Функции ситуации машины Тьюринга с номером k ...................................... 58
2.6.3. Построение универсальной функции.................................................................. 60
2.7. Теорема Клини о неподвижной точке и теорема Райса ......................................... 63
2.8. Сложность алгоритмов...................................................................................................... 64
Глава 3. Рекурсивная перечислимость и разрешимость................ 68
3.1. Общерекурсивные функции и предикаты.................................................................. 68
3.2. Нумерации наборов натуральных чисел..................................................................... 70
3.2.1. Нумерации пар натуральных чисел...................................................................... 70
3.2.2. Нумерация наборов натуральных чисел длины k............................................ 72
3.2.3. Нумерация конечных последовательностей натуральных чисел .............. 73
3.3. Рекурсивно перечислимые множества ........................................................................ 74
3.4. Рекурсивно перечислимые множества наборов натуральных чисел................ 76
3.5. Общерекурсивные предикаты ........................................................................................ 78
3.6. Общерекурсивные множества наборов натуральных чисел................................ 80
3.7. Функции с рекурсивно перечислимым графиком................................................... 81
3.8. Примеры алгоритмически неразрешимых проблем ............................................... 87
3.9. Варианты уточнения понятия алгоритма................................................................... 89
3.9.1. Ассоциативные исчисления .................................................................................... 89
3.9.2. Системы подстановок Туэ ........................................................................................ 90
3.9.3. Алгоритмическая неразрешимость проблемы тождества
полугрупп и логики предикатов ....................................................................................... 91
3.9.4. Грамматики.................................................................................................................... 95
3.9.5. Продукции Поста........................................................................................................ 96
3.9.6. Нормальные алгоритмы Маркова......................................................................... 97
3.9.7. Операторные алгоритмы.......................................................................................... 98
Глава 4. Гедель о неполноте формальных систем................................. 99
4.1. Аксиоматическая арифметика........................................................................................ 99
4.2. Алгоритмическая неразрешимость содержательной арифметики..................103
4.3. Алгоритмическая неразрешимость логики предикатов второго порядка.....107
4.4. Нумерическая выразимость ..........................................................................................108
Содержание 5
Часть II. АЛГОРИТМЫ НА ГРАФАХ......................................................................112
Глава 5. Способы задания графов.....................................................................113
5.1. Графы, мультиграфы, псевдографы ............................................................................113
5.2. Задание графов...................................................................................................................115
5.3. Операции над графами....................................................................................................117
5.4. Маршруты, цепи, циклы, связность............................................................................117
5.4.1. Алгоритм построения кратчайшей цепи в графе ..........................................119
5.4.2. Алгоритм поиска кратчайшего пути в ориентированном графе ..............120
Глава 6. Обходы графов.............................................................................................127
6.1. Эйлеровы графы................................................................................................................127
6.2. Алгоритм построения эйлерова цикла.......................................................................128
6.3. Полные циклы и последовательности де Брюйна .................................................132
6.4. Гамильтоновы графы........................................................................................................134
6.5. Коды Грея.............................................................................................................................135
Глава 7. Деревья...............................................................................................................137
7.1. Деревья и лес.......................................................................................................................137
7.2. Характеристические свойства деревьев ....................................................................137
7.3. Каркасы и хорды в связном графе...............................................................................140
Глава 8. Циклы в графах.............................................................................................142
8.1. Линейное пространство двоичных наборов.............................................................142
8.2. Линейное пространство подграфов данного графа...............................................143
8.3. Подпространство четных подграфов..........................................................................144
8.4. Циклический ранг графа ................................................................................................147
8.5. Матричная теорема о деревьях.....................................................................................150
Глава 9 Двудольные графы и паросочетания..........................................151
9.1. Двудольные графы............................................................................................................151
9.2. Паросочетания....................................................................................................................152
9.3. Алгоритм построения совершенного паросочетания
для двудольного графа ............................................................................................................154
9.4. Системы различных представителей .........................................................................155
9.5. Сети Петри...........................................................................................................................159
9.5.1. Описание сети Петри...............................................................................................159
9.5.2. Определение сети Петри........................................................................................160
Глава 10. Планарные графы ...................................................................................165
10.1. Плоские графы.................................................................................................................165
10.2. Формула Эйлера для плоских графов.....................................................................166
6 Содержание
10.3. Критерий планарности Понтрягина–Куратовского...........................................168
10.4. Алгоритм построения плоского изображения графа .........................................168
Глава 11. Раскраска графов ...................................................................................172
11.1. Хроматическое число и хроматический класс......................................................172
11.2. Раскраска вершин ...........................................................................................................172
11.3. Верхняя и нижняя оценки хроматического числа ..............................................173
11.3.1. Внутренне устойчивые множества вершин графа ......................................173
11.3.2. Алгоритм вычисления всех наибольших внутренне устой
чивых множеств вершин графа G = (V, E)...................................................................174
11.3.3. Внешне устойчивые множества вершин графа ............................................175
11.3.4. Алгоритм вычисления всех наименьших внешне устойчивых
множеств вершин графа G = (V, E) ................................................................................176
11.4. Оптимальная раскраска вершин графа ...................................................................177
11.5. Раскрашивание планарных графов...........................................................................178
Глава 12. Потоки в транспортных сетях........................................................181
12.1. Двухполюсные сети........................................................................................................181
12.2. Дивергенция .....................................................................................................................182
12.3. Потоки в сетях..................................................................................................................183
12.4. Сечения в сетях................................................................................................................184
12.5. Величина потока и пропускная способность сети...............................................185
12.6. Максимальный поток ....................................................................................................186
12.6.1. Алгоритм Форда–Фалкерсона .........................................................................187
12.6.2. Помечивающий алгоритм Форда–Фалкерсона...........................................191
Глава 13. Перечисление графов.........................................................................196
13.1. Число помеченных графов...........................................................................................196
13.2. Графы и группы подстановок......................................................................................197
13.2.1. Группы подстановок и лемма Бернсайда........................................................197
13.2.2. Теорема Пойа............................................................................................................201
13.2.3. Раскраска вершин куба.........................................................................................204
13.2.4. Составление ожерелий .........................................................................................206
Часть III. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ......................................................209
Глава 14. Порождение комбинаторных конфигураций
и их пересчет.......................................................................................................................210
14.1. Размещения, перестановки, сочетания....................................................................210
14.2. Правило суммы и правило произведения ..............................................................211
14.3. Подсчет числа размещений, перестановок, сочетаний ......................................211
14.3.1. Число размещений и перестановок без повторений ..................................211
Содержание 7
14.3.2. Число размещений с повторениями.................................................................212
14.3.3. Число сочетаний без повторений......................................................................212
14.3.4. Число сочетаний с повторениями.....................................................................212
14.3.5. Число перестановок данной спецификации .................................................213
14.3.6. Число размещений данной спецификации....................................................213
Глава 15. Производящие функции для комбинаторных
конфигураций и для их чисел................................................................................215
15.1. Аппарат формальных степенных рядов..................................................................215
15.2. Производящие функции для сочетаний .................................................................216
15.2.1. Сочетания без повторений ..................................................................................216
15.2.2. Сочетания с повторениями с ограничениями
на число повторений...........................................................................................................217
15.2.3. Сочетания с повторениями без ограничений
на число повторений...........................................................................................................218
15.3. Производящие функции для размещений с повторениями ............................219
15.4. Числа Стирлинга, Белла, Каталана ..........................................................................221
Глава 16. Комбинаторно-логический аппарат........................................223
16.1. Включения и исключения............................................................................................223
16.2. Приложения формулы включений и исключений..............................................226
16.2.1. Задача о беспорядках.............................................................................................226
16.2.2. Задача о встречах ....................................................................................................227
Глава 17. Рекуррентные последовательности.......................................228
17.1. Конечные разности.........................................................................................................228
17.2. Рекуррентные уравнения.............................................................................................230
17.3. Линейные рекуррентные уравнения с переменными
коэффициентами.......................................................................................................................231
17.4. Метод Лагранжа вариации произвольных постоянных вычисления
частного решения неоднородного уравнения .................................................................238
17.5. Линейные рекуррентные уравнения с постоянными
коэффициентами.......................................................................................................................243
Глава 18. Частично упорядоченные множества,
решетки, булевы алгебры........................................................................................249
18.1. Отношение частичного порядка ................................................................................249
18.2. Топологическая сортировка вершин бесконтурного орграфа.........................252
18.3. Решетки..............................................................................................................................253
18.4. Изоморфизм решеток....................................................................................................255
18.5. Булевы алгебры ...............................................................................................................256
8 Содержание
Приложения..........................................................................................................................261
1. Графы ........................................................................................................................................261
2. Комбинаторика......................................................................................................................268
Литература............................................................................................................................276
Обозначения ........................................................................................................................279
