AOP_Tom1 (1021736), страница 162
Текст из файла (страница 162)
3. На шаге 1)1 следует установить Б +- Л. (Б — переменная связи, которая указывает на верх стека,) Шаг Ы2 люжно изменить таким образом: "Если МООК(Р) обозначает унарный оператор, установить Ц +- Б, Б е- НЬ1МК(Ц), Р1 +- 111МК(Р). Если ИООК(Р) обозначает бинарный оператор, установить Ц +- 5, Ц! +- 511МК(Ц), 5 +- Н11МК(Ц1), Р1 + — ЬЬТМК(Р), Р2 '.— НЬ1МК(Р1). Затем выполнить 01РР[ТТРК(Р))". Шаг РЗ после изменений может выглядеть так: "Установить 511МК(Ц) е- 5, 5 +- Ц", а шаг ))4 будет таким: "Установить Р < — Рэ".
Операцию 151МК(01) е- Ц можно исключить на шаге Ы5, если предположить, что 5 = Ы.1ИК(ОТ) . Очевидно, что этот метод можно обобщить для тернарных операторов и операторов более высокого порядка. 4. Для представления наподобие (10) потребуется и — тл полей 511МК и и + (и — т) полей НЬ1ИК. Разница в общем количестве связей для этих двух типов представления равна и — 2пк Если поля 511МК н 1ИРО используют примерно одно и то же пространство внутри узла, а гл очень велико (а именно, если неконцевые узлы имеют очень высокую степень), представление (10) выглядит предпочтительнее.
5. Совершенно неразумно было бы включать прошитые связи 511ИК, так как связь 511МК в любом случае указывает только на РАНБМТ. Прошитые связи ЬЬТИК, подобные тем, которые использовались в 2.3.2 — (4), были бы полезны только при обходе дерева справа налево, например если бы потребовалось совершить обход дерева в реверсивном обратном или фамильном порядке. Но эти операции без прошитых связей 111МК не так уж сложно выполнить, если только узлы имеют не очень высокую степень. 6. Ь1. Установить Р < — РТНБТ, Р1НБТ е- Л. Ь2. Если Р = Л, прекратить выполнение алгоритма.
В противном случае установить Ц <- 511ИК(Р). 1 3. Если РАНКМТ(Р) = Л, установить 551ИК(Р) е- Р1НБТ, Р1НБТ +- Р. В противном случае установить Н +- РАНБМТ(Р), Н11МК(Р) +- 1 СН11 0(Н). ЬСН15005) +- Р. Ь4. Установить Р +- Ц и вернуться к шагу Ь2, А 7. (1,5)(2,3,4,7)(б,8,9). 8. Следует выполнить шаг ЕЗ нз алгоритма Е, а затем проверить справедливость выражения 2 = Ь. 9. РАВЕМТ(й]: 5 0 2 2 0 8 2 2 8 й: 1 2 3 4 5 6 7 8 9 10.
Один из способов заключается в занесении в поле РАВЕМТ каждого корневого узла числа узлов его дерева со знаком "минус" (эти значения можно легко обновлять). Зателз, если !РАВЕМТ(]] ~ ) !РАВЕМТ(й] ! на шаге Е4, происходит взаимный обмен ролями значений 7' и й. Как показал М.
Д. Мак-Илрай (М. )). Мс!!гоу), этот метод позволяет сократить количество шагов до О(!оВ н). Для достижения еще более высокой скорости можно использовать следующее предположение Алана Триттера (А!ав Тг!ссег); на шаге Е4 установить РАВЕМТ(х] +- й для всех значений х зг й, которые встретились на шаге ЕЗ. Это вынуждает выполнить еще один проход вверх по дереву, но приводит также к сокращению нх длины, а потому последующий поиск выполняется гораздо быстрее (см, раздел 7.4.1).
11. Достаточно определить преобразование, которое выполняется для каждого входного потока (Р,],0:й). Т1. Если РАВЕМТ(Р) З( Л, установить у з — 7 + ПЕЬТА(Р), Р +- РАВЕМТ(Р) и повторить этот шаг Т2. Если РАВЕМТ(0) ф Л, установить А з — й + ПЕ1.ТА(О), О з — РАВЕМТ(О) и повторить этот шаг ТЗ.
Если Р = О, проверить справедливость условия 1 = й (если оно не выполняется, значит, входной поток содержит противоречивые соотношения эквивалентности). Если Р ф О, установить ПЕЕТА(О) +- у' — й, РАВЕМТ(О) +- Р, 180(Р) +- ш!п(1ВП(Р), ЬВП(Ц) + ПЕ1 ТА(Ц)) и ПВП(Р) +- шах(ПВП(Р), ПВП(О) + ПЕ(ТА(О) ). Замечание. Для должным образом сформулированных условий можно допустить, чтобы объявления "АВВАТ ХП:и]" поступали вперемешку с отношениями эквивалентности, либо допустить присвоение некоторых адресов переменным до того, как будет установлена их эквивалентность другим переменным, и т. д. Иные способы развития этого алгоритма можно найти в САСМ 7 (1964), 301-303, 506.
12. (а) Да. (Если это условие не является обязательным, то можно избежать циклического повторения операций с Б на шагах А2 и А9.) (Ь) Да. 13. Ключевым фактом является то, что направленная вверх от Р цепь связей ПР всегда охватывает те же переменные и степени этих переменных, что и направленная вверх от О цепь связей ПР, но в последней цепочке могут присутствовать дополнительные шаги для перелзенных со степенью "нуль". (Это условие выполняется на протяжении всего алгоритма за исключением шагов А9 и А10.) Теперь переход к шагу АВ возможен либо после шага АЗ, либо паоле шага А10, и в каждом таком случае выполняется проверка истинности условия ЕХР(О) ф О.
Следовательно, ЕХР(Р) ф О. В частности, отсюда следует, что Р ~ Л, О Р. Л, ОР(Р) ~ Л, ПР(О) ~ Л, а значит, следует и справедливость сформулированного в упражнении утверждения. Таким образом, чтобы получить это доказательство, нужно показать, что указанное выше условие для цепочки связей ОР при выполнении данного алгоритма не нарушается. 16. Докажите (лгетодом индукции по количеству узлов одного дерева Т), что если Р указывает на Т и если стек в исходном состоянии пуст, то после выполнения шагов Г2 — г4 он будет содержать только одна значение — 7'(корень(Т)).
Это верно для и = 1. Если и ) 1, существуют 0 ( д = ПЕОВЕЕ(корень(Т)) поддеревьев Тм...,Тю По индукции и определению стека, а также на основании того, что при обратном порядке обхода после Тм..., Тг располагается корень дерева Т, получим в результате применения этого алгоритма )(Тл),..., ((Тг), а затем и /(корень(Т)), что н требовалось доказать. Аналогично можно доказать корректность алгоритма г' для лесов. 17. С1.
Опустошить стек и установить Р указывающим на корень данного дерева (последний узел в обратном порядке). Вычислить /(КООЕ(Р) ). С2. Поместить в стек ОЕОНЕЕ!Р) копий 7(ВООЕ(Р)). СЗ. Если Р является первым узлом в обратном порядке, прекратить выполнение алга. рнтлла. В противном случае установить Р указывающим на его предшественника в обратном порядке (например, для (9) это значит просто установить Р +- Р— с). С4. Вычислить Т(НООЕ(Р) ) с помощью значения верхнего элемента стека, которое равно 7(КОЗЕ(РАВЕЕТ(Р) ) ). Удалить это значение из стека н вернуться к шагу С2.
$ Замечание. Алгоритм, аналогичный данному, может быть основан не на обратном, а на прямолл порядке, как в упр. 2. На самом деле для этого можно использовать также фамильный порядок илн порядок уровней, прячем в последнем случае вместо стека можно использовать очередь. 18. Таблицы 1КР01 н В51ЕК, а также описанный в данном разделе способ вычисления ЕТАО позволяют получить эквивалентное бинарное дерево в обычном представлении. Теперь для достижения пели нужно совершить обход этого дерева в обратном порядке, попутно подсчитывая степени.
Р1. Пусть Н, 0 и 1 — стеки, которые в исходном состоянии пусты. Тогда следует установить В ~ п + 1, 0 ~ О, )' г- О, й +- О. Р2. Если (верх)Н > 2+ 1, перейти к шагу Р5. (Если бы существовало поле СТАО, можно было бы вместо этого условия использовать условие ьТАО()) = 0.) РЗ. Если стек 1 пуст, прекратить выполнение алгоритма; в противном случае установить л ~ 1, й +- й + 1, 1КР02(й) + — 1КРОЫ, ОКОВКЕ(й) ~ О. Р4. Если Ы.1НКЫ = О, перейти к шагу РЗ; в противном случае удалить верхний элемент стека Н (который равен Вь1КК(!) ). Р5.
Установить верх(0) +- верх(0) + 1, 7' г — 7 + 1, 1 ~ )', 0 ~ О. Если Н11ККЦ ф О, установить В ~ Ы.1КК(Я и перейти к шагу Р2. А 19. (а) Это эквивалентно утверждению, что связи ЗООРЕ не пересекаются. (Ь) Первое дерево леса содержит А + 1 элементов. Доказательство можно продолжить методом индукции, (с) Условие (а) выполняется для минимальных значений. Замечания. Из упр, 2.3.2 — 20 следует, что г1~4г... 4„также может интерпретироваться на основании инверсии: если й-й узел в обратном порядке является рл-м узлолл в прямолл порядке, то бл — зто количество элеллентов > й, которые располагаются слева от й в рлрг...р„. Аналогичная схема, в которой перечисляется количество наследшлков каждого узла в обратном порядке для данного леса, приводит к последовательности чисел с~сг...сл, которые характеризуются свойствамн (!) О < сл < й и (В) й > ) > й — сл, из чего следует ) — с„> й — сл.
Алгоритмы на основе таких последовательностей были исследованы Ж. М. Палло (Л, М. Ра!!о) в работе Сошр. Х 29 (1985), 171 — 175. Обратите внимание, что сл является размером левого поддерева й-го узла в снмметричном порядке обхода соответствующего бинарного дерева. бл также можно интерпретировать как размер праеогс поддерева й-го узла в силлметрнчном порядке обхода соответствующего бинарного дерева, а именно— бинарного дерева, которое соответствует данному лесу согласно методу из упр. 2.3.2-5. Отношение 4л < бл для 1 < й < и определяет интересное решеточное упорядочение лесов и бинарных деревьев, которое впервые было предложено Д. Тамари (Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
