Вариант 4106743400.
Формулировка (в виде ЦП) какой задачи приведена ниже:
В теме про полиномиальный в среднем алгоритм для «SAT» мы применяли формулу…
Какой из этих тестов на простоту не является рандомизированным:
Паросочетание, покрывающее все вершины графа, называется
В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке полиномиальность в среднем доказана для следующего распределения входных данных:
Сложность алгоритма динамического программирования для задачи о рюкзаке, который «помнит» о наиболее «легких» допустимых решениях:
Цикл, проходящий через все вершины графа, называется
Для чего применяется «метод условных вероятностей»:
Какой класс ошибок допускают алгоритмы решающие задачи из класса BPP?