AOP_Tom3 (1021738), страница 193
Текст из файла (страница 193)
29. Верхние 2 узлов проигравших переходят на соответствующие позиции основных узлов, Оставшиеся узлы проигравших образуют 2~ поддеревьев с 2" — 1 узлами в каждом; они подключаются к основным узлам в симметричном порядке крайнее слева додерево— к крайнему слева основному узлу и т. д. (См. К. Е(е, 14. Е!еэег, Асса 1вГогшабса 34 (1997), 429 — 447.) ЗО. Предположим, что к 1 основным узлам подключен 2"-узловой подграф полного 2" ! — 1 узлового дерева проигравших. В этом дереве имеется один узел на уровне 0 и 2 узлов на уровне 1 при 1 < 1 < п+ й. Поддерево с корнем на уровне 1 > 1 имеет 2"э" ' ' — 1 узлов.
Таким образом, все корни 1 несвязанных 2"-узловых деревьев должны находиться на уровнях < и. Каждое из этих поддеревьев должно содержать минимум один узел на уровне й, поскольку существует только 2" ' < 2" узлов иа уровнях < й. Отсюда следует, что 1 < 2" ~. Но количество ребер основного графа равно, по меньшей мере, 1 т 2(2" — 1) — 1, как следует из (и) и (ш), поскольку существует не меньше этого количества узлов проигравших, родитель которых имеет отличную картину в основном графе.
(Необходимо предполагать, что и > к. если и = й — 1, то существует соответствующий основной граф с 2" + 2" ' — 2 ребрами.] РАЗДЕЛ 5.4.2 1 б 10 13 18 20 24 20 2. После первой фазы слияния все оставшиеся фиктивные серии будут находиться на ленте Т и их будет самое большее ае — а„~ < а„~ Следовательно, все они исчезнут в течение второй фазы слияния, 3.
Имеем (ОП),0[2),...,0(Т)) = (а„— о„р, а„— а„рег,...,о„-а„), так что выполнение интересующего нас условия следует из того, что последовательность а неубывающая. Это условие важно для правильной работы алгоритма, так как на п«агах !]2 и ]]3 никогда О(у -!- П не уменьшается чаще, чем 0(1]. 4.
(1 — г — — г~)а(г) = 1 в силу (3). Далее, С(г) = 2 „>,(а„+ Ь„+ ср + «1„»- е„)г" = (г+ ° + ге)а(г) + (г+ ° . + г~)а(г) + + го(г) = (5г+ 4гг -~-Згз+2г~+ г~)а(г). 5. Пусть др(г) = (г — 1)/р(г) = грш — 2гр+ 1 и Ьр(г) = грт' — 2г". Теорема Руше (Вопсйе) (.1, Есо!е Ро1усесйтдие. 21,37 (1858), 1-34) утверждает; Ьр(г) и др(г) имеют равное число корней внутри окружности )г) = 1 + с при условии, что )Ьр(г)! > )Йр(г) — др(г)) = 1 ««а окружности.
Если ф ' > с > 0 имеем )Ьр(г)! > (1+ «)р(1 — с) ) (1+ ф ') (1 — ф ') = 1. Следовательно, др имеет р корней с абсолютной величиной < 1. Они различны, так как йсб(др(г), д'(г)) = йс«](др(г), (Р+ 1)г — 2Р) = 1. (АЛХМ 67 (1960), 745-752.) 6. Положим са = — с«р(о )/д (о «). Тогда р(г)/д(г) — се/(1 — ог) аналитична в круге )г) < Я для некоторого Я > /о/; следовательно, коэффициенты (г") р(г)/д(г) = сео" -~- О(Е ") Значит, !в 3 = и!по+!пса + О((о]1) "): а из и = (!пЯ/!по) + О(1) следует, что О((оК) ") = О(З '). Аналогично положим с« = огр(о «)/д'(о «)г, сг = — ор'(о ')/ д«(о ') г+ ор(о 'др(о-' )/д'(о-')г и рассмотрим р(г)/д(г) — с« /(1 — ог) — сг/(1 — ог).
7. Пусть ор —— 2г и г = -1/2рт Тогда гр~ = гр -«г и в результате получается ре« . рт« сходЯщийсЯ РЯд ор = 2 2 „> (' „"Р) г"/(1 — ЬР) = 2 — 2 "— Р2 ге + 0(Р 2 зе), как следУет из формулы 1.2.6 — (25) Замечание. Отсюда следует, что величина р в упр. 6 становится примерно равной !об 3 с ростом р. Аналогично для табл. 5 и 6 коэффициент с приближается к 1/((ф+ 2) !и ф) при большом чигле лент.
8. Очевидно, А«ее = 1, А«ш = 0 для «и < О. Рассматривая все варианты для первого слагаемого, получаем А«р = А«р, + -+Л'„р при т ) О. Следовательно, ]д'р~ = Г~'"~ «р«б» б» (ЬейгЬпсЬ с!ег СотЬтасоН1«(] е!рг!8: ТеиЬпег, 1901), 136-137.] 9. Рассмотрим положение крайнего глева нуля, если таковой имеется; находим, что К~Р« = Г«,"~ .
Замечание. Существует простое взаимно однозначное соответствие между такими последовательностями нулей и единиц и изображениями и«+ 1, рассмотренными в упр. 8: добавьте 0 к правому концу последовательности и посьютрите на положение всех нулей. 10. Лемма. Если и = Г р +. + Г р является таким представлением, где ««» у > р, топ < Г ",. Доказательство. Этот результат очевиден, если и«< р. В противном случае пусть (с есть минимальное число, такое, что/«) у«а«+1; имеем Й < р и по индукции Г«р«+...
+ Гб» < Г«р«, следователы«о, п < Г«р« -> + ГСр~, < Г«р« «««««««-«' ««и-«-« — ««е«' Искомое теперь может быть доказано индукцией по и Если и > О, то пусть / буде« максимальным числол«, таким, что ГШ«< и. Лемма показывает, что любое представление и должно состоять из Г~~~ нлюс представление и — Г~~~ По ин,тук«ши «« — Г~Р~ имеет « « « единственное представление нужного вида, и это представление не содержит всех чисел ëЫ ..., Г~Р«, так как 1 максимально.
— ,-ре« Замечания. Случай, когда р = 2. упомянутый в работе Е. Еес]«еп«]от(, В!топ Бсерсп 29 (1952), 190-195, был рассмотрен в упр. 1.2.8-34. Имеется простой алгоритм перехода от представления и к представлению и -~-1, работающий с последовательностью нулей и единиц с«... с«се, такой, что «« = 2 с,Г«з „.
НапРимеР, если Р = 3, мы смотРим на пРавые цифРы н 1р« заменяем...Она... 1,... 01 на . 10,... 011 на... 100; затем осуществляем "перенос" влево, если зто необходимо, заменкя .. 0111... на .. 1000.... (См. последовательности нулей и единиц в упр. 9 в том порядке, в котором они записаны.) Подобная система счисления была исследована в работе %. С Ьупсй, Г]Ьопасс] Сгпаггег!у 8 (1970), 6 — 22. Автор приводи« очень интересный способ ее применения для управления и фазой распределения, и фазой слиянин многофазной сортировки. 12. Й-я степень содержит точные распределения для уровней с Й вЂ” 4 до Й-го в последова- тельных строках с наибольшими элементами справа.
13. Доказывается индукцией по уровню. 15. Эта теорема была доказана Д. Э. Зэйаом (!у. А. Хате), статья которого упоминается в тексте раздела. 16. Д. Э. Зэйв показюц что число вводимых (и выводимых) записей равно 5!ойт» 5 + —,'5 !обх, !обт > 5+ 0(5). 17. Пусть Т = 3; А»(х) = бх + 35х~ + 5бхз +, В»»(х) = хз + 15х~ + 35хз + . Тп (х) = 7хз + 50х" + 91хз + 64хз + 19х'е + 2х". Оптимальное распределение для 5 = 144 требует 55 серий на Т2. Это обязательно приводит к неоптимальному распределению для 5 = 145. Д.
Э. Зэйв изучил процедуры такого вида, близкие к оптимальным. 16. Пусть 5 = 9, Т =- 3. Рассмотрим следующие две схемы. Альтернатива Т1 Т2 ТЗ Стоимость Оптимальное многофазное слияние Т1 Т2 ТЗ Стоимость О'1е О'1з 1» 1»Зз 3' 3' — 3 1 9 1 Оз>з Оз>з 1 1з3' 3 3' 3' — 9' 0'2» 6 2' 7 3 6' б 9 31 0»23 22 32 (Еще один способ улучшения "оптимального" многофазного метода состоит в пересмотре того, в каких местах выводной ленты появляются фиктивные серии на каждой фазе слияния. Например, результат слияния 0 1 с 0 1 можно было бы рассматривать как гз за 2'О'2'0'2' вместо 0»2з.
Таким образом, остается ьшого нерешенных вопросов, связанных с оптимальностью ) 14. (а) п(1) = 1, поэтому будем считать, что Й > 1, Закон Т„» = ТШ ц!» ц 4- + Тщ р>!» ц показывает, что Т„» < ТШЕ,>» тогда и только тогда, когда Т>„» р>!» ц < Т !»»>. Пусть г - произвольное положнтольное целое и пусть и' — минимальное число, такое, что Тш,>!»,» Т„!»,» тогда Тщ,>!» ц > Тщ» ц для всех и > и', поскольку это тривиально для и > п(Й вЂ” 1) + г, .а иначе Т>,Н» ц > Трп „>>» ц > Т '>»-ц > Т,ц»»>.
(Ь) То же рассуждение прн г = и — и показывает, что Т„» < Т„» влечет за собой Тщ,>» < Ты,>» длн всех 1 > О. Значит, из рекуррентного соотношения следует, что Т!„»» < ТШ,>» для всех 1 > 0 и Й > Й'. (с) Пусть 6(5) — наименьшее и, такое, что Е„(5) принимает свое минимальное значение. Требуемая последовательность ЛХ существует тогда и только тогда, когда 6(5) < 4(5+ 1) для всех 5. Предположим, что и = К(5) > Ц5 + 1) = и', так что Е (5) < Е„(5) и Е„(5 + 1) > Е„(5 + 1). Существует наименьшее 5', такое, что Е„(5') < Е„(5'); имеем гп = Е„(5') — Е„(5'— 1) < Е„(5') — Е„(5' — 1) = ш'. Тогда 2», Т„„< 5' < 2»» Т„»; следовательно, существует некоторое Й' < тп, такое, что Т„» < Т» .
Аналогично имеем ! = Е„(5 + 1) — Е,»(5) > Е„(5+ 1) — Ем(5) = !'; значит, 2 „, Т„» > 5+ 1 > з „, Т„». Поскольку !' > т' > ш, существует некоторое Й > тп, такое, что Т„„> Т„». Но зто противоречит п. (Ь). 19. Окончательный Уровень Т1 Т2 ТЗ Т4 Сумма результат на и+1 И„ Т(Ь) а„зв + 2а„Т(Ь вЂ” 1) Ь„ с„+ а„ с„ И„+ а„ а Ь 2О. а(г) = 1/(1 — гг — гз — г~), 1(г) = (Зг+Зг +2гз+г~)/(1 — гг — вз — г~), 2 „>, Т„(х)г" = х(Зг+Зг'+ 2г'+ г')/(1 — х(г'+ г'+ г")) 21 = Ав-г +1, С = Ав-гАп-г+ 1, Во А„-гА гА„-в +1, А = А -гА -зА -з+ 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
