17. Ссылки на более ранние работы по этой теме можно найти в обзоре J. Sammet, САСМ 9 (1966), 555-569.

18. Сначала следует таким образом установить LLINK [j] RLINK[j] j для всех j, чтобы каждый узел находился в циклическом списке длиной 1. Тогда для j = п, п - 1, ..., 1 (в таком порядке), если PARENT [j] = О, установить г j, в противном случае вставить циклический список, начиная с j, в циклический список, начиная с PARENT [j] , в следующем порядке: к PARENT[j], I <- RLIM[fc], i 4- LLIM[j], LLIMCj] 4- к, RLIM[fc] 4- j, LLIM ill 4- i, RLINK [г] 4- I. Этот алгоритм корректен, так как (а) каждый некорневой узел всегда располагается перед своим родителем или последователем своего родителя; (Ь) узлы каждого семейства располагаются в списке родителя в порядке их следования; (с) прямой порядок является единственным порядком, который удовлетворяет условиям (а) и (Ь).

20. Если и является предком узла v, то по индукции автоматически следует, что узел и предшествует узлу v в прямом порядке обхода и следует за узлом v в обратном порядке. И наоборот, если узел и предшествует узлу v в прямом порядке и следует за узлом v в обратном порядке, то докажем, что узел и является предком узла v. Это утверждение очевидно, если узел и является корнем первого дерева. Если и не является корнем первого дерева, то и узел v не будет корневым, так как и следует за узлом v в обратном порядке; далее доказательство выполняется по индукции. Аналогично, если и не принадлежит первому дереву, то и узел v не принадлежит ему, так как узел и предшествует узлу v в прямом порядке. (Результат этого упражнения также следует из результата упр. 3. Значит, можно получить быстрый способ проверки прародства, зная расположение каждого узла в прямом и обратном порядках обхода.)

21. Если узел NODE(P) является бинарным оператором, то указателями двух его операндов будут Р1 = LLINK (Р) и Р2 = RLINK (Р1) = $Р. В алгоритме D используется тот факт, что Р2$ = Р, так что RLIM(Pl) можно заменить указателем Q1, т. е. указателем на производную узла NODE(Pl), а затем вновь переустановить RLIM(Pl) на шаге D3. При обработке тернарных операций получим, что Р1 = LLIM(P), Р2 = RLINK(Pl), РЗ = RLINK(P2) = $Р, а потому обобщить обработку бинарных операций довольно трудно. После вычисления производной Q1 можно временно установить RLINK (Р1) 4- Q1, а затем после вычисления следующей производной Q2 установить RLINK(Q2) 4- Q1 и RLIM(P2) 4- Q2 и переустановить RLINK(Pl) 4- Р2. Но такое решение вряд ли можно считать элегантным, а с возрастанием степени операторов оно становится все более неуклюжим. Следовательно, способ на основе временного изменения RLINK(Pl) в алгоритме D может рассматриваться всего лишь как уловка, но никак не как общий метод решения подобных задач. Более эстетичный способ управления процессом дифференцирования основан на алгоритме 2.3.3F (см. упр. 2.3.3-3), потому что он сформулирован в более общем виде так, что его можно применять для операторов с более высокими степенями и не прибегать к каким-либо трюкам.

22. Из данного определения сразу же следует, что такое отношение является транзитивным, т. е. если Г С Г и Г С Г", то Г С Г". (На самом деле легко видеть, что это отношение является частичным упорядочением.) Если допустить, что / может отобразить каждый узел на себя, то ясно, что 1{Т) СТ и г{Т) С Т. Следовательно, если Т С 1{Т) илп Т С г(Г), то обязательно Г С Г.

Предположим, что /; и /г являются функциями, для которых выполняются отношения 1{Т) с 1{Т) и г{Т) С г(Т) соответственно. Пусть f{u) = fi{u), если и принадлежит 1{Т), f{u) = корень дерева Т, если и является корнем дерева Т, а в противном случае f{u) - fr{u). Тогда для такой функции / выполняется отношение Т СТ. Например, пусть г{Т) обозначает г(Т)\корень дерева Т. Тогда получим следующее: прямой порядок дерева Т = корень дерева Т прямой порядок дерева {1(Т)) прямой порядок дерева (г(Г));

а прямой порядок дерева Т = /(корень дерева Т) прямой порядок дерева {1{Т)) прямой порядок дерева (г(Т)).

Обратное утверждение не верно: рассмотрите поддеревья с корнями 6 и 6 на рис. 25.

РАЗДЕЛ 2.3.3

1. Да, их можно восстановить точно так, как (3) можно вывести из (4), но заменяя LTAG и RTAG, а также LLINK и RLINK и используя очередь вместо стека.

2. В алгоритм F внесем следующие изменения. На шаге F1 фразу "Р пусть указывает на первый узел леса в обратном порядке" заменим фразой "Р пусть указывает на последний узел леса в прямом порядке". На шаге F2 в двух местах заменим фрагмент "/(xd),..., f(xi)" фрагментом "/(xi),..., f{xd)"- На шаге F4 выполним такие действия: "Если Р указывает на первый узел в прямом порядке, то прекратить выполнение алгоритма. (Тогда стек в направлении сверху вниз будет содержать элементы /(корень(Т1)), /(корень(Тт)), где Ti,...,Tm-деревья данного леса по направлению слева направо.) В противном случае установить Р указывающим на его предшественника в прямом порядке (Р <- Р - с для данного представления) и вернуться к шагу F2".

