69. Пусть qk =pk+ pfc+i H----; тогда неравенство qk > max(0,1 - (k - 1)(M - n)/M) дает

нижнюю границу Cn = J2k>i Чк-

70. Люкер (Lueker) и Молодович (Molodowitch) [Combinatorica 13 (1993), 83-96] привели замечательно простое доказательство подобного результата, но у них появляется дополнительный множитель (log М) под знаком О; указанный результат получается тем же путем с помощью определенных трюков при оценке вероятностей. А. Р. Сигель (А. R. Siegel) и Ж. П. Шмидт (J. Р. Schmidt) показали, что в действительности ожидаемое количество проб при двойном хешировании составляет 1/(1 - а) Ч- 0{1/М) для фиксированного а = N/M. [Computer Science Tech. Report 687 (New York: Courant Institute, 1995).]

72. [J. Сотр. Syst. Sci. 18 (1979), 143-154.] (a) При данных ключах Ki, Kn и К вероятность того, что Kj находится в том же списке, что и К, равна < 1/М, если К ф Kj. Следовательно, ожидаемый размер списка равен < 1 4- (А - 1)/М.

(b) Предположим, что существует Q возможных символов и имеется М возможных вариантов выбора для каждого hj. Случайный выбор каждого hj эквивалентен выбору случайной строки из матрицы Н из М строк и Q столбцов с элементом h(xi... х/) = (hi(xi) -I- • • • Ч- hi{xi)) mod М в столбце xi... х;. В столбцах К = xi... xi и К = xi... xi с Xj ф xj для некоторого j имеем h{K) = (s 4- hj(xj))modM и h{K) = (s -f- hj{xj)) modM, где s = Eij hi(xi) и s = Eiji(t) независимы от hj. Значения hj{xj) - hj{xj) равномерно ргюпределены по модулю М; следовательно, мы имеем h{K) = h{K) с вероятностью 1 /М без учета значений s и s.

(c) Да; добавление любой константы к hj{xj) прибавляет к h{x) константу по модулю М.

73. (i) Это специальный вариант упражнения 72, (с), в котором каждый ключ рассматривается как последовательность битов, а не символов, (ii) Из доказательства (Ь) следует, что достаточно показать равномерность распределения hj{xj) - hj{xj) по модулю М при Xj ф xj. В действительности вероятность того, что hj{xj) = у и hj{xj) = у, равна 1/М для любых данных у и у, поскольку уравнения ajXj + bj = у и ajxj + bj = у по модулю с простым М имеют единственное решение {aj,bj) для любых данных {у, у).

Если М не является простым и р - простое число, большее, чем М, подобный результат имеет место, если предположить hj{xj) = ((ojXj 4-6j) modp) modM, где aj и bj выбраны случайным образом по модулю р. В этом случае семейство не является полностью универсальным, но достаточно близко к таковому для достижения практических целей: вероятность коллизии различных ключей не превышает 1/М + г(М - г)/Мр < 1/М -\-М/Ар, где г =-р mod М.

74. В целом, это утверждение ложно. Например, предположим, что М = А = п, и рассмотрим матрицу Н с () строками, по одной для каждого варианта размещения п нулей в различных столбцах; ненулевыми являются элементы 1, 2, ..., А-п слева направо в каждой строке. Эта матрица универсальна, потому что в каждой паре столбцов имеется (п-г) - < (п) () = R-l совпадений; однако число нулей в каждой строке составляет ф 0(1) + 0(N/M).

Примечание. Этот пример указывает, что ожидаемый размер списка существенно отличается от ожидаемого количества коллизий при вставке нового ключа. Рассмотрим предположение h(xi... х;) = hi(xi), где hi выбрано случайным образом. Такое семейство хеш-функций делает ожидаемый размер каждого списка равным N/M; конечно, это еще не универсальное семейство, потому что множество из N ключей, имеющих один и тот же первый символ xi, приведет к образованию одного списка размером А и пустых прочих списков. Ожидаемое количество коллизий будет равно А(А - 1)/2, однако для универсального хеш-семейства это число не превышает N(N - 1)/2М независимо от множества ключей.

