Рецензии на книгу
"Искусство программирования, том 3. Сортировка и поиск, 2-е издание"

22.11.2005
Компьютерра ONLINE
Денис Коновальчик
http://www.computerra.ru/offline/2001/387/7737/page3.html

Свершилось! Возможно, именно этим возгласом многие математики и компьютерщики приветствовали долгожданное переиздание трехтомника Дональда Кнута - классической монографии по составлению и анализу компьютерных алгоритмов. Те пухлые, мышиного цвета талмуды первого русского издания, вышедшие почти четверть века назад, славно потрудились на ниве автоматизации народного хозяйства, став настоящим бестселлером (насколько это возможно при отсутствии свободного рынка). Эта увесистая серия входила в золотой фонд любого уважающего себя специалиста по АСУП, достать же ее в библиотеках было практически невозможно: редкие счастливчики держали у себя драгоценные тома годами. Хорошо помню резкий «скачок акций» Кнута в родной alma mater в связи с открытием специализации «инженер-программист». Рецидивы прошлого, кстати, дают себя знать и поныне: узнав о готовящемся в «Вильямсе» переиздании, ваш покорный слуга, как и многие другие поклонники искусства программирования, сделал онлайновый заказ на них еще в канун Рождества и с тех пор не раз стоически переносил объявления на сайте о переносе даты выхода в свет Кнута-2000. Что ж, ожидание не было напрасным: свежеиспеченная троица надежно обосновалась на моем столе. Раздобыв по такому случаю старые, видавшие виды тома прежнего издания, могу засвидетельствовать: «апгрейд» Кнута до «новой версии» вполне оправдан хотя бы потому, что ни искусство программирования, ни искусство полиграфии все эти годы не теряли времени даром.

Разумеется, не терял времени и сам Дональд Кнут, значительно дополнивший и исправивший главный труд своей жизни. Им внесены в текст сотни правок, многие из которых на счету его онлайновых корреспондентов. К слову, главный «искусствовед программирования» держит слово, исправно выплачивая символические 256 центов за каждую ошибку, найденную в тексте монографии (что несколько напоминает тактику разработки open source, столь популярную сегодня). Судя по тому, как непросто отыскать брешь в фундаментальных построениях маэстро Кнута, этот гонорар просто бесценен для его обладателя.

Творчески перерабатывая материал в духе времени, автор вместе с тем остался верен «генеральной линии», намеченной им добрые четыре десятка лет назад: система нумерации глав не изменилась ни на йоту, при этом каждый из томов остался самодостаточным и практически независимым по тематике от двух других. Новая версия перевода учла изменения, произошедшие в русскоязычной терминологии за эти годы, заменив, к примеру, допотопные «ЭВМ» современными «компьютерами», «табло» - «диаграммами», а «отрезки» - «сериями». Вместе с тем отсутствие слова «компьютер» в русскоязычном названии серии (как известно, Кнут назвал свое детище «The Art Of Computer Programming») мне представляется довольно спорным, особенно в наши дни, когда значение термина «программирование» размыто донельзя (примером тому - НЛП).

Верстка нового трехтомника просто изумительна, и во многом благодаря стараниям автора, который задумал и воплотил в жизнь настольные издательские системы TеX и Metafont, идеально подходящие для подготовки математических книг, а также лично бдел над оригинал-макетом своего детища. И все же не обошлось без ложки дегтя: схема-вкладыш из 3-го тома, иллюстрирующая слияние массивов данных на лентах (поистине транспарант, который впору вешать на стену), в «новом» Кнуте просто-напросто впечатана в текст в виде нескольких «слепых» страниц с ненавязчивым призывом «сделай сам». Не исключено, впрочем, что это было допущено намеренно, дабы погрязшие в drag-n-drop компьютерщики не забыли, как следует обращаться с ножницами и клеем.

