Вялый М., Подольский В., Рубцов А., Шварц Д., Шень А. - Лекции по дискретной математике [2017, PDF, RUS]

Предисловие 8
I Начальные примеры
1 Математическая индукция
1.1 Задача о раскраске плоскости . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2 Общая схема доказательств по индукции . . . . . . . . . . . . . . . . . 15
1.3 Варианты рассуждений по индукции . . . . . . . . . . . . . . . . . . . . 16
1.3.1 С чего начинать? . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.2 Сведение к меньшим . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3.3 Переформулировка: принцип наименьшего числа . . . . . . . . . 19
1.4 Как не надо . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.5 Как догадаться, что доказывать? . . . . . . . . . . . . . . . . . . . . . . 22
1.6 Доказательства по индукции и без . . . . . . . . . . . . . . . . . . . . . 25
1.7 Индукция и рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.8 Доказательства неравенств по индукции . . . . . . . . . . . . . . . . . . 31
1.8.1 Неравенство Бернулли . . . . . . . . . . . . . . . . . . . . . . . . 31
1.8.2 Среднее арифметическое и геометрическое . . . . . . . . . . . . 32
1.9 Пример из алгебры: системы однородных уравнений . . . . . . . . . . . 35
1.10 Коды Грея . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
1.11 Теорема Холла о представителях . . . . . . . . . . . . . . . . . . . . . . 40
1.12 Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . 42
2 Подсчёты
2.1 Правило суммы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.2 Рекуррентное соотношение: пример . . . . . . . . . . . . . . . . . . . . . 48
2.3 Рекуррентное соотношение: число путей . . . . . . . . . . . . . . . . . . 51
2.4 Слова и правило произведения . . . . . . . . . . . . . . . . . . . . . . . 53
2.5 Выбор с ограничениями . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.6 Подсчёты с кратностью . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.7 Подмножества и числа сочетаний . . . . . . . . . . . . . . . . . . . . . . 61
2.8 Ещё о числах сочетаний . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.8.1 Симметрия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.8.2 Сумма чисел в строке . . . . . . . . . . . . . . . . . . . . . . . . . 64
2.8.3 Знакочередующаяся сумма . . . . . . . . . . . . . . . . . . . . . . 65
2.8.4 Снова о включениях и исключениях . . . . . . . . . . . . . . . . 66
2.8.5 Пути, подмножества, слова . . . . . . . . . . . . . . . . . . . . . 67
2.8.6 Соседние числа в строке . . . . . . . . . . . . . . . . . . . . . . . 69
2.8.7 Монеты и перегородки . . . . . . . . . . . . . . . . . . . . . . . . 70
2.9 Бином Ньютона и производящие функции . . . . . . . . . . . . . . . . . 72
2.10 Числа Каталана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
2.10.1 Правильные последовательности скобок . . . . . . . . . . . . . . 80
2.10.2 Рекуррентная формула . . . . . . . . . . . . . . . . . . . . . . . . 82
2.10.3 Вычисление с помощью отражений . . . . . . . . . . . . . . . . . 84
2.10.4 Вычисление с производящей функцией . . . . . . . . . . . . . . 86
2.10.5 Вычисление с теорией вероятностей и поворотами . . . . . . . . 88
2.10.6 Доказательство по индукции с дробными параметрами . . . . . 89
2.10.7 Неассоциативные произведения, триангуляции и стековый калькулятор . . . . . . . . . . . . . . . . . . . . . . . . 90
2.11 Что дальше? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3 Графы
3.1 Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.1.1 Граф авиарейсов . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.1.2 Перестановка коней . . . . . . . . . . . . . . . . . . . . . . . . . . 96
3.1.3 Эйлер и мосты в Кёнигсберге . . . . . . . . . . . . . . . . . . . . 98
3.1.4 Рукопожатия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
3.1.5 Задачи и решения . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
3.1.6 Разбор контрольной* . . . . . . . . . . . . . . . . . . . . . . . . . 101
3.1.7 Знакомые и незнакомые . . . . . . . . . . . . . . . . . . . . . . . 103
3.2 Неориентированные графы . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.2.1 Определение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
3.2.2 Соседи. Степени вершин . . . . . . . . . . . . . . . . . . . . . . . 107
3.2.3 Связные компоненты . . . . . . . . . . . . . . . . . . . . . . . . . 110
3.2.4 Расстояния. Простые пути . . . . . . . . . . . . . . . . . . . . . . 117
3.2.5 Деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
3.2.6 Полное бинарное дерево . . . . . . . . . . . . . . . . . . . . . . . 123
3.3 Ориентированные графы . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
3.3.1 Определение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
3.3.2 Степени вершин . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
3.3.3 Пути и достижимость . . . . . . . . . . . . . . . . . . . . . . . . . 125
3.3.4 Достижимость и разрезы . . . . . . . . . . . . . . . . . . . . . . . 126
3.3.5 Компоненты сильной связности и ациклические графы . . . . . 128
3.3.6 Графы преобразований . . . . . . . . . . . . . . . . . . . . . . . . 130
3.4 Эйлеровы циклы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
3.4.1 Определение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
3.4.2 Критерий существования . . . . . . . . . . . . . . . . . . . . . . . 132
3.4.3 Последовательности де Брёйна . . . . . . . . . . . . . . . . . . . 134
3.4.4 Гамильтоновы циклы . . . . . . . . . . . . . . . . . . . . . . . . . 135
3.5 Двудольные графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
3.5.1 Определение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
3.5.2 Двудольные графы и раскраска в два цвета . . . . . . . . . . . . 136
3.5.3 Степени вершин . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
3.5.4 Паросочетания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
3.6 Клики и независимые множества . . . . . . . . . . . . . . . . . . . . . . 140
4 Арифметика остатков
4.1 Чётные и нечётные числа . . . . . . . . . . . . . . . . . . . . . . . . . . 143
4.2 Деление на 3 и остатки . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
4.3 Деление с остатком . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
4.4 Сравнения по модулю . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
4.5 Таблицы сложения и умножения по модулю N . . . . . . . . . . . . . . 149
4.6 Обратимые остатки по модулю N . . . . . . . . . . . . . . . . . . . . . . 151
4.7 Обратимые элементы и диофантовы уравнения . . . . . . . . . . . . . . 153
4.8 Алгоритм Евклида . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
4.9 Алгоритм Евклида и диофантовы уравнения . . . . . . . . . . . . . . . 156
4.10 Однозначность разложения на множители . . . . . . . . . . . . . . . . . 159
4.11 Китайская теорема об остатках . . . . . . . . . . . . . . . . . . . . . . . 161
4.12 Малая теорема Ферма . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
4.13 Функция Эйлера и теорема Эйлера . . . . . . . . . . . . . . . . . . . . . 165
4.14 Что дальше? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
II Основные конструкции
5 Множества и логика
5.1 Основные свойства множеств и операции с множествами . . . . . . . . 169
5.2 Теоретико-множественные тождества . . . . . . . . . . . . . . . . . . . . 174
5.3 Логические переменные, логические связки . . . . . . . . . . . . . . . . 177
5.4 Наблюдения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
5.5 Какие связки необходимы? . . . . . . . . . . . . . . . . . . . . . . . . . . 183
5.5.1 Полнота дизъюнкции, конъюнкции и отрицания . . . . . . . . . 185
5.5.2 Полнота конъюнкции и отрицания . . . . . . . . . . . . . . . . . 186
5.5.3 Алгебраическое доказательство теоремы 5.1 . . . . . . . . . . . . 186
5.6 Формула включений-исключений . . . . . . . . . . . . . . . . . . . . . . 187
5.6.1 Первое доказательство . . . . . . . . . . . . . . . . . . . . . . . . 188
5.6.2 Второе доказательство . . . . . . . . . . . . . . . . . . . . . . . . 189
5.6.3 Формула для симметрической разности . . . . . . . . . . . . . . 190
6 Функции
6.1 Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
6.2 Функции и связанные с ними понятия . . . . . . . . . . . . . . . . . . . 192
6.2.1 Терминология и обозначения . . . . . . . . . . . . . . . . . . . . 192
6.2.2 Образ множества, полный прообраз . . . . . . . . . . . . . . . . 194
6.3 Декартово произведение множеств и графики функций . . . . . . . . . 197
6.4 Инъекции, сюръекции и биекции . . . . . . . . . . . . . . . . . . . . . . 201
6.4.1 Определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
6.4.2 Биекции и сравнение множеств . . . . . . . . . . . . . . . . . . . 204
6.5 Композиции функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
6.5.1 Определение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
6.5.2 Ассоциативность . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
6.5.3 Обратная функция . . . . . . . . . . . . . . . . . . . . . . . . . . 208
6.5.4 Степени композиций . . . . . . . . . . . . . . . . . . . . . . . . . 210
6.6 Подсчёты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
6.7 Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . 214
7 Отношения и их графы
7.1 Отношения в естественном языке . . . . . . . . . . . . . . . . . . . . . . 216
7.2 Отношения с точки зрения математики . . . . . . . . . . . . . . . . . . 217
7.3 Свойства бинарных отношений . . . . . . . . . . . . . . . . . . . . . . . 219
7.4 Графы, матрицы и бинарные отношения . . . . . . . . . . . . . . . . . . 221
7.5 Отношения эквивалентности . . . . . . . . . . . . . . . . . . . . . . . . . 221
7.6 Композиция отношений . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
7.7 Отношения: что дальше? . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
7.8 Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . 228
8 Мощность множеств
8.1 Равномощные множества . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
8.1.1 Определение равномощности . . . . . . . . . . . . . . . . . . . . 229
8.1.2 Свойства равномощности . . . . . . . . . . . . . . . . . . . . . . . 230
8.1.3 Примеры равномощных множеств . . . . . . . . . . . . . . . . . 231
8.2 Счётные множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
8.2.1 Определение и простейшие примеры . . . . . . . . . . . . . . . . 233
8.2.2 Свойства счётных множеств . . . . . . . . . . . . . . . . . . . . . 234
8.3 Несчётные множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
8.3.1 Интервал и отрезок равномощны . . . . . . . . . . . . . . . . . . 238
8.3.2 Добавление счётного множества . . . . . . . . . . . . . . . . . . . 239
8.3.3 Числа и последовательности . . . . . . . . . . . . . . . . . . . . . 240
8.3.4 Отрезок и квадрат . . . . . . . . . . . . . . . . . . . . . . . . . . 241
8.4 Диагональный аргумент Кантора и сравнение мощностей . . . . . . . . 242
8.4.1 Несчётность отрезка . . . . . . . . . . . . . . . . . . . . . . . . . 242
8.4.2 Сравнение мощностей . . . . . . . . . . . . . . . . . . . . . . . . . 244
8.5 Что дальше? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
9 Упорядоченные множества
9.1 Отношения порядка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
9.1.1 Отношения строгого частичного порядка . . . . . . . . . . . . . 250
9.1.2 Строгие и нестрогие порядки . . . . . . . . . . . . . . . . . . . . 251
9.2 Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
9.3 Операции над частично упорядоченными множествами . . . . . . . . . 255
9.4 Какие порядки считать «одинаковыми»? . . . . . . . . . . . . . . . . . 256
9.5 Конечные линейные порядки . . . . . . . . . . . . . . . . . . . . . . . . 258
9.6 Порядки и индукция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
9.7 Антицепи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
10 Вероятность: первые шаги
10.1 Элементарная теория вероятностей: определения . . . . . . . . . . . . . 264
10.2 Вероятность объединения событий . . . . . . . . . . . . . . . . . . . . . 272
10.3 Вероятностный метод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
10.4 Условные вероятности . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
10.5 Случайная величина, математическое ожидание . . . . . . . . . . . . . 284
10.6 Частота орлов при подбрасывании монеты и биномиальные коэффициенты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
10.7 Большие уклонения: неравенство Чернова . . . . . . . . . . . . . . . . . 296
10.8 Подробности для любознательных . . . . . . . . . . . . . . . . . . . . . 298
10.8.1 Ещё одна элементарная оценка отношения биномиальных коэффициентов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
10.8.2 Другое доказательство неравенства Чернова . . . . . . . . . . . 299
11 Комбинаторные игры
11.1 Позиции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
11.2 Стратегии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
11.3 Разбор с конца . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
11.4 Симметричные стратегии . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
11.5 Ним . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
11.6 Сумма игр и функция Шпрага–Гранди . . . . . . . . . . . . . . . . . . 319
III Вычислимость
12 Разрешающие деревья
12.1 Задача об угадывании числа. Деление пополам. Мощностная нижняя оценка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
12.2 Формализация модели . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
12.3 Угадывание числа, неадаптивный вариант задачи . . . . . . . . . . . . 328
12.4 Ограниченные модели разрешающих деревьев. Сортировка, взвешивания, булевы функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
12.5 Рассуждение с противником . . . . . . . . . . . . . . . . . . . . . . . . . 333
13 Булевы схемы и формулы
13.1 Булевы схемы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
13.2 Формулы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
14 Алгоритмическая неразрешимость
14.1 Игра FRACTRAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
14.2 Что утверждается? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
14.3 Отступление о процессорах . . . . . . . . . . . . . . . . . . . . . . . . . 355
14.4 Кодирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
14.5 Класс вычислимых функций . . . . . . . . . . . . . . . . . . . . . . . . . 357
14.6 Определение вычислимости? . . . . . . . . . . . . . . . . . . . . . . . . . 358
14.7 Компромисс . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
14.8 Композиция вычислимых функций . . . . . . . . . . . . . . . . . . . . . 359
14.9 Не все функции вычислимы . . . . . . . . . . . . . . . . . . . . . . . . . 360
14.10Неразрешимость проблемы остановки . . . . . . . . . . . . . . . . . . . 361
14.11Самоприменимость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
14.12Перечисление останавливающихся программ . . . . . . . . . . . . . . . 363
14.13Как доказать неразрешимость? . . . . . . . . . . . . . . . . . . . . . . . 364
14.14Язык программирования для доказательства теоремы Конвея . . . . . 365
14.15Сведение проблемы остановки: от программ к пасьянсам . . . . . . . . 369
15 Вычислимые функции, разрешимые и перечислимые множества
15.1 Примеры вычислимых функций . . . . . . . . . . . . . . . . . . . . . . . 373
15.2 Не все функции вычислимы (повторение) . . . . . . . . . . . . . . . . . 378
15.3 Разрешимые множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
15.4 Перечислимые множества . . . . . . . . . . . . . . . . . . . . . . . . . . 380
15.5 Вычислимость и конечные объекты . . . . . . . . . . . . . . . . . . . . . 387
15.6 Универсальная вычислимая функция . . . . . . . . . . . . . . . . . . . 388
15.7 Главная универсальная функция . . . . . . . . . . . . . . . . . . . . . . 393
15.8 Теорема Райса – Успенского . . . . . . . . . . . . . . . . . . . . . . . . . 397
15.9 Теорема о неподвижной точке . . . . . . . . . . . . . . . . . . . . . . . . 401
15.10Решения задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
16 Машины Тьюринга
16.1 Определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
16.2 Тезис Чёрча – Тьюринга . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
16.3 Машины Тьюринга и свойства вычислимых функций . . . . . . . . . . 413
16.4 Использование машин Тьюринга в доказательствах . . . . . . . . . . . 415
16.5 Композиция функций, вычислимых по Тьюрингу, и уборка мусора . . 416
16.6 Многоленточные машины Тьюринга . . . . . . . . . . . . . . . . . . . . 419
16.7 Моделирование многоленточной МТ на одноленточной . . . . . . . . . 422
16.8 Универсальная машина Тьюринга . . . . . . . . . . . . . . . . . . . . . 424
16.9 Универсальная 3-ленточная машина для 1-ленточных машин . . . . . 426
16.10Соответствие между абстрактной теорией алгоритмов и МТ . . . . . . 429
Лекции по дискретной математике (черновик от 22 ноября 2017)Оглавление 7
16.11Машины Тьюринга в доказательствах неразрешимости . . . . . . . . . 433
16.11.1 Задача достижимости на графе подстановок слов . . . . . . . . 433
16.11.2 Неразрешимость задачи достижимости для графа подстановок слов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
16.12Решения задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437