Алгоритмы — это всего лишь пошаговые алгоритмы решения задач, и большинство таких задач уже были кем-то решены, протестированы и проверены. Можно, конечно, погрузится в глубокую философию гениального Кнута, изучить многостраничные фолианты с доказательствами и обоснованиями, но хотите ли вы тратить на это свое время?
Откройте великолепно иллюстрированную книгу "Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих" и вы сразу поймете, что алгоритмы — это просто. А грокать алгоритмы — это веселое и увлекательное занятие.




Оглавление книги "Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих"



Предисловие . 11
Благодарности . 12
О книге 14
Структура книги 15
Как работать с этой книгой . 16
Для кого предназначена эта книга 16
Условные обозначения и загружаемые материалы . 17
Об авторе . 17
От издательства 17
Глава 1. Знакомство с алгоритмами 18
Введение 18
Что вы узнаете об эффективности алгоритмов 19
Что вы узнаете о решении задач . 19
Бинарный поиск 20
Более эффективный поиск 23
Упражнения 27
Время выполнения 28
«O-большое» 29
Время выполнения алгоритмов растет с разной скоростью 29
Наглядное представление «O-большое» 32
«O-большое» определяет время выполнения в худшем случае 34
Типичные примеры «O-большого» 35
Упражнения 36
Задача о коммивояжере 37
Шпаргалка 39
Глава 2. Сортировка выбором 40
Как работает память . 41
Массивы и связанные списки . 43
Связанные списки . 45
Массивы . 46
Терминология . 47
Упражнения 48
Вставка в середину списка 49
Удаление 50
Упражнения 51
Сортировка выбором . 53
Пример кода . 57
Шпаргалка 58
Глава 3. Рекурсия 59
Рекурсия . 60
Базовый случай и рекурсивный случай 63
Стек 65
Стек вызовов 66
Упражнения 68
Стек вызовов с рекурсией . 69
Упражнения 73
Шпаргалка 74
Глава 4. Быстрая сортировка . 75
«Разделяй и властвуй» 76
Упражнения 85
Быстрая сортировка 85
Снова об «O-большом» . 92
Сортировка слиянием и быстрая сортировка . 93
Средний и худший случай . 95
Упражнения 99
Шпаргалка 99
Глава 5. Хеш-таблицы . 100
Хеш-функции 103
Упражнения 107
Примеры использования . 107
Использование хеш-таблиц для поиска . 108
Исключение дубликатов 110
Использование хеш-таблицы как кэша 112
Шпаргалка 116
Коллизии 116
Быстродействие 119
Коэффициент заполнения . 122
Хорошая хеш-функция 124
Упражнения 125
Шпаргалка 126
Глава 6. Поиск в ширину . 127
Знакомство с графами . 128
Что такое граф? 131
Поиск в ширину 132
Поиск кратчайшего пути . 135
Очереди . 136
Упражнения 137
Реализация графа . 138
Реализация алгоритма 141
Время выполнения 146
Упражнения 147
Шпаргалка 150
Глава 7. Алгоритм Дейкстры 151
Работа с алгоритмом Дейкстры . 152
Терминология . 157
История одного обмена . 160
Ребра с отрицательным весом . 167
Реализация . 170
Упражнения 181
Шпаргалка 181
Глава 8. Жадные алгоритмы 182
Задача составления расписания 183
Задача о рюкзаке 185
Упражнения 187
Задача о покрытии множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
Приближенные алгоритмы 189
Упражнения 196
NP-полные задачи . 196
Задача о коммивояжере — шаг за шагом . 197
Как определить, что задача является NP-полной? . 202
Упражнения 205
Шпаргалка 205
Глава 9. Динамическое программирование . 206
Задача о рюкзаке 206
Простое решение 207
Динамическое программирование . 208
Задача о рюкзаке: вопросы . 217
Что произойдет при добавлении элемента? . 217
Упражнения 220
Что произойдет при изменении порядка строк? . 220
Можно ли заполнять таблицу по столбцам, а не по строкам? . 221
Что произойдет при добавлении меньшего элемента? . 221
Можно ли взять часть предмета? 221
Оптимизация туристического маршрута 223
Взаимозависимые элементы 224
Может ли оказаться, что решение требует более двух «подрюкзаков»? . 225
Возможно ли, что при лучшем решении в рюкзаке остается пустое место? 226
Упражнения 226
Самая длинная общая подстрока . 226
Построение таблицы . 228
Заполнение таблицы . 229
Решение . 230
Самая длинная общая подпоследовательность 232
Самая длинная общая подпоследовательность — решение 233
Упражнения 235
Шпаргалка 235
Глава 10. Алгоритм k ближайших соседей . 236
Апельсины и грейпфруты 236
Построение рекомендательной системы 239
Извлечение признаков 240
Упражнения 245
Регрессия . 245
Выбор признаков 248
Упражнения 249
Знакомство с машинным обучением 249
OCR 250
Построение спам-фильтра . 251
Прогнозы на биржевых торгах 252
Шпаргалка 252
Глава 11. Что дальше? 254
Деревья 254
Инвертированные индексы 258
Преобразование Фурье . 259
Параллельные алгоритмы . 260
MapReduce 261
Для чего нужны распределенные алгоритмы? . 261
Функция map 261
Функция reduce . 262
Фильтры Блума и HyperLogLog 263
Фильтры Блума . 265
HyperLogLog 265
Алгоритмы SHA . 266
Сравнение файлов 267
Проверка паролей . 268
Локально-чувствительное хеширование 269
Обмен ключами Диффи—Хеллмана . 270
Линейное программирование 272
Эпилог 273
Ответы к упражнениям . 274