Кормен, Лейзерсон, Ривест, Штайн¶

Кормен, Лейзерсон, Ривест, Штайн — это коллектив авторов одного из наиболее известных и авторитетных учебников по алгоритмам, «Introduction to Algorithms» (в русском переводе — «Алгоритмы: построение и анализ»). Книга, впервые опубликованная в 1990 году, является стандартным справочным и учебным пособием для студентов, преподавателей и специалистов в области компьютерных наук, инженерии и смежных дисциплин. Она охватывает широкий спектр алгоритмов, структур данных, методов их анализа и математических основ, необходимых для понимания вычислительных процессов.

¶История создания

Первое издание «Introduction to Algorithms» вышло в 1990 году в издательстве MIT Press. Авторами выступили Томас Х. Кормен (Thomas H. Cormen), Чарльз Э. Лейзерсон (Charles E. Leiserson), Рональд Л. Ривест (Ronald L. Rivest) и Клиффорд Штайн (Clifford Stein). Все четверо на момент написания книги были профессорами или исследователями в ведущих университетах США (Массачусетский технологический институт, Дартмутский колледж, Колумбийский университет). Книга задумывалась как замена устаревшему учебнику «The Art of Computer Programming» Дональда Кнута, который, несмотря на фундаментальность, был сложен для массового обучения.

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

¶Содержание книги

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

¶Основные разделы

• Основы: введение в анализ алгоритмов, асимптотическая нотация (O-большое, Ω, Θ), рекуррентные соотношения, основы теории вероятностей.
• Сортировка и порядковые статистики: алгоритмы сортировки (быстрая, сортировка слиянием, пирамидальная, сортировка подсчётом, поразрядная, блочная), поиск k-го наименьшего элемента.
• Структуры данных: массивы, списки, стеки, очереди, хеш-таблицы, двоичные деревья поиска, красно-чёрные деревья, B-деревья, кучи (фибоначчиевы, биномиальные), структуры данных для непересекающихся множеств.
• Продвинутые методы проектирования: динамическое программирование, жадные алгоритмы, алгоритмы на графах (поиск в ширину и глубину, кратчайшие пути, минимальные остовные деревья, потоки в сетях).
• Сложность и NP-полнота: классы P и NP, NP-полнота, сведения, примеры NP-полных задач (задача коммивояжёра, задача о рюкзаке, задача о выполнимости).
• Алгоритмы для специальных задач: алгоритмы на строках (поиск подстроки, алгоритм Кнута-Морриса-Пратта, алгоритм Бойера-Мура), алгоритмы вычислительной геометрии (выпуклая оболочка, пересечение отрезков), криптографические алгоритмы (RSA, Диффи-Хеллман), параллельные алгоритмы.

¶Особенности изложения

Каждый раздел содержит:

• Формальное описание алгоритма на псевдокоде.
• Доказательство корректности.
• Анализ времени работы и используемой памяти.
• Примеры работы с иллюстрациями.
• Упражнения для самостоятельного решения (с ответами в конце книги).

¶Авторы

• Томас Х. Кормен (род. 1956) — профессор компьютерных наук в Дартмутском колледже (США). Специализируется на алгоритмах, параллельных вычислениях и образовании в области информатики. Автор нескольких книг по алгоритмам и программированию.
• Чарльз Э. Лейзерсон (род. 1953) — профессор Массачусетского технологического института (MIT). Известен работами в области параллельных вычислений, архитектуры компьютеров и алгоритмов. Соавтор учебника «Introduction to Algorithms» с первого издания.
• Рональд Л. Ривест (род. 1947) — профессор MIT, один из создателей криптосистемы RSA (совместно с Ади Шамиром и Леонардом Адлеманом). Лауреат премии Тьюринга (2002). Внёс вклад в теорию алгоритмов, криптографию и теорию сложности.
• Клиффорд Штайн (род. 1965) — профессор Колумбийского университета (США). Специализируется на алгоритмах, комбинаторной оптимизации и теории графов. Присоединился к авторскому коллективу начиная со второго издания.

¶Значение и влияние

Книга «Introduction to Algorithms» является одним из самых цитируемых учебников в области компьютерных наук. По данным Google Scholar, на неё ссылаются более 50 000 раз. Она переведена на десятки языков, включая русский, китайский, японский, немецкий, французский. Русский перевод выполнен под редакцией В. В. Панова и издаётся с 1998 года.

Учебник используется в большинстве ведущих университетов мира для преподавания курсов по алгоритмам и структурам данных. Его часто называют «библией алгоритмов» из-за полноты охвата и строгости изложения. Книга оказала значительное влияние на формирование современной учебной программы по информатике, заменив более ранние работы, такие как «The Art of Computer Programming» Дональда Кнута.

¶Критика

Несмотря на широкое признание, учебник подвергается критике за:

• Сложность для начинающих: многие студенты отмечают, что книга требует хорошей математической подготовки и не всегда подходит для первого знакомства с алгоритмами.
• Объём: четвёртое издание содержит более 1300 страниц, что делает его громоздким для быстрого ознакомления.
• Отсутствие практических примеров на реальных языках программирования: псевдокод, используемый в книге, не всегда легко перевести в работающий код на конкретном языке (например, C++, Python, Java). Однако в четвёртом издании появились примеры на Python.
• Устаревание отдельных разделов: некоторые темы, такие как параллельные алгоритмы, быстро развиваются, и книга не всегда успевает за новыми достижениями.

¶Интересные факты

• Псевдоним «CLRS» (по первым буквам фамилий авторов: Cormen, Leiserson, Rivest, Stein) стал общепринятым сокращением для обозначения книги.
• Первое издание было написано вручную на бумаге, а затем набрано в системе TeX. Авторы использовали собственные макросы для оформления алгоритмов.
• Книга стала настолько популярной, что её неофициально называют «Кормен» (по фамилии первого автора) среди русскоязычных студентов и программистов.
• В 2022 году вышло четвёртое издание, в котором впервые были включены разделы по алгоритмам машинного обучения (например, метод опорных векторов, деревья решений) и современным структурам данных (например, хеш-таблицы с открытой адресацией).

¶Источники

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. (2013). Алгоритмы: построение и анализ (3-е изд.). Вильямс.
• Google Scholar — цитирования книги «Introduction to Algorithms».
• Официальный сайт MIT Press — описание четвёртого издания.