Издательство "Вильямс" - Рецензии на книгу "Искусство программирования, том 1. Основные алгоритмы, 3-е издание"

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

19.06.2006
Компьютерра
Денис Коновальчик
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-архитектуру.

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

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

27.01.2006
Открытые системы (портал)
Геля Рузайкин
http://www.osp.ru/os/2000/09/075.htm

Эта цель и по сей день не достигнута, но на пути к ней Лейбницу вместе с Ньютоно Речь идет об «Искусстве программирования» Дональда Кнута, перевод которой выпустил в этом году издательский дом «Вильямс». Потребность в этих книгах в России очень велика, не только в силу того, что они стали крайне редкими в переводе издательства «Мир», опубликованного еще в 70-80-е годы, но и по причине бурного развития информационных технологий, когда программирование вовлекает в свою орбиту все больше пользователей. Положение усугубилось еще и тем, что переход к так называемому промышленному стилю в программировании, основанному на программных продуктах, привел к значительному снижению понимания места программирования и его идеологии в информационных технологиях, уступив стремлению принять участие в версионных гонках. Желание узнать, что нового в поступившей версии продукта, мало стимулировало к занятиям фундаментальными проблемами программирования, поэтому сегодня программирование – это написание текста на заданном языке. Тогда как всякая задача, подлежащая программированию, нуждается в своей постановке и выборе подходящих алгоритмов, требующих порой нетривиального анализа.

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

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

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

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

Том 2. Квазичисленные алгоритмы.

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

Глава 4. Арифметика.

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

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

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

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

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

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

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

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

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

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

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

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

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

В основные понятия автор включил алгоритм, математическую индукцию, числа и действия с ними, числовые функции, анализ алгоритмов, а также асимптотические представления. Кроме того, описан гипотетический цифровой компьютер MIX, на базе которого строится материал упражнений и иллюстрируются основные методы программирования. В главные понятия вошли: подпрограммы, сопрограммы, программы-интерпретаторы, а также ввод-вывод. Особый интерес вызывает попытка автора рассматривать модель компьютера, вобравшего в себя характерные черты шестнадцати известных цифровых ЭВМ 60-70-х. Вот его некоторые характеристики. Это двоично-десятичный компьютер, машинное слово из пяти байтов и знака и т.п. Алгоритм на языке MIX должен работать правильно независимо от размера байта. И, разумеется, у него имеется язык ассемблера MIXAL, на котором и написаны примеры в книге. Главу завершает параграф, посвященный истории и библиографии развития основных методов программирования, затронутых в книге.

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

Работе с информационными структурами в памяти, в частности, представлению структурной информации, вытекающему из таблиц данных, организованных с помощью пяти связей (компиляторы COBOL) посвящен отдельный раздел. Завершают главу разделы, в которых рассмотрены методы динамического выделения памяти, такие как резервирование, освобождение или «система двойников», а также сведения по истории их трансформации, библиографии и сравнению.

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

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

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 лет автор внес значительные изменения и дополнения в третье издание первого и второго томов и во второе издание третьего тома. Примерно в два раза увеличено число упражнений. Некоторые разделы переработаны с учетом теоретических результатов последних лет. Расширен предметно-именной указатель.

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

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