Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 50
Текст из файла (страница 50)
[М47] Дает ли назначение одинаковых вероятностей последовательностям проб мээнимальиое значение Ск среди всех методов открытой адресации? 56. [М21] (С. К. Джонсон (Б. С. Лойпвон).) Найдите десять перестановок множества (О, 1, 2, 3, 4), которые зквивавентны равномерному исследованию в смысле теоремы П. 59. [М25] Докажите, что если назначение вероятностей перестановкам зквивалснтно равномерному исследованию в смысле теоремы (1, то при достаточно больвюм М чигдо перестановок с ненулевыми вероятностями превосходит ЛХ" для любого фиксированного показателя степени а. 60. [М47] Вудсы говорить, что схема открытой адресации включает единсщеснное хсэлироеание„если в ней используется в точности М последовательностей проб, начинающихся со всех возможных значений А(К), каждое из которых встречается с вероятностью 11ЛХ.
Является ли наилучшая схема единственного хепэирования (в смысле минимума Сл) асимптотически лучше случайных схем, описанных в (29)? В частности, справедливо ли С м > 1+ э о + уэоз + 0(сэз) прн М -э с ? 61. [ЛХ40] Является ли метод, анализировавшийся в упр. 46, наихудшей возможной схемой с единственным хешированием в смысле упр. бО? 62.
[М40] Схема с единственным хешированием называется чээклическон, если увеличения рэ рт ..рч-э (в обозначениях упр. 44) фиксированы при всех К. (Примерами такого метода являются линейное исследование и последовательности, рассмотренные в упр. 29 и 47.) Оищимальной схемой с единственным хешированием является та, значение См которой минимально среди всех (ЛХ - Цпи схем с единственным хешированием при данном М. При ЛХ < 5 наилучшая схема с единственным хешированием является ээиклической.
Справедливо ли зто для любого М? 63. [МЯБ] Если в хеш-таблице выполняются случайные вставки и удаления, то сколько независимых вставок в среднем следует сделать, чтобы все М позиций были занятыми в то или иное время? (Это значение представляет собой среднее время работы на отказ метода удаления, просто помечающего ячейки как "удаленные".) 64, [М41] Проанализируйте ожидаемое поведение алгоритма В (удаление с линейным исследованием). Сколько раз в среднем выполняется шаг В4? ь 63.
[ЯО] (Ключи переменной длины.) Во многих приложениях с хеш-таблицами используются ключи, представляющие набор символов произвольной длины. В таких приложениях нельзя просто хранить ключ в таблице, как в программах из этого раздела. Каким образом можно организовать работу хеш-таблиц с ключами переменной длины на 813-компьютере? ь 66. (88] (Оле Амбль (01е АпгЫе), 1973.) Можно ли так вставить ключи в открытую х.штаблицу с использованием их числового или алфавитного порядка, чтобы в случае поиска по алгоритму В нли О можно было сделать вывод о его неудачном завершении, встретив ключ, меньший, чем аргумент поиска? 67, [М41] Пусть Ф ключей с хеш-адресами аг аг...
ан вставляются в хеш-таблицу согласно алгоритму 1, и пусть с(, — смещение /-го ключа из его начального положения аг", тогда Сн = 1+ (дг +Из+ +Ил)/Х. Теорема Р гласит, что перестановка а не влияет на сумму дг + дг + - + дн; однако такая перестановка может значительно изменить сумму дг + дг -ь + 4,. Например, хеш-последовательность 1 2 ... Ж-1 А1-1 делает дг дг ...
с(н 1 с(н равным 0 О ... О гг'-1 н 2 дг' = (Ф вЂ” 1)г, это время как ее зеркальное отражение Ф вЂ” 1 Х-1 ... 21 приводит к более "цивилизованному" перемещению 0 1 ... 1 1, длЯ котоРого ч, дгг = Ф вЂ” 1. а) Какое размещение аг аг ... ан минимизирует 2 дгг? Ь) Поясните, каким образом следует модифицировать алгоритм 1, чтобы после каждой вставки сохранялся набор перемещений с наименьшей дисперсией.
с) ОпРеделите сРеднее значение 2„агг с Указанной модификацией н без нее. 68. [М41] Чему равна дисперсия среднего числа проб в случае успенпюго поиска по злгорнтму Е? В частности, чему равно среднее (А + дг+ . + дн) в обозначениях упр. 87? 66. [Мйб] (Эндрю Яо (Апбгеч г'ао).) Докажите, что схемы циклического единственного хеширования удовлетворяют неравенству С„'ы > -"(1+ 1/(1 — а)) в смысле упр.
62. [Указание. Покажите, что для неудачного поиска требуется ровно /с проб с вероятностью р, < (М вЂ” Н)/М.) 70. [НМ48] Докажите, что ожидаемое количество проб, необходимых для вставки (аМ + 1)-го элемента при помаши двойного хеширования, не превышает ожидаемого количества рг„б ( М Онгтеьн. р р р следовании. 71. [40] Поэкспериментируйте с поведением алгоритма С при его адаптации к внешнему поиску так, как описано в тексте. ь 72. [М28) (Универсальное хеширование.) Представьте гигантскую матрицу Н, имеющую по одному столбцу для каждого возможного ключа К. Элементы Н представляют собой числа от 0 до М вЂ” 1; строки Н представляют хеш-функции.
Мы говорим, что Н определяет универсальное семейсгнеа хеш-функций, если любые два столбца совпадают не более чем в Н/М строках, где Н вЂ” общее количество строк, а) Докажите, что если Н универсальна в этом смысле и хеш-функция (г ьыбираегся случайным образом из строки Н, то ожидаемый размер списка, содержащего все данные ключи К в методе раздельных цепочек (см. рнс.
38) после вставки любого ыножества различных ключей Кн Кг..., Кч будет равен < 1 + рр/М, Ь) Предположим, что каждый Ьэ в (9) представляет собой случайно выбранное отображение множества всех символов на множество (О, 1,..., М вЂ” 1). Покажите, что это соответствует универсальному семейству хеш-функций. с) Останется ли рнгультат (Ь) справедливым, если Ь (О) = О для всех Х, но ЬХ(х) случайно при х ~ О? 73. [МЯб1 (Картер (Саг~ег) и Вегман (%ебшап).) Покажите, что п.
(Ь) предыдущего упражнения выполняется, даже когда ЬХ не являются полностью случайными функцяямн, но имеют один из следующих видов. (1) Пусть ху — двоичное число (Ьдь ц... Л,.~Ь,а)ь Тогда Ьэ(ху)(одцбд!>+" +о11611+оэоьэд)шойм где каждое агэ выбирается случайно по модулю М. (Е) Пусть ЛХ вЂ” простое число; положим О < хэ < М. Тогда Ь;(хэ) = (а,х, +Ь ) щобМ, где а и Лэ выбираются случайным образом по модулю ЛХ, 74. (МЯ9) Пусть Н определнет универсальное семейство хеш-функций. Докажите или опровергните следующее.
Даны Н различных столбцов и некоторая случайным образом выбранная строка. При этом ожидаемое число нулей а этой строке. принадлежащих выбранным столбцам„равно О(1) + 0(Н/М). (Таким образом, каждый список в методе раздельных цепочек будет иметь ожидаемый размер.) 76, (МЯЯ) Докажите или опровергните следующие утверждения о хеш-функции Ь нз (9), если Ь, представляют собой независимые случайнью функции. а) Вероятность того, что Ь(К) = т, равна 1/М для всех О < гл < М. Ь) Если К ~ К', вероятность того, что Ь(К) = гл и ЦК') = га', равна 1/Мэ для всех О<тщ'<М.
с) Если К, К'и К"' различны, вероятность того, что ЦК) = т, Ь(К') = ш' н Ь(К") = гл", равна 1/Мз для всех О < т, т', гл" < М. 4) Если К, К', К" н К"' различны, вероятность того, что Ь(К) = гл, ЦК') = ш', Ь(К") = ги" и Ь(К'") = гль', равна 1/М для всех О < т, гл', ш", щ"' < М, ь 76.
(МЯХ) Предложите путь изменения (9) для ключей с переменной длиной, сохраняю- щего свойства универсального хеширования. 77. (МЯЯ) Пусть Н определяет универсальное семейство хеш-функций из 32-битовых клю- чей в 16-битовые (так что Н имеет 2зэ столбца, а в обозначениях упр. 72 ЛХ = 2'~), 256-битовый ключ можно рассматривать как конкатенацию восьми 32-битовых частей х!Хэхзхэхэхехгхз~ его можно отобразить в 16-битовый адрес при помощи хеш-функции Ьэ(Ьз(Ьэ(Ьт(хь)Ьз(хэ))Ьт(Ьг(хэ) Ь~(ха)))Ьз(Ьг(Ьг(хэ)Ьг(хе)) Ьэ(Ь~(хт)Ь~(хэ)))), где Ьм Ьэ, Ьз и Ьэ — случайно и независимо выбранные строки Н (здесь, например, Ь|(х~)Ь~(хэ) означает 32-бнтовое число, полученное конкатенацией Ь|(х~) и Ь,(хэ)).
Докажите, что вероятность того, что два различных ключа хешируются в один и тот же адрес, меньше 2 '~. (Для этой схемы требуется гораздо меньше случаиных выборов, чем для (9).) Она сделала из названий настоян)ий каш, Это Юк тОчно~. — ГРАНЗ' АЛЛЕН (ЕЙАНТ АССЕГч) (шатры сима ('Где 'Гелия от 5иелз), )869) "нА5н, и". Длл этого слова нет определении — никто не знает, что такое "лазн': — АМБРОЗ БИРС (АМВРОЕЕ В1ЕРСЕ) (дьявольский словарь ( Гне Оекй'з О)сзголагу), хроб) ' В переводе привлось использовать ачекь схожее по звччаиякз ) и лаже по смыслу) слово ккги, озяачакяпее армяиское горячее блкгдо из рублежя о мяса.
— Прим. перев, 6.5. ВЫБОРКА ПО ВТОРИЧНЫМ КЛЮЧАМ Мы зАкОнчили изучеНие поиска по первичным ключам, т, е, по ключам, которые однозначно определяют запись в файле. Однако иногда необходимо выполнить поиск, основанный на значениях других полей записей, помимо первичного ключа. Этн другие поля часто именуются вторичными ключами или атрибутами записи. Например, имея файл регистрации с информацией о студентах университета, можно найти всех второкурсников из Огайо, не специализирующихся по математике нли статистике, или всех незамужних франкоговорящих аспиранток...
В общем случае полагается, что в каждой записи содержится несколько атрибутов, и необходимо найти все записи с некоторыми значениями этих атрибутов. Определение требуемых записей называется запросам (~)иггл). Обычно запросы подразделяются на следующие трн типа. а) Проспюй запрос, определяющий конкретное значение некоторого атрибута, например "СПЕЦИАЛИЗАЦИЯ = ИАТЕИАТИКА" или "ИЕСТОЖИТЕЛЪСТВО.ШТАТ ОГАЙО' ! Ь) Защюс диапазона, запрашиваюпщй определенный диапазон значений некоторого атрибута, например "ЦЕНА < $18.00" нли "21 < ВОЗРАСТ < 23'*.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
