Дискретная математика для программистов

Предисловие ко второму изданию ......Page 13
Вступительное слово к первому изданию ......Page 14
Введение ......Page 15
1.1.1. Элементы и множества ......Page 22
1.1.3. Парадокс Рассела ......Page 24
1.2. Алгебра подмножеств ......Page 25
1.2.2. Равномощные множества ......Page 26
1.2.3. Конечные и бесконечные множества ......Page 27
1.2.4. Добавление и удаление элементов ......Page 28
1.2.5. Мощность конечного множества ......Page 29
1.2.6. Операции над множествами ......Page 30
1.2.7. Разбиения и покрытия ......Page 31
1.2.9. Свойства операций над множествами ......Page 32
1.3. Представление множеств в компьютере ......Page 33
1.3.2. Генерация всех подмножеств универсума ......Page 34
1.3.3. Алгоритм построения бинарного кода Грея ......Page 35
1.3.4. Представление множеств упорядоченными списками ......Page 36
1.3.5. Проверка включения слиянием ......Page 37
1.3.6. Вычисление объединения слиянием ......Page 38
1.3.7. Вычисление пересечения слиянием ......Page 39
1.3.8. Представление множеств итераторами ......Page 40
1.4.2. Прямое произведение множеств ......Page 43
1.4.3. Бинарные отношения ......Page 44
1.4.5. Степень отношения ......Page 45
1.4.7. Свойства отношений ......Page 46
1.4.8. Представление отношений в компьютере ......Page 47
1.5. Замыкание отношений ......Page 49
1.5.2. Транзитивное и рефлексивное транзитивное замыкания ......Page 50
1.6. Функции ......Page 51
1.6.1. Функциональные отношения ......Page 52
1.6.2. Инъекция, сюръекция и биекция ......Page 53
1.6.3. Образы и прообразы ......Page 54
1.6.5. Представление функций в компьютере ......Page 55
1.7.1. Определение ......Page 56
1.7.2. Классы эквивалентности ......Page 57
1.7.4. Ядро функционального отношения и множества уровня ......Page 58
1.8.2. Минимальные элементы ......Page 60
1.8.3. Алгоритм топологической сортировки ......Page 61
1.8.4. Верхние и нижние границы ......Page 62
1.8.6. Вполне упорядоченные множества ......Page 63
1.8.7. Индукция ......Page 64
Упражнения ......Page 65
2.1.1. Операции и носитель ......Page 67
2.1.2. Замыкания и подалгебры ......Page 68
2.1.3. Алгебра термов ......Page 69
2.1.5. Свойства операций ......Page 70
2.1.7. Гомоморфизмы ......Page 71
2.1.8. Изоморфизмы ......Page 72
2.2.1. Полугруппы ......Page 73
2.2.2. Определяющие соотношения ......Page 74
2.2.3. Моноиды ......Page 75
2.2.4. Группы ......Page 76
2.2.5. Группа перестановок ......Page 78
2.3. Алгебры с двумя операциями ......Page 79
2.3.1. Кольца ......Page 80
2.3.3. Поля ......Page 81
2.4. Модули и векторные пространства ......Page 82
2.4.1. Векторное пространство ......Page 83
2.4.2. Свойства нуль-вектора ......Page 84
2.4.4. Базис и размерность ......Page 85
2.5.1. Определения ......Page 87
2.5.3. Решётка с дополнением ......Page 88
2.5.4. Частичный порядок в решётке ......Page 89
2.5.5. Булевы алгебры ......Page 90
2.6.1. Определения ......Page 91
2.6.2. Максимальные независимые подмножества ......Page 92
2.6.3. Базисы ......Page 93
2.6.4. Жадный алгоритм ......Page 94
2.6.5. Примеры матроидов ......Page 96
Упражнения ......Page 97
3.1.1. Функции алгебры логики ......Page 99
3.1.2. Существенные и несущественные переменные ......Page 101
3.1.4. Булевы функции двух переменных ......Page 102
3.2.1. Реализация функций формулами ......Page 103
3.2.2. Равносильные формулы ......Page 105
3.2.3. Подстановка и замена ......Page 106
3.2.4. Алгебра булевых функций ......Page 107
3.3.1. Двойственная функция ......Page 109
3.3.3. Принцип двойственности ......Page 110
3.4.1. Разложение булевых функций по переменным ......Page 111
3.4.2. Совершенные нормальные формы ......Page 112
3.4.3. Эквивалентные преобразования ......Page 114
3.4.4. Минимальные дизъюнктивные формы ......Page 115
3.4.5. Геометрическая интерпретация ......Page 116
3.4.6. Сокращенные дизъюнктивные формы ......Page 118
3.5.1. Замыкание множества булевых функций ......Page 119
3.5.2. Замкнутые классы ......Page 120
3.5.3. Полные системы функций ......Page 121
3.5.5. Теорема Поста ......Page 122
3.6.1. Табличные представления ......Page 124
3.6.2. Строковые представления ......Page 126
3.6.3. Алгоритм вычисления значения булевой функции ......Page 127
3.6.4. Деревья решений ......Page 128
Упражнения ......Page 132
Глава 4. Логические исчисления ......Page 133
4.1.2. Формулы ......Page 134
4.1.3. Интерпретация ......Page 135
4.1.4. Логическое следование и логическая эквивалентность ......Page 136
4.2.1. Определение формальной теории ......Page 138
4.2.2. Выводимость ......Page 139
4.2.4. Общезначимость и непротиворечивость ......Page 140
4.3.1. Классическое определение исчисления высказываний ......Page 141
4.3.2. Частный случай формулы ......Page 142
4.3.3. Алгоритм унификации ......Page 143
4.3.5. Производные правила вывода ......Page 144
4.3.6. Дедукция ......Page 145
4.3.7. Некоторые теоремы исчисления высказываний ......Page 147
4.3.8. Множество теорем исчисления высказываний ......Page 150
4.3.9. Другие аксиоматизации исчисления высказываний ......Page 151
4.4.1. Определения ......Page 152
4.4.2. Интерпретация ......Page 155
4.4.4. Непротиворечивость и полнота чистого исчисления предикатов ......Page 156
4.4.5. Логическое следование и логическая эквивалентность ......Page 157
4.4.6. Теория равенства ......Page 158
4.4.8. Теория (абелевых) групп ......Page 159
4.4.9. Теоремы Гёделя о неполноте ......Page 161
4.5.1. Постановка задачи ......Page 162
4.5.3. Сведение к предложениям ......Page 163
4.5.4. Правило резолюции для исчисления высказываний ......Page 165
4.5.6. Опровержение методом резолюций ......Page 166
4.5.7. Алгоритм метода резолюций ......Page 167
Комментарии ......Page 168
Упражнения ......Page 169
Глава 5. Комбинаторика ......Page 170
5.1.2. Размещения ......Page 171
5.1.3. Размещения без повторений ......Page 172
5.1.5. Сочетания ......Page 173
5.1.6. Сочетания с повторениями ......Page 174
5.2.1. Графическое представление перестановок ......Page 175
5.2.3. Инверсии ......Page 176
5.2.4. Генерация перестановок ......Page 177
5.3.1. Элементарные тождества ......Page 179
5.3.2. Бином Ньютона ......Page 180
5.3.3. Свойства биномиальных коэффициентов ......Page 181
5.3.5. Генерация подмножеств ......Page 182
5.4.2. Числа Стирлинга второго рода ......Page 184
5.4.3. Числа Стирлинга первого рода ......Page 185
5.5. Принцип включения и исключения ......Page 186
5.5.2. Принцип включения и исключения ......Page 187
5.5.3. Число булевых функций, существенно зависящих от всех своих переменных ......Page 188
5.6.1. Теорема обращения ......Page 189
5.6.2. Формулы обращения для биномиальных коэффициентов ......Page 190
5.6.3. Формулы для чисел Стирлинга ......Page 191
5.7.2. Метод неопределённых коэффициентов ......Page 192
5.7.3. Числа Фибоначчи ......Page 193
Упражнения ......Page 194
Глава 6. Кодирование ......Page 196
6.1.2. Таблица кодов ......Page 198
6.1.3. Разделимые схемы ......Page 199
6.1.5. Неравенство Макмиллана ......Page 200
6.2.1. Минимизация длины кода сообщения ......Page 203
6.2.2. Цена кодирования ......Page 204
6.2.3. Алгоритм Фано ......Page 205
6.2.4. Оптимальное кодирование ......Page 206
6.2.5. Алгоритм Хаффмена ......Page 208
6.3.1. Кодирование с исправлением ошибок ......Page 210
6.3.3. Возможность исправления всех ошибок ......Page 211
6.3.4. Кодовое расстояние ......Page 212
6.3.5. Код Хэмминга для исправления одного замещения ......Page 213
6.4. Сжатие данных ......Page 215
6.4.2. Предварительное построение словаря ......Page 216
6.4.3. Алгоритм Лемпела-Зива ......Page 217
6.5.1. Криптография ......Page 219
6.5.2. Шифрование с помощью случайных чисел ......Page 220
6.5.3. Криптостойкость ......Page 221
6.5.4. Модулярная арифметика ......Page 222
6.5.5. Шифрование с открытым ключом ......Page 223
6.5.6. Цифровая подпись ......Page 225
Комментарии ......Page 226
Упражнения ......Page 227
7.1. Определения графов ......Page 228
7.1.1. История теории графов ......Page 229
7.1.2. Основное определение ......Page 230
7.1.4. Диаграммы ......Page 231
7.1.6. Изоморфизм графов ......Page 232
7.2. Элементы графов ......Page 233
7.2.2. Валентность ......Page 234
7.2.3. Маршруты, цепи, циклы ......Page 236
7.2.6. Эксцентриситет и центр ......Page 237
7.3.1. Виды графов ......Page 238
7.3.2. Двудольные графы ......Page 239
7.3.4. Операции над графами ......Page 240
7.4.1. Требования к представлению графов ......Page 242
7.4.3. Матрица инциденций ......Page 243
7.4.5. Массив дуг ......Page 244
7.4.6. Обходы графов ......Page 245
7.5.1. Графы и отношения ......Page 247
7.5.2. Достижимость и частичное упорядочение ......Page 248
7.5.3. Транзитивное замыкание ......Page 249
Упражнения ......Page 250
8.1.1. Объединение графов и компоненты связности ......Page 252
8.1.2. Точки сочленения, мосты и блоки ......Page 253
8.1.3. Вершинная и рёберная связность ......Page 254
8.1.4. Оценка числа рёбер через число вершин и число компонент связности ......Page 255
8.2. Теорема Менгера ......Page 256
8.2.1. Непересекающиеся цепи и разделяющие множества ......Page 257
8.2.2. Теорема Менгера в «вершинной форме» ......Page 258
8.3.2. Трансверсаль ......Page 260
8.3.4. Теорема Холла — формулировка и доказательство ......Page 261
8.4. Потоки в сетях ......Page 262
8.4.1. Определение потока ......Page 263
8.4.3. Теорема Форда-Фалкерсона ......Page 264
8.4.4. Алгоритм нахождения максимального потока ......Page 266
8.5. Связность в орграфах ......Page 268
8.5.2. Компоненты сильной связности ......Page 269
8.5.3. Выделение компонент сильной связности ......Page 270
8.6.1. Длина дуг ......Page 271
8.6.2. Алгоритм Флойда ......Page 272
8.6.3. Алгоритм Дейкстры ......Page 273
8.6.4. Дерево кратчайших путей ......Page 275
8.6.5. Кратчайшие пути в бесконтурном орграфе ......Page 276
Комментарии ......Page 277
Упражнения ......Page 278
9.1.1. Определения ......Page 279
9.1.2. Основные свойства деревьев ......Page 280
9.1.3. Центр дерева ......Page 283
9.2.1. Ориентированные деревья ......Page 284
9.2.2. Эквивалентное определение ордерева ......Page 286
9.2.3. Упорядоченные деревья ......Page 287
9.2.4. Бинарные деревья ......Page 288
9.3.1. Представление свободных деревьев ......Page 289
9.3.2. Представление бинарных деревьев ......Page 291
9.3.4. Алгоритм симметричного обхода бинарного дерева ......Page 294
9.4.1. Ассоциативная память ......Page 295
9.4.2. Способы реализации ассоциативной памяти ......Page 296
9.4.3. Алгоритм бинарного (двоичного) поиска ......Page 297
9.4.5. Алгоритм вставки в дерево сортировки ......Page 298
9.4.6. Алгоритм удаления из дерева сортировки ......Page 299
9.4.7. Вспомогательные алгоритмы для дерева сортировки ......Page 301
9.4.9. Выровненные и полные деревья ......Page 302
9.4.10. Сбалансированные деревья ......Page 304
9.4.11. Балансировка дереьев ......Page 306
9.5.1. Определения ......Page 308
9.5.2. Схема алгоритма построения кратчайшего остова ......Page 309
9.5.4. Алгоритм Прима ......Page 310
Упражнения ......Page 312
10.1.1. Циклы и разрезы ......Page 314
10.1.2. Фундаментальная система циклов и циклический ранг ......Page 316
10.1.3. Фундаментальная система разрезов и коциклический ранг ......Page 318
10.1.4. Подпространства циклов и коциклов ......Page 319
10.2. Эйлеровы циклы ......Page 320
10.2.1. Эйлеровы графы ......Page 321
10.2.2. Алгоритм построения эйлерова цикла в эйлеровом графе ......Page 322
10.2.3. Оценка числа эйлеровых графов ......Page 323
10.3.1. Гамильтоновы графы ......Page 324
10.3.2. Задача коммивояжёра ......Page 325
10.4.1. Покрывающие множества вершин и рёбер ......Page 326
10.4.2. Независимые множества вершин и рёбер ......Page 327
10.4.3. Связь чисел независимости и покрытий ......Page 328
10.5.1. Постановка задачи отыскания наибольшего независимого множества вершин ......Page 329
10.5.2. Поиск с возвратами ......Page 330
10.5.3. Улучшенный перебор ......Page 331
10.5.4. Алгоритм построения максимальных независимых множеств вершин ......Page 333
10.6.2. Доминирование и независимость ......Page 334
10.6.4. Связь задачи о наименьшем покрытии с другими задачами ......Page 335
10.7.1. Хроматическое число ......Page 336
10.7.2. Хроматическое число графа и его дополнения ......Page 337
10.7.3. Точный алгоритм раскрашивания ......Page 338
10.7.4. Приближённый алгоритм последовательного раскрашивания ......Page 339
10.7.5. Улучшенный алгоритм последовательного раскрашивания ......Page 340
10.8.2. Эйлерова характеристика ......Page 341
10.8.3. Теорема о пяти красках ......Page 343
Упражнения ......Page 344
Указатель обозначений ......Page 346
Литература ......Page 349
Предметный указатель ......Page 351