Коллекция завершающих каждую главу алгоритмических упражнений, любовно собираемых автором на протяжении четырех десятилетий (именно их красоте и изяществу книга во многом обязана своей популярностью), выросла чуть ли не вдвое. Каждое из них традиционно оценивается в баллах сложности, где 50 баллов по «шкале Кнута» представляют неразрешимую научную проблему, а «штиль» подразумевает немедленный ответ. Впечатляет стремление автора быть на острие прогресса даже в упражнениях: так, цена одной из задач, предлагаемых Кнутом в каждом томе «для затравки» (!), «усохла» с 50 баллов в старом издании до 45 в новом. Причиной «девальвации» стало… всколыхнувшее недавно математический мир доказательство Великой теоремы Ферма! Что ждет нас, читателей, в XXI веке? Не пора ли подыскивать место на полках для следующих томов «Искусства программирования» (насколько известно, серия должна включать семь томов)? На эти и многие другие вопросы Кнут отвечает на своей Web-страничке. По словам автора, выход английской версии 4-го тома, посвященного комбинаторным алгоритмам и рекурсии, запланирован на 2003 год, но зато он «распухнет» настолько, что выйдет тремя отдельными книгами - «Алгоритмы перебора с возвратом», «Алгоритмы на сетях и графах», «Оптимизация и рекурсия». Морально устаревшую машину MIX в трудах Кнута к тому времени вытеснит новая машина MMIX (не путать с MMX!), имеющая полноценную RISC-архитектуру.

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

Что ж, изменения действительно налицо. И радует тот факт, что в следующий век программисты всея Руси вступят, имея под рукой обновленные книги Дона Кнута. А уж то, что эти книги позволяют справиться с более серьезными проблемами, чем написание резюме, можете быть уверены.

08.10.2004
PC Week (портал)
Александр Ливеровский
http://pcweek.ru/?ID=55076

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

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

Книга, задуманная Дональдом Кнутом в 1962 г., должна была состоять из 12 глав. Однако в процессе написания автор пришел к выводу, что каждая глава требует гораздо более фундаментального рассмотрения. В результате полный набор книг, озаглавленный "Искусство программирования", приобрел следующую структуру.

Том 1. Основные алгоритмы.

Глава 1. Основные понятия.

Глава 2. Информационные структуры.

Том 2. Получисленные алгоритмы.

Глава 3. Случайные числа.

Глава 4. Арифметические операции.

Том 3. Сортировка и поиск.

Глава 5. Сортировка.

Глава 6. Поиск.

Том 4. Комбинаторыне алгоритмы.

Глава 7. Комбинаторный поиск.

Глава 8. Рекурсия.

Том 5. Синтаксические алгоритмы.

Глава 9. Лексикографический поиск.

Глава 10. Синтаксический анализ.

Том 6. Теория языков.

Глава 11. Математическая лингвистика.

Том 7.Компиляторы.

Глава 12. Перевод языков программирования.

Первый том оригинального американского издания вышел в 1968 г. (В предисловии к современному изданию почему-то утверждается, что первое издание вышло в 1972 г.) Перевод на русский язык трех томов первого издания вышел последовательно в 1976, 1977 и 1978 гг. общим тиражом 186 тыс. экземпляров. Все три тома вместе стоили 12 руб. 27 коп. Первые шесть глав нового издания составили три огромных тома объемом 192,25 условных печатных листа (в переводе на русский язык).

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

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

Как известно, для представления излагаемого материала Кнут решил не использовать алгоритмические языки FORTRAN или ALGOL, а применить машинно-ориентированный язык "идеальной" вычислительной машины MIX.

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

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

Первый том носит название "Основные алгоритмы". Описанные в нем понятия и алгоритмы являются базой для компьютерного программирования и владеть ею должен каждый программист. Впечатляет глубина рассмотрения любого вопроса и объем рассмотренного автором материала.

Читатель узнает, как, когда и где возникло понятие алгоритм, что такое стеки, очереди, деки и деревья, научится динамически распределять память, собирать "мусор" и еще делать многое другое.

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

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

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

В третьем томе в главе 5 рассматриваются методы выполнения сортировок, а в главе 6 - поиска. Сортировка и поиск - исключительно важный раздел программирования, и Кнут, например, считает, что "практически каждый важный аспект программирования возникает в связи с сортировкой и поиском!".

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

Потратив десять лет на создание системы компьютерного набора METAFONT и TEX, теперь он применяет ее для набора своей книги. И не только он. Многие научные издательства используют его систему.

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

За прошедшие 35 лет автор внес значительные изменения и дополнения в третье издание первого и второго томов и во второе издание третьего тома. Примерно в два раза увеличено число упражнений. Некоторые разделы переработаны с учетом теоретических результатов последних лет. Расширен предметно-именной указатель.

Книги изданы на хорошей бумаге в твердом ламинированном переплете и будут долго служить своим владельцам.

Хочется пожелать издательству "Вильямс" коммерческого успеха и скорейшего дополнительного тиража, а себе - дожить до выхода в свет всех книг Дональда Кнута