3. На шаге D1 следует установить S «- Л. (S - переменная связи, которая указывает на верх стека.) Шаг D2 можно изменить таким образом: "Если NODE(P) обозначает унарный оператор, установить Q S, S RLIM(Q), Pl +- LLINK(Р). Если NODE(P) обозначает бинарный оператор, установить Q +- S, Q1 4- RLIM(Q), S 4- RLINK(Ql), Pl 4- LLINK(P), P2 •(- RLINK(Pl). Затем выполнить DIFF [TYPE (P)]". Шаг D3 после изменений может выглядеть так: "Установить RLIM(Q) +- S, S <- Q", а шаг D4 будет таким: "Установить Р <- Ps". Операцию LLIM(DY) <- Q можно исключить на шаге D5, если предположить, что S = LLIM(DY). Очевидно, что этот метод можно обобщить для тернарных операторов и операторов более высокого порядка.

4. Для представления наподобие (10) потребуется п - т полей LLINK и п + (п - т) полей RLINK. Разница в общем количестве связей для этих двух типов представления равна п - 2т. Если поля LLIM и INFO используют примерно одно и то же пространство внутри узла, а т очень велико (а именно, если неконцевые узлы имеют очень высокую степень), представление (10) выглядит предпочтительнее.

5. Совершенно неразумно было бы включать прошитые связи RLINK, так как связь RLIM в любом случае указывает только на PARENT. Прошитые связи LLIM, подобные тем, которые использовались в 2.3.2-(4), были бы полезны только при обходе дерева справа налево, например если бы потребовалось совершить обход дерева в реверсивном обратном или фамильном порядке. Но эти операции без прошитых связей LLINK не так уж сложно выполнить, если только узлы имеют не очень высокую степень.

6. L1. Установить Р •(- FIRST, FIRST 4- Л.

L2. Если Р = Л, прекратить выполнение алгоритма. В противном случае установить Q 4- RLINK (Р).

L3. Если PARENT(P) = Л, установить RLINK(P) 4- FIRST, FIRST 4- P. В противном случае установить R 4- PARENT(Р), RLINK (Р) 4- LCHILD (R), LCHILD (R) 4- P.

L4. Установить Р 4- Q и вернуться к шагу L2.

7. {1,5}{2,3,4,7}{6,8,9}.

8. Следует выполнить шаг ЕЗ из алгоритма Е, а затем проверить справедливость выражения j = к.

9. PARENTM: 502208228 к : 123456789

10. Один из способов заключается в занесении в поле PARENT каждого корневого узла числа узлов его дерева со знаком "минус" (эти значения можно легко обновлять). Затем, если I PARENT [j] I > I PARENT [А:] на шаге E4, происходит взаимный обмен ролями значений j и к. Как показал М. Д. Мак-Илрой (М. D. МсПгоу), этот метод позволяет сократить количество шагов до O(logn).

Для достижения еще более высокой скорости можно использовать следующее предположение Алана Триттера (Alan Tritter): на шаге Е4 установить PARENT[х] 4- к для всех значений х / к, которые встретились на шаге ЕЗ. Это вынуждает выполнить еще один проход вверх по дереву, но приводит также к сокращению их длины, а потому последующий поиск выполняется гораздо быстрее (см. раздел 7.4.1).

11. Достаточно определить преобразование, которое выполняется для каждого входного потока (Р, j, Q,fc).

TI. Если PARENT(Р) ф Л, установить j <- j -I-DELTA (Р), P 4- PARENT(P) и повторить этот шаг.

Т2. Если PARENT(Q) ф Л, установить к +- к + DELTA (Q), Q <- PARENT(Q) и повторить этот шаг.

ТЗ. Если Р = Q, проверить справедливость условия j - к (если оно не выполняется, значит, входной поток содержит противоречивые соотношения эквивалентности). Если Р # Q, установить DELTA(Q) <- j - к, PARENT(Q) 4- Р, LBD(P) 4- min(LBD(P), LBD(Q) -fDELTA(Q)) и UBD(P) 4-max(UBD(P), UBD(Q) -fDELTA(Q)). Замечание. Для должным образом сформулированных условий можно допустить, чтобы объявления "ARRAY Х[/:и]" поступали вперемешку с отношениями эквивалентности, либо допустить присвоение некоторых адресов переменным до того, как будет установлена их эквивалентность другим переменным, и т. д. Иные способы развития этого алгоритма можно найти в САСМ 7 (1964), ЗОЬЗОЗ, 506.

12. (а) Да. (Если это условие не является обязательным, то можно избежать циклического повторения операций с S на шагах А2 и А9.) (Ь) Да.

13. Ключевым фактом является то, что направленная вверх от Р цепь связей UP всегда охватывает те же переменные и степени этих переменных, что и направленная вверх от Q цепь связей UP, но в последней цепочке могут присутствовать дополнительные шаги для переменных со степенью "нуль". (Это условие выполняется на протяжении всего алгоритма за исключением шагов А9 и .410.) Теперь переход к шагу А8 возможен либо после шага A3, либо посте шго-а А10, и в каждом таком случае выполняется проверка истинности условия EXP(Q) / 0. Следовательно, ЕХР(Р) 7 0. В частности, отсюда следует, что Р / Л, Q 7 Л, иР(Р) ф Л, UP(Q) 7 Л, а значит, следует и справедливость сформулированного в упражнении утверждения. Таким образом, чтобы получить это доказательство, нужно показать, что указанное выше условие для цепочки связей UP при выполнении данного алгоритма не нарушается.

16. Докажите (методом индукции по количеству узлов одного дерева Т), что если Р указывает иа Т и если стек в исходном состоянии пуст, то после выполнения шагов F2-F4 он будет содержать только одно значение - /(корень(Т)). Это верно для п = 1. Если п > 1, существуют О < d = DEGREE(kopehb(T)) поддеревьев Ti,...,Td. По индукции и определению стека, а также на основании того, что при обратном порядке обхода после