Глава 1. Основы алгоритмизации 24
Метод 24
Алгоритм и структура данных 25
Псевдокод 25
Свойства алгоритма 28
Асимптотическая сложность алгоритма 29
Обычные функции рабочего цикла 33
Визуализация функций 38
Практические рекомендации 39
Резюме 41
Упражнения 41
Глава 2. Численные алгоритмы 45
Рандомизация данных 45
Генерирование случайных величин 45
Рандомизация массивов 50
Генерирование неравномерных распределений 52
Нахождение наибольшего
общего делителя 52
Возведение в степень 54
Работа с простыми числами 56
Нахождение простых множителей 56
Нахождение простых элементов 58
Проверка на простоту 59
Численное интегрирование 60
Формула прямоугольников 61
Формула трапеций 62
Адаптивная квадратура 63
Интеграция Монте-Карло 66
Нахождение нулей 67
Резюме 69
Упражнения 70
Глава 3. Связные списки 72
Основные положения 72
Однонаправленные связные списки 73
Передвижение по спискам 73
Нахождение ячеек 74
Использование ограничителей 75
Добавление ячеек в начало списка 76
Добавление ячеек в конец списка 77
Вставка ячеек 77
Удаление ячеек 78
Двунаправленные связные списки 79
Сортированные списки 80
Алгоритмы для работы со связными списками 81
Копирование 82
Сортировка вставкой 82
Сортировка методом выбора 84
Многопотоковые связные списки 85
Связные списки с циклами 86
Маркировка ячеек 87
Использование хеш-таблиц 88
Повторная трассировка списка 89
Реверсирование списка 90
Черепаха и кролик 92
Циклы в двунаправленных связных списках 94
Резюме 94
Упражнения 94
Глава 4. Массивы 96
Основные положения 96
Одномерные массивы 98
Нахождение элементов 98
Нахождение минимальной, максимальной и средней величин 98
Вставка элементов 100
Удаление элементов 101
Ненулевые нижние пределы 101
Двумерные массивы 101
Массивы высокой размерности 102
Треугольные массивы 105
Массивы с разрывом 108
Нахождение строки и столбца 110
Получение значения 111
Установка значения 111
Удаление значения 113
Матрицы 115
Резюме 117
Упражнения 117
Глава 5. Стеки и очереди 119
Стеки 119
Стеки связных списков 120
Стеки массивов 121
Двойные стеки 123
Алгоритмы с использованием стеков 124
Очереди 129
Очереди связных списков 130
Очереди массивов 130
Специализированные очереди 133
Резюме 134
Упражнения 134
Глава 6. Сортировка 136
Алгоритмы 0(N2) 136
Сортировка вставкой в массивах 136
Сортировка выбором в массивах 138
Пузырьковая сортировка 139
Алгоритмы 0(N х logN) 142
Пирамидальная сортировка 142
Быстрая сортировка 148
Сортировка слиянием 155
Алгоритмы быстрее 0(N х log N) 157
Сортировка подсчетом 157
Блочная сортировка 159
Резюме 160
Упражнения 161
Глава 7. Поиск 163
Линейный поиск 163
Бинарный поиск 164
Интерполяционный поиск 165
Резюме 166
Упражнения 167
Глава 8. Хеш-таблицы 168
Основы хеш-таблиц 168
Прямое связывание 170
Открытая адресация 171
Удаление элементов 172
Линейное пробирование 173
Квадратичное пробирование 174
Псевдослучайное пробирование 176
Двойное хеширование 176
Упорядоченное хеширование 176
Резюме 178
Упражнения 179
Глава 9. Рекурсия 181
Базовые алгоритмы 181
Факториал 181
Числа Фибоначчи 183
Ханойская башня 184
Графические алгоритмы 187
Кривые Коха 187
Кривая Гильберта 189
Кривая Серпинского 190
Салфетки 193
Алгоритмы с возвратом 194
Задача о восьми ферзях 195
Ход коня 198
Сочетания и размещения 200
Сочетания с циклами 201
Сочетания с повторениями 202
Сочетания без повторений 204
Размещения с повторениями 204
Размещения без повторений 205
Удаление рекурсии 206
Удаление хвостовой рекурсии 206
Хранение промежуточных значений 208
Удаление общей рекурсии 209
Резюме 212
Упражнения 212
Глава 10. Деревья 215
Терминология 215
Свойства бинарного дерева 219
Представление деревьев 220
Общие правила построения деревьев 220
Построение завершенных деревьев 223
Обход дерева 223
Обход в прямом порядке 224
Симметричный обход 226
Обход в обратном порядке 227
Обход в ширину 228
Время выполнения обхода 229
Упорядоченные деревья 229
Добавление вершин 230
Поиск вершин 231
Удаление вершин 232
Связные деревья 235
Построение связных деревьев 236
Использование связных деревьев 238
Специализированные алгоритмы 240
Игра «Животные» 240
Расчет математических выражений 241
Деревья квадрантов 243
Префиксные деревья 248
Резюме 252
Упражнения 253
Глава 11. Сбалансированные деревья 257
АВЛ-деревья 257
Добавление значений 258
Удаление значений 260
2-3-деревья 261
Добавление значений 262
Удаление значений 264
B-деревья 266
Добавление значений 267
Удаление значений 268
Разновидности сбалансированных деревьев 270
Иерархически организованные B-деревья 270
B+-деревья 270
Резюме 272
Упражнения 272
Глава 12. Деревья принятия решений 274
Поиск по деревьям игры 274
Минимакс 275
Начальные ходы и реакции 279
Эвристика дерева игры 279
Поиск по деревьям принятия решений 281
Задачи оптимизации 282
Метод полного перебора 282
Метод ветвей и границ 284
Эвристика дерева принятия решений 285
Другие задачи дерева принятия решений 290
Резюме 294
Упражнения 295
Глава 13. Основные сетевые алгоритмы 296
Терминология 296
Разные представления сети 299
Обход сети 302
Обход в глубину 302
Обход в ширину 304
Проверка связности 305
Остовные деревья 307
Минимальные остовные деревья 308
Поиск путей 309
Поиск произвольного пути 309
Поиск кратчайшего пути с помощью установки меток 310
Поиск кратчайшего пути с помощью коррекции меток 313
Поиск кратчайшего пути между всеми парами вершин 315
Резюме 320
Упражнения 320
Глава 14. Дополнительные сетевые алгоритмы 324
Топологическая сортировка 324
Поиск циклов 327
Раскрашивание карты 328
Закрашивание двумя цветами 328
Закрашивание тремя цветами 330
Закрашивание четырьмя цветами 331
Закрашивание пятью цветами 331
Другие алгоритмы закрашивания карт 335
Максимальный поток 336
Распределение рабочих мест 338
Минимальный разрез в потоке 340
Резюме 342
Упражнения 343
Глава 15. Строковые алгоритмы 345
Парные скобки 345
Вычисление арифметических выражений 347
Синтаксические деревья 347
Сопоставление с шаблоном 348
Детерминированные конечные автоматы 349
Построение ДКА для регулярных выражений 351
Недетерминированные конечные автоматы 354
Поиск строк 355
Вычисление редакционного расстояния 359
Резюме 361
Упражнения 362
Глава 16. Криптография 365
Терминология 366
Перестановочные шифры 367
Перестановка строк/столбцов 367
Перестановка столбцов 369
Маршрутные шифры 371
Шифры подстановки 372
Шифр Цезаря 372
Шифр Виженера 373
Простая подстановка 375
Схема одноразовых блокнотов 375
Блочные шифры 376
Подстановочно-перестановочные сети 377
Шифр Фейстеля 378
Шифрование с открытым ключом и RSA 380
Функция Эйлера 381
Обратные величины 381
Пример использования RSA 382
Практические соображения 383
Другие области применения криптографии 383
Резюме 384
Упражнения 385
Глава 17. Теория вычислительной сложности 387
Обозначения 388
Классы сложности 388
Сведение 391
3SAT 393
Паросочетание в двудольном графе 393
NP-сложность 394
Задачи обнаружения, сообщения и оптимизации 394
Сообщение 396
NP-полные задачи 397
Резюме 399
Упражнения 400
Глава 18. Распределенные алгоритмы 402
Виды параллелизма 402
Систолические массивы 403
Распределенные вычисления 405
Многопроцессорные вычисления 407
Состояние гонки 407
Взаимная блокировка 411
Квантовые вычисления 412
Распределенные алгоритмы 413
Отладка распределенных алгоритмов 413
Чрезвычайно параллельные алгоритмы 414
Сортировка слиянием 416
Задача обедающих философов 416
Задача двух генералов 419
Задача византийских генералов 420
Согласование 423
Выбор лидера 426
Снимок 427
Синхронизация часов 428
Резюме 429
Упражнения 429
Глава 19. Головоломки, встречающиеся на собеседованиях 432
Как задавать вопросы с подвохом 433
Как отвечать на вопросы с подвохом 435
Резюме 439
Упражнения 440
Приложение А. Собрание алгоритмических понятий 442
Приложение Б. Решения к упражнениям 453
Глоссарий 522
Алфавитный указатель 536
Добавить комментарий