Часть I. ВВЕДЕНИЕ
Эта часть книги — о компьютерной алгебре и системах компьютерной алгебры; основные понятия алгоритмов и их сложности представлены в ней наряду с понятиями структур данных. Разъясняется различие между компьютерной алгеброй и численным анализом;
В численном анализе вещественные числа аппроксимируются числами с плавающей точкой, поскольку внутреннее устройство большинства компьютеров ориентировано на работу с числами, состоящими не более чем из 10 десятичных цифр. Это приводит к неточным вычислениям, которые выполняются очень быстро, поскольку арифметические операции реализованы на аппаратном уровне.
Компьютерная алгебра имеет дело в основном с целыми числами произвольной точности, употребляя соответствующие структуры данных; это приводит к безошибочным вычислениям, которые выполняются несколько медленнее, так как арифметические операции должны быть реализованы в программном обеспечении.
Глава 1. Что такое компьютерная алгебра?
Термин компьютерная алгебра (или символьные и алгебраические вычисления) объясняется способностью компьютеров манипулировать математическими выражениями, заданными символьно, а не численно, подобно тому, как это делается в алгебре при помощи карандаша и бумаги. Имея дело главным образом с точными числами (целыми и рациональными числами бесконечной точности) и алгебраическими выражениями в их символьном представлении, системы компьютерной алгебры могут освободить ученых от утомительной рутинной работы, связанной с численными ошибками (усечение и округление), и, таким образом, помочь им глубже понять различные изучаемые физические явления — «цель вычислений в проникновении в суть, а не в цифрах» (согласно Р. Хэммингу). Это проникновение в суть достигается иногда при вычислении значений математических выражений, но во многих случаях при использовании алгебраических средств соотношения между величинами становятся яснее.
Компьютерная алгебра применяется к широкому кругу проблем. Рассмотрим, например, теорию гравитации, где исследуются возможные варианты общей теории относительности. Для того чтобы согласовываться с экспериментальными данными, эти варинанты должны удовлетворять теоретическому критерию Биркгофа; компьютерная алгебра является подходящим средством для применения этого критерия. Другой пример можно взять из неврологии, где система уравнений моделирует распространение сигнала по нерву. При некоторых условиях эти уравнения могут порождать повторяющиеся серии сигналов, так называемые wamn. Для того чтобы проверить устойчивость волнового пакета, достаточно вычислить знак некоторого математического выражения. Получить само это выражение вручную — кропотливый труд, но с использованием компьютерной алгебры это становится рутинным вычислением (Pavelle et al., 1981).
