Участник:Олеся Кузнецова/Задача random-bit-generator — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
Строка 1: Строка 1:
<latex>
+
* [[Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/Модификация random-bit-generator]]
Задача:
+
Имеется генератор случайных битов, который выдаёт 0 или 1 с вероятностью $\frac{1}{2}$. Предложите алгоритм,
+
который, используя данный генератор, возвращает 0 с вероятностью $\frac{1}{3}$ и 1 c вероятностью $\frac{2}{3}$. Оцените
+
время работы вашего алгоритма в среднем и в худшем случае. (Под временем работы в этой задаче
+
будем понимать количество битов, которые нужно сгенерировать генератором, чтобы получить один бит
+
на выходе).
+
  
Ее решение:
+
<latex>
 
Алгоритм следующий: генерируем последовательность из трех бит до тех пор, пока не получится 000, 001 или 011. Если получилось 000,
 
Алгоритм следующий: генерируем последовательность из трех бит до тех пор, пока не получится 000, 001 или 011. Если получилось 000,
 
возвращаем 0, если 001 или 011 - 1. Вероятность получить 0, таким образом, равна
 
возвращаем 0, если 001 или 011 - 1. Вероятность получить 0, таким образом, равна
Строка 30: Строка 24:
 
</latex>
 
</latex>
  
[[Категория:Решения]]
+
[[Категория:S1]]

Текущая версия на 04:01, 16 мая 2019