Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 101
Текст из файла (страница 101)
Однако зто противорр щт условию аогнутостн. Следовательно, /(рх + (1 — Р)у) > Р/(х) + (1 — р)/(у) прн 0 < Р < 1, что геометрически очевидно. Теперь по индукции можно доказать, что /(Р,х, + +Р„хи) > Р«/(х«)+ .+Р„/(х„), посколькУ /(Р«х«+ +Рис„) > Р«/(х;)+ + Р««-г/(я»-г) +(Р «-«+ Р )/((Ри-«х -«+ Р ти)/(Р -«+Ри)) прн и > 2. Согласно лемме Е имеем Н(А)') = Н(««.') + ч» Р,Н(г« /р«,...,,„/Р«); «-! и последняясумма ~,", « ~"™ «р«/(г«,/р«) < 2"„" «/Д ™.,ги) = Н(У), где функция/(х) = х !3(1/х) вогнута. 37.
Согласно п. (а) упр. 3,3.2-26 имеем Рг(Р«> в) = (1 — в)и '. Отсюда г« ЕН(Р«„...,Р ) = г«ЕР« !3(1/Р«) = и/ (1 — в)" ««4(в!3(1/в)) = -(А+В)/!п2, о где А=и/о(! — в) '«(»=1н 1 п «1 В = и / (1 — в)" '!поев = ~~«( )( — Ц»в»(- — !пв) ! = — Н„ согласно упр. 1 2 7-13. Таким образом, ответ равен (Н вЂ” 1)/ !и 2, (Это значение 13 и+ (т— 1)/!п 2+0(г» ') очень близко к максимальной знтропииН(-',..., -„') = !бп, и Н(Р«,...,Р„) с высокой вероятностью равна й(!об п).) 38. Если в» « —— в», имеем д» « = р» = д» = 0 (см.
(26)). Постройте дерево для и — 1 вероятности(р«,...,р»-«,р»+«,...,р;до,...,д»-«,д»»«,...,д„) изамените лист (я-.») двухлистовым поддеревом. 39. Можно провести доказательство так я«е, как и в теореме М, если 0 < ш«< шг « . ш„и в» = к «+ - + и», поскольку из ш» > 2 ' следует что в» «+ 2 ' < в» < щ», -2 ' прк упорядоченных весах. Следовательно, имеем )««») < 1+ 13(1/ш»). (Этот результат вместе с соответствующей нижяей границей Н(ш,,..., ши) составлял теорему 9 в оригинальной статье Шеннона 1948 года.) 40. При к = в+ 3 указанная перестановка изменяет цену с д» «!+ д»!+ д»-г!»-г до д» г!+ д», ! + д»!» г, так что изменение равно (д» г — д»)(! — !»-г); зта величина отрицательна при ! < !» г, поскольку д»-г > д».
Точно так же прн к > в + 4 перестановка изменяет цену на величину б = ди+«(! !и+«) + д +г(! — !»г) + ди»г(! +« — !и+г) + ' + д»-г(!»-» — !»-г) + д»- (!»- — !) +д»(!»-г — !). Мы имеем д«+«> д«+в, д»+г > ди+«, ..., д»- г > д». Таким образом, находим д < (д» г — д»)(! — !»-г) + (д»-в — д»-«И! — !»-в) < 0; например, при четном Ь вЂ” з Ь < Ч»-з(1 — 1лю) + 9»-з(1 — а+э) + 9»-з(1»+з — 1»+з) + ' + 9»-з(1»-з — 1»-з) + 9»-з(1»-з — 1) + 9»(1»-з — 1) (для нечетного Ь вЂ” з выводится похожее выражение). Отсюда гледует, что Ю отрнпательно, кроме сл)'чая 1»- з = 1. 41. КРОН10172'»НИООЬРОН1КЬИ1903лл 42.
Пусть 91 = ИТ(Р)). Основная идея заключается в том, что на шагах С2-Сб есе а» становятся ббльшими, чем начальное значение д» з + а», или равными ему, 43. Вызвав рекурсивную пропедуру глагЬ(рмО), где пзагй(Р, 1) означает следующее: ЬКККЫР) +- 1; если Н,1ИК(Р) Р Л, то тагй(ШИК(Р),1 + 1), если М,ХИК(Р) Р Л, то плагй(ВАХИН(Р),1 + 1). 44. Установите глобальные переменные 1» — О, пз +- 2п и вмзовите рекурсивную подпро- грамму ЬиЖ(1), где Ьи»Ы(1) означает следующее.
Установить у <- пл. Если ЬКЧИ. (Хз ) = 1, та присвоить |.ЫИК(Х) ) +- 1 и 1»- 1+ 1, в противном случае присвоить пл»- пл — 1, ЬЬКИК(Х) ) +- Х и Ьий((1 + 1). Если $.КЖЫХз) = 1, то присвоить Ы.1ИК(Х ) +-1 и 1»- 1+ 1'„ в противном случае присвоить гп+- зп — 1, 82.1ИК(Х»)»- Х и Ьэ»Ы(1+ 1). Переменная у локальна по отношению к построенной подпрограмме, (Это элегантное решение предложена Р. Е. Таржаном (В, Е. Тацап), Я)СОМР 6 (1977), 639.) Внимание. Если числа 1э, ..., 1„не соответствуют никакому бинарному дереву, алгоритм запиклится. 45.
Представить рабочий массив Ра, ..., Рз в виде списка с двойными связями, который также имеет связи со сбалансированным деревом (см. раздел 6.2.3). Если "попарно убмвающне" веса равны Оз, ..., д, с 91 в корне дерева, можно перейти па дереву влево или вправо на основании значений 9) и 9)лы двойные связи обеспечивают мгновенный доступ к (Оль (Поля ИЬИН не являются необходимыми; при чередовании сохраняется сямметрнчный порядок, а потому вносить изменения в двойнме связи не нужно,) Отдельные семейства весов, для котормх задача может быть решена за время О(п), были представлены Ху (Нв) и Моргенталером (ЫогбепсЬа)ег) в Ъесгпге Массе гп Сошр. Ясг', 1120 (1996), 234-243; однако неизвестно, достаточно ли времени О(п) в общелз случае.
46. См. 1ЕЕЕ Тгапз. С-23 (1974), 268-271, кроме того, см, упр. 6.2.3-21. 47. См. Л1»епйазпр апс1 МеЫЬогп, эАСМ 27 (1980), 412-427. 48. Не позволяйте сложному анализу случаев К = 3 (Лопаээеп апб КппЗЬ, Х Сошр. Яуэз. Яс1 16 (1978), 301-322) и Ф = 4 (Ваеэа-уазез, В)Т 29 (1989), 378 — 394) запугать вас) В этой области достигнут определенный прогресс (см. 1ювсЬахб, Вапбйапагппавэпа, апг) ЯсЬоы, ТЬеог. Сашр, Яс). 93 (1992), 201-225), 49. Этот вопрос был впервые исследован Дж.
М. Робсоном (э. М. НоЬэоп) (Аиэсгайал Сошр. э. 11 (1979), 151-153), Б. Питтелем (В. Р)эте1) (э. МаЗЬ. Апа1. Арр)ю. 103 (1984), 461-480) и Люком Девраем (ало Оежоуе) (,)АСМ ЗЗ (1986), 489-498; Асса 1пб 24 (1987), 277-298), которые получили предельные формулы, выполняющиеся с вероятностью л 1 при и -+ ао; см. Н.
М. МаЬшоцд, Еза)ас)оп аг" Ваидош БеагсЬ 2гезн (%'1)еу, 1992), гла- ва 2. Впоследствии Люком Девроем и Брюсом Ридом (Вгпсе Бее)) (Б!СОМР 24 (1995), 1157-1162) был найден попахивающий шаманством результат — они доказаля, что средняя высота равна п)пгг+ 0(!об)обп) с дисперсией 0(!об)обп)г, где а = 1/Т(1/2е) ш 4.31107 04070 01005 03504 70760 96446 8902783916-, а Т(г) = 2 ~ г и" 'х"/и! представляет собой функцию дерева. РАЗДЕЛ 6.2.3 1. При преобразованиях должен сохраняться симметричный порядок узлов; в противном случае получить бинарное дерево поиска невозможно. 2. 3(3) = 0 только в том случае, когда 3 указывает на корень дерева (иа шагах АЗ и Л4 значение 3 не изменялось) и все узлы от 3 до точки вставки сбалансированы.
3. Обозначим через рл наибольшее возможное отношение числа.несбалансированных узлов к общему количеству узлов в сбалансированном дереве вьюотой Ь. Тогда рг = О, рг = -', рг = 1. Докажем, что рл ж (Рл+г — Ц/(Рл+г — Ц, Пусть Тл — дерево, которое максимизирует значение р», тогда можно предположить, что его левое поддерево имеет высоту Ь - 1, а правое — высоту Ь вЂ” 2 (так как, если бы оба поддерева имели высоту Ь вЂ” 1, интересующее нас отношение было бы меньше, чем рл-г).
Следовательно, это отношение для Тл ие превышает (рл-г№+рл-г№ + Ц/(№+№+Ц, где (№,№) — количество узлов в (левом, правом) поддереве. Приведенное выражение принимает максимальное значение при минимальных значениях (№, №). Значит, Тл представляет собой дерево Фибоначчи и согласно упр. 1.2.8-28 рл < )) — 1 4. При Ь = 7 дерево имеет большую длину пути, (Прглмечанис. В работе С. С. Роегег, Ргос.
АСМ Ь)аг, Сов!. 20 (1965), 197-198, приведена некорректная процедура построения №узловых сбалансированных деревьев с максимальной длиной пути. Эдвард Лагг (Ебв ахг) 1,о88) обнаружил, что на рнс, 3 у Фостера дан неоптимальный результат после 24 шагов (узел 22 может быть перемещен за узел 25).) Дерево Фибоначчи порядка Ь, однако, минимизирует значение (Ь+ а)Ьà — (длина внешнего пути(Т)) по всем сбалансированкым деревьям Т высотой Ь вЂ” 1 для любой неотрицательной константы а (это утверждение легко доказывается с помощью индукции по Ь). Длина его внешнего пути равна г ЬР»-г + л(Ь вЂ” ЦР» = (лг/»/5) ЬГл+г + 0(Рл+г) = 6)(Ь4 ). Следовательно, гьтина пути аобого №узлового сбалансирсеанного дерева не превышает ш)п(Ь)г! — 4)(Ьй ) + 0(Ьг)) < Х)обер! — Х)об )об, Ьг+ 0(Ь'), Более того„если Ьг велико и Ь ш ! )8 !»г), Ь = (Ь/ )3 4 — )обе Ь! = )об„Х вЂ” )об„)об Ь! + 0(Ц, можно построить сбалансированное дерево с длиной пути ЬЬ'+ О(Х) следующим образом; запишем Ьг+1 = Рл+Рл-г+ +Рллг+Х' = Рл»г-Рл+г+Ж' н построим бинарное дерево с )г"' узлами; затем последовательно объединим его с деревьями Фибоначчи порядков Ь, Ь + 1, ..., Ь вЂ” 1 [см.
Й. )л)е)п апс) )1. Ъооб, ТЬеогег!са! Сотр. Бей 72 (1990), 251-264), 5. Это утверждение может быть доказано по инлукции. Если Тк обозначает построенное дерево, имеем при 2" < Ас < 2" + 2 Тт-с с ТФ о -1 п и2 +2 <Ас<2 6, Коэффициент прн «" в «В!(«)Вл( ) представляет собой число бинарных деревьев с и узлами, левое поддерево которых сбалансировано н имеет высоту ), а сбалансированное правое по«дерево имеет высоту Ь. 7. Скос = Ст + 2В -сВ -о; следовательно, если положить оо = !п2, ос — — О, а ь« = ! п(1+ 2Вкес Вл/Ско+с) = О(1/В, С~+«) и д = ехр(оо/2+ оп /4+ ао/8+ . ), то можно найти, что О < Оо" — С = С„(ехр(о„/2+ о„ьс/4+ .) — 1) < 1, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