с другой стороны, можно показать, что ожидаемый размер каждого списка в универсальном семействе равен 0{1)+0{N/\/M ). Предположим, что в строке h имеется zh нулей. Тогда в ней содержится как минимум () пар одинаковых элементов. Максимум Ea=i при условии J2h=i i2) - ()/• достигается, когда каждое Zh равно z, где (j) = ()/М, а именно

2 V 4 М V М

75. (а) Очевидно, что утверждение истинно, даже если /12, hi тождественно равны нулю. (Ь) Верно в соответствии с ответом к 72, (Ь). (с) Верно. Результат ясен, если все К, К и К" отличаются в некоторой позиции символа. В противном случае примем, что Xj = xj ф xJ и Хк ф хк - Xfc. Тогда величины hj{xj) + hk(xk), hj{xj) + hix) и hj{xj) + h{xk) независимы одна от другой, равномерно распределены и не зависят от других I - 2 символов ключей, (d) Неверно. Рассмотрим, например, случай для М = I = 2 с однобитовыми символами. Тогда все четыре ключа хешируются в одну и ту же позицию с вероятностью 1/4.

76. Используем h{K) = {hoil) + hi{xi)-{-----\-hi{xi)) mod М, где каждая функция hj выбирается, как в упр. 73. Случайные коэффициенты для hj (и при желании предварительно вычисленный массив значений) генерируются при первом появлении ключа длиной > j. Поскольку I не ограничено, матрица Н бесконечна; однако в реальной работе программы будет использоваться только ее конечная часть.

77. Пусть р < 2~* - вероятность того, что два 32-битовых ключа имеют один и тот же образ в Н. Наихудшая ситуация складывается, когда два данных ключа совпадают в семи из их восьми 32-битовых подключей; значит, вероятность коллизии равна 1 - (1 -р)" < 4р. [См. Wegman and Carter, J. Сотр. Syst. Sci. 22 (1981), 265-279.]

РАЗДЕЛ 6.5

