Таблицы Брадиса

Насколько это близко к идеалу?

Насколько это близко к идеалу?

Математическое просвещение - Винберг Э. Б

Для 8 вершин есть контрпример (это следует из утверждения 3).

НИЖНИЕ ГРАНИЦЫ

Итак, в конечном счёте мы нашли (даже двумя разными способами) решение задачи за 16 попыток. Насколько это близко к идеалу? Более об­що, каковы нижние оценки для числа попыток, необходимых для решения теста длины 30?

Ниже — один из возможных подходов к проблеме нижних границ.

Во-первых, если мы в проделанных попытках поменяем на противопо­ложные все свои ответы на один и тот же вопрос, то все результаты этих попыток изменятся на 1 — увеличатся, если мы поменяли неправильный ответ на правильный, и уменьшатся в противном случае. Поэтому если какой-то алгоритм позволяет узнать правильные ответы на все вопросы, то можно поменять в нем ответы так, чтобы в первой его попытке на все вопросы отвечать «да», — в результате тоже должен получиться работа­ющий алгоритм.

Пусть ответ на первую попытку был равен 15. Это означает, что число вариантов уменьшилось с 2[50] до = 155 117 520. Если в любой из сле­дующих попыток мы дали чётное число ответов «нет», то ответом будет нечётное число от 1 до 29 (15 возможных ответов), а если количество от­ветов «нет» чётно, то ответом будет чётное число от 0 до 30 (16 ответов). Итого в каждом случае число вариантов может сократиться не более чем в 16 раз, поэтому после 6 следующих попыток может остаться не менее чем (лб) /166 вариантов заполнения теста. Целая часть этого числа больше 1 — она равна 8. Таким образом, 7 попыток не хватит (даже при адаптивном алгоритме).

Обобщение этого подхода даёт результат 1 + log^ (к), где K = N/2.

СПИСОК ЛИТЕРАТУРЫ

[1]  http://www.research.att.com/~njas/sequences/