Вариант 180656082.
Для какой задачи в курсе использовался "метод условных вероятностей" с последовательным определением значения переменных:
Сложность алгоритма динамического программирования для задачи о рюкзаке, который «помнит» о наиболее «легких» допустимых решениях:
Какой алгоритм используется в алгоритме Кристофидеса?
Как называется задача оптимизации со следующей формулировкой:
С какой точностью работает модифицированный жадный алгоритм для задачи о рюкзаке из соответствующей темы?
Какова точность, гарантируемая жадным алгоритмом в задаче о покрытии?
В работах по теории сложности алгоритм называется полиномиальным в среднем, если для входов длины n и времени работы алгоритма T, выполняется:
Какой алгоритм используется только в лучшем из рассмотренных в теме FPTAS-алгоритмов для рюкзака?
В теме про полиномиальный в среднем алгоритм для «SAT» мы применяли формулу…
Какой класс ошибок допускают алгоритмы решающие задачи из класса BPP?
Какой класс ошибок допускают алгоритмы решающие задачи из класса PP?
Какие условия на существование полиномиального в среднем алгоритма упаковки требуются в соответствующей теме?
Какой класс ошибок допускают алгоритмы решающие задачи из класса ZPP?
Вероятностные «zero-error»-алгоритмы:
Паросочетание, покрывающее все вершины графа, называется
Цикл, проходящий через все ребра графа по одному разу, называется
Какова точность, гарантируемая жадным алгоритмом в задаче о k-покрытии?
Формулировка (в виде ЦП) какой задачи приведена ниже:
Формулировка (в виде ЦЛП) какой задачи приведена ниже:
Сложность алгоритма динамического программирования для задачи о рюкзаке, который «помнит» о наиболее «дорогих» допустимых решениях:
Если алгоритму из темы про полиномиальный в среднем алгоритм упаковки подать на вход единичную матрицу инцидентности, он, если считать от длины входа, затратит время …
Какова точность, гарантируемая гибридным вероятностным алгоритмом из темы про вероятностное округление MAX-SAT?
Есть граф G=(V,E). Разбиение множества вершин V на непересекающиеся множества S и T называется:
Рассмотрим модификацию задачи «Сумма размеров», разрешим даже отрицательные размеры.
Формально: Даны натуральные числа , , и число B.
Надо узнать, существует ли решение в 0/1 переменных уравнения .
Существует ли полиномиальный алгоритм для этой задачи?
В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке полиномиальность в среднем доказана для следующего распределения входных данных:
В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке рассматривался алгоритм, который оперирует множеством…