В структуре данных находится k-элементное подмножество A n-элементного множества. Необходимо проверить, принадлежит ли A элемент x. Для этого можно сделать не более t запросов к структуре: каждый запрос q представляет собой конечную строку битов, ответ на каждый запрос — один бит.

Структура данных представляет собой таблицу с двумя столбцами: первый столбец состоит из всевозможных запросов q (известных заранее), а правый из битов-ответов на запрос – правый столбец формируется после загрузки в структуру множества A. Пусть s(n, k, t) – минимальное количество строк в такой таблице которое достаточно отвести под такую структуру данных.

  1. Чему равно s(n, k, 1)?

  2. Найдите min(s(n, k, t)), при каком t он достигается?

задан 24 Мар 2:05

изменен 24 Мар 11:11

Из описание непонятно, что представляет собой запрос (сколько в нём бит, что он сам по себе означает и т.п.). Также надо объяснить, что означает положительный или отрицательный ответ на него.

(24 Мар 8:21) falcao

@falcao Запрос - это множество S⊆{1,...,N}, где N - кол-во элементов в структуре, по условию задачи просто какое-то конечное число бит. Ответ положительный, если x∈S и отрицательный иначе, содержит в себе один бит.

Пример: для структуры данных бинарное дерево необходимо совершить log_2(N) запросов

(24 Мар 11:40) Наум Петров

@a_b_c: пока не понимаю постановку задачи. Можно ли объяснить простым языком (скажем, на уровне формулировок олимпиадных задач)? Изначально можно подумать на следующее: загадано число x от 1 до n. Можно задавать вопросы в форме k-элементного подмножества, получая ответ, принадлежит ли ему x. И тогда можно говорить о минимальном числе вопросов, которые задаются заранее, и требуется гарантированно угадать число. Но тогда непонятна роль параметра t.

(24 Мар 14:57) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×230
×142

задан
24 Мар 2:05

показан
48 раз

обновлен
24 Мар 14:57

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru