Программирование: теоремы и задачи (стр. 27 )

ков с помощью переменных

Содержание: array [1..n] of T;

Следующий: array [1..n] of 1..n;

ПервСвоб: 1..n;

Вершина: array [1..k] of 1..n;

так же, как мы это делали для k стеков ограниченной суммарной

длины. Напишите соответствующие программы. (Теперь с удалением

будет меньше проблем.)

Решение. Перед началом работы надо положить Вершина[i]=0

для всех i=1..k, и связать все места в список свободного

пространства, положив ПервСвоб=1 и Следующий[i]=i+1 для

i=1..n-1, а также Следующий[n]=0.

function принадлежит (t: T): boolean;

| var i: integer;

begin

| | i := Вершина[h(t)];

| i := Вершина[h(t)];

| {осталось искать в списке, начиная с i}

| while (i <> 0) and (Содержание[i] <> t) do begin

| | i := Следующий[i];

| end; {(i=0) or (Содержание [i] = t)}

| belong := Содержание[i]=t;

end;

procedure добавить (t: T);

| var i: integer;

begin

| if not принадлежит(t) then begin

| | i := ПервСвоб;

| | {ПервСвоб <> 0 - считаем, что не переполняется}

| | ПервСвоб := Следующий[ПервСвоб]

| | Содержание[i]:=t;

| | Следующий[i]:=Вершина[h(t)];

| | Вершина[h(t)]:=i;

| end;

end;

procedure исключить (t: T);

| var i, pred: integer;

begin

| i := Вершина[h(t)]; pred := 0;

| {осталось искать в списке, начиная с i; pred -

| предыдущий. если он есть, и 0, если нет}

| while (i <> 0) and (Содержание[i] <> t) do begin

| | pred := i; i := Следующий[i];

| end; {(i=0) or (Содержание [i] = t)}

| if Содержание[i]=t then begin

| | {элемент есть, надо удалить}

| | if pred = 0 then begin

| | | {элемент оказался первым в списке}

| | | Вершина[h(t)] := Следующий[i];

| | end else begin

| | | Следующий[pred] := Следующий[i]

| | end;

| | {осталось вернуть i в список свободных}

| | Следующий[i] := ПервСвоб;

| | ПервСвоб:=i;

| end;

end;

11.2.2. (Для знакомых с теорией вероятностей.) Пусть

хеш-функция с m значениями используется для хранения множества,

в котором в данный момент n элементов. Доказать, что математи-

ческое ожидание числа действий в предыдущей задаче не превосхо-

дит С*(1+n/m), если добавляемый (удаляемый, искомый) элемент t

выбран случайно, причем все значения h(t) имеют равные вероят-

ности (равные 1/m).

Решение. Если l(i) - длина списка, соответствующего

хеш-значению i, то число операцией не превосходит C*(1+l(h(i)));

усредняя, получаем искомый ответ, так как сумма всех l(i) равна

n.

Эта оценка основана на предположении о равных вероятностях.

Однако в конкретной ситуации всё может быть совсем не так, и

значения хеш-функции могут "скучиваться": для каждой конкретной

хеш-функции есть "неудачные" ситуации, когда число действий ока-

зывается большим. Приём, называемый "универсальным хешировани-

ем", позволяет обойти эту проблему. Идея состоит в том, что бе-

рётся семейство хеш-функций, причем любая ситуация оказывается

неудачной лишь для небольшой части этого семества.

Пусть H - семейство функций, каждая из которых отображает

множество T в множество из n элементов (например, 0..n-1). Гово-

рят, что H - универсальное семейство хеш-функций, если для любых

двух различных значений s и t из множества T вероятность события

"h(s)=h(t)" для случайной функции h из семейства H равна 1/n.

(Другими словами, те функции из H, для которых h(s)=h(t), сос-

тавляют 1/n-ую часть всех функций в H.)

Замечание. Более сильное требование к семейству H могло бы

состоять в том, чтобы для любых двух различных элементов s и t

множества T значения h(s) и h(t) случайной функции h являются

независимыми случайными величинами, равномерно распределенными

на 0..n-1.

11.2.3. Пусть t[1]..t[u] - произвольная последовательность

различных элементов множества T. Рассмотрим количество действий,

происходящих при помещении элементов t[1]..t[u] в множество, хе-

шируемое с помощью функции h из универсального семейства H. До-

казать, что среднее количество действий (усреднение - по всем h

из H) не превосходит C*u*(1+u/n).

Решение. Обозначим через m[i] количество элементов последо-

вательности, для которых хеш-функция равна i. (Числа

m[0]..m[n-1] зависят, конечно, от выбора хеш-функции.) Коли-

чество действий, которое мы хотим оценить, с точностью до посто-

янного множителя равно сумме квадратов чисел m[0]..m[n-1]. (Если

k чисел попадают в одну хеш-ячейку, то для этого требуется при-

мерно 1+2+...+k действий.) Эту же сумму квадратов можно записать

как число пар <p, q>, для которых h[t[p]]=h[t[q]]. Последнее ра-

венство, если его рассматривать как событие при фиксированных p

и q, имеет вероятность 1/n при p<>q, поэтому среднее значение

соответствующего члена суммы равно 1/n, а для всей суммы получа-

ем оценку порядка u*u/n, а точнее u*u/n + u, если учесть члены с

p=q.

Оценка этой задачи показывает, что в на каждый добавляемый

элемент приходится в среднем C*(1+u/n) операций. В этой оценке

дробь u/n имеет смысл "коэффициента заполнения" хеш-таблицы.

11.2.4. Доказать аналогичное утверждение для произвольной

последовательности операций добавления, поиска и удаления (а не

только для добавления, как в предыдущей задаче).

Указание. Будем представлять себе, что в ходе поиска, до-

бавления и удаления элемент проталкивается по списку своих кол-

лег с тем же хеш-значением, пока не найдет своего двойника или

не дойдет до конца списка. Будем называть i-j-столкновением

столкновение t[i] с t[j]. Общее число действий примерно равно

числу всех столкновений плюс число элементов. При t[i]<>t[j] ве-

роятность i-j-столкновения равна 1/n. Осталось проследить за

столкновениями между равными элементами. Фиксируем некоторое

значение x из множества T и посмотрим на связанные с ним опера-

ции. Они идут по циклу: добавление - проверки - удаление - до-

бавление - проверки - удаление - ... Столкновения между ними

происходят между добавляемым элементом и следующими за ним про-

верками (до удаления включительно), поэтому общее их число не

превосходит числа элементов, равных x.

Теперь приведем примеры универсальных семейств. Очевидно,

для любых конечных множеств A и B семейство всех функций, отоб-

ражающих A в B, является универсальным. Однако этот пример с

практической точки зрения бесполезен: для запоминания случайной

функции из этого семейства нужен массив, число элементов в кото-

ром равно числу элементов в множестве A. (А если мы можем себе

позволить такой массив, то никакого хеширования нам не требует-

ся!)

Более практичные примеры универсальных семейств могут быть

построены с помощью несложных алгебраических конструкций. Через

Z[p] мы обозначаем множество вычетов по простому модулю p, т. е.

{0,1,...,p-1}; арифметические операции в этом множестве выполня-

ются по модулю p. Универсальное семейство образуют все линейные

функционалы на Z[p] в степени n со значениями в Z[p]. Более под-

робно, пусть a[1],...,a[n] - произвольные элементы Z[p];

рассмотрим отображение

h: <x[1]...x[n]> |-> a[1]x{1]+...+a{n]z[n]

Мы получаем семейство из (p в степени n) отображений, параметри-

зованное наборами a[1]...a[n].

11.2.5. Доказать, что это семейство является универсальным.

Указание. Пусть x и y - различные точки пространства Z[p] в

степени n. Какова вероятность того, что случайный функционал

принимает на них одинаковые значения? Другими словами, какова

вероятность того, что он равен нулю на их разности x-y? Ответ

дается таким утверждением: пусть u - ненулевой вектор; тогда все

значения случайного функционала на нем равновероятны.

В следующей задаче множество B={0,1} рассматривается как

множество вычетов по модулю 2.

11.2.6. Семейство всех линейных отображений из (B в степени

m) в (B в степени n) является универсальным.

Родственные идеи неожиданно оказываются полезными в следу-

ющей ситуации (рассказал Д. Варсонофьев). Пусть мы хотим написать

программу, которая обнаруживала (большинство) опечаток в тексте,

но не хотим хранить список всех правильных словоформ. Предлага-

ется поступить так: выбрать некоторое N и набор функций

f[1],...,f[k], отображающих русские слова в 1..N. В массиве из N

битов положим все биты равными нулю, кроме тех, которые являются

значением какой-то функции набора на какой-то правильной слово-

форме. Теперь приближённый тест на правильность словоформы та-

ков: проверить, что значения всех функций набора на этой слово-

форме попадают на места, занятые единицами.

Глава 12. Множества и деревья.

12.1. Представление множеств с помощью деревьев.

Полное двоичное дерево. T-деревья.

Нарисуем точку. Из нее проведем две стрелки (влево вверх и

вправо вверх) в две другие точки. Из каждой из этих точек прове-

дем по две стрелки и так далее. Полученную картинку (в n-ом слое

будет (2 в степени (n - 1)) точек) называют полным двоичным де-

ревом. Нижнюю точку называют корнем. У каждой вершины есть два

сына (две вершины, в которые идут стрелки) - левый и правый. У

всякой вершины, кроме корня, есть единственный отец.

Пусть выбрано некоторое конечное множество вершин полного

двоичного дерева, содержащее вместе с каждой вершиной и всех ее

предков. Пусть на каждой вершине этого множества написано значе-

ние фиксированного типа T (то есть задано отображение множества

вершин в множество значений типа T). То, что получится, будем

называть T-деревом. Множество всех T-деревьев обозначим Tree(T).

Рекурсивное определение. Всякое непустое T-дерево разбива-

ется на три части: корень (несущий пометку из T), левое и правое

поддеревья (которые могут быть и пустыми). Это разбиение уста-

навливает взаимно однозначное соответствие между множеством не-

пустых T-деревьев и произведением T * Tree (T) * Tree (T). Обоз-

начив через empty пустое дерево, можно написать

Tree (T) = {empty} + T * Tree (T) * Tree (T).

Поддеревья. Высота.

Фиксируем некоторое T-дерево. Для каждой его вершины x оп-

ределено ее левое поддерево (левый сын вершины x и все его по-