Сейчас я сам изучаю алгоритмы Лас-Вегаса и Монте-Карло, и у меня есть два вопроса, может быть, они простые, но я не могу на них ответить, если кто-то может мне помочь... Заранее спасибо
Рассмотрим алгоритмы Монте-Карло A для задачи P, ожидаемое время выполнения которой не превышает T(n) для любого экземпляра размера n, который дает правильное решение с вероятностью y(n). Предположим далее, что при наличии решения задачи P мы можем проверить его правильность за время t(n). Покажите, как получить алгоритм Лас-Вегаса, который всегда дает правильный ответ на P и работает за ожидаемое время не более (T(n)+t(n))/y(n).
Пусть 0‹ε2‹ε1‹1. Рассмотрим алгоритм Монте-Карло, который дает правильное решение задачи с вероятностью не ниже 1-ε1 независимо от входных данных. Сколько независимых выполнений этого алгоритма достаточно, чтобы повысить вероятность получения правильного решения не менее чем на 1-ε2 независимо от входных данных?
