Алгоритмический взгляд на программирование

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

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

Первая книга принадлежит перу известных специалистов в области теории графов В. Н. Касьянова и В. А. Евстигнеева «Графы в программировании: обработка, визуализация и применение». Этот труд объемом более тысячи страниц, разбит на три части, в которых рассматриваются обработка и визуализация графов, применение их и граф-моделей. В книге имеются приложения, включающие материалы по равнодоступным машинам, языкам высокого уровня, NP-полным задачам и характеристикам размещений графов. Данное издание может быть использовано и преподавателями для создания специальных курсов и практикумов по программированию, а также для повышения квалификации ИТ-специалистов.

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

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

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

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

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

Следует обратить внимание на библиографические комментарии и списки литературы, завершающие каждую главу и имеющие самостоятельный интерес, открывающие путь читателю для самостоятельной работы. Данная книга займет достойное место на полке рядом с трудами Д. Кнута, А. Ахо, Дж. Хопкрофта и ряда других.

Вторая книга — Hacker?s Delight — является сборником программных приемов, собранных ее автором, Генри Уореном. Как отмечено в предисловии, «главная тема книги — рассмотреть базовые структурные отношения среди целых чисел и битовых строк, а также эффективные операции над ними». Во «Вступлении» автор уточняет: «Основное внимание уделено приемам работы с отдельными машинными словами или командами. Чаще всего в таких приемах используется смесь арифметических и логических команд».

Свою книгу автор начал с введения системы обозначений, команд и модели оценки времени их выполнения, рассмотрел «основы» — манипуляции с битами, словами, логические операции, сложение и многие другие действия, всего 20 функций. В последующих главах полезные алгоритмы подсчета битов, поиска и перестановки битов и байтов в слове. Эффективные приемы реализации компьютерной арифметики продемонстрированы в книге на алгоритмах выполнения округления до степени «2» и вычисления границ целых чисел, их сумм и разностей, а также логических выражений. Рассмотрены способы реализации алгоритмов вычисления целочисленных значений некоторых элементарных функций, использующих методы дихотомии. Приведены приемы для вычисления квадратного и кубического корней, степени и логарифма целых чисел.

Глава, посвященная приемам использования различных систем счисления в программировании, для большинства читателей книги явится «изысканным блюдом». Несколько завершающих глав книги описывают хорошо известные математические задачи, весьма полезные при программировании. Автор выбрал приемы построения кода Грея, кривой Гилберта, простых чисел, позволяющие при программировании реализовывать перебор без повторов всех n-разрядных двоичных чисел и всех целочисленных точек произвольного квадрата на плоскости, а также вычислять по известным из теории чисел формулам простые числа. В книге коротко рассмотрены отношения целых чисел и чисел с плавающей точкой, точнее автор критически анализирует рекомендации стандарта IEEE 754-1985.

Однако необходимо отметить, что перевод и редактирование книги вызывают ряд замечаний. Первое, не удачен перевод заглавия, в котором сделан акцент на «трюках», тогда как гораздо важнее демонстрация автором самого того пути к трюкам, которым он прошел. Второе замечание касается напрасных попыток переводчика или редактора заменять устоявшиеся термины, например, «дихотомия» на «бинарный поиск» или округление «до числа» на «к числу» — при чтении такого перевода создается впечатление, что предыдущего опыта не существует. Вряд ли стоит забывать, что теория чисел много старше computer science.