эксперимент
Nov. 29th, 2015 12:02 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
a_shenТут недавно обсуждалась (простая) задача по теории вероятностей - просьба к читателям, изучавшим эту науку, потратить минуту или две и написать в комментарии, как они её решали бы и насколько эта задача, по их мнению, лёгкая.
Есть вероятностный алгоритм, который для простого числа всегда говорит, что оно простое, а для составного числа говорит, что оно составное в 90% случаев. (Реальные алгоритмы действуют лучше, и не одинаково для всех составных чисел, но примем такую условность и предположим, что рассматриваемый алгоритм действительно таков.) Некто хочет найти 1000-битовое простое число так: выбирает случайные 1000 битов бросанием монеты и проверяет, не получилось ли простое число по этому алгоритму, при этом делает две проверки для повышения надёжности (пока не найдётся число, которое дважды будет названо простым этим алгоритмом). Какова вероятность, что первое найденное им число действительно окажется простым?
(Для чистоты эксперимента комментарии вначале скрываются - потом будут открыты)
Есть вероятностный алгоритм, который для простого числа всегда говорит, что оно простое, а для составного числа говорит, что оно составное в 90% случаев. (Реальные алгоритмы действуют лучше, и не одинаково для всех составных чисел, но примем такую условность и предположим, что рассматриваемый алгоритм действительно таков.) Некто хочет найти 1000-битовое простое число так: выбирает случайные 1000 битов бросанием монеты и проверяет, не получилось ли простое число по этому алгоритму, при этом делает две проверки для повышения надёжности (пока не найдётся число, которое дважды будет названо простым этим алгоритмом). Какова вероятность, что первое найденное им число действительно окажется простым?
(Для чистоты эксперимента комментарии вначале скрываются - потом будут открыты)
