Введение в алгоритмы: Книга: «Алгоритмы. Вводный курс» — Томас Кормен. Купить книгу, читать рецензии | Algorithms Unlocked | ISBN 978-5-907144-90-3 — RC74 — интернет-магазин радиоуправляемых моделей

Содержание

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

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

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

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

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

Практику же ничего не заменит.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вместо итога

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

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

от сортировок до машины Тьюринга

Если вы плохо знакомы с теоретическими основами computer science, загляните сюда – мы нашли для вас хороший вводный курс по алгоритмам.

Если хочешь подтянуть свои знания, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:

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

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

В итоге будешь браться за сложные проекты и повысишь чек за свою работу 🙂

Интересно, хочу попробовать

10 видеоуроков от Рахима Давлеткалиева всего за 2,5 часа введут вас в курс дела и дадут наводку, что изучать дальше.

Урок 1. Что такое алгоритмы?

Начинается курс с самых основ: понятия алгоритма и краткой истории происхождения. Лектор расскажет, откуда алгоритмы взялись и зачем нужны, какое отношение к ним имеют Аль-Хорезми (самое прямое), Чарльз Бэббидж и лорд Байрон (очень косвенное).

Теперь вы знаете:

кто «изобрел» алгоритмы;
чем алгоритм отличается от программы;
что произошло в 1834 году;
зачем аналитической машине нужна была ручка;
как входные данные могут влиять на эффективность алгоритма.

Урок 2. Пример простого алгоритма

Знаете, какое слово в информатике и программировании самое важное? Нет, не алгоритм 🙂 Обязательно посмотрите второй урок: там об этом подробно рассказывают. А еще демонстрируют пример простейшего алгоритма, после которого вы точно поймете, что это такое.

Теперь вы знаете:

что такое псевдокод и зачем он нужен.

Углубляемся в тему:

Изучаем алгоритмы: полезные книги, веб-сайты, онлайн-курсы и видеоматериалы

6 бесплатных книг по алгоритмам в программировании

Урок 3. Знакомство с алгоритмами сортировки

Сортировка – одна из самых распространенных задач в программировании (и в жизни). Если вы в этом не уверены, смотрите третий урок курса. Кроме жизненных примеров он продемонстрирует, что существует очень много способов сортировать различные вещи. Некоторые из них эффективны, а другие – совершенно бесполезны.

Кроме непосредственно сортировок, в этом уроке затрагивается очень важная концепция – сложность алгоритмов и способы ее оценки.

Теперь вы знаете:

о каких пузырьках идет речь в алгоритме bubble sort;
что и куда вставляется при сортировке вставками;
почему bogosort – это неудачная идея для сортировки;
что бывают худшие и лучшие случаи входных данных;
как абстрагироваться от физической реализации вычислительных устройств при оценке эффективности алгоритма.

Еще немного о сортировках:

Какая сортировка самая быстрая? Тестируем алгоритмы
Сортировки в гифках: 8 популярных алгоритмов

Урок 4. Разделяй и властвуй

Переходим к одной из самых эффективных алгоритмических концепций. В четвертом уроке лектор расскажет о сортировке слиянием и о ее преимуществах перед уже рассмотренными видами сортировок.

Теперь вы знаете:

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

что значит «логарифмический рост алгоритма».

Урок 5. Сложность алгоритмов и Big O

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

Теперь вы знаете:

как математически описать масштабируемость алгоритмов;
что такое асимптотическая нотация и зачем она нужна;

чем O отличается от Ω;
почему для оценки быстродействия можно отбросить все степени аргумента, кроме самой большой.

Подробнее о нотациях здесь:

Анализ алгоритмов для начинающих: вводное руководство

Урок 6. Графы

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

Теперь вы знаете:

как абстракции (да-да, вот оно главное слово из второго урока) помогают решать реальные проблемы;
почему не любой граф можно обвести одним росчерком;
как найти самый короткий путь из точки A в точку B;
кто такой Дейкстра.

Графы – это очень интересно:

Иллюстративное введение в теорию графов и её применение
10 алгоритмов на графах в гифках

Урок 7.

Структуры данных

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

Теперь вы знаете:

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

Полезные курсы:

Наиболее полный видеокурс по алгоритмам и структурам данных
Алгоритмы и структуры данных: развернутый видеокурс

Урок 8. Деревья и двоичные деревья

В восьмом уроке курса по алгоритмам лектор разбирается с рекурсивными деревьями, растущими сверху вниз. Оказывается, они бывают разными.

Теперь вы знаете:

чем глубина узла отличается от его высоты;
как устроено двоичное дерево поиска;
формулу расчета высоты дерева;
можно ли хранить деревья в массивах;
почему с низкими деревьями проще работать;
какова эффективность операций с деревьями;
в чем особенность red-black tree.

Еще немного о структурах данных:

10 структур данных, которые вы должны знать (+видео и задания)

Урок 9. Машина Тьюринга

Еще одна крутая абстрактная концепция computer science – машина Тьюринга, придуманная, как можно догадаться, Аланом Тьюрингом. Что это за штука – смотрите в девятом уроке.

Теперь вы знаете:

что Алан Тьюринг сделал для развития компьютерной науки;
из каких частей состоит легендарная машина Тьюринга;
в чем ее детерминированность.

Урок 10. P vs. NP

Почему мы вообще обсуждаем сложность и эффективность алгоритмов, если компьютеры невероятно умные и быстрые? Ведь они в принципе могут решить любую задачу. А вот и нет, и на этом – последнем – уроке курса вы вкратце коснетесь самой интересной части computer science: нерешенных проблем.

Теперь вы знаете:

что такое задачи P- и NP-класса;
какую роль здесь играет машина Тьюринга;
можно ли быстро решить проблему, если ее решение можно быстро проверить;
какие задачи до сих пор не решены и почему;
в чем магия NP-полных задач.

Супер! Вы прошли этот небольшой курс по алгоритмам. В награду за усердие вот вам еще пара интересных статей:

Взламываем шифры: криптография за 60 минут
Без паники! Разбираемся с алгоритмами в 6 шагов
6 алгоритмов решения задач по спортивному программированию
ТОП-15 алгоритмических задач, реализованных на C++