AOP_Tom1 (1021736), страница 102
Текст из файла (страница 102)
[15] Какие классы содержались бы в (12), если бы в (11) отсутствовало отношение 9 ей3э 6. [15] Алгоритм Е задает древовидную структуру, которая представляет заданные пары эквивалентных элементов, но в этом разделе явно не указывается, как можно использовать результат выполнения алгоритма Е Создайте алгоритм, который может установи гь справедливость выражения "1 = А" при условии, что 1 < 1 < и, 1 < )г < и и алгоритм Е задает таблицу РАНЕИТ для некоторого набора пар эквивалентных элементов 9. [20] Предложите таблицу наподобие (15) и схему вида (16), которые изображали оы деревья, полученные после обработки алгоритмам Е всех пар эквивалентных элементов в (11) в направлении слева направо 10. [28] Для обработки и пар эквивалентных элементов с помощью алгоритма Е в худшем случае потребуется выполнить около и шагов Покажите, как можно было бы модифипиг ровать этот алгоритм, чтобы повысить эффективность его работы в данном случае ь 11.
[84] (Обвлвленил эквиваленшнвсти ) В некоторых компилируемых языках программирования, особенно в языке ГОНТНАИ, предусмотрена возможность перекрытия ячеек памяти, которые выделены для таблиц, последовательно размещенных в памяти Программист предлагает компилятору набор отношений вида "Х(1] ш Т(А]", который означает, что для переменной Х(1+ э] выделяется та же ячейка памяти, что и для переменной Т(А + э] при всех э Кроме того, для каждой переменной определен диапазон допустимых индексов Например, 'АККАТ ХП и]" означает, что нужно выделить некоторую область памяти для элементов таблицы Х [Ц, Х [1 + Ц, ..., Х [и].
Для каждого класса эквивалентности переменных компилятор резервирует минимально возможный блок последовательно расположенных ячеек дамяти, чтобы в нем можно было хранить все элементы таблицы для допустимых значений индексов. Например, предположим, чта имеются таблицы АВВАТ Х [О. 10], АВВАТ Т [3: 10], АВВАТ А[1:П и АВВАТ Е[ — 2:О], а также пары эквивалентных элементов Х[7] = Т[3], Е[0] = А[0] и Т[1] г— и А[8]. Для этих переменных необходимо выделить 20 последовательных ячеек памяти: Хо Хл Хл Хб Хб Хб Хб Хт Хб Хо Хло ° Ф ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° Е-о Е-л Ео Ал Тб Т4 Тб Тб Тг Тб То Тле (Адрес расположенной за элементом АШ ячейки памяти не соответствует нн одному диапазону допустимых значений индексов для любого массива, но эту ячейку все равно придется зарезервировать.) Назначение этого упражнения заключается в модификации алгоритма Е таким образом, чтобы его можно было применять в более общем юлучае, который только что был описан.
Допустим, необходимо создать компилятор такого языка, а таблицы внутри самого компилятора имеют по одному узлу в каждом массиве с полями МАМЕ, РАВЕМТ, ПЕЬТА, ЬВП и ПВП. Допустим также. что компилятор предварительно обработал все объявления АВВАТ таким образом, что при наличии объявления бАВВАТ Х [(;и]" и Р, указывающего на узел Х, МАМЕ(Р) = "Х", РАВЕИТ(Р) = Л, ПЕ1.ТА(Р) = О, 1.ВП(Р) = 1, ОВП(Р) = и.
Задача заключается в создании алгоритма, который обрабатывал бы объявления эквивалентности так, чтобы после выполнения алгоритма получалось следующее: РАВЕИТ(Р) = Л означает, что ячейки памяти Х[(ВП(Р)],..., Х[ПВП(Р)] должны быть зарезервированы в памяти для этого класса эквивалентности; РАВЕИТ(Р) = 0 ф Л означает, «то ячейка памяти Х[А] эквивалентна ячейке Т[й 4- ПН.ТА(Р)], где МАМЕ(0) = 'Т". Например, до обработки перечисленных выше пар эквивалентных элементов узлы могли выглядеть так, Р ИАИЕ(Р) РАВЕМТ(Р) ПЕ1.ТА(Р) ЕВП(Р) ОВП(Р) а Х Л 0 0 10 Т Л 0 3 10 '7 А Л 0 1 1 б Е Л 0 -2 0 А после обработки они могут иметь следующий вид.
4 Π— 3 (Здесь "б'" обозначает данные, которые не имеют никакого отношения к рассматриваемой задаче.) Создайте алгоритм, который выполняет зто преобразование. Предположите, чта данные из входного потока поступают в виде (Р, 7, ц, й), а это означает, что '"х []] ьз т [к] ", где МАМЕ(Р) = "Х" и МАМЕ(0) = "Т". Непременно убедитесь в талл, что эти пары эквивалентных отношений не противоречат одна другой. Например, Х[Ц = 7[2] будет противоречить Х [2] = 7 П ] . 1 ХИРО1[(] И.1ИК [1] 1 2 3 4 5 б 7 8 А В С К Р Е Н Г 5 3 0 0 О 8 0 10 9 10 .7 С 0 О к следующему виду: 1МР02[1] В К С А Н Е У Г С Р ОЕОМЕЕ[]] О О ! 2 О 1 О 1 0 3 19. [МЕ7) Вместо использования связей ЕСОРЕ в (5) можно было бы просто указать коли- чество наследников для каждого узла в прямом порядке: ОЕЕС 3 0 1 0 5 1 0 1 О О 1МРО А В С К Р Е Н Г У С Пусть 010з ..0„— последовательность чисел> указывающих количество наследников для узлов одного леса, полученная таким образом.
а) Покажите, что 9+ 0» < п для 1 < 1 < и и что из к < 0 < И+ с]» следует 2 801 < )с+А. Ъ) И наоборот, докажите, что если 40з...0 является последовательностью неотрицательных целых чисел, которые удовлетворяют условиям (а), то она является пос чзовательностью количеств узлов-наследников для данного леса. 12. [81[ В начале алгоритма А з1еременаые Р и О указывают на корни двух деревьев. Пусть Ро и Оа — значения переменных Р и Ц до выполнения алгоритма А. (а) Всегда ли по завершении выполнения этого алгоритма Оа будет содержать адрес корня дерева, представляюгдего результат суммирования двух заданнгях полиномов? (Ъ) Будут ли переменным Р и Ц возвращены их исходные значения Ро и Це по окончании выполнения этого алгоритма? ° 13. [МЕР[ Предложите неформальное доказательство того, что в алгоритме А в начале шага А8 всегда справедливы равенства ЕХР(Р) = ЕХР(0) и СЧ(ОР(Р)) = СМ(ОР(Ч)). (Это очень важно для понимания принципа работы алгоритма.) 14.
[40[ Предложите формальное доказательство (нли опровержение) справедливости алгоритма А. 15. [40] Создайте алгоритм для вычисления произведения двух полиномов, показанных на рис. 28. 16. [М84[ Докажите корректность алгоритма Г. ь 17. [25[ Алгоритл1 Р позволяет вычислить локально определенную функцию по направлению "снизу вверх", которая сначала вычисляется для детей некоторого узла, а затем— и для самого узла, тогда как локально определенной функцией Лля узла х по направлению "сверху вниз' 7' называется функция, которая зависит только от узла х и значения функции ] для родителя узла х.
С помощью вспомогательного стека создайте алгоритм, аналогичный алгоритму Р, который оценивает локально определенную функцию по направлению "сверху вниз" 1 для каждого узла этого дерева. (Подобно алгоритму Р данный алгоритм должен эффективно обрабатывать деревья, которые хранятся в обратном порядке со степенями узлов, как в (9).) ь 18.
[ЕМ[ Создайте алгоритм, который на основе двух таблиц 1ИР01[э] и ЕЪХИК[1] для 1 < 7' < и, соответствующих последовательному представлению в прямом порядке обхода, позволяет создать таблицы 1ИР02 [1] н ОЕОЕЕЕ[1] для 1 < 1 < и, соответствующие последовательному представлению в обратном порядке обхода с указанием степеней.
Например, согласно (3) и (9) этот алгоритм должен привести таблицы с) Предположим, что Ас~з .. И„и г!14... Н'„— последовательности количеств узлов- наследников для двух лесов. Докажите, что существует третий лес с такой последовательностью количеств узлов-наследников: ш1п(!,, !',) щ1п(д„Н',)... ш п(Н„, А„).
2.3.4. Основные математические свойства деревьев Древовидные структуры еще задолго до изобретения компьютеров были объектом обширных математических исследований, а потому в течение многих лет было накоплено большое количество интересных фактов об их свойствах. В настоящем разделе предложен краткий обзор математической теории деревьев, который позволяет не только глубже понять их природу, ио и применить эти результаты на практике в компьютерных алгоритмах. Читателям, которым не интересна чисто математическая сторона обсуждаемых вопросов, рекомендуется сразу же перейти к подразделу 2.3.4.5, в котором с практической точки зрения рассматривается несколько вопросов, наиболее часто возникающих при использовании описываемых ниже приложений. Приведенный ниже материал, в основном, относится к большому разделу математики, а именно — к теории графов.
К сожалению, в этой области не существует устоявшейся терминологии, и автор придерживается обычной практики при написании современных книг по теории графов. Иначе говоря, здесь используются термины, аналогичные, но не идентичные тем терминам, которые применяются в других книгах по теории графов. В следующих подразделах (и далее во всей книге) будет предпринята попытка выбрать короткие, но емкие термины для наиболее важных понятий.
Они будут выбраны среди общеупотребительных слов так, чтобы в то же время они не противоречили общепринятой терминологии. Следует учесть, что здесь эта терминология имеет непосредственное отношение к компьютерным приложениям. Поэтому инженер-электрик может назвать деревом то, что здесь называется свободным деревом, так как более краткий термин "дерево" обозначает более широкое понятие, которое часто используется в компьютерной литературе, а потому оно гораздо важнее в компьютерных приложениях.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
