Энциклопедия ХХI века

Эта цель и по сей день не достигнута, но на пути к ней Лейбницу вместе с Ньютоном удалось заложить современное здание математики, а живущим в конце ХХ века продвинуться в понимании идей и практике программирования. Так родилась около тридцати лет назад серия книг о «нечисленном анализе», которой суждено стать энциклопедией следующего века по вопросам культуры программирования.

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

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

Том 1. Основные алгоритмы.
Глава 1. Основные понятия.
Глава 2. Информационные структуры.
Том 2. Квазичисленные алгоритмы.
Глава 3. Случайные числа.
Глава 4. Арифметика.
Том 3. Сортировка и поиск.
Глава 5. Сортировка.
Глава 6. Поиск.
Том 4. Комбинаторные алгоритмы.
Глава 7. Комбинаторный поиск.
Глава 8. Рекурсия.
Том 5. Синтаксические алгоритмы.
Глава 9. Лексикографический поиск.
Глава 10. Синтаксический поиск.

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

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

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

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

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

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

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

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