AOP_Tom3 (1021738), страница 207
Текст из файла (страница 207)
|>о 29. »рлажоле (Е!а!о!ес) и Седгевик (Беййеиюй) (Я!СОМР 15 (1986), 748 — 767) показы|и, что среднее количество таких узлов примерно равно 0.372Х при М = 2 и 0.689Х при М = 16. В работе Флажаче и Ричмонда [Капйош Я»госсе»ив апй А!6оп|йшз 3 (1992), 305 — 320) приводится обобщение этого результата. 30. Итерируя рекуррентное соотношение, получаем Ь (с) в виде суммы всех возможиых членов вида ( ) (Р») ( ) дляп>р|»..
р >1. 31. Ь'„(!) = 1'', см. упр. 5.2.2-36, (Ь). (Дополнительную информацию о дисперсии и предельных распределениях М-арных обобщений деревьев метода "Патриция" можно найти в работах Р. К!гзсЬепЬо(ег апй Н. Ргой!пйег, Бес»осе Хосез !л Сошр. Яс!. 226 (1986), 177-185; Ж. Бара|»йо»гз!»1, бАСМ 37 (1990), 691 — 711; В Ка!з, Р. бас»!пе», апй %.
Бзрап1»ов з1а, Я1АМ Х О|зсгеге Ма»И. 6 (1993), 197 — 213.] 32. Сумма нолей 381Р равна количеству узлов в соответствующем бинарном дереве, поэтому ответом является величина Ал (см. упр. 20). 33. Вот как была получена формула (18). А(2с) — 2А(г) = е»* -2е*+1+ А(г)(е" — 1) может быть приведено к виду А(2х)/(еы — 1) = (е' — 1)/(е' + 1) + А(с)/(е* — 1). Следовательно, А(з) = (е' — 1) 2 >»(сма — 1)/(еыа + 1). Теперь, если /(з) = 2 с„з", то 2„.>» /(с/2|) = 2,'с,.х"/(2" — 1). В нашем случае ((г) = (е* — 1)/(е' + 1) = СапЬ(х/2), что эквивалентно 1 — 2с '(з/(е* — 1) — 2з/(сы — 1)) = 2 „>, В„е»с" (2"+' — 1)/(и+ 1)!. Дальнейший вывоД очевиден. 34. (а) Рассмотрим 2 >»2 " '(„")В»/2" 1~ '1; согласно упр. 1.2.11.2 — 4 1" ' + ..
+ (т— 1)" ' = (Во(т) — В„)/и. (Ь) Пусть Я„(гп) = 2 "", (1 — к/гп)" и Т„(п|) = 1/(е"г"' — 1). При !г < гп(2 имеем е ~"» > ехр(п!п(1 — й/гп)) > ехр(-Ьп(т — !гоп/т|) > е «"» (1 — й~/т~). Значит, (1 — й/т)" = е ~ "| + 0(е ~о»"'й~п/т~). Поскольку Я„(т) = б „~, (1 — й/т)о + О(2 ") и Т„(гп) = 2„'ь' г» е ~"г +О(е "г'), ил»еем Я (т) = Т„(т)+0(е "г и/т»). СУмма членов 0(ехр(-и/2")п/2||) равна О(п' '), так как сумма при !' ( 16 и имеет порядок и '(1 + 2/е + (2/е) + ., а сумма при ( > 18п — порядок и '(1 + 1/4 + (1/4)| + (с) Доказательство аналогично доказательству, лриведенному в разделе 5.2.2 при )я) с 2|г; затем используется аналитическое продолжение. (й) -' !6(п/я) + 7/(2 1п 2) — з + б(п) + 2/и, где б(п) = (2/!и 2) 2 3>,И(Д вЂ” 2яй/!и 2)Г( — 2ягй/!и 2) ехр(2лгй !К и)) = (1/!и 2) 2 г ю 31(Ь(! + 2лгй/!и 2) ехР(2тг)б !Е(п/Я)))/ совЬ(Я'Я/!и 2).
Дисперсия и высшие моменты были вычислены В. Шнанковским (Ч'. Яграп)бопвМ),,1АСЛГ 37 (1990), 691-711. 35. Ключи должны иметь вид (о079057ц ПО)З)агг, о170573, о17150573, а17151ьгб), ГдЕ П,/г,... есть строки из нулей и единиц, !о! = а — 1, Щ = Ь-1 и т. д Вероятность того, что пять случайных ключей имеют такой вид, равна 5! 2' '+5 '+' '7~ '/23~ б'+~б'+'7'+'~бт'+'тб = ;,/2ыбь+г.бвбЯ 36. Пусть и — число внутренних узлов (а) (и'/2') П(1/3(х)) = и! П(1/2ц') 'в(х)), где длина внутреннего пути дерева. (Ь) ((и + 1)!/2") П(1/(2'7 ) — 1)).
(Рассмотрите суммирование ответа к упр. 35 по всем а, Ь, с, 4 > 1.) 37. наименьшая модифицированная длина внешнего пути равна 2 — 1/2к 2 и достигается только в случае вырожденного дерева (длина внешнего пути которого максимальна). (Можно доказать, что наибольшая модифицированная длина внешнего пути достгггвется тогда н только тогда, когда все внешние узлы расположены не более чем на двух смежных уровнях! Однако дерево с меньшей длиной внешнего пути не всегда имеет большую модифицированную длину внешнего пути.) 38. Рассмотрите подзадачу поиска деревьев с А узлами с параметрами (о,58), (и, -'/)),..., (а, 2 ""1)).
39. См. М!уа1саэуа, 37пЬа, ЯиЕцо, аггб НовЫ, ЯГСОМР 6 (1977), 201.234. 40. Пусть 71/г — истинная длина периода последовательности Построим дерево, подобное дереву метода "Патриция", с аеаг... В КачЕСтвЕ МаССнва ТЕХТ и с А7/г ключами, начинающимися с позиций О, 1,, Л1/г — 1. (В соответствии с выбором г ни один ключ не является началом другого.) Включим я каждый узел поле БТХЕ, в котором содержится количество помеченных патей ссылок в поддереве, лежащем ниже этого узла. Для выполнения указанной операции используйте алгоритм Р. Если поиск неудачен, ответ -- О; в случае успешного поиска и / < и ответ — г. И наконец, если поиск успегвен и / > и, ответ равен г 31281Р).
43. ОжидаемаЯ высота асимптотически пРиближаетсЯ к (1 + 1/3) !о8м !7' с отклонением 0(1). (См. Н. МепдеЫоп, 1ЕЕЕ Тгапвасбгопв ВЕ-8 (1982), 611-619:, Р Р)а)о!еЦ АсСа ГаГогташ гса 20 (1983), 345-369: Н Реъгоуе, Асга 1пГопоабзса 21 (1984), 229. 237; В. Ргые), Аб)танеев гп Арр17еб! РгоЬаЬ31йу 18 (1986), 139. 155; Ъ'. Яграп!гонвМ, А)бог!213ш!са 6 (1991), 256 — 277.) Средняя высота случайного дерева цифрового поиска с М = 2 асимптотически приближается к 1Кп + ъ/2!873 (АМоив апб ЯЫе!Йв, Ргобаб!Иу ТЬеогу алс) Не!абеб! ЕгеМэ 79 (1988), 509-542]; то же самое справедливо н для случайного дерева метода "Патриция" [Р!гге! апс1 НпЫп, .)опгла! оГ СопгЫпвгопа) ТЬеогУ А55 (1990), 292 — 312).
44. См. ВОРА 8 (1997), 360 — 369; такая структура поиска тесно связана с алгоритмом быстрого многоключевого поиска, обсуждавшимся в ответе к упр. о.2.2 30. ?К. Клемент (3. С!епгепг), Ф. Флажоле (Р. Р!а)о!ег) и В. Вали (В. Лга!!ее) показали, что при тернарном представлении поиск по лучу выполняется примерно в три раза быстрее, чем при использовании бинарного представления (2), с учетом доступа к узлам (см, ВОРА 9 (1998), 531-539).
45. Вероятность (ТНАТ, ТНЕ, ТН13) перед (В01ЬТ, НООБЕ, 13, ЛАСК), (НООБЕ,1Б,ЛАСК) перед (ВОТЬТ), (НООБЕ,13) перед (3АСК), (13) перед (НООЯЕ), (ТН13) перед (ТНАТ, ТНЕ) и (ТНЕ) перед (ТНАТ) раина— 3 3 г 3 7 7 3 3 2 3 2 55' РАЗДЕЛ 6.4 1. — 37 < г11 с 46. Таким образом, в ячейках памяти, предшествующих ТАВЬЕ и гледующих эа ТАВ1.Е, не должны содержаться данные, которые соответствуют аргументу (например, их первый байт мог бы быть нулевым).
Очевидно, что было бы плохо хранить К в таком диапазоне! (Значит, можно сказать, что метод из упр. 6.3-4 использует меньшее пространство, поскольку границы той таблицы никогда не нарушаютсв.) 2. Т09 (буксир). (В состоянии ли читатель найти десять слов из не более чем пяти букв, которые заполнят пустоты между — 10 и 30?) 3. Коды символов удовлетворяют соотношениям А + Т = 1 + й, 8 — Е = 0 — Е, а потому получим либо /(АТ) = /(18), либо /(ЕЕ) = /(08).
Обратите внимание на то, как команды 4 и 5 из табл. 1 разрешают зту дилемму, оставляя гП в достаточно узком диапазоне. 4. Рассмотрим случай для Л пар. Наименьшее и, такое, что т "и!~ ( )( )2 "< — приза=365, равно 88 Если вы пригласите 88 человек (включая себя), вероятность появления трио с одним днем рождения составит 0.511065, для 87 человек зта вероятность снижается до 0.499455.
См. С. Р. Р1пз)ш, АММ 67 (1960), 830. 5. Эта хеш-функция плоха, поскольку она принимает не более 26 различных значений, причем некоторые нз них буд т встречаться явно чаще других. Даже при двойном хешировании (если предположить, например, что Лз(К) = 1+ второй байт К и М = 101) низкав скорость поиска превысит выигрыш от высокой скорости вычисления хеш-функции.
Кроме того, поскольку в программах на языке ГОКТЕАХ часто встречается куда больше, чем 100 различных переменных, значение М = 100 явно малб. 6. Не на 811-компьютере, поскольку почти всегда будет получаться арифметическое переполнение (слишком велико делимое). (Было бы неплохо иметь возможность вычислить (юК) гаоб М, в особенности для линейного исследования при с = 1, но, к сожалению, большинство компьютеров не предоставляют ее из-за переполнения частного.) 7. Если К(х) кратен Р(х), то В(аз) = 0 в СГ(2~) для всех у б Я. Пусть Я(х) = х" + + х", где а~ > . > а, > 0 и з < а Выберем 1 — з значений а,ю,...,ао таких, что а»,...,а~ представляют собой различные неотрицательные числа, меньшие и. 51атрица Вандермонда ) сингулярна, поскольку сумма ее первых з столбцов равна нулю.
Однако это противоречит тому факту, что а ',..., а"' — различные элементы СР(2~) (см. упр. 1.2.3-37). (Первоначально идея полнномиального хеширования была предложена группой исследователей нз 1ВМ (М. Навал, Б. Мигоба, Р. Р. Ра)егшо, М. Начег, ап»1 С. Бсйау, 1ВМ Х Яезевгсб Вс Рече!оршслз 7 (1963), 121 129; см. также Г Я. Рвзеаз 3311888 (1967)).) 8. По индукции. Сильнав индуктивная гипотеза может быть дополнена тем фактом, что 1(-1) (г9» + 9» ~)В) = (-1) (г(9»В — р») + (9» ~ — р» ~)) при О < г < а».
"Рекордно низкие" значения (пВ) достигаются для и = 9», дз+ Ф, 29» + Ф,..., аздз + 9~ = Од» + В», 94 + дз, ..., а494 + дз = Оде + дз, ..., "рекордно высокие" — для и = дв, Ф + дв, а»Ф + Вв = Одз + Вю ., .. Это шаги, на которых формируется интервал с номером 0 новой длины. (Дальнейшая структура может быть выведена обобщением системы счисления Фибоначчи из упр. 1.2.8-34; см. 1,. Н. ВашвЛазч, Х ХпшЬег ТЛеогч 13 (1981), 138-175.) 9.
Имеем ф ' = //1, 1, 1,... // и ф з = //2, 1, 1,... //. Пусть В = //ам аз,... //, В» //а»»ма»в з, ., // и пусть О» = 9»+9» ~В» з в обозначениях нз упр. 8. Если а» > 2, плохим является самое первое разбиение. Три размера интервалов в упр. 8 равны (1 — гВ» з)/С», Вь»Я» и (1 — (г — 1)бь-»)/(»ь соответственно. так что отношение первых двух длин составляет (аь — г) + дь.
Эта величина меньше — прн г = аь и аье» ) 2; следовательно, » чтобы не было плохих разбиений (а», аэ,...) должны быть равны 1. (Другие связанные с данной темой теоремы можно найти в работе В. Ь. Сга]»аш ап»] Л. Н. Чац Ь»п», Сапа»(»ап з. Ма»Ь. 20 (19б8), 1020-1024, и в указанной в ней литературе.) 10. Вы найдете элегантное доказательство в работе Е. М, Ь»апК, ])»зсге»е Ма1Ь, 28 (1979), 325-326. 11. Проблемы могут начаться при К = О. Ес»»и потребовать, чтобы все ключи были ненулевыми, как в программе Ь, такое изменение может иметь смысл; прн этом можно было бы помечать пустые позиции нулевым значением.
12. Можно хранить К в КЕТ[0], заменив при этом строки 14-19 следующими строками. БТА ТАВ1.Е(КЕТ) А — 31 СИРА ТАВЬЕ.2(КЕТ) С вЂ” 1 — 32 СИРА ТАВЬЕ,2(КЕТ) А — о1 УИЕ 2В С вЂ” 1 — о2 ]Е ЗГ А — 51 ЗН 122 БР .4 — л1 2Н ЕИТ1 0,2 С вЂ” 1 — 32 ЕИТ1 0,2 л2 ЬВ2 ТАВЬЕ,1(ЬТИК) С вЂ” 1 — 52 ЗИР БОССЕББ з2 3 "Сохраненное" время составляет С вЂ” 1 — 5А + з + 4л1 единиц, что в результате оборачивается потерей, поскольку С очень редко превышает 5. (Оказывается, не всегда гледует оптимизировать внутренние циклы!) 13. Пусть записи в таблнпе относятся к двум различным типам, как и в алгоритме С, с дополннтельныч однобнтовым полем ТАСБ] в каждой записи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
