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

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

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

Является ли конкатенация двух разрешимых языков перечислимой?

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

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

P1

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

P2

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

У языков 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.

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

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

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

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

Выберите не NP-полную задачу

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

Является ли разрешимым множество натуральных чисел, не превосходящих :

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

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

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

Гамильтонов цикл в графе:

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

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

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

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

Формулировка (в виде ЦЛП) какой задачи приведена ниже:

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

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

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

Цикл, проходящий через все ребра графа по одному разу, называется

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

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

Пусть

• — задача поиска гамильтонового цикла в графе , где V — делится на 3.
• — задача подтверждения наличия гамильтонового цикла в таком графе.

Что верно?

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

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

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

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

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

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

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

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

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

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