Грокаем алгоритмы

Обложка книги
Адитья Бхаргава, 2017, издательство «Питер», ISBN 978-5-496-02541-6

Книга для тех, кто хочет получить базовое представление о распространённых алгоритмах и их применении. Алгоритмы рассматриваются на примере реальных, а не абстрактных задач. Всё объясняется доходчиво и с множеством иллюстраций.

Что можно узнать из книги

Как устроена память, как в ней хранятся массивы и связные списки, какие у них преимущества и недостатки.

Как работает рекурсия, что такое стек вызовов и как она на него влияет.

Как решать задачи с помощью стратегии «разделяй и властвуй», как эта стратегия используется в алгоритмах быстрой сортировки и сортировки слиянием.

Как устроены хеш-таблицы, что такое хеш-функция, коллизии и коэффициент заполнения. Как хеш-таблицы применяются: моделирование отношений между объектами, устранение дубликатов, кеширование данных.

Как моделировать сети с помощью графов, чем направленные графы отличаются от ненаправленных, как с помощью графа и поиска в ширину найти кратчайшее расстояние между двумя объектами; что такое топологическая сортировка; что такое взвешенные графы, как в них искать кратчайшее расстояние между объектами с помощью алгоритма Дейкстры, в каких случаях алгоритм Дейкстры не работает.

Как определить, что задача не имеет быстрого алгоритмического решения (NP-полные задачи), как решать такие задачи с помощью приближённых алгоритмов и жадной стратегии.

Что такое динамическое программирование, как и где оно применяется.

Как строить системы классификации на основе алгоритма k ближайших соседей, где ещё его можно применить, что такое извлечение признаков и регрессия и как они применяются в биржевых торгах, спам-фильтрах и системах рекомендаций.

В конце книги приводится краткий обзор 10 алгоритмов и структур данных, которые подробно не рассматривались в книге: бинарное дерево поиска, инвертированные индексы, преобразование Фурье, параллельные алгоритмы и MapReduce, фильтры Блума и HyperLogLog, SHA, обмен ключами Диффи-Хеллмана, линейное программирование.