Алгоритмы: введение в разработку и анализ

Алгоритмы: введение в разработку и анализ (2006)
Автор: Левитин А.В.

Целевая аудитория: начинающие разработчики на любом языке программирования.

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

В книге рассматриваются следующие темы:
✔️ основы анализа эффективности алгоритмов;
✔️ метод грубой силы;
✔️ метод декомпозиции;
✔️ метод уменьшения размера задачи;
✔️ метод преобразования;
✔️ динамическое программирование и многое другое.

Преимущества:
➕ большой и качественный материал по теме;
➕ множество примеров кода.

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

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

Начну с минусов (чтобы закончить на позитиве :-).
Довольно мутная глава 10 о классификации сложных неполиномиальных задач, хотя в целом общая мысль понятна. Пара теорем в основном тексте (про приложение, где тоже куча теорем, не скажу - не читал) также как-то не очень воспринимается. Опечатков в книге практически нет - те которые есть (в основном в некоторых рисунках) легко восстанавливаются из контекста. Разве что в самом начале (что может повлиять на решение о дальнейшем чтении) настораживает абзац, где речь идет о НОД, а определение приведено для НОК и через пару страниц тяжеловат абзац об усовершенствовании решета Эратосфена (хотя из примера опять же ясно что хотел сказать автор)
На этом собственно минусы и заканчиваются, и которые - ничто по сравнению с огромными плюсами. Первое - это удачная классификация алгоритмов не по решаемым ими задачам (сортировка, поиск и т. д.), а по принципам, лежащим в их основе (грубая сила, декомпозиция, преобразование, жадные методы, динамическое программирование и т. д. ). Ну и самое главное - это язык и стиль автора. Все алгоритмы настолько доходчиво объясняются словами и диаграммами, что приведенный во многих местах псевдокод попросту становиться невостребованным, т. к. если понятна идея, то написать псевдо- (а за ним и рабочий) код - дело вторичное и обычно несложное. В этом смысле можно сказать, что упомянутого в комментариях желания прочесть после данной книги что-то более фундаментальное (например, Кормена) как раз и не возникает (ну разве что почитать что-либо о неполиномиальных задачах). Так как более подробные книги (если конечно они не используются в качестве справочника) обычно читаются в надежде понять что-то, что не понятно здесь. Во время чтения я даже параллельно с Левитиным сравнивал две крайние альтернативы (конечно только просматривая и читая избранные абзацы) - Кормена и Вирта. Так вот Кормен отбивает желание углубляться в него как объемом, так и испещренностью текста псевдокодами, доказательствами чего-либо и общей насыщенностью всевозможными обозначениями. У Вирта другая крайность - при небольшом объеме текст в некоторых местах настолько "заархивирован", что на "распаковку" смысла приходиться хорошенько потратиться. Сравнить хотя бы алгоритмы поиска подстрок у Левитина и Вирта: у первого - слова и картинки, у второго - предикатные уравнения (конечно и у Вирта есть слова и картинки - но общее впечатление именно такое). Вообщем, на мой взгляд, Левитин - действительно, как сказано в аннотации, один из лучших по данной теме.
P. S. Кстати для расширения кругозора по алгоритмам (именно для этого, а не для понимания чего-то непонятного у Левитина :-) мой кандидат для следующего прочтения - это Скиена (вроде бы с похожим стилем).