Тест по сложности алгоритмов для 3 курса ИСПРАН — вопросы

Какой метод применялся в теме про подсчет выполняющих наборов для ДНФ?

Существует ли алгоритм, который выписывает одну за другой все машины Тьюринга, которые останавливаются, будучи запущенными на пустой ленте?

Рассмотрим модификацию задачи «Сумма размеров», разрешим даже отрицательные размеры.

Формально: Даны натуральные числа , , и число B.

Надо узнать, существует ли решение в 0/1 переменных уравнения .

Существует ли полиномиальный алгоритм для этой задачи?

У языков L1-L4 доказаны следующие полиномиальные сводимости по Карпу: «L1→L2», «L3→L2→L4» Рассмотрим утверждения:

I

Если L4 в P, то L2 в P

II

Если L1 или L3 в P, то L2 в P

III

L1 в P, тогда и только тогда, когда L3 в P

IV

Если L4 в P, то L1 в P и L3 в P.

Какой класс ошибок допускают алгоритмы решающие задачи из класса BPP?

Множество S является разрешимым, тогда и только тогда, когда существует такая машина Тьюринга T, что:

Существует ли алгоритм, который выписывает одну за другой все машины Тьюринга, которые не останавливаются, будучи запущенными на пустой ленте?

Рассмотрим модификацию задачи «Сумма размеров», разрешим даже отрицательные размеры.

Формально: Даны натуральные числа , , и число B.

Надо узнать, существует ли решение в 0/1 переменных уравнения .

Существует ли полиномиальный алгоритм для этой задачи?

Выберите верное утверждение

Возможно ли сконструировать алгоритм , который для произвольной машины Тюринга и входа определит, остановится ли данная М.Т. на заданном входе?

Метод многократного запуска вероятностного алгоритма, с целью уменьшения вероятности ошибки называется:

Сложность алгоритма динамического программирования для задачи о рюкзаке, который «помнит» о наиболее «легких» допустимых решениях:

Выберите верное верное утверждение из списка ниже, если верных вариантов ответа несколько, то выберите наиболее сильный из них:

Какой прием используется в FPTAS-алгоритме для рюкзака?

Какой алгоритм используется только в лучшем из рассмотренных в теме FPTAS-алгоритмов для рюкзака?

Для какой задачи в курсе использовался "метод условных вероятностей" с последовательным определением значения переменных:

Какие из подходов к решению вычислительно трудных задач изучались в курсе?

Паросочетание, это подмножество...

Найдите неверное утверждение:

Какое утверждение неверно?

Пересечение двух каких классов окажется пустым, если окажется, что ?

Пусть сводится по Карпу к . Выберите верное утверждение:

Задача 2SAT:

Найдите неверное утверждение:

Какой из этих тестов на простоту не является рандомизированным:

С какой точностью работает «чисто» жадный алгоритм для задачи о рюкзаке («хватать предметы по убыванию удельной стоимости, пока не кончится место в рюкзаке»)?

Является ли пустое множество разрешимым?

Какой алгоритм используется в алгоритме Кристофидеса?

Найдите неверное утверждение:

Предположим, открыли полиномиальный алгоритм, вычисляющий наибольшую клику в заданном графе. Что тогда будет, согласно вариантам на картинке?

Выберите корректное утверждение:

Выберите общепринятое определение класса NPC (NP-полных задач).

тогда и только тогда, когда: