AOP_Tom1 (1021736), страница 96
Текст из файла (страница 96)
Поле ТУРЕ используется для того, чтобы можно было различать узлы разных типов. Например, ТУРЕ = 0 означает, что узел представляет константу, а поле 1ИРО содержит ее значение; ТУРЕ = 1 означает, что узел представляет переменную, а поле 1ХРО содержит ее пятибуквенное имя:, ТУРЕ > 2 означает, что узел представляет оператор, а поле 1МРО содержит символьное имя этого оператора, т.
е. значения ТУРЕ = 2, 3, 4, ... используются для обозначения операторов +, — , х, ( и т. д. Здесь нас меньше всего будет интересовать вопрос, как древовидная структура представлена в памяти компьютера, поскольку эта тема очень подробно анализируется в главе 10. Предположилл лишь, что дерево уже размещено в памяти компьютера, и отложим на потом все вопросы, связанные с операциями ввода и вывода. Рассмотрим классический пример выполнения алгебраических преобразований, а именно — поиск производной некоторого выражения как функции от х. Программы алгебраического дифференцирования, которые появились еще в 1952 году, были в числе первых программ для символьных вычислений. На примере процесса дифференцирования можно проиллюстрировать лпюгие методы алгебраических преобразований.
к тому же он имеет большое практическое значение для выполнения теоретических расчетов в различных областях науки и техники. Читатели, которые не знакомы с основами вычислительной математики, могут рассматривать эту задачу как абстрактное упражнение в области алгебраических преобразований, которые определяются следующими правилами. Р(и / и) = Р(и)/е — (и х Р(и))/(и 7 2) В(и 7 г) = В(и) х (и х (и 7 (и — 1))) + ((!пи) х Р(и)) х (и 7 и) (18) (19) Эти правила позволяют оценить производную Р(у) для любой формулы у, состоящей из перечисленных выше операторов. Знак "-" в правиле (14) является унарным оператором, который отличается от бинарного оператора "-" в (16).
Далее для обозначения унарного отрицания в узлах деревьев будет использоваться обозначение "пе8". К сожалению, правил (11) †(19) недостаточно, так как, применив их вслепую для очень простой формулы у = 3 !п(х + 1) — а/х~, получим правильный, но совершенно неудобный для дальнейшей работы результат: Р(у) = 0 !п(х + 1) +3((1+ 0)/(х+ 1)) — (О/хз — (а(Ц2х~ ')+ ((1пх) 0)хз))/(хз)з). (20) Для сокращения количества лишних операций в этом результате нужно предусмо- треть особые случаи сложения с нулем, умножения на нуль, умножения на единицу и возведения в степень "единица", Таким образом можно сократить выражение (20) с приведением его к виду .В(у) = 3(1/(х+ 1)) — (( — (а(2х)))/(х ) ). (21) Теперь оно стало более наглядным, но еще не совсем идеальным.
На самом деле понятие удовлетворительного вида результата математичегких преобразований не очень хорошо определено, поскольку разные математики предпочитают разные способы представления итоговых формул. Однако ясно,что формула (21) не так проста, как могла бы быть. Чтобы представить ее в более приемлемом виде, необходимо разработать специальные программы упрощения алгебраических выражений (см. упр. 17), которые позволят привести формулу (21), например, к виду Р(у) = 3(х+ 1) ' + 2ах (22) Здесь мы ограничимся описанием программ, с помощью которых можно получить результат в виде формулы (21), а не (22). При составлении такого алгоритма прежде всего нас будут интересовать подробности реализации этого процесса внутри компьютера.
Во многих языках высокого уровня и в специальных программах, которые доступны для большинства типов компьютеров, предусмотрены специальные встроенные средства, позволяющие упростить подобные алгебраические преобразования. Однако назначение этого примера заключается в приобретении опыта работы с основными операциями с деревьями.
Основная идея такого алгоритма заключается в обходе дерева в обратном порядке с вычислением производной каждого посещаемого узла до тех пор, пока не будет вычислена производная всего выражения. Использование обратного порядка обхода означает, что узел оператора (например, "+") посещается после того, как будут продифференцированы его операнды. Правила (11)-(19) подразумевают, что каждая подчиненная формула исходной формулы рано или поздно будет продифференцирована,' а потому дифференцирование можно выполнять в обратном порядке обхода дерева.
При работе с правопрошитым деревом уже необязательно применять стек во время выполнения этого алгоритма. С другой стороны, недостаток подобного представления дерева заключается в том, что необходимо делать копии поддеревьев. Например, в правиле для Р(и Т в) потребуется трижды копировать и и и, тогда как вместо дерева можно было бы использовать представление в виде Списка из раздела 2.3.5 и избежать такого копирования.
Алгоритм Х) (Дифференцирование). Если Т вЂ” адрес заголовка списка, который указывает на формулу, представленную в описанном выше виде, а ОТ вЂ” адрес заголовка списка для пустого дерева, то в результате выполнения этого алгоритма МООЕ(ОТ) будет указывать на дерево, представляющее производную от Т по Х. 1)1. [Инициализация.] Установить Р г — Тэ (а именно, первый узел дерева при обходе в обратном порядке, который является первым узлом соответствующего бинарного дерева в симметричном порядке). Р2.
[Дифференцирование.] Установить Р1+- (.ПМК(Р) и, если Р1 ф А, также установить Ц1 +- Н.1МК(Р1). Затем выполнить описанную ниже программу 01РР[ТТРЕ(Р)]. (Программы 01ГР[0) 01РР[1) и т. д, вычисляют производную дерева с корнем Р и задают для указательной переменной Ц значение адреса корня этой производной. Чтобы упростить спецификацию программ 01РР, прежде всего следует установить переменные Р1 и Ц1.) ПЗ.
[Восстановление связи.! Если ТТРЕ(Р) обозначает бинарный оператор, установить К11МК(Р1) +- Р2. (Пояснение дается ниже, при описании следующего шага.) Р4. [продвижение к Рэ.] Установить Р2 г- Р, Р г — Ры теперь, если йтАО(Р2) = 0 (т. е. если МООЕ(Р2) имеет справа брата илн сестру), установить йг.1МК(Р2) +- Ц, (Именно здесь и заключена суть этого алгоритма: г.труктура дерева Т временно разрушается так, чтобы сохранить для дальнейшего использования связь с производной Р2. Недостающая связь будет восстановлена позднее, на шаге РЗ. Более подробное описание этой уловки приводится в упр. 21.) 1)5.
[Обход завершен?] Если Р ф Т, вернуться к шагу Р2. В ггротивноы случае установить ь1.1МК(ОТ) г- Ц и К11МК(Ц) +- ОТ, КТАО(Ц) +- 1. 1 Программа. описанная в алгоритме В, является общей программой операций дифференцирования, непосредствешю выполняемых программамн 01РГ[0), 01РР[Ц...., которые вызываются на шаге Р2. Во многом алгоритм Р напоминает программу управления интерпретирующей системы (или компилятор), которая рассмотрена в разделе 1.4.3, но совершает обход дерева, а не простой последовьэ тельности инструкций. Для завершения ллгорнтма Р необходимо определить програггыы, которые непосредственно выполняют дифференцирование. Далее утверждение "Р указывает на дерево" будет озпачать,что узел МООЕ(Р) является корнем дерева, которое хранится в памяти компьютера в виде правопрошитого бинарного дерева, хотя оба указателя КЕ1МК(Р) н КТАО(Р) утрачивают смысл при работе с таким деревом.
Воспользуемся функцией консглруированил деревьев (Осе согмгпгсйои /шгсггогг). которая позволяет создавать новые деревья за счет объединения деревьев меньшего размера. Пусть х обозначает узел иекоторого типа, содержащий константу, переменную или оператор, а 0 и Ч обозначают указатели иа деревья. В таком случае ТКЕЕ(х, О, Ч) образует новое дерево с корнем х и поддеревьями О и Ч этого корня: Н».= АЧА11., 1МРО(Н) +- х, 1Л.1НК(Н) +- О, И.|НК(О) +- Ч, КТАО(О) +- О, Н.1МК(Ч) +- Н, КТАО(Ч)» — 1; ТКЕМ(х,О) аналогично образует новое дерево только с одним поддеревом: Н ~ АЧАП., 1МРО(Н) +- х,!.Е1МК(Н) »- О, КУХНЕ(О) »- Н, КТАО(О) +- 1; ТКЕЕ(х) образует новое дерево с корнем х, который является концевым узлом: Н »:= АЧА1Е, 1МРО(Н) » — х.
ШМК(Н) +- Л. Кроме того,для ТУРЕ(Н) задается зиачеиие, соответствующее типу узла х. Во всех случаях значением ТКЕЕ является Н, т. е. указатель иа только что построенное дерево. '!нтателю следует тщательно изучить эти определения, поскольку оии иллюстрируют представление дерева иа основе бинарного дерева.
Еще цдка функция. СОРТ(0), создает копию дерева, па которое указывает О, а ее значением является указатель иа только что созданное дерево. Основные фуикпии ТКЕЕ и СОРУ упрощают процесс поэтапиого создания дерева, соответствующего производной для заданной формулы. Нуль-арпые операторы (константы и переменные). Для этих операций узел МОРЕ(Р) являетгя комцевым, а значения переменных Р1, Р2, Ц1 и Ц для их выполиеиия несущественны.
Р1РР(03: (МОРЕ(Р) — константа.) Установить Ц +- ТКЕЕ(О). 01РР Ш: (МООЕ(Р) — переменная.) Если 1МРО(Р) = "Х', установить ֻ— ТКЕЕ(1): в противном случае установить Ц» — ТКЕЕ(0). Уиарпые операторы (логарифм и оп»рицание). Для этих операций МООЕ(Р) имеет одного ребенка. (!.
иа которого указывает Р1, а Ц указывает иа ])(У). Значения переменных Р2 и Ц1 для выполнения этих операций несущественны. Р1РР(2]: (МОРЕ(Р) — "!и".) Если 1ИРО(Ц) ф О, установить Ц +- ТКЕЕ("/",Ц, СОРТ(Р1)). 01РР(З]: (ИООЕ(Р) — "пей".) Если 1МРО(Ц) Зе О, установить Ц +- ТКЕЕ("пей*',Ц). Бинарные операторы (сложение, вычитание, умножение, деление, возведение в степе»»ь). Для этих операций МОРЕ(Р) имеет двух детей, (»' и 1; иа которых указывают Р1 и Р2 соответственно; Ц1 и Ц указывают иа Ю(()) и В(1с) соответственно. 01РР(43: (Операция "+".) Если 1МРО(Ц1) = О, установить АЧА1Ь»:= Ц1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