1. Путь, описанный в указании, может быть преобразован посредством замены каждого идущего вниз шага из точки (г-1, j) к "новому рекордно низкому" значению (г, j - 1) шагом, идущим вверх. Если предпринимается с таких изменений, путь заканчивается в (т, п - 2( Ч-2с), где с>0ис>2< - п; следовательно, п - 2t + 2с > п - 2к. В перестановке, соответствующей измененному пути, наименьшие с элементов списка В отвечают измененным шагам вниз, а в списке А содержится ( - с элементов, соответствующих неизмененным шагам вниз.

Нетрудно увидеть, что при t = к построение обратимо; следовательно, строится в точности (1) перестановок. Заметим, что в соответствии с этим доказательством содержимое списков А и С может располагаться в произвольном порядке.

Примечание. Мы сосчитали эти пути в упр. 2.2.1-4 несколько иным способом. При к = [п/2] данное построение доказывает лемму Спернера, которая гласит, что невозможно иметь более („/2j) подмножеств множества {1, 2, ...,п}, таких, что ни одно подмножество не содержится в другом. [Эмануэль Спернер (Emanuel Sperner), Math. Zeitschrift 27 (1928), 544-548.] Если бы существовал такой набор подмножеств, каждая из () перестановок могла бы иметь не более одного из подмножеств в начальных позициях; в то же время каждое подмножество появляется в некоторой перестановке. Построение, использованное здесь, представляет скрытую форму более общей конструкции, с помощью которой И. Г. де Брейн (N. G. de Bruijn), К. ван Эббенхорст Тенгберген (С. van Ebbenhorst Tengbergen) и Д. Круйсвик (D. Kruyswijk) [Nieuw Archief voor Wisiunde (2) 23 (1951), 191-193] доказали обобщение леммы Спернера для мультимножеств: "Пусть М - мультимножество, содержащее п элементов (считая повторения). Набор всех [п/2 J-элементных мультиподмножеств М представляет собой наибольший возможный набор, такой, что ни одно мультиподмножество не содержится в другом". Например, наибольший такой набор

при М = {a,a,b,b,c,c} состоит из семи мультиподмножеств: {а,а,Ь}, {а, а, с}, {a,b,b}, {а, 6, с}, {а, с, с}, {b,b,c}, {6, с, с}. Этот набор соответствует семи перестановкам шести атрибутов (Al, Bi, А2, В2, Аз, Вз) для случая, когда запрос, включающий А{, содержит также Bi. Дополнительные комментарии по этому вопросу приводятся в статье С. Greene and D. J. Kleitman, J. Combinatorial Theory A20 (1976), 80-88.

2. Пусть aijk - список всех ссылок на записи, имеющие значения трех атрибутов (г, j, к), и предположим, что список аоп - самый короткий среди списков аои, аш, аио- Тогда списком с минимальной длиной является aooiaoiiainaioiaiooaiioaiiiaonaoio. Однако, если аоп пуст и пуст также любой из списков аооь аою и аюо, длина может быть сокращена путем удаления одного из двух вхождений ащ [CACJVf 15 (1972), 802-808].

3. (а) Зерна аниса и/или мед, возможно, в комбинации с мускатным орехом и/или ванилином. (Ь) Никакие.

4. Пусть pt - вероятность того, что запрос включает в точности t-битовые позиции, и пусть Pt - вероятность того, что t данных позиций в случайной записи равны 1. Тогда ответом будет J2t Pi минус вероятность того, что искомая запись действительно найдена; последняя вероятность равна (Г)/(), где N = (). По принципу включения и исключения

Pt = J2-iy Qf{n-j,k,r)/f(n,k,r),

где f(n, к, г) - количество возможных выборов г различных /г-битовых кодов атрибутов в п-битовых полях, а именно

/(п,/с,г)= ((р). При q = г имеем согласно упр. 1.3.3-26

pt=Y:M)iY){,i,)pt.<={l)EyyOn-j

Примечание. Приведенные выше вычисления впервые были выполнены в более общей форме в G. Orosz and L. Takacs, J. of Documentation 12 (1956), 231-234. Легко показать, что среднее значение ЕР равно п(1-/(п -1, k,q)/f(n, к, q)). Предположение о том, что коды случайных атрибутов в записях и запросах необязательно должны быть различными, как в случаях использования технологий Харрисона и Блюма, может быть проанализировано таким же образом с f(n,k,r) = (2). Когда параметры находятся в соответствующих диапазонах, получаем и (1 - е"""") и JptPt w Pn(i-exp(-fc,/n))-

6. L(t) = iy)irJj)Li(j)L2(t - j)/{"+) (следовательно, если Li(t) « JVia" и L2(t) и N2a-\ TO L(t) « NiNia).

7. (a) L(l) = 3, L(2) = if. (b) L(l) = 3, L(2) = 2, L(3) = 1. [Примечание. Три-виальное проецирующее отображение типа 00**-> О, 01**->1, 10**-2, 11**-3 представляет собой отображение, наихудший случай которого хуже, но средний - лучше: L(l) = 3, L(2) = 2l,L(3) = li.]

8. (а) При S = SoOUSil имеем ft(S) = ft(So USi) + ft-i(So) + ft-i(Si). Таким образом, ft(s,m) представляет собой минимум /((so, m - 1) 4-/t-i(so, m - 1) 4-/t-i (si, m-1) повеем So и si, таким, что 2"" > so > si > 0 и so Ч- si = s. Чтобы доказать, что минимум достигается для so = rs/2] si = [s/2J, можно использовать индукцию по m с очевидным результатом при m = 1: дано m > 2. Пусть gi(s) = ft(s,m - 1) и ht(s) = ft(s,m - 2). Тогда по индукции ((so) 4-fft-i(so) 4-( i(si) = /i(([so/2l) 4-/it-i([so/2]) + ht-i([so/2}) + ht-i([so/2]) + ht-2(\so/2]) + /i( 2(Lso/2j) + ht-i([si/2]) + ht-2(\si/2]) + /i( 2(Lsi/2j), что > 9t(iso/2] + [si/2]) 4-(-i([so/2] + rsi/2]) --t-i(Lso/2j + Lsi/2J). Если so > si --1, имеем