elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
Что должен знать каждый программист: Алгоритмы
elizarov

Несколько лет назад я опубликовал небольшую заметку под названием "Список книг которые должен прочитать каждый Java программист", в которой поделился книги, которые должен прочитать каждый профессиональный Java программист не зависимо от конкретной прикладной области, в которой он работает. Но технологий и языков программирования много. А есть ли какие-нибудь базовые навыки, которыми должен владеть каждый программист? Безусловно есть. Одним из таких навыков является построение и анализ алгоритмов.

Про алгоритмы написано множество книг и учебников. Конечно, нельзя не упомянуть фундаментальный труд Дональда Кнута "Искусство программирования", классическую книгу Никлауса Вирта "Алгоритмы + структуры данных = программы". Всех не перечесть.

Introduction to Algorithms Cover Однако, из всех книг про алгоритмы есть одна, которая безусловно выделяется своей глубиной, полнотой и актуальностью, оставаясь одновременно доступной для понимания и интересной. Это замечательная книга Томаса Кормена, Чарльза Лейзерсона, Рональда Ривеста, и Штейна Клиффорда "Алгоритмы: построение и анализ".

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

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

В 2009 году было выпущено её третье издание и в 2012 году планируется выпуск его перевода на Русский язык.

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

Построение и анализ алгоритмов это основа профессиональной деятельности любого программиста и основа профессионального образования программиста. Книга "Алгоритмы: построение и анализ" содержит материал, который должен знать каждый программист.

UPDATE: А еще программист должен знать языки программирования.


  • 1
странно, мне казалось что на одной из работ я видел её переведенную версию
p.s.
вот еще интересная книга http://www.ozon.ru/context/detail/id/1458852/

Спасибо. Знаний мало не бывает. "Алгоритмические трюки для программистов" это специфический набор приемов и трюков связанных, в основном, с особенностями двоичного представления чисел. Такими вещами, безусловно, нужно владеть при оптимизации каждого такта производительности, но вряд ли нужно уметь прямо вот каждому программисту.


Edited at 2011-12-23 10:46 am (UTC)

Мне кажется, что Вирта нужно прочитать, а вот Кормен и Кнут это уже справочники.

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

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

А я не знаю в чем устарел Вирт. Неужели сортировки или Б-деревья уже устарели? А списки и рекурсивные алгоритмы?
А современные алгоритмами мне кажутся SVM и генетические алгоритмы. Но насколько я помню Кормен о них ни слова не говорит.

Конечно, сортировки и B-деревья вечны. В Кормене они тоже есть. Алгоритмы, как и теоремы не устаревают.

Вирт устарел в том плане, что он не говорит о современных достижениях (собственно потому, что книга-то старая). В Кормене же много современных вещей.

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


Edited at 2011-12-23 12:00 pm (UTC)

А что вы в Кормене считаете современным?

Употреблять слова "современный" и "устаревший" к таким книгам учебники по фундаментальным алгоритмам конечно не очень корректно с моей стороны. Все-таки они и должны быть консервативными и их надо оценивать на основании других критериев.

Да, Кормен безусловно и объективно более свеж. Даже в первом издании пробежав по оглавлению можно увидеть, например, кучи Фибоначчи, которые опубликованы в 1987, а это уже через 10 лет после публикации учебника Вирта в 1977 году. И это именно то, что я имел ввиду под словом "современно" для такого фундаментального труда.

Книжка Вирта всё-таки содержит катастрофически мало материала, даже если отбросить его новизну. И дело даже не алгоритмах. Там не представлена одна из ключевых техник анализа алгоритмов — амортизированное время. А без него, многие современные алгоритмы и программные комплексы просто нельзя представить. Без него, например, нельзя понять почему так крут хэш (которого там тоже нет).

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

В этой - http://www.algorist.com/ - есть много интересных задач и историй (якобы реальных), как придумывали алгоритмы.

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

+1, очень хорошая книга

а в ePUB/mobi есть?!

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Introduction to Algorithms (Third Edition) [third edition ed.] (9780262033848) The MIT Press 2009

на обменниках и в онлайн-библиотеках только в PDF

  • 1
?

Log in

No account? Create an account