AOP_Tom3 (1021738), страница 161

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 161)

При ЛХ < 6 наилучшая схема с единственным хешированном является циклической. Справедливо ли зто для любого ЛХ? 63. [МЯБ[ Если в хеш-таблице выполняются случайные вставки и удаления, то сколько независимых вставок в среднем следует сделать, чтобы все М позиций были занятыми в то или иное время? (Это значение представляет собой среднее время работы на отказ метода удаления, просто помечающего ячейки как 'удаленные".) 64.

[ЛЦ!) Проанализируйте ожидаемое поведение алгоритма К (удаление с линейным исследованием). Сколько раз в среднем выполняется шаг К4? ь 65. [Я0) (Ключи переменной длины.) Во многих приложениях с хеш-таблицами используются ключи, представляющие набор символов произвольной длины. В таких приложениях нельзя просто хранить ключ в таблице, как в программах из этого раздела Каким образом можно организовать работу хе>п-таблиц с ключами переменной длины на ИХ!-компьютере? ь 66. [Я5[ (Оле Амбль (О!в Ащ!>!е), 1973.) бМожно ли так вставить ключи в открытую хештаблицу с использованием их .ивлового или алфавитного порядка, чтобы в случае поиска по алгоритму Е или Р можно было сдслать вывод о вго неудачном завершении., встретив ключ, меньший, чем аргумент поиска? 6Т. [М4![ Пусть !т' ключей с хеи>-адресами а> аг...

ая вставлиются в хеш-таблицу согласно алгоритму Е и пусть б!> — смещение 2-го ключа из его начального положения а„: тогда Ся = 1+ (б!>+б!г+ +йя)/Аб Теорема Р гласит, что перестановка а не влияет на сумму б!> х б?г + . + б!л, однако такая перестановка может значительно измоннп сумму б!> + б(г + + б!д. Например, хеш-последовательность 1 2,.

>>б-1 !б' — 1 делает б(> б(г ... а>у > йя равным О О ... О Ж вЂ” 1 н 2 б!г = (Аб — 1)г, в то время как ее зеркальное отражение Аб — 1 ббб — 1 ... 2! приводит к более бцнвилнзованноъбу" перемещению О 1 ... 1 1б для которого 2 0> = Аб — 1. а) Какое размещение а> аг ., ая минимизирует 2 >1,? 1>) поясните, каким образом следует модифицировать алгорнтьб ь, чтобы поело каждой вставки сохранялся набор перемещений с наименьшей дисперсией. с) Определите среднее значение 2„ 0> с указанной модификацией н без нее. 68. [М41[ Чему равна дисперсия среднего числа проб в случае успешного поиска по алгоритму !.? В частности, чему равно среднее (с(> + б!г + + >4н) в обозначениях упр.

67? 69. [МЯ5[ (Эндрю Яо (Апйгев Уао) ) Докажите, что схемы циклического единственного хеширования удовлетворяют неравенству С' м > -'(1 -Ь 1/(1 — и)) в смысле упр. 62. [Указание. Покажите, что для неудачного поиска требуется ровно?с проб с вероятностью р, «(М вЂ” Н)/М[ 76. [Йм43[ Докажите, что ожидаемое количество проб, ббеобходнлбых для вставки (ам+ 1)-го элемента при помощи двойного хеширования, не превышает ожидаемого количества б, ь * ( бй 'Обьбмб>м) следовании. Т1. [40) Поэкспериментируйте с поведением алгоритма С при его адаптации к внешнему поиску так, как описано в тексте.

ь 72. [МЯЯ[ (Универсальное хеширование.) Представьте гигантскую матрицу Н, имеющую по одному столбцу для каждого возможного ключа К. Элементы Н представляют собой числа от О до М вЂ” 1; строки Н представляют хеш-функции. Мы говорим, что Н обтределяет универсальное семсйсбпва ХСШ->дУикций, если любые два столбца совпадают ие более чем в Н/М строках, где Н -- общее количество строк. а) Докажите, что если Н универсальна в этом смысле н хеш-функция й выбирается случайным образом из строки Н, то ожидаемый размер списка, содержащего все данные ключи К в методе раздельных цепочек (см. рнс. 38) после вставки любого множества различных ключей К>, Кг, ..., Кя будет равен «1 4- бб/М.

Ь) Предположим, что каждый Л в (9) представляет собой случайно выбранное отображение множества всех символов на множество (О, 1,..., М вЂ” 1). Покажите, что это соответствует универсальному семейству хеш-функций. с) Останется ли результат (Ь) справедливым, если Л,(0) = 0 для всех 1, но Л (х) г.гучайно при х 88 О? ТЗ. (МЯб) (Картер (Сагсег) и Вегман (Чгейшап).) Покажите, что п. (Ь) предыдущего упражнения выполняется, даже когда Л, не являются полностью случайными функциямн, но имеют один из следующих видов.

(!) Пусть хг — двоичное число (Ь 1„»...Ь11Ь„в)г. Тогда Лг (хг) = (а Ш»Ьгщ» + 4-а„1Ь11+ агвЬ18) шос1 М, где каждое а,н выбирается случайно по модулю М. (В) Пусть М вЂ” простое число; положим 0 < х, < М. Тогда Л,(хг) = (а,х, + Ь,) шог(М, где аг и Ь, выбираются случайным образом по модулю М. 74. (МЯЯ) Пусть Н определяет универсальное семейство хеш-функций. Докажите или опровергните шгедующее. Даны Н различных столбгшв н некоторая 1лучайным образом выбранная строка.

Прп этом ожидаемое чишю пулей в этой строке, принадлежащих выбранным столбцам, равно 0(1) + 0(1у/М). (Таким образом. каждый список в методе раздельных цепочек будет иметь ожидаемый размер.) Тб. (МЯб) Докажите или опровергните следующие утверждения о хеш-функцин Л из (9), если Лг продставляют собой независимые случайные функции. а) Вероятность того, что Л(К) = гп, равна 1/М для всех 0 < гп < М. Ь) Если К 48 К', вероятность того, что Л(К) = гп и Л(К') = т', равна 1/Мг для всех О<тт'<Лг.

с) Если К, К' и К" различны, вероятность того, что Л(К) = т, Л(К') = т' и Л(К") = ш'т, равна 1/Мн для всех 0 < т, т', т ' < М. 4)) Егзн К, К', К" и К"' различны, вероятность того, что Л(К) = пй Л(К ) = гп', Л(К" ) = гпа н Л(Ка') = т", равна 1/М4 для всех 0 < т, т, т~, т ~ < М.

ь Тб. (МЯ!) Предложите путь изменения (9) для ключей с переменной длиной, сохраняющего свойства универсального хеширования. 77. (МЯЯ) Пусть Н определяет универсальное семейство хеш-функций нз 32-битовых ключей в 16-битовые (так что Н имеет 287 столбца, а в обозначениях упр. 72 ЛХ = 218). 25б-битовый ключ можно рассматривать как конкатенацию восьми 32-битовых чнстей Х!згХЗх4ХНХГХ7Х8; ого можно отобразить в 16-битовый адрес при помощи хеш-функции /14 (Лз (Л7(711(хг) Л1(х г) ) Лг (Л1(хн) Л1(х4) )) Л8 (Лг(Л1(хн) Л1(хв) ) Лг (Л1 (х7) Ьц (хн) ) ) ), ГДЕ Л1, Лг, Лн н Л4 — СлуЧайНО И НЕЗависимо выбранные строки Н (здесь, нш1РимеР, Л1(х1)Л1(хг) означает 32-битовое число, полученное конкатенацией 711(х1) и Л1(хг)). Докажите, что вероятность того, что два различных ключа хешируются в один и тот же адрес, меньше 2 .

[Для этой схемы требуется гораздо меньше случаиных выборов, чем — 14 для (9).) Она сделала нз названий настоящий хаш, это уж точно'~. — ГРАНТ АЛЛЕН (БРАНТ АССЕН) ~шатры сина (тпе тепрз ог зпегп), заар) "Ндлн, х". Для этого слова нет определения — никто не знает, что такое "пазпс — АМБРУАЗ БИРС (АМВЯОЬЕ В~ЕНСЕ) ~дьявольский словарь ГТпе Овей'з Русйопагу), зяаб) * В переводе пришлось использовать очень схожее по звччанню !н лаже по смыслу) слово хаш, означающее армянское горячее блюдо нз рубленого мнса, .

Прим. перев. ОТВЕТЫ К УПРАЖНЕНИЯМ ")нег, довольно.' — сказал возмущенный отец. — Есть граница любому терпенью. Если пятый вопрос гы задашь наконец, Сосчитаешь ступень за ступенью!"* — льюис кэррол (ье>)у>5 сдн>эосат), длиса я стране чудес, гл. 5. (1352) ПРИМЕЧАНИЯ К УПРАЖНЕНИЯМ 1. Задача средней сложности для читателей с математическим уклоном. 3.

См, И>. 3. ЙеЪедие, Тор>ся >и Китбег ТЬеогу 2 (Веаб)пб, Маяя. Аг>б>яоп-ЪЮея\еу. 1956), СЬар>ег 3; Р. Н>ЬепЬо>т, 13 Ьесгигея оп Гегтаг'я Ьаяс ТЬеогет (Хен Уог>с Зрг>ибер-Уег>аб, 1979); А. %'1>ея, Апаа>я ог" Ма> Ьетацгя 141 (1995), 443-551. РАЗДЕЛ 5 1. Пусть р(1)... р(п) и д(1)...

у(п) — две различные перестановки, удовлетворяющие этим условиям, и пусть г — минимальный индекс, при котором р(г) ~ 9(г). Тогда р(г) = д(1) при некоторых >», а д(1) = р(>г) при некоторых >с > г. Поскольку Крб> < Кр>ь> = Кэб) < Кы ) = Крн), имеем Кр>Л = Ксб)> а так как сортировка устойчива, то р(г) < р(>р) = 9(г) < д(1) = р(1), чего быть не может, 2. Да, если все операции сортировки были устойчиямми.

(В противном случае этого утверждать нельзя.) Ясно, что Алиса и Крис получили одинаковые результаты; то же самое получил и Билл, так как вследствие устойчивости при равных больших ключах малые ключи расположились в порядке неубывапия. Формальное доказательство: пусть после сортировки по малым ключам Билл получил Нр»>... Нюн) —— Н',... Нн, а после второй сортировки по большим ключам Н, >>>... Н >н) = Н>Ы>>))». Н>й>ь )) НужнО показать что при 1 < г < Х (кр>г>л> ьрыр))) < (кры>н.>)).'ьры>>ьг))). Если Крмб)) ф Крйц).р»>, то Кр>яь» < Кр~,,н,,>)> если же Кайн>) = Кр>мы))>, то К',> —— К'Ь„», и тогда 9(1) < д(г+ 1).

Следовательно, >г'Ь> < >р'б+», т. е Ьр> Ь)> < Ьр>яба,>). 3. Всегда можно собрать вместе записи с одинаковыми ключами, сохранна при этом их относительное расположение; тогда в последующих операциях каждая такая группа рассматривается как неделимое целое.

Следовательно, можно считать, что все ключи различны. Пусть а < Ь < с < а; эти три ключа можно упорядочить так: або, Ьса или саЬ. Далее, если упорядочены Аг — 1 различных ключей тремя способал>и, можно это сделать и для >У ключей, поскольку при К> « Кн-р > Кн либо К,. > < Кн < К, для некоторого г, либо К,ч < К>. Лереяод С. Я. Маршака. 4. Сначала сравним слава, не обращая внимания на регистр символов, затем воспользуемся регистром символов для уточнения порядка.

Характеристики

Список файлов книги