РЕЦЕНЗИИ
Кнут Дональд. Искусство программирования. Т. 1-3. Издательский дом “Вильямс”, 2000.
Издательский дом “Вильямс”, выпустив перевод первых трех томов третьего издания давно ставшего классическим труда Д. Кнута, сделал прекрасный подарок не только тем, кто серьезно занимается компьютерным программированием, но вообще всем интересующимся этим предметом. Труд Кнута относится к редким книгам, которые не утеряли своего значения за прошедшие 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 тыс. экземпляров, а тираж нового перевода- 17 тыс. Все три тома вместе стоили 12 руб. 27 коп. Первые шесть глав перевода на русский язык нового издания составили три огромных тома объемом 192,25 условных печатных листа.
Как обещает Кнут, четвертый и пятый тома будут вскоре изданы, а остальные находятся в процессе написания.
Книги Кнута принадлежат к редкой категории технических книг, которые не устаревают с течением времени. И причина тому - тщательный подбор материал, энциклопедичность и мастерство изложения. Трудно даже представить себе объем переработанных автором статей, диссертаций и книг.
Как известно, для представления излагаемого материала Кнут решил не использовать алгоритмические языки FORTRAN или ALGOL, а применить машинно-ориентированный язык “идеальной” вычислительной машины MIX. Обосновывая этот ход в первом издании, он писал, что “алгоритмические языки больше подходят при решении вычислительных задач, нежели при решении нечисленных задач, которые здесь рассматриваются”, и что существующие в настоящее время языки недостаточно совершенны для таких тем, как “сопрограммы, буферизация ввода-вывода+ рекурсия”. В новом издании в обосновании применения машинно-ориентированного языка этот абзац опущен, но остальная аргументация сохранена.
Первый том носит название “Основные алгоритмы”. Описанные в нем понятия и алгоритмы являются базой для компьютерного программирования и владеть ею должен каждый программист. Впечатляет глубина рассмотрения любого вопроса и объем рассмотренного автором материала. Читатель узнает, как, когда и где возникло понятие алгоритм, что такое стеки, очереди, деки и деревья, научится динамически распределять память, собирать “мусор” и еще делать многое другое. Обилие упражнений для самостоятельной проработки составляет важную часть материала, так как без их выполнения невозможно выучить предмет. Каждое упражнение снабжено оценкой его трудности по “логарифмической” шкале, которая колеблется от 00 (чрезвычайно легкое упражнение) до 50 (исследовательская проблема, еще не получившая решения).
В третьей главе во втором томе “Получисленные алгоритмы” читатель узнает все, что известно в настоящее время о генерировании случайных чисел. Кстати, по сравнению с первым изданием книги эта глава подверглась значительной переработке и в ней появились программы на языке Си. Назначение главы 4 - анализ арифметических операций: сложения, вычитания, умножения и деления. Несмотря на то что арифметику мы начинаем учить с раннего детства, здесь можно найти много интересного про эту науку. В главе рассматриваются алгоритмы выполнения операций над числами с “плавающей точкой”, дробями, очень большими числами, полиномами со степенными рядами и затронуты такие вопросы, как преобразование чисел из одной системы счисления в другую, разложение на множители, операции над полиномами и степенными рядами.
В третьем томе в главе 5 рассматриваются методы выполнения сортировок, а в главе 6 - поиска. Сортировка и поиск - исключительно важный раздел программирования, и Кнут, например, считает, что “практически каждый важный аспект программирования возникает в связи с сортировкой и поиском!”.
При подготовке первого издания “Искусства программирования” к печати Кнут встретился со значительными неудобствами и начал разработку редакционно-издательской системы, которая сможет облегчить ему выпуск последующих томов. Потратив десять лет на создание системы компьютерного набора METAFONT и TEX, теперь он применяет ее для набора своей книги. И не только он. Многие научные издательства используют его систему. Правда, с точки зрения читателя, было бы правильней, если бы автор потратил это время для написания остальных задуманных им книг, которых мы все с нетерпением ожидаем.
За прошедшие 35 лет автор внес значительные изменения и дополнения в третье издание первого и второго томов и во второе издание третьего тома. Примерно в два раза увеличено число упражнений. Некоторые разделы переработаны с учетом теоретических результатов последних лет. Расширен предметно-именной указатель.
Книги изданы на хорошей бумаге в твердом ламинированном переплете и будут долго служить своим владельцам.
Хочется пожелать издательству “Вильямс” коммерческого успеха и скорейшего дополнительного тиража, а себе - дожить до выхода в свет всех книг Дональда Кнута.
Издательский дом “Вильямс” (812) 230-3248.
