Мюллер Дж. П., Массарон Л. - Алгоритмы для чайников, 2-е изд. (Для чайников) [2025, PDF, RUS]

ВВЕДЕНИЕ
Об этой книге .. . . . . .. . . . . .. . .... . . . .. . .... . ......... .. . . .. . 14
Глупые предположения ......................... . ............................ 16
Значки. используемые в книге . . . . ...... . ........ . .................. 17
Помимо книги ...................................................................... 18
Куда двигаться дальше . . .. . . ......... .. . . . . .... . .. .. ... .. ... . 19
РАЗДЕЛ 1. НАЧАЛО РАБОТЫ С АЛГОРИТМАМИ .. . ................... 21
Глава 1.
Знакомство с алгоритмами . ..... . . . ................. . .................. 23
§ 1. Описание алгоритмов .................................................... 24
Правильный способ приготовления тостов: определение
применения алгоритмов .......... . . . ....................................... 26
Алгоритмы повсюду . . . . . ..... . . .. . . . .. . . . . .. .. . . . .. . . . .. 29
§ 2. Использование компьютеров для решения проблем .......... 30
Максимальное использование возможностей
современных ЦП и графических процессоров . . . .. . .. . .. ... . . 31
Работа со специализированными чипами . . . ... . . . . .. . . . ..... 32
Сети: совместное использование - это больше чем забота ........ 33
Использование доступных данных . ........ . . . . . ...... . ............ 34
§ 3. Различение проблем и решений ......... .. . ... ... . . . .. . ..... 35
Корректность и эффективность ... . . . .. . . . . . ... . . . .. . . . .... 35
Понимание. ч то бесплатный сыр только в мышеловке ............ 36
Адаптация страте гии к проблеме .. . .......... . ....................... 36
О п исание ал горитмов на универсальном языке ................... 37
Решение проблем, похожих на кирпичные стены, только
сложнее .................................. . ........................................ 37
§ 4. Структурирование данных для получения решения ......... 38
Понимание точки зрения компьютера ........................... . ..... 38
Упорядочивание данных имеет значение .... .. .. . ... .. ...... .. . 39
ГЛАВА 2.
Рассматриваем проектирование алгоритмов . ..... . .... . .......... 40
§ 1. Начинаем решать проблему .... . ............ . ...................... 41
Моделирование реальных задач ... .... .. .. ... .. .. .. .. ......... ... 42
Поиск реш ен ий и контрпримеров .. . . . ... .. . .. .. . . . .. ... .. . 44
Стоя на плечах гигантов ................... . ................................. 45
§ 2. Разделяем и властвуем . . ......................... . ................... 46
Избегаем решений методом полного перебора . .................. . . 47
Принцип KISS (Keeping it simple. silly. или «не усложняй») ...... 48
Разделение проблемы обычно эффективнее ........................... 48
§ 3. Узнаем . что жадность может быть полезной ........ . ... .... 49
Применение жадного подхода ......... . . . . . .. . .. . ....... . .49
Поиск хорошего решения ....................... . ..................... 50
§ 4. Вычисление затрат и последующие эвристики ..... . . ..... . 51
Представление задачи в виде пространства ..... . ......... 52
Случайный поиск и везение . .......... . . . . .. . . . . ........ . . 53
Использование эвристики и функции стоимости ..... . ..... 54
§ 5. Оценка алгоритмов .... . . . ...................... . ........... 55
Моделирование с использованием абстрактных
машин . . . ....... . . .. . . . .. . . . . ..... . .. . . . . .. . . . . ... .... . . . 56
Еще более абстрактный подход ................. . ......... 57
Работа с функциями . . .......... . ...... . ........ . . . ....... 58
ГЛАВА 3.
Работа с Google Colab.................. . ............. . ....... . ........ 62
§ 1. Определение Google Colab . . . . . ..... . . . . . .. . .. .. ... . ... 63
Понимание функций Google Colab ........ . ...... . ......... 63
§ 2. Работа с блокнотами ...................... . ...... . ......... 69
Создание нового блокнота ............ . ......... . ......... 69
Открытие существующих блок н отов . .. . . . . .. . . . . . ....... . . 70
Сохранение блокнотов ......................... . ... . ..... 72
§ 3. Выполнение общих задач . ...... . ............... . . . ......... 74
Создание ячеек с кодом . ............. . . . . . .. . . . . ....... . . 75
Создание текстовых ячеек . . . . ..... . .. . . . . .. . . . . . ....... . . 77
Создание специальных ячеек ..... . ............. . ... . ..... 77
Редактирование ячеек ...... . . . . . . . .... . ........ . ......... 78
Перемещение ячеек ................... . . . . .. ... .. .. .. .... 78
§ 4. Использование аппаратного ускорения . . . . . .. ... . . ....... . . 79
§ 5. Выполнение кода ................................ . ......... 79
§ 6. Получение помощи ........... . . . . . ...... . ........ . . . ...... . 80
ГЛАВА 4.
Выполнение базовых операций с данными на Python ............... 82
§ l. Выполнение вычислений с использованием векторов и матриц . . 83
Понимание скалярных и векторных операций ................. 84
Выполнение умножения векторов ................... . ............ 86
Создание матр и цы - правильный способ начать ........... 86
Умножение матриц .... . . . ............. . ............................. 87
Определение расширенных матричных операций .... . ..... 89
§ 2. Создание комбинаций правильным способом .... . ........ 91
Работа с перестановками . . . . . ........ . . . . .. .... .. . .... . . . 91
Перемешивание комбинаций . . ... . . . .. . . . .. . ... . . ....... . . 93
Борьба с повторениями ........ ... . . . . ....... .. ... .... . ............ 94
§ 3. Получен и е желаемых результатов с помощью рекурсии ... 94
Объяснение рекурсии . ....... . .......................................... 95
Устранение хвостовой рекурсии ....................................... 98
§ 4. Более быстрое выполнение задач ................ . ........... 99
Рассматриваем метод «разделяй и властвуй» .... ... .. . . . ... 99
Разл ичение разных возможных решений ......................... 102
ГЛАВА 5.
Разработка класса для матричных вычислений ... .. .. .. .... 104
§ l . Избегание использования NumPy ... . . . . .... . . . .. . .. 105
§ 2. Почему стоит использовать классы ........................ 107
§ 3. Создание базового класса ................................. 108
Создание матрицы .... . .... . ............... . ................... 109
Вывод результирующей матрицы . . . . . . ................... 110
Доступ к конкретным элементам матрицы .................. 111
Выполнение скалярного сложения и сложен ия
матриц . . . ............... . .................................................. 112
Выполнение умножения . .... . ... .. . ... .. . .. .. .. . .... . .. .. 113
§ 4. Манипулирование матрицей .... .... . ... .. .. . .. . . . .... 117
Транспонирование матр ицы ........................................... 117
Вычисление определителя ............................................... 118
Уплощение матрицы (преобразование в одномерный
список) .... .... . . . .... . ..... . .... . ...... . ..... . . ........... . . .. 122
РАЗДЕЛ 2. ПОНИМАНИЕ НЕОБХОДИМОСТИ
СОРТИРОВКИ И ПОИСКА . .... . .. .... . .. .. ... .. . .. ... . ..... . 123
ГЛАВА 6.
Структурирование данных . . .... .. ...... .. . . .. . .. . . ....... .. 125
§ 1. Определение необходимости структуры ............... . .... 126
Облегчаем пон и ман ие содержимого . .. ... . ..... ... .... . .. 126
Сопоставление данных из разных источников ............. 127
Учет необходимости исправления дан ных ... . ............. 129
§ 2. Упорядочивание и нагромождение данных .... . .... ..... 132
Упорядочивание в стеках ..... .... . . . .... . ..... . ...... . .. 132
Использование очередей ............................................ 134
Поиск данных с помощью словарей . ......... .. .......... 135
§ 3. Работа с деревьями ............ . .............. .. .......... 136
Пон имание основ деревьев ... . ... . ........ . ... . .... . .. .. 137
Построение дерева . ............. . . . . .. ....... . . . . .. . . . . . 138
§ 4. Представление отношений в виде графа ....... . ....... 140
Выходим за рамки деревьев ......................................... 140
Построение графов ... . ..... . .... . . . .... . . . .... . . .... . .. 141
ГЛАВА 7.
Упорядочивание и поиск данных ... . ......... . .................. 143
§ 1. Сортировка данных с помощью сортировки слиянием
и быстрой сортировки ........ . ......................................... 144
Почему важна сортировка данных ..... . . . . .. . . .. . ........ 144
Применение улучшенных методов сортировки . ....... .... 148
§ 2. Использование деревьев поиска и кучи . .... ............ 154
Рассматриваем необходимость эффективного
поиска .. . ............ . . . .. . ............ . . . .. . .. . ....... . 154
Построение бинарного дерева поиска .................... 156
Выполнение специализированного поиска с помощью
бинарной кучи .............................................................. 158
§ 3. Опираясь на хеширование . .. . ............ . . .. . . .. . ... 159
Раскладываем все по корзинам .... .... . . .... . ........... 160
Избегание коллизий ............ . ............... . . . ...... 161
Создание собственной хеш-функции ................. . ... 163
РАЗДЕЛ 3. ИССЛЕДОВАНИЕ МИРА ГРАФОВ ... . ....... . ....... 167
ГЛАВА 8.
Основы теории графов ..................................... . ....... . . 169
§ 1. Объяснение важности сетей ...................... . ........ 170
Рассматриваем суть графа ......... . ............................... 171
Графы повсюду .................. . ............. . ..................... 173
Социальная сторона графов ... ... . ............. . .............. 175
Понимание под графов . . . .. . ............ . . .. . . .. . ........ 176
§ 2. Определение того, как рисовать граф ............. . ........ 177
Различаем ключевые атрибуты .. . ............... . ........ 177
Визуализация графа .. . . . .............. . ........ .. .. .. ... 179
§ 3. Измерение функциональности графа ............. . ........ 180
Подсчет ребер и вершин ........................ . ... . .... 181
Вычисление центральности ..................... . ........ 183
§ 4. Перевод графа в числовой формат ................ . ........ 186
Преобразование графа в матрицу ....... . . . .. . .. . ........ 186
Использование разреженных представлений ............. 188
Использование списка для хранения графа ...... . ........ 188
ГЛАВА 9.
Восстанавливая связи . ........................................ . ....... 190
§ 1. Эффективное прохождение графа ................ . ........ 191
Создание графа .................. . . ..................................... 192
Применение поиска в ширину ..... . ............. .. .. . .... 193
Применение поиска в глубину ..... ... .. . .... . ... .. .. .. ... 195
Выбор подходящего метода ............. . . . .. . .. . ........ 197
§ 2. Сортировка элементов графа ..... .. . . . . ......... . ... . ... 197
Работа с направленными ациклическими графами (DAG) . . 198
Использование топологической сортировки . . . .. ...... .. . 199
§ 3. Сведение к минимальному остовному дереву .............. 200
Истори ческий контекст поиска минимального остовного
дерева ..... . . .. . . . .. . . .......... . . . . .. . . ..... . ... .. . . . . 200
Работа с невзвешенными и взвешенными графами . .. . . . .. 201
Создание примера минимального остовного дерева ....... 201
Выбор правильных алгоритмов ... . . .. . ......... . ......... 203
Знакомство с приоритетными очередями . ..... . . . . .. . . . .. 204
Использование алгоритма Прима .. . .... . . .. . . .. . ...... .. . 205
Тестирование алгоритма Краскала . . ....... . . .. . . .... . .. . 207
О п ределение наилучшего алгоритма ... . ... . ........ . .... 209
§ 4. Поиск кратч айше го маршрута ... . . .. . . . .. . . ....... . . . 210
О п ределение понятия поиска кратчайшего пути . . . .. . . . .. 211
Добавление отрицательного ребра . . ....... . ... .. .... . ... 213
Объяснение алгоритма Дейкстры . . ...... .. .... . .... . . . .. 215
Объяснение алгоритма Беллмана - Форда ..... . . . . .. . . . . . 218
Объяснение алгоритма Флойда - Уоршелла . .... ...... .. . 221
ГЛАВА 10.
Раскрывая секреты графов .......................................... . 226
§ 1. Представление социальных сетей как графов ............... 227
Кластеризация сетей на группы . .. . . . .. . . ..... . . . . .. . . . . . 227
Обнаружение сообществ . . ....... . .. . ... .. . . . .. ...... .. . 230
§ 2. Навигация графа . . . ....... . . . ............................. 233
Подсчет степеней разделения .... . . . . . ........ . ... .. . . . . . 233
Случайное блуждание по графу . .. . . . .. . . ..... . . . . .. . . . . . 235
ГЛАВА 11.
Поиск нужной веб-страницы .. . . .. .. ... .. . . .. . .. . .. . . ........ .. 237
§ 1. Поиск мира в поисковой системе . . .. .... ...... . . .. ... .. . .. . 238
Поиск данных в интернете ....... . . . . . ........ . . . . .. . . . . . 238
Как н айти нужные данные .................................................... 239
§ 2. Объяснение алгоритма PageRank ... . . .... . .. . . . ........ . .. 240
Понимание логики алгоритма PageRank .... . . .. . . .... . .. . 241
Объясняя принципы работы PageRank .. . . . ... .. . .. . .. .. . . 243
§ 3. Реализация PageRank . . . . ..... . . . .. . . . .. . . . . ... . . . . .. 243
Реализация скрипта на Python . . .. . . ....... . . .. . . .... . .. . 244
Борьба с наивной реализацией . . .. . .... .... . . . .. ...... .. . 247
Внедрение скуки и телепортации .. . . .. ... .... . . . ...... . .. 251
Заглядывая внутрь поисковой системы . .... . .. . ... .. . .. .. 252
Другие применения PageRank .............. . . . ............... . .. . 253
§ 4. Выход за рамки парадигмы PageRank . ....... . . . .. . ..... 253
Знакомство с семантическими запросами ...... . . . . .. . . . . . 254
Использование ИИ для ранжирования результатов поиска 254
РАЗДЕЛ 4. ОБРАБОТКА БОЛЬШИХ ДАННЫХ .. .. . .... .. ... . . . . 255
ГЛАВА 12.
Управление большими данными . ... . .. . ...... . ....... . .......... 257
§ 1. Преобразование энергии в данные .............. . . . ........ 258
Понимание следствий закона Мура ..... . . . . .. ... .. . ... ... 259
Поиск данных повсюду . .... . ......... ..... .. .. . . .. . ..... 261
Внедрение алгоритмов в бизнес ......... . .... . .. . ........ 264
§ 2. Потоковые потоки данных ...... . . . ............. . . .. . ...... 266
Анализ потоков с правильным рецептом .................. 268
Сохраняя нужные данные ... . .......... . . .... . . . . ........ 270
§ 3. Скетчинг ответа на основе п отоковых данных ..... ...... 274
Фильтрация элемен тов потока по существу ...... .. . ...... 275
Демонстрация фильтра Блума ............ . .......... . .... 278
Определение количества уникальных элементов ..... .. ... 281
Уч имся подсч ит ывать объекты в потоке ................... 283
ГЛАВА 13.
Распараллеливание операций .. .. ... . .. .. . ... .. ... . . ....... .. 285
§ 1. Управление огромным и объемами данных . . . ... . . .. .. 286
Понимание параллельной парадигмы .... . .. .. . .. . .... . ... 287
Распределение файлов и операц и й ............. .. .. . .... 289
Применение решения MapReduce ................. . ...... 292
§ 2. Разработка алгоритмов для MapReduce ........... . ........ 297
Настройка симул я ции MapReduce ....... . . .... . . . ........ 298
Иссл едование с помощью отображения . . .... . .. . ....... 300
ГЛАВА 14.
Сжатие и сокрытие данных .... . .... . . ..... .. ... .. ............ . . . 304
§ 1. Уменьшение объема данных ... .. .. ... .. .. .. .. .. .. ....... .. 305
Понимание кодирования .... . .... .. .... . . . .... . . . ....... 305
Рассматриваем эффекты сжатия ................ .. ....... 307
Выбор конкретного типа сжатия . ................. . ..... 309
Выбор прав и льного кодирования ...... . ................. . 311
Кодирование с использованием сжатия Хаффмана ........ 314
Запоминание посл едовательностей с помощью LZW ...... 317
§ 2. Сокрытие ваших секретов с помощью криптографии ....... 321
Подстановка символов ............ ... .. . .... . ....... ............... ... 322
Работа с шифр ованием AES ............. . .. . .... . .................... 324
РАЗДЕЛ 5. РЕШЕНИЕ СЛОЖНЫХ ЗАдАЧ .... ....... .... .. ... . . . . 327
ГЛАВА 15.
Работа с жадными алгоритмами .... . ......... . ...................... . 329
§ 1. Решаем . когда лучше быть жадным .. . . . . ..... . .. . ... .. 330
Почему жадный подход эффективен . .. . . ..... . . . . .. . . . . ... 332
Держим жадные алгоритмы под контролем ........................... 333
Рассмотрение NР-полных задач ........................................... 335
§ 2. Как жадность может быть полезна .. ... .... .. .... . .... . .... 338
Организация кешированных данных компьютера ... .. . .. . . . 338
Конкуренция за ресурсы ..................................................... 340
Возвращаясь к кодированию Хаффмана . .... .... . .... . ... 343
ГЛАВА 16.
Применение динамического программирования ................... . 347
§ 1. Объяс нение динамического программировани я . ......... .. . 348
Исторический экскурс ............ . . . ......................................... 349
Как сделать задачи динамическими . .... . . .. . . .. ......... 350
Преобразование рекурсии в динамическое решение ...... 351
Использование мемоизации ...... . . . . .. ....... . ... .. ... . . 355
§ 2. Открываем лучшие ди н амичные рецепты ..... .. . ........ . .. 358
Заглядываем в рюкзак ... . . .. ...... . ......... .. . . .... . .. . 358
Путешествие по городам ...... .. .. . ... .. . .. .. .. . ... .. .. . . 363
Приближенный поиск строк ... ....... . .. . . . .. . .... . .. .. . . 368
ГЛАВА 17.
Использование рандомизированны х алгоритмов . .. ... ... . .. . ..... 372
§ 1. Определение принципа работы рандом изации . ... . . . .. . .... 373
Рассмотрим. почему нужна рандомизация ..... . . . . .. . . . . . 374
Понимание работы вероятности .......................... 375
Понимание распределений . ...... . . ....... . . .... .... . ... 377
Моделирование использования метода Монте- Карло ...... 381
§ 2. Внесение случайности в вашу ло гику . . .. . . ..... . . . . .. . . . 383
Вычислен ие медианы с помощью быстро го выбора ....... 384
Моделирование методом Монте-Карло ....... . ........... 387
Более быстрая сортировка с помощью быстрой
сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
ГЛАВА 18.
Выполнение локального поиска . . . . ....... . .. . .. . .. . .... .. . ... .. 392
§ 1. Понимание локального поиска ............................. 393
Знакомство с окрестностью .... . .. . ...... .. . . .. . ...... ... 394
§ 2. Представляем приемы локально го поиска . . ....... . . .. . . . .. 396
Объя снение алгоритма восхождения к вершине
на примере задачи о ферзях ....... . .... . .. . .... . .... . . .. 398
Знакомство с имитацией отжига .... . ..................... 401
Избегание повторов с помощью поиска с за претами . ... . 403
§ 3. Решение выполнимости булевых схем ...... .. . .... . . .... .. 404
Решение 2-SAT с п омощью рандомизации .. .. . .......... 405
Реализация кода на Python ..................... . ....... 406
Осознание важности начальной точки .. . . .... . . . . ........ 410
ГЛАВА 19.
Применение линейного программирования . . ....... . ............... 412
§ 1. Использование линейных функций в качестве инструмента .. 413
Осваиваем необходимую математику .... . . .... ........... 415
Учимся у прощать при планировании ............. . ........ 417
Понимание ограничений .... . . . . . ................. . ...... 420
§ 2. Использование линейного программирования на практике .. 421
Настройка PuLP дома . . . .... . .......... . . . .. . . . .......... 422
Оптимизация производства и выручки ........... . ........ 422
ГЛАВА 20.
Рассмотрение эвристических методов . . . . ... .. ... . .... . . . .. ... 427
§ 1. Дифференциальная эвристика ....... .. .. . . . . .. ... .. . ... ... 428
Рассматривая цели эвристик . . ..... .... ... .... .... .. ... . .429
§ 2. Маршрутизация роботов с использованием эвристики ....... 432
Разведка на неизвестной территории ... . ................. 433
Использование мер расстоян ия в качестве
эвристики . .......... . . . .. . . . .......... . . . .. . . . . . ....... .435
§ 3. Объяснение алгоритмов поиска п ути .............. . ... . .... 436
Создание лабиринта . . . . .... . .......... . ...... . .......... 437
В поисках быстрого маршрута по первому наилучшему
совпадению ..... .... . . . .. . . . ..... . .... . . .... . . ......... 440
Эвристический обход с помощью А* ............. . ........ 444
РАЗДЕЛ 6. ЧАСТЬ ДЕСЯТИ . . . . ....... . .. . .......... . ...... .. . . . .. . .449
ГЛАВА 21.
Десять алгоритмов, которые меняют мир .... . ....... . ....... . ....... 451
§ 1. Использование процедур сортировки ............. . ... . .... 452
§ 2. Поиск вещей с помощью процедур поиска ........ . ........ 453
§ 3. Встряхиваем вещи с помощью случайных чисел ... . ........ 453
§ 4. Вы п олнение сжатия да нных ....................... . ... . .... 454
§ 5. Сохранение данных в секрете . . . ... . ...... . .... . . . ... . .... 455
§ 6. Изменение домена данных .. . . . . .. . .... .. . ... .. .. ... . ... ... 456
§ 7. Анализ ссылок ......... . . .... . .......... . . .. . . . . . . ....... .456
§ 8. Выявление закономерностей в данных ..... . ............... 457
§ 9. Работа с автоматизацией и автоматическими ответами . ...... 458
§ 10. Создание уникальных идентификаторов ... .. ............. 459
ГЛАВА 22.
Десять нерешенных алгоритмических проблем ..... . ......... . .... 460
§ 1. Быстрое решение проблем ...... . ............... . . . ........ 461
§ 2. Более эффективное решение задач 3SUM .... . ... .. ..... . .. 461
§ 3. Ускорение умножения матриц .............................. 462
§ 4. Определение остановки п рограммы ........................ 463
§ 5. Создание и использование односторонних функций ........ 463
§ 6. Умножение действительно больших чисел ............. . .... 464
§ 7. Разделение ресурсов п оровну ............................ .465
§ 8. Сокращение време н и расчета расстояния редактирования .. 465
§ 9. Игра в игру «Паритет» ..... . . . ...... . ...................... 466
§ 10. Понимание пространственных проблем ................... 466
ОБ АВТОРАХ . ...... ..... ......... . ..................................... 468
Посвящение Джона ........................................... 468
Посвящение Луки ...... . ...... .. ....... . . . ...... .. ............ 469
Благодарности Джона ......... . . . .. . .......................... 469
Благодарности Луки . . . . . ............. . . . . . ................... 470
Предметный указатель . ......... . ..................................... 471