Вариант 944049534.
Какой алгоритм используется в алгоритме Кристофидеса?
Паросочетание, покрывающее все вершины графа, называется
Для чего применяется «дерандомизация»:
В теме про полиномиальный в среднем алгоритм для «SAT» наш алгоритм…
Для какой задачи в курсе использовался "метод условных вероятностей" с последовательным определением значения переменных:
Какова точность, гарантируемая гибридным вероятностным алгоритмом из темы про вероятностное округление MAX-SAT?
Гамильтонов цикл в графе:
Вероятностный алгоритм A, который, получая
за время, полиномиальное от , выдает в качестве выхода , такое, что
называется: