Что можно почитать, чтобы понять, что происходит в 3 задаче из листка?

Question

Что можно почитать, чтобы понять, что происходит в 3 задаче из листка?

2 Ответы

Vladimir Kuznetsov · Answer 1 · 2018-12-05T10:53:01+0000

Решить задачу 2 и вникнуть в смысл мат ожидания.

Для 2 мне помогла (и по факту решила) https://neerc.ifmo.ru/wiki/index.php?title=Универсальное_семейство_хеш-функций

Мат ожидание - среднее значение случайной величины. По большому счету, этого хватило сдать 3ю.

admin · Answer 2 · 2018-12-05T21:15:13+0000

Постараюсь пояснить условие.

Итак, есть некоторое множество $H=\{h_1, h_2, \dots, h_k\}$ - функций из множества $U$ во множество $Z_n=\{0,1, \dots, n-1\}$ .

Первое условие

$Pr[h(x)=i] \leq 1/n \ \ \ (1)$

означает следующее. Зафиксируем некоторые $x \in U$ и $i \in Z_n$ . Переберем все функции $h \in H$ и для каждой из них проверим, верно ли то, что $h(x) = i$ . Условие (1) означает, что доля тех функций, для которых $h(x) = i$ верно, ко множеству всех функций $h \in H$ , не превышает $1/n$ .

Рассмотрим второе условие

$E(|\{y \in S|h(x)=h(y)\}|) \leq 1 \ \ \ (2)$

Зафиксируем некоторый $x \in U$ и будем перебирать все функции $h \in H$ . Для каждой конкретной функции $h$ рассмотрю количество $y \in S$ , для которых $h(x) = h(y)$ . Обозначу эту величину $R(h)$ .

Итак,

$R(h)= |\{y \in S|h(x)=h(y)\}|.$

Величина $R(h)$ может принимать разные значения: большие, если для данной функции $h$ нашлось много $y \in S$ , для которых $h(x) = h(y)$ , или $R(h)=0$ , если для данной функции $h$ не нашлось ни одного $y \in S$ , для которого верно $h(x) = h(y)$ .

Итак, условие (2) означает следующее: среднее значение $R(h)$ по всем $h$ не превышает 1, т.е.

$\frac{R(h_1)+R(h_2) + \dots + R(h_k)}{k} \leq 1$

В задаче требуется ответить на вопрос. Следует ли второе условие из первого. Если да, то доказать, если нет, то построить контрпример.

Что можно почитать, чтобы понять, что происходит в 3 задаче из листка?

Пожалуйста, войдите или зарегистрируйтесь для публикации ответа на этот вопрос.

2 Ответы

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.