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

Description

Алгоритмы - это всего лишь пошаговые алгоритмы решения задач, и большинство таких задач уже были кем-то решены, протестированы и проверены. Можно, конечно, погрузиться в глубокую философию гениального Кнута, изучить многостраничные фолианты с доказательствами и обоснованиями, но хотите ли вы тратить на это свое время? Откройте великолепно иллюстрированную книгу, и вы сразу поймете, что алгоритмы - это просто. А rрокать алгоритмы - это веселое и увлекательное занятие. Предисловие 11 Благодарности 12 О книге 14 Структура книги 15 Как работать с этой книгой 16 Для кого предназначена эта книга 16 Условные обозначения и загружаемые материалы 17 Об авторе 17 От издательства 17 Глава 1. Знакомство с алгоритмами 18 Введение 18 Что вы узнаете об эффективности алгоритмов 19 Что вы узнаете о решении задач 19 Бинарный поиск 20 Более эффективный поиск 23 Упражнения 27 Время выполнения 28 «О-большое» 29 Время выполнения алгоритмов растет с разной скоростью 29 Наглядное представление «О-большое» 32 «О-большое» определяет время выполнения в худшем случае 34 Типичные примеры «О-большого» 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 Снова об «О-большом» 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 NР-полные задачи 196 Задача о коммивояжере - шаг за шагом 197 Как определить, что задача является NР-полной? 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