AOP_Tom3 (1021738), страница 202
Текст из файла (страница 202)
Да; коммутативной будет даже операция удаления нз перестановок, определенная в доказательстве теоремы Н (если пренебречь перенумерацней). При наличии элемента между элементами Х и У коммутатнвность удаления очевидна, поскольку на операцию удаления влияет только относительное расположение элементов Л, У и их наследников и удаления Х и У не взаимодействуют между собой. С другой стороны, если У является преемником Х н У вЂ” больший елемент, то оба порядка удаления просто удаляют элементы Х н У. Если 1 — преемник Л; а Я вЂ” преемник У, оба удаления приведут к замещению первого встреченного элемента Х, У или Е элементом Е и к удалению второго н третьего из встретившихся элементов нз перестановки.
18. Воспользуйтесь упр. 1.2.7-14. 19. 2Нн — 1 — 2~ ь,()г — 1)~/)г)У~ = 2Нл — 1 — 2/д+ 0(Ю ~). (РаспРеделение ПаРето б.1-(13) приводит к подобному асимптотнческочу результату с поправкой 0(п ~ )або).) 20. Да, конечно. Предположим, что К~ < < Кл, так что дерева, построенное при помощи алгоритма Т, вырожденное. Если, например, рь = (1+ ((Ю+ 1)/2 — 1) е) /А, среднее число сравнений равно ()у+1)/2 — ()у — 1) е/12, в то время как оптимальное дерево требует менее ()К ЛГ~) сравнений.
21. -', Зш Кэб, ее, -'. (Большинство углов равны 30', б0' или 90'.) 22. При М = 2 это очевидно,' при Ы > 2 имеем г((, у — Ц < г(1+1,/-Ц < г[(+1, Я. 23. (Увеличение веса первого узла в конце концов приведет к его перемещению в корневое положение. Это наводит на мысль о сложности динамического поддержания оптимальности дерева.) 24. Пусть с означает цену дерева, полученного посредством удаления п-га узла из аптимальнаго дерева. Тогда с(0, н — 1) < с < с(0, и) — о„ц поскольку опорация удаления всегда перемещает (сс-1) на один уровень вверх. Аналогично с(0, и) < с(О, я — 1) + у„ц так как при предлагаемой замене цена дерева равна последнему выражению, откуда следует, что с(0, и — 1) = с = с(0, и) — 9„ 25.
(а) Предположим, что А < В и В < С, и пусть а Е А, Ь Е В, с Е С, с < о. Если с < Ь, та с Е В; следовательно, с Е А и о Е В; значит, а Е С. Если с > Ь, то а Е В; следовательно, а Е С и с Е В; значит, с Е А. (Ь) Это легко доказать самостоятельно. 26. Цена любого дерева имеет вид у+ 1х, где у > 0 — некоторое действительное числа, а 1 — — целое, большее О. Минимум конечного числа таких функций (взятых по всем деревьям) всегда имеет описанный вид. 27.
(а) Иэ ответа к упр. 24 (в частности, из того, что с = с(0, и — 1)) вытекает, что ГГ(О, -Ц = В(0, ) ~ ( ). (Ь) Если 1 = 1', результат в указании тривиален В противном случае обозначим пути к Я как ОО и ° ОО и Поскольку г = гв > зв = з и гг < вг = и, можно найти уровень Л > О, такай, что гл > вл н глэс < валс По индукции имеем глас Е ГГ(гл,п), злю Е В(зл,п) и В(вл,п) < В(гл, и). Значит, галс Е В(вл, н) и вллс Е ГГ(гл, н); отсюда следует результат, приведенный в указании. Теперь для доказательства того, что ГГ'„< Вл, положим, чта г Е Вл, з Е Вл, з < г, и рассмотрим аптилсэльные деревья, показанные для х = хл Получим, что 1 > 1л, и можно предположить, что 1' = 1л. Для доказательства соотношения Вл < ГГ~ле, положим, что г Е Вл, з Е Вл+,. з < г, и рассмотрим оптимальные деревья, показанные для х = хлеп Получим, что 1 < 1л, и можно предположить, что 1 = 1л.
29. Это вырожденное дерево (см. упр. 5) с 700 на вершине дерева н ТНЕ внизу, которое требует в среднем 19.158 сравнений. Дуглас А. Гамильтон (Пооб!ав А. Наш(йан) доказал, что наихудшим деревом всегда является некоторое вырожденное дерево Таким образом, существует О(п )-злгоритм пав лучения наихудших бинарных деревьев поиска. 30. См.
В. Ь Стезэоег, ГлГоппабап Ргосевв!п8 1еггегв 4 (1976), 90-94, Р. Р. Уао, В(АМ э'. АГбеЬга(с алд Оисгесе МеСЛог1в 3 (1982), 532-540. 31. См. Асга1оГогплабса 1 (1972), 307-310. 32. Когда М достаточно велико, оптимальное дерево должно иметь указанный внл и минимальная цена должна быть в М раз больше минимальной длины внешнего пути плюс решение сформулированной проблемы. (Прамечанае. Статья Весснера, указанная в ответе к упр. 30, поясняет, как найти оптимальное бинарное дерево поиска высоты < П Для частного случая рс = .
= р = 0 решение было получено Т. Ч. Ху (Т. С. Но) и К. Ч. Таном (К. С. Тап) (МВС ВерогС 1111 (Повн оГ И'(всооэсп, 1970)). А. М. Гарсия (А. М. Сагсйа) и М. Л. Воч (М. Ь. 'лгасйв) доказэлн, что в этом случае все внешние узлы окажутся л~аксимум на двух уровнях, если шшл=~ (дл-~ + йл) > шах 2 л йл, а также пРедставили алгаРнтм, тРебУющий только 0(п) шагов для поиска оптимального двухуровневого дереза). 33. Решение поставленной задачи можно найти в А.
1Сас, ЯГСОМР 5 (1976), 9 — 18; альтернативные варианты рассмотрены в работе П. Зра1ег, Асеа ГгсГогша11са 31 (1994), 729-740. 34. Согласно аппроксимации Стирлинга при рг...р„~ О это значение равно 2нйч" ""Ь х х(2яН)!' "!зг(рг, ..р„) Пг(1+ 0(1/!У)). 35. Минимальное значение правой части неравенства, равное 1-р+ Н (р, 1 — р), достигается прн 2х =- (1 — р)/р.
Однако согласно (20) при !г = 2 Н(р, д, г) < 1 — р+ Н(р, 1 — р). 36. Сначала докажем утверждение нз указания, принадлежащее Дженсену (2епвеп) (Асса Иа!!г, ЗО (1906), 176 — 193). Если / вогнута. следовательно, функция д(р) = /(рх+ (1— р)у) — р/(х) — (1 — р)/(у) вогнута, кроме того, она удовлетворяет условию д(О) = д(1) = О. Если длн некоторого 0 ( р < 1 д(р) < О, то должны существовать ра < р, для которого д'(ра) < О, и рг > р, для которого д~(рг) > 0 согласно теореме о среднем Однако зто противоречит условию вогнутостн.
Следовательно, /(рх + (1 — р) у) > р/(х) + (! — Р)/(у) при 0 < р < 1, что геометрически очевидно. Теперь по индукции можно доказать, что /(р~хг + . + р„х„) > рг/(хг) +. + р„/(х„), поскольку /(ргхг + . +р х„) > рг/(хг) + + р -г/(х„.г) + (р — г +р )/((р„-гх .-» + р х )/(р г +р )) при и > 2. Согласно лемме Е имеем Н(ХР) = Н(Х) + г» р,Н(г,г/р„..., гг„/р,); =! и послевняя сумма г ", 2., г р,/(го/рг) < 2 г", /(~,, г,) = Н(!'), где Функция /(х) = х !3(1/х) вогнута. 37. Согласно п. (а) упр 3 3.2-26 имеем Рг(Р| > з) = (1 — з)" ' Отсюда г' ЕН(Ри..., Р ) = иЕРг !3(!/Рг) = из/ (1 — з)" И(в!6(!/з)) = -(4+ В)/!п2, а где А = и /а' (! — з)" ' Зв = 1 и г г Н= ~ (! —.)"- ° =Ц )( !), ~ н,) = Н„ а »=г ~-Ь/ ~а согласно упр.
122.7-13. Таким образом, ответ равен (27„— 1)/!н 2. (Это значение !3 и+ (7— 1)/!в 2+0(и ') очень близко к максимальной энтропии Н( — ',..., г ) = !3 гг, и Н(рг,..., р„) с высокой вероятностью равна Й(!об и).) 38. Если в» г — — в», имеем д» г = р» = д» = 0 (см. (26)). Постройте дерево для и-1 вероятности(рг,...,р» г,р»тг,...,рглда,...,9» г,д»тг,...,9,) и замените лист (я — !) двухлистовым поддеревом. 39. Можно провести доказательство твк же, как н в теореме М, если О < юг < юг « ю„и з» = юг+ - +ге», поскатьку из к» > 2 ' следует, что з» г+ 2 ' < в» ( з»,.г — 2 ' прн упорядоченных весах. Следовательно, имеем )и»( < 1+ !6(!/ги»).
(Этот результат вместе с соответствующей нижней границей Н(г ° г,,им) составлнл теорему 9 в оригинальной статье Шеннона 1948 года.) 40. При х = в+3 указанная перестановка изменяет цену с д» г!+9»1+ 9»-г!» г до д»-г!+ д»-г1+ д»!»-г, так что изменение равно (д» г — д»)(1 — 1» г): эта величина отрицательна при ! ( !» г поскольку д» г > д» Точно так же при 1г > з + 4 перестановка измгннет цену на величину б = дгтг(1 — !. г) + д.тг(! — 1.»г) + д. г(1.»г — 1 ° тг) + + д»-г(!»-4 — !»-г) + д.,(! — О + 9.(! — !). Мы имеем д,тг > д тг, д* г > д г,, д»-г > д». Таким образом, находим б < (ч»-г — д»)(! — 1» — г) + (Ч» — г — ч» — г)(! — !»-г) < О; например, при четном )» — й б ~ Чй-й(! ! +») + Чй 2(! !»+2) + 7»-э(!й+! !»+э) + ' ' +Ч»-2(!й-й !й-2) + Чй — ~(!й-э — !) + Ч»(!й-й — !) (для нечетного Ь вЂ” з выводится похожее выражение).
Отсюда следует, что б отрицательно, кроме случая !й э = ! 41. ЕГСНТВХ727НВСВАРЦК)КЬИ1И05а. 42. Пусть Чй = ИТ(Р!). Основная идея заключается в том, что на шагах С2 — Сб есе Ч» становится ббльшимн, чем начальное значение Ч» ~ + Ч», или равными ему. 43. Вызвав рекурсивную процедуру тагй(рм О), где тагб(Р, !) означает следующее; ЬЕЧЕЬ(Р) +- !! если ШИК(Р) ф Л, то тагА(ШИК(Р), .1+ 1); если М.1ИК(Р) ф Л, то тагА(М.1ИК(Р),1+ 1). 44. Установите глобальные переменные ! +- О, т +- 2п и вызовите рекурсивную подпро- грамму Ьи»Ы(1), где Ьи»Ы(!) означает следующее.
Установить ! +- т. Если ЬЕГЕС(Хю ) = 1, то присвоить 551ИК(Х» ) й — 1 и ! +- 1+ 1; в противном случае присвоить гп й- т — 1, ШИК(Х>) й- Х и Ьи)Ы(1+ 1). Если СЕЧЕЬ(Х~) = 1, то присвоить В).1ИК(Х, ) + — 1 и ! +- 1+ 1; в противном случае присвоить т й- т — 1, КХ.ХИК(Х,) + — Х и Ьи»Ы(!+ 1). Переменная у локальна по отношению к построенной подпрограмме.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
