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

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

С какой точностью работает модифицированный жадный алгоритм для задачи о рюкзаке из соответствующей темы?

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

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

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

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

Рассмотрим пару задач на графах.

P1

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

P2

Для заданного графа, подтвердить или опровергнуть, что в нем есть цикл, который проходит по каждому ребру точно один раз, без исключений.

Пусть X — задача из NP. Что верно?

Что верно для NP-полных и NP-трудных задач:

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

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

Рассмотрим две задачи разрешения, P1 и P2, такие что

• P1 сводится полиномиально по Карпу к 3SAT
• 3SAT сводится полиномиально по Карпу к P2

Что можно утверждать?

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

Пусть S — задача из NPC, а Q и R — тоже задачи, но про них известно только, что Q — полиномиально сводиться по Карпу к S, а S — к R.

Что будет верно?

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

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

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

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

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

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

Какова точность, гарантируемая жадным алгоритмом в задаче о покрытии?

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

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

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

Аню и Колю попросили показать, что задача X — NP-полна. Аня показала полиномиальную сводимость по Карпу от 3SAT к X, а Коля показал полиномиальную сводимость по Карпу от X к 3SAT.

Что можно утверждать?

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

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

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

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

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

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

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

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

Вероятностные «zero-error»-алгоритмы:

В работах по теории сложности алгоритм называется полиномиальным в среднем, если для входов длины n и времени работы алгоритма T, выполняется:

Предположим, разумеется, что Тогда что будет верно?

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