Изменения

Перейти к: навигация, поиск

Список заданий по продвинутым алгоритмам 2021 осень

388 байт добавлено, 16:44, 18 октября 2021
Нет описания правки
# Известно, что у учителя есть $2^k$ яблок для некоторого целого неотрицательного $k$. На глазах у студентов он съедает одно яблоко, а остальное раздает ученикам А и В, чтобы ни один из них не видел, сколько получает другой. А и В не знают числа $k$. Они могут показать друг другу по одному знаку из трёх возможных: почесать голову правой, левой или обеими руками. К удивлению учителя, ученики всегда знают, кто получил больше яблок или что учитель съел единственное яблоко сам. Как такое возможно?
# Вероятностный алгоритм поиска минимума некоторый функции от входных данных размера $n$ работает за полином $p(n)$ и дает верный ответ с вероятностью $1/2$. Как найти верный ответ с вероятностью $99/100$ за полином от $n$?
# Вероятностный алгоритм проверки некоторого предиката от входных данных размера $n$ работает за полином $p(n)$ и дает верный ответ с вероятностью $1/2$. Можно ли найти верный ответ с вероятностью $99/100$ за полином от $n$?# Вероятностный алгоритм проверки некоторого предиката от входных данных размера $n$ работает за полином $p(n)$ и дает верный ответ с вероятностью $2/3$. Как найти верный ответ с вероятностью $99/100$ за полином от $n$?
Анонимный участник

Навигация