6 книг об алгоритмах и структурах данных

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

1

Дасгупта С., Пападимитриу Х., Вазирани У., «Алгоритмы»

Основной плюс учебника заключается в том, что многие алгоритмы объяснены гораздо короче и проще, чем в других книгах: с одной стороны, без излишнего формализма, с другой — без потери математической строгости. Авторы попытались не просто привести классические алгоритмы, но и показать, как до них можно было догадаться самому. Доступно излагаются такие стандартные темы, как О-символика, алгоритмы сортировки, метод «разделяй и властвуй», жадные алгоритмы, динамическое программирование. При этом покрыты и такие менее стандартные темы, как универсальное хеширование, линейное программирование и квантовые алгоритмы. Книга вполне подойдет новичкам: есть много примеров, картинок и несложных упражнений, а возникающие математические понятия авторы объясняют на специально отведенных для этого врезках.

2

Шень А., «Программирование: теоремы и задачи»

Хорошо известный в узких кругах программистов учебник от Александра Ханиевича Шеня (у которого есть много других отличных учебников по математике) организован как последовательность задач, к каждой из которых приводится подробное решение. При чтении стоит пытаться сначала решить задачу самому и только потом читать решение. Если решить получится самостоятельно, вы получите большое удовольствие. Если же не получится, вы с бо́льшим интересом и уважением отнесетесь к прочитанному решению. Круг покрытых тем довольно широкий.

3

Alexander S. Kulikov, Pavel Pevzner, «Learning Algorithms Through Programming and Puzzle Solving»

Недавняя книга-задачник, которая хорошо подходит для новичков. В учебнике обсуждаются основные методы разработки алгоритмов: жадные алгоритмы, метод «разделяй и властвуй», сортировки, динамическое программирование. По каждой из этих тем дано несколько задач — как простых, так и сложных, которые нужно сдать в систему автоматической проверки. Система прогоняет решение на десятках тщательно подобранных тестовых данных. В каждом случае проверяется, что решение находит верный результат и что оно это делает очень быстро — менее чем за секунду, даже на больших объемах данных. В книге есть отдельная глава, обсуждающая лучшие практики реализации алгоритмов и частые ошибки, с примерами кода на C++ и Python. Рассказывается о том, как тестировать реализации (в частности, о стресс-тестировании). Еще одна отличительная черта книги — интерактивные головоломки. Они помогут читателям догадаться до некоторых алгоритмических идей самостоятельно.

4

Jon Kleinberg, Eva Tardos, «Algorithm Design»

Отличный учебник, который, с одной стороны, подходит для начинающих, а с другой — содержит и такие продвинутые темы, как класс PSPACE, локальный поиск и равновесие Нэша, вероятностные алгоритмы. Изложение и живое, и строгое одновременно. Еще одна особенность книжки — упражнения. Во многих из них описана реальная практическая задача, в которой нужно сначала понять, какая математическая модель ей соответствует, и только потом придумывать алгоритм. Несколько первых таких задач в каждой главе приводятся с подробными решениями.

5

М. А. Бабенко, М. В. Левин, «Введение в теорию алгоритмов и структур данных»

Учебник покрывает первую часть курса, который авторы на протяжении многих лет читают в Школе анализа данных «Яндекса». Бо́льшая часть книги посвящена алгоритмам и структурам данных для сортировки и поиска. Учебник подразумевает некоторую математическую грамотность читателя, поэтому вряд ли подходит для новичков. В то же время отлично подходит для более опытных читателей: в книге почти нет примеров, авторы везде сразу переходят к делу. Изложение сжатое, но везде математически строгое. Помимо стандартных алгоритмов и структур данных, разобраны такие экзотические темы, как сплей-деревья, разные виды куч, совершенные хеш-функции, эффективные алгоритмы для задачи range minimum query. Каждый раздел завершается несколькими алгоритмическими задачами олимпиадного типа, которые снабжены подробными решениями.

6

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, «Introduction to Algorithms»

Ставший уже классическим учебник по алгоритмам — одна из наиболее цитируемых книг по Computer Science, продано более полумиллиона копий. Часто используется как основной учебник в курсах по алгоритмам в США, с аббревиатурой CLRS (по первым буквам фамилий авторов). Покрывает довольно широкий набор базовых алгоритмов и структур данных. По этой причине может быть использован не только как учебник, но и как энциклопедия. Изложение достаточно формальное (утверждения о корректности и времени работы алгоритма часто вынесены в отдельную теорему), есть много примеров и упражнений — как простых, так и сложных.

Еще несколько книг

Ниже мы приводим еще несколько книг с уклоном в разные области алгоритмов с менее детальными описаниями.

Antti Laaksonen, «Competitive Programmer’s Handbook»  — базовые алгоритмы и структуры данных с уклоном в олимпиадное программирование. Много примеров кода на C++.

Dan Gusfield, «Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology»  — о том, как эффективно работать со строками и текстами.

Phillip Compeau, Pavel Pevzner, «Bioinformatics Algorithms: An Active Learning Approach»  — алгоритмы в биоинформатике.

Joseph O’Rourke, «Computational Geometry in C»  — алгоритмы и структуры данных для решения геометрических задач.

Rajeev Motwani, Prabhakar Raghavan, «Randomized Algorithms»  — вероятностные алгоритмы: о том, как случайные числа помогают строить более эффективные или простые алгоритмы.

Vijay V. Vazirani, «Approximation Algorithms»  — о том, как быстро находить достаточно хорошие решения для трудных оптимизационных задач.

Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S., «Parameterized Algorithms»  — алгоритмы для трудных задач, которые имеют приемлемое время работы в случае, когда некоторый параметр у входных данных не слишком велик.