обратном порядке обхода дерева; в то же время этот символ обозначает последователя узла Р при симметричном порядке обхода бинарного дерева.

В качестве примера .использования этих методов для решения практических задач рассмотрим некоторые операции с алгебраическими формулами. Такие формулы лучше всего представлять в виде древовидных структур, а не как одно- или двумерные конфигурации символов, и даже не как бинарные деревья. Например, формулу у = 31п{х -I-1) - а/х можно представить в виде дерева таким образом.

0<-...............

©-

в левой части рисунка показано обычное дерево, подобное представленному на рис. 21, в котором бинарные операторы -, х, / и t (последний символ обозначает возведение в степень) имеют по два поддерева, соответствующих их операндам. Унарный оператор In имеет одно поддерево, а переменные и константы являются концевыми узлами. В правой части рисунка показано эквивалентное правопрошитое бинарное дерево, включающее дополнительный узел у, который является заголовком списка этого дерева. Заголовок списка имеет вид, представленный условиями 2.3.Н8).

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

При обходе узлов дерева в левой части (7) получим

-x3 1n-fxl/at2;2 для прямого порядка; (8)

3 3;l--lnxa3;2t/ - Для обратного порядка. (9)

Алгебраические выражения наподобие (8) и (9) имеют очень большое значение и называются польской системой обозначений, так как в виде (8) она впервые была

использована польским логиком Яном Лукасевичем (Jan Lukasiewicz). Выражение (8) является префиксным обозначением {prefix notation) формулы (7), а выражение (9) - ее постфиксным.бозначением {postfix notation). В следующих главах эта система обозначений будет рассмотрена подробнее, а здесь лишь отметим, что польская систе.ма обозначений непосредственно связана с основными способами обхода деревьев.

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

(10)

Здесь поля RLINK и LLINK имеют обычное значение, а значение поля RTAG является отрицательным для связей-нитей (что соответствует RTAG = 1 в выражениях алгоритма). Поле TYPE используется для того, чтобы можно было различать узлы разных типов. Например, TYPE = О означает, что узел представляет константу, а поле INFO содержит ее значение; TYPE = 1 означает, что узел представляет переменную, а поле INFO содержит ее пятибуквенное имя; TYPE > 2 означает, что узел представляет оператор, а поле INFO содержит символьное имя этого оператора, т. е. значения TYPE = 2, 3, 4, ... используются для обозначения операторов +, -, X, / и т. д. Здесь нас меньше всего будет интересовать вопрос, как древовидная структура представлена в памяти компьютера, поскольку эта тема очень подробно анализируется в главе 10. Предположим лишь, что дерево уже размещено в памяти компьютера, и отложим на потом все вопросы, связанные с операциями ввода и вьшода.

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

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

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

D{u I v) = D{u)lv -{их D{v))/{v t 2) (18)

D{u t w) = D{u) X (u 5; (u t (г - 1))) + ((Ь и) x D{v)) x (u t г) (19)

Эти правила позволяют оцбнить производную D{y) для любой формулы у, состоящей из перечисленных выше операторов. Знак "-" в правиле (14) является унарным оператором, который отличается от бинарного оператора "-" в (16). Далее для обозначения унарного отрицания в узлах деревьев будет использоваться обозначение "neg".

К сожалению, правил (11)-(19) недостаточно, так как, применив их вслепую для очень простой формулы

у = 3\п{х +1) - а/х, получим правильный, но совершенно неудобный для дальнейшей работы результат:

D{y) = О • \п{х + 1) + 3((1 + 0)/{х + 1))

- (0/х2 - (а(1(2х2-) + ((1пх) • 0)х))/{хУ). (20)

Для сокращения количества лишних операций в этом результате нужно предусмотреть особые случаи сложения с нулем, умножения на нуль, умножения на единицу и возведения в степень "единица". Таким образом можно сократить выражение (20) с приведением его к виду

D{y) = 3(1/(х + 1)) - {{-{а{2х)))/{х)). (21)

Теперь оно стало более наглядным, но еще не совсем идеальны.м. На самом деле понятие удовлетворительного вида результата математических преобразований не очень хорошо определено, поскольку разные математики предпочитают разные способы представления итоговых формул. Однако ясно, что формула (21) не так проста, как могла бы быть. Чтобы представить ее в более приемлемом виде, необходимо разработать специальные программы упрощения алгебраических выражений (см. упр. 17), которые позволят привести формулу (21), например, к виду

D{y) = 3{x + 1)- +2ах-\ (22)

Здесь мы ограничимся описанием программ, с помощью которых можно получить результат в виде формулы (21), а не (22).

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

Основная идея такого алгоритма заключается в обходе дерева в обратном порядке с вычислением производной каждого посещаемого узла до тех пор, пока не будет вычислена производная всего выражения. Использование обратного порядка обхода означает, что узел оператора (например, "-Ь") посещается после того, как буд>т продифференцированы его операнды. Правила (И)-(19) подразумевают, что