Этюды для программистов

Инструментовка. Это еще одна задача, требующая списков или деревьев и рекурсивных процедур для их обработки. Для таких задач был создан Лисп, но наравне с ним подойдут и многие другие языки для работы со списками. Снобол несколько слабее по части внутренней обработки данных, но чрезвычайно мощные возможности по анализу вводимой и подготовке выводимой информации делают Снобол конкурентоспособным кандидатом. На самом деле здесь подойдет любой язык типа Паскаля или PL/I, так или иначе приспособленный для работы с текстами, имеющий определяемые структуры данных и рекурсивные процедуры.

Длительность исполнения. Одному исполнителю на 3 недели.

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

Для многих важных математических операций не существует методов, которые позволяли бы всегда вычислять результат в символьном виде. Важное место среди них занимает интегрирование. Хотя любая рациональная функция имеет неопределенный интеграл, простой пример функции 1/х (неопределенный интеграл от нее — ln x) показывает, что нам не надо далеко ходить за функциями, нарушающими границы замкнутого пространства рациональных функций. Расширение пространства функций путем добавления показательных функций и логарифмов, как предложено выше, лишь обостряет проблему. Не решает проблемы даже использование определенного интеграла, поскольку результат определенного интегрирования может и не быть константой, если подинтегральное выражение содержит переменные, отличные от переменной интегрирования, или если пределы интегрирования не константы. Символьные интеграторы были одними из первых программ, написанных для демонстрации «интеллектуального» поведения ЭВМ. Если вы будете работать над предлагаемой задачей в два или три раза дольше, то сможете создать примитивный интегратор.

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

Литература

Мозес (Moses J.). Algebraic Simplification: A Guide for the Perplexed, CACM, 14, 8, pp. 527–537, 1971.

Мозес (Moses J.). Symbolic Integration: The Stormy Decade, CACM, 14, 8, pp. 548–560, 1971.

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

21. Превратное обратное, или Ошибки при работе с плавающей точкой

Многие из методов, которые сейчас изучаются в средней школе, создавались величайшими математиками в течение столетий. Среди них — методы решения системы линейных уравнений, которые неявно включают методы обращения квадратных матриц. Начинающий алгебраист, изучая эти алгоритмы, может усомниться в том, что они всегда будут работать; но, испробовав метод на двух-трех примерах* наш скептик отбросит всякие сомнения. Он даже себе не представляет, какой его ждет удар: программа, написанная им в соответствии с простым и обоснованным алгоритмом, дает совершенно неверные результаты. Разве можно заподозрить, чтобы метод обращения матриц, придуманный королем математиков Гауссом, оказался несостоятельным?