Вероятность/Задачи/eupce-1-18 — различия между версиями

Текущая версия на 16:58, 17 мая 2023

• Есть функция
• и известно что .

Единственный способ вычисления F — использовать таблицу поиска, в которой хранится значения F. К сожалению, злой противник изменил значение 1/5 записей в этой таблице.

Опишите простой рандомизированный алгоритм, который, учитывая входной Z, выводит значение, которое равняется f(z) с вероятностью не менее 1/2.

Ваш алгоритм должен работать для каждого значения Z, независимо от того, какие записи изменил противник.

Дополнительно, предположим, вам разрешено повторить этот ваш начальный алгоритм три раза. Как этим воспрользоваться, чтобы максимально увеличить вероятность правильного ответа, и какова эта вероятность?