Вариант 782692501.
Метод многократного запуска вероятностного алгоритма, с целью уменьшения вероятности ошибки называется:
Какой алгоритм используется в алгоритме Кристофидеса?
Формулировка (в виде ЦП) какой задачи приведена ниже:
Вероятностные «zero-error»-алгоритмы:
В теме про полиномиальный в среднем алгоритм для «SAT» наш алгоритм…
Какой класс ошибок допускают алгоритмы решающие задачи из класса BPP?
Какие условия на существование полиномиального в среднем алгоритма для «SAT» требуются в соответствующей теме?
Напомним, что у нас n переменных и m скобок, p — вероятность появления переменной в каждой скобке.
Как называется задача оптимизации со следующей формулировкой:
Какова точность, гарантируемая жадным алгоритмом в задаче о покрытии?