Стоит прочитать: обзор книги Кормена и Лейзерсона «Алгоритмы. Построение и анализ»

Дмитрий Красичков

предприниматель, программист, основатель IT-компании

Возможно, выскажу весьма неоднозначное мнение, но считаю, что глобально программистам книги не особо нужны. Вернее, не настолько нужны, как многим другим. Поймите меня правильно, чтение — прекрасный способ получения знаний для подавляющего большинства специальностей, и когда разработчик, например, переходит на руководящую работу книги по менеджменту будут отличным подспорьем. Тем не менее, если говорить непосредственно о программировании, то скорость развития технологий не позволяет ждать выхода соответствующей литературы, а уж тем более ее перевода на русский язык (мы оптимистично надеемся, что каждый программист свободно читает на английском, но исходя из моей практики, это далеко не так).

Существенная часть прикладных знаний в IT устаревает за 4-5 лет, но официальной документации в совокупности с примерами, конференциями и статьями вполне хватает, чтобы держать себя «в форме» и осваивать новый материал на теоретическом уровне. Практику же ничего не заменит.

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

Библия программиста

Удачно сочетая в себе полноту и строгость изложения материала, книга Кормена стала де-факто стандартом в отрасли в качестве учебника для подготовки программистов. Показательно, что ведущие мировые университеты, включая MIT, использует ее как основной учебник по соответствующему курсу. Более того, этот фундаментальный труд будет полезен далеко не только студентам, многие профессиональные разработчики найдут для себя что-то новое, а в дальнейшем книга может послужить отличным настольным справочником.

В книге Кормена представлено детальное описание таких важных тем, как: сортировки, структуры данных, динамическое программирование, жадные алгоритмы, алгоритмы на графах, параллельные вычисления и многое другое. По сути, охватывая основной спектр современных алгоритмов.

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

Структура изложения

Автор начинает повествование с основ анализа алгоритмов. Этот раздел крайне важен для понимания остального материала, т.к. формирует необходимый математический аппарат для сравнения алгоритмов между собой. Именно благодаря этому мы можем аргументировано говорить «алгоритм A лучше, чем B для этой задачи» и наоборот. Остальные главы книги относительно самодостаточны и могут изучаться в произвольном порядке.

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

Начинающий уровень

• Быстрая сортировка.
• Сортировка кучей.
• Сортировка за линейное время.
• Медианы и порядковые статистики.
• Элементарные структуры данных.
• Хеш-таблицы.
• Двоичные деревья.
• Динамическое программирование.
• Жадные алгоритмы.

Средний уровень

• Красно-черные деревья.
• Б-деревья.
• Алгоритмы на графах.
• Амортизационный анализ.
• Алгоритмы параллельных вычислений.

Продвинутый уровень

• Остальные разделы на выбор.

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

Зачем мне теория алгоритмов?

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

Для изучения данной области есть как минимум три, с моей точки зрения, достаточно веские причины.

Во-первых, знание теории алгоритмов позволяет вам писать эффективный код. Это научит вас применять правильные инструменты в правильных местах. Например, в следующий раз вы будете понимать, почему тут стоит использовать HashMap (применительно к языку Java), а в другом случае TreeMap и т.д.

На первый взгляд можно предположить, что широкая доступность дешевых вычислительных ресурсов позволяет игнорировать такие параметры программы, как потребляемая память и/или время выполнения, ведь всегда можно докупить оперативной памяти или новый процессор. Отчасти эта точка зрения имеет право на жизнь, но нужно учитывать, что и объем обрабатываемых данных, и нагрузка на ресурсы также растут. В современном мире эффективные алгоритмы востребованы еще больше, чем раньше.

Не стоит исключать и возможность столкнуться с отраслью, где требования к эффективности программы изначально очень высокие в силу какой-либо специфики. Например, компьютерная графика или разработка под «железо» достаточно показательны в этом плане. В частности, у меня был опыт написания программного обеспечения для дорожных контроллеров и светофоров, и ресурсы некоторых микросхем были настолько скудными, что на них не ставили даже операционную систему.

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

В-третьих, подавляющее большинство технологических гигантов (такие как Google, Facebook, Yandex и т.д.) весьма требовательно относятся к знаниям теории алгоритмов у кандидатов при приеме на работу. Например, есть замечательная книга G.L. McDowel «Cracking the Coding Interview» по прохождению собеседований подобного формата и даже беглого взгляда на ее оглавление достаточно, чтобы понять, насколько сильно эти темы пересекаются с материалами из книги Кормена.

Безусловно, не все хотят работать в подобных компаниях, но для кого-то это может стать дополнительным стимулом.

Вместо итога

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

Знание теории алгоритмов необходимо, чтобы быть квалифицированным специалистом в своей профессии, а книга «Алгоритмы. Построение и анализ» Томаса Кормена и Чарльза Лейзерсона однозначно является одной из лучших в этой области и крайне рекомендуется к ознакомлению. Я буду очень рад, если благодаря этой статье кто-то узнает об этой книге и на нашем рынке станет чуточку больше профессионалов.