2011-gre-cs-practice-book.pdf/Q37 — различия между версиями
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q37-08c765 == <i>Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80…») |
StasFomin (обсуждение | вклад) |
||
| (не показано 6 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q37-08c765 == | == Вопрос: Q37-08c765 == | ||
| − | + | Хеш-функция h отображает 16-битовые входные значения на 8-битовые хеш-значения. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | Каково наибольшее значение k, такое что в любом наборе из 1000 входных значений существует хотя бы k входных значений, которые функция h отображает на одно и то же хеш-значение? | |
| − | + | ||
| − | + | ||
| − | + | ||
=== Ответы === | === Ответы === | ||
| − | + | * Правильный ответ: 4 | |
| − | + | * 3 | |
| + | * 10 | ||
| + | * 64 | ||
| + | * 256 | ||
| − | + | === Объяснение === | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | Для начала определим количество возможных различных хеш-значений. Так как хеш-функция возвращает 8-битовые значения, у нас есть <m>2^8 = 256</m> возможных уникальных хешей. | |
| − | + | ||
| − | + | ||
| + | Теперь рассмотрим задачу. Нам нужно найти максимальное число <m>k</m>, которое гарантирует, что среди любых 1000 входных значений найдется хотя бы <m>k</m> таких, которые имеют одинаковое хеш-значение. | ||
| − | === | + | Чтобы решить эту задачу, мы можем использовать принцип Дирихле. Этот принцип гласит, что если у вас больше объектов, чем ячеек, в которых они могут находиться, то хотя бы одна ячейка будет содержать более одного объекта. |
| − | < | + | |
| − | {{ | + | В нашем случае объекты — это входные значения (всего их 1000), а ячейки — это возможные хеш-значения (всего их 256). |
| + | |||
| + | Применяя принцип Дирихле, мы хотим распределить 1000 объектов между 256 ячейками таким образом, чтобы хотя бы одна ячейка содержала максимально возможное количество объектов. Для этого мы вычислим минимальное количество объектов, которое должно попасть в каждую ячейку, если бы распределение было равномерным: | ||
| + | |||
| + | <m>\text{{Минимальное количество объектов в каждой ячейке}} = \left\lfloor \frac{\text{{Всего объектов}}}{ \text{{Количество ячеек}}} \right\rfloor = \left\lfloor \frac{1000}{256} \right\rfloor = 3</m> | ||
| + | |||
| + | Это означает, что каждая ячейка гарантированно получит минимум 3 объекта. Однако нам нужно учесть, что некоторые ячейки могут получить больше объектов, поскольку общее количество объектов не делится ровно на количество ячеек. Чтобы найти максимальное количество объектов в одной ячейке, мы добавляем остаток от деления: | ||
| + | |||
| + | <m>\text{{Максимальное количество объектов в одной ячейке}} = 3 + 1 = 4</m> | ||
| − | + | Таким образом, гарантируется, что хотя бы одна ячейка содержит 4 объекта. Следовательно, наибольшее значение <m>k</m>, при котором в любом множестве из 1000 входных значений обязательно найдутся хотя бы <m>k</m> элементов с одним и тем же хеш-значением, равно 4. | |
| − | + | {{cstest-source|2011-gre-cs-practice-book.pdf|33|37}} | |
| − | + | ||
| − | + | ||
| − | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 16:06, 19 декабря 2024 (UTC)}} | |
| − | + | [[Категория:Криптография]] | |
| + | [[Категория:Хэш-таблицы]] | ||
Текущая версия на 16:06, 19 декабря 2024
Вопрос: Q37-08c765
Хеш-функция h отображает 16-битовые входные значения на 8-битовые хеш-значения.
Каково наибольшее значение k, такое что в любом наборе из 1000 входных значений существует хотя бы k входных значений, которые функция h отображает на одно и то же хеш-значение?
Ответы
- Правильный ответ: 4
- 3
- 10
- 64
- 256
Объяснение
Для начала определим количество возможных различных хеш-значений. Так как хеш-функция возвращает 8-битовые значения, у нас есть возможных уникальных хешей.
Теперь рассмотрим задачу. Нам нужно найти максимальное число , которое гарантирует, что среди любых 1000 входных значений найдется хотя бы таких, которые имеют одинаковое хеш-значение.
Чтобы решить эту задачу, мы можем использовать принцип Дирихле. Этот принцип гласит, что если у вас больше объектов, чем ячеек, в которых они могут находиться, то хотя бы одна ячейка будет содержать более одного объекта.
В нашем случае объекты — это входные значения (всего их 1000), а ячейки — это возможные хеш-значения (всего их 256).
Применяя принцип Дирихле, мы хотим распределить 1000 объектов между 256 ячейками таким образом, чтобы хотя бы одна ячейка содержала максимально возможное количество объектов. Для этого мы вычислим минимальное количество объектов, которое должно попасть в каждую ячейку, если бы распределение было равномерным:
Это означает, что каждая ячейка гарантированно получит минимум 3 объекта. Однако нам нужно учесть, что некоторые ячейки могут получить больше объектов, поскольку общее количество объектов не делится ровно на количество ячеек. Чтобы найти максимальное количество объектов в одной ячейке, мы добавляем остаток от деления:
Таким образом, гарантируется, что хотя бы одна ячейка содержит 4 объекта. Следовательно, наибольшее значение , при котором в любом множестве из 1000 входных значений обязательно найдутся хотя бы элементов с одним и тем же хеш-значением, равно 4.
Исходники — вопрос 37 на 33 странице книги «2011-gre-cs-practice-book.pdf»