AOP_Tom2 (1021737), страница 146

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 146)

(Теперь всего имеется 6| — Ьа+ . +6| — 6| 1 = и — 1 чисел.) с) Рассортировать числа нз (а) и (Ь) в порядке возрастания. Можно легко проверить, что это дает (е-цепочку: числа из (Ь) равны некоторым удвоенным элементам из (а) илн (Ь); кроме того, данный элемент представляет собой предшествующий подчеркнутый элемент. Если а, = 6 + аы где 6э — наибольший подчеркнутый элемент, меньший, чем аь то аь = а, — Ь < Ь+1 — Ьм поэтому 2"'(28 — 1) = 2ь' — 2"" в цепочке подчеркнут и предшествует 2" — 1.

Поскольку 2" — 1 равно (2"' — 2'") + (2"' — 1), где оба эти значения содержатся в цепочке, имеем аддитивную цепочку со свойством 1а. $ Цепочка, соответствующая (51) и построенная в доказательстве теоремы О., такова: 1,2,3,6,12,15,30,31,60,120,240,ай,510,1020,1023.,2040, 4080,4095,В160,163320.32640,692800,130560,261120,262143. Графическое представление. Аддитивная цепочка (1) естественным образом соответствует ориентированному графу, вершины которого помечены как а, для 0 < 1 < г и в котором мы рисуем дуги от аэ к а, и от аь к а, в качестве представления каждого шага а, = а + аь из (2). Например, аддитивная цепочка 1, 2, 3, 6, 12, 15, 27, 39, 78, 79, которая может быть получена из рис.

15, соответствует ориентированному графу Если а, = а, ч- аь ддя более чем одной пары индексов (~, 6), выбираем определенные у и х ддя нашего построения. В целом, все вершины такого ориентированного графа, кроме первой, будут началом ровно двух дуг. Однако в действительности это не важное свойство графа, потому что оно маскирует тот факт, что различные аддитивные цепочки, по сути, являются эквивалентными.

Если вершина имеет выходную степень 1, то она используется только в олпом последующем шаге. и поэтому подобный шаг представляет собой сумму а +аь+а, которая может быть вычислена либо как (а +аь)+а,„, либо как аэ+(аь+а ), либо как аь+(и -ьа„,). Какой именно вариант выбран, не важно, но соглашения об аддитивных цепочках заставляют нас их различать. Можно избежать такой избыточности, удалив все вершины, выходная степень которых равна 1 и которые соединены дугами со своими предшественницей и преемницей.

Например, приведенный выше граф должен принять вид (52) Также можно удалить любую вершину, выходная степень которой равна О, за исключением, естественно, конечной вершины а,, поскольку она соответствует неиспользуемому шагу в аддитивной цепочке. Таким образом, каждая аддитивная цепочка дает приводимый ориентированный граф, который содержит одну вершину-источник, помеченную как 1, и одну вершину-сток, помеченную как п. Каждая вершина, кроме источника, имеет входную степень > 2, и каждая вершина, кроме стока, имеет выходную степень > 2. И наоборот, любой такой ориентированный граф без ориентированных циклов соответствует минимум одной аддитивной цепочке, поскольку можно топологическн рассортировать вершины и записать Н вЂ” 1 дополнительных шагов для каждой вершины входной степени И > О.

Длина аддитивной цепочки без учета неиспользуемых шагов может быль определена в процессе просмотра приведенного графа. Она равна (53) (число дуг) — (число вершин) + 1, поскольку удаление вершины выходной степени 1 удаляет также одну дугу. Две аддитивные цепочки экаивилентны, если они имеют один и тот же приведенный граф. Например, .адаптивная цепочка 1, 2, 3, 6, 12, 15, 24, 39, 40, 79 эквивалентна цепочке, о которой шла речь в начале этого раздела, поскольку она также сводится к графу (52). Этот пример показывает, что незвездная цепочка может быть эквивалентна звездной цепочке.

Ллдитивная цепочка эквивалентна звездной попочке тогда и только тогда, когда ее приведенный ориентированный граф может быть топологически рассортирован лишь одним-единственным образом. Важное свойство такого графического представления аддитивных цепочек указано Н. Пиппенгером (Х. Р)ррепйег): метка каждой вершины в точности равна количеству ориентированных путей от источника к данной вершине. Таким образом, задача поиска оптима.льной алдитивной цепочки для и эквивалентна задаче минимизации величины (53) по всем ориентированным графам, имеющим одну вершину- источник и одну вершину-сток и в точности и ориентированных путей от источника к стоку.

Такая характеристика имеет удивительное следствие в связи с симметричностью ориентированного графа. Если обратить направления всех дуг, источник и сток поменяются местами и получится другой ориентированный граф, соответствующий множеству адднтивных цепочек для того же значения и. Эти аддитивные цепочки имеют такую же длину (53), как и первоначальная цепочка. Например, если развернуть все стрелки в (52) спрана налево и пометить вершины в соответствии с числом путей от правой соседней вершины, получится 79 25 12 6 2 1 (54) Одной из звездных цепочек, соответствуюшнх этому приведенному ориентированному графу, является 1.

2, 4, 6, 12, 24, 26, 52, 78, 79; ее можно назвать дральной по отношению к исходной алдитивной цепочке. В упр. 39 н 40 обсуждаются важные последствия такого графического представления и принципа дуальности. УПРАЖНЕНИЯ 1. [151 Чему равно значение Я при завершении работы алгоритма Ат 2. [Я4) Напишите М1Х-программу для алгоритма А, вычисчяющую х" шог1ю для дшь ных целых и и х, где го — размер машинного слова. Считается. что Н1Х имеет бинарные операшш знй, ЗАК и др., описанные в разделе 4.5 2.

Напишите еще одну програллллу, вычисляющую х'* люби: последовательно (посредством многократного умножения на х), и сравните время работы этих программ 3. [ЯЯ) Как вычисляется х~~' при помощи (а) бинарного метода, (Ь) тернарного метода, (с) кватернарного (четверичного) метода и (г1) метода множителя? 4. [МЯО] Найдите число и, для которого восьмеричный (2з-арный) метод дает иа десять умножений меньше, чем бинарный метод. 5. [Я41 На рис. 14 показаны первые восемь уровней дерева степеней. В предположении, чзо ?г-й уровень дерева построен. его (Я+ 1)-й уровень определяется следующим образом: берем каждый узел и на Й-м уровне слева ншграво н присоединяем к нему снизу узлы п+ 1, п+ ам п -л ал, ., и+ ал ~ —— 2гл (именно в таком порядке), где 1, ал, ам, ал ~ представляет собой путь от корня дерева ло узла п.

Нри этом, однако, устраняются все узлы, которые уже пояаяялись в дереве. Разработайте эффективный алгоритм, который строит первые г + 1 уровней дерева степеней [Указание. используйте два массива перелленных, 11нкп[1) и 11ккк[1), для О <1 < 2', ати переменные указывают соответственно вверх и вправо для числа 1 в дереве.) б. [МЯб) Есзи внести незначительные нзлленеиия в определение дерева степеней, данное в упр. 5, чтобы узлы, расположенные ниже и, присос,шнялись в порядке убь~ваная глрил м, и+ам из-а,, и+1, а не возРастания, получится дерево, первые пять уровней которого выглядят как [ 4 3 Покажите, что это дерево дает метод вычисления з", который требует столько же умножений, сколько при двоичном методе.

Поэтому модифицированное дерево, несмотря на то что оно строится почти так же, как и дерево степеней, дает более плохой метод вычисления степеней. 7. [М21] Докажите, что имеется бесконечно много значений п, для которых а) метод множителя лучше бинарного метода; Ь) бина1»ный метод лучше метода множителя; с) метод дерева степеней лучше как бинарного метода, так и метода множителей. (В данном случае понятие "лучше'' "означает вычисление х" с использованием меньшего количества умножений.) 8. [М21] Докажите, что дерево степеней (упр. 5) никогда не дает для вычисления х" большего количества умножений, чем бинарный метод.

° 9. [25] Разработайте процедуру возведения в степень, аналогичную алгоритму А, но базирующуюся на гл = 2'. Ваш метод должен выполнять примерно 18 и+и+го умножений, где и — количество ненулевых цифр в т-арном представлении числа и. 10. [10] На рис. 15 показано дерево, которое указывает для каждого п < 100 единственный путь вычисления х" с минимально возможным количеством умножений. Каким образом это дерево можно расположить в памяти компьютера, используя только 100 ячеек памяти? з' 11.

[М2б] Дерево на рис. 1о изображает алдит~вные цепочки ас, .ам ..., а„, у которых 1(а;) = 1 для всех» в цепочке. Найдите все алднтивные цепочки для п = 43 и п = 77, имеющих это свойство. Покажите, что дюбое дерево, подобное изображенному на рис. 15, должно включать в себя либо путь 1, 2, 4, 8, 9, 17, 34, 43, 77, либо путь 1, З, 4, 8, 9, 17, 34, 68, 77. 12. [М10) Нельзя ли расширить показанное на рнс. 15 дерево до бесконечного дерева, которое давало бы правило вычисления х" с нанмевыпим количеством умножений для всех положительных целых чисел и? 13. [М21) Найдите звездную цепочку длиной А + 2 для каждого из четырех случаев, перечисленных в теореме С (следовательпо, теорема С остается справедливой и при замене 1 на Г.) 14.

[М29] Завершите доказательство теоремы С, показав, что (а) шаг г — > це является малым шагом; (Ь) Л(а, ») не может быть меньше, чем гл — 1. 15. [М43] Напишите компьютерную программу для расширения теоремы С, определяющую все л.. .такие, что 1(п) = Л(п) + 3, н все п, для которых Г(п) = Л(п) + 3. 16. [НМ15] Покажите, что теорему П трудно получить, используя бинарный метод; если (и) обозначает длину аддитианой цепочки для п, построенной бвнарпым 8Х-методоьг, в отношение 1 (и)(Л(п) не стремится к определенному пределу при п -Ф оо, 17.

[М25] Объясните, как найти интервалы Ум ..., зю требующиеся в доказательстве леммы Р. 18. [г»М24] Пусть 2 — положительная константа. Покажите, что существует константа а < 2, такая, что (т+ в) (1+ с) з ((та+ з) ) для всех больших т, где сумма берется по всем з, 1, с. удовлетворяющим (30). 19. [МЯЗ]»Мультимножество» подобно множеству, но оно может содержать один и тот же элемент конечное число рвз. Если А и  — мультимиожества, то мультимножества А !у В, А О В и А О В определяются следующим образом: элемент, встречающийся а раз в А и Ь раз в В, встречается в АЕ В а+ Ь рвз, в ЛО — шах(а, Ь) и в А Π — ппп(а, Ь) раз.

(»Ьйножество» является мультимпожеством, в котором нет элементов, встречающихся более одного раза: если А и  — множества, то множествами являются и А О В, и А П В и данные здесь определения в этом случае согласуются с определениями обьединения и пересечения множеств.) а) Разложение натурального числа и на простые множители представляет собой мультимпожество?у, элементами которого являются простые числа, причем П я = п. Тот факт, что каждое натуральное число может быть единственным образом разложено на простые множители, дает взаимно однозначное соответствие между множеством натуральных чигел и конечными мультимножествами простых чисел, например если п = 2 - 3 17, соответствующим мультимножеством является?»' = (2,2,3,3,3, 17).

Характеристики

Список файлов книги