Вариант 4186942771.
Сложность алгоритма динамического программирования для задачи о рюкзаке, который «помнит» о наиболее «дорогих» допустимых решениях:
Выберите корректное утверждение:
Метод многократного запуска вероятностного алгоритма, с целью уменьшения вероятности ошибки называется:
Гамильтонов цикл в графе:
Какой класс ошибок допускают алгоритмы решающие задачи из класса PP?
Аню и Колю попросили показать, что задача X — NP-полна. Аня показала полиномиальную сводимость по Карпу от 3SAT к X, а Коля показал полиномиальную сводимость по Карпу от X к 3SAT.
Что можно утверждать?
Выберите верное следствие:
Пусть X — задача из NP. Что верно?
Какое утверждение неверно?
Пусть сводится по Карпу к . Выберите верное утверждение:
Выберите не NP-полную задачу
Рассмотрим модификацию задачи «Сумма размеров», разрешим даже отрицательные размеры.
Формально: Даны натуральные числа , , и число B.
Надо узнать, существует ли решение в 0/1 переменных уравнения .
Существует ли полиномиальный алгоритм для этой задачи?
Замкнутость по какой из операций выполнена как для разрешимых, так и для перечислимых языков?
Вероятностные «zero-error»-алгоритмы:
Существует ли алгоритм, который выписывает одну за другой все машины Тьюринга, которые останавливаются, будучи запущенными на пустой ленте?
Для чего применяется «метод условных вероятностей»:
Рассмотрим две задачи разрешения, P1 и P2, такие что
Какой прием используется в FPTAS-алгоритме для рюкзака?
Какой метод применялся в теме про подсчет выполняющих наборов для ДНФ?
Пусть задача A — «есть ли цикл в ненаправленном графе». Рассмотрим набор утверждений.
Что верно?
Какова наилучшая сложность алгоритма из темы про FPTAS-алгоритмы для рюкзака?
Найдите неверное утверждение:
Паросочетание, это подмножество...
Для чего применяется «дерандомизация»:
Выберите общепринятое определение класса NPC (NP-полных задач).
тогда и только тогда, когда:
Пусть
Какой алгоритм используется в алгоритме Кристофидеса?
В работах по теории сложности алгоритм называется полиномиальным в среднем, если для входов длины n и времени работы алгоритма T, выполняется:
Сложность алгоритма динамического программирования для задачи о рюкзаке, который «помнит» о наиболее «легких» допустимых решениях:
Какой класс ошибок допускают алгоритмы решающие задачи из класса BPP?