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

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
Еженедельный по «сложности алгоритмов» для 3 курса ИСПРАН

Вариант 997002568.

Ваше имя*:

Вопрос 1

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

  1.  Если X можно решить за полиномиальное время на ДМТ, то P=NP
  2.  Нет полиномиального алгоритма для X
  3.  Все остальные варианты — неверны.
  4.  Если X — NP-hard, то она NP-полная
  5.  X может быть неразрешима
  6.  X — NP-трудная

Вопрос 2

Выберите верное следствие:

  1.  Из перечислимости множества следует его ко-перечислимость;
  2.  Ничего из этого не является верным;
  3.  Из разрешимости множества следует его ко-разрешимость;

Вопрос 3

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

  1.  TSP-выполнимость
  2.  SAT
  3.  Клика (есть ли в графе клика больше заданной)
  4.  2SAT
  5.  3SAT
  6.  Вершинное покрытие
  7.  Сумма множеств

Вопрос 4

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

  1.  Нет
  2.  Да

Вопрос 5

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

  1.  , то T останавливается и выводит 0
  2.  , то T останавливается и выводит 1
  3.  , то T останавливается и выводит 1, а если , то T останавливается и выводит 0
  4.  , то T останавливается и выводит 1, а если , то T зацикливается

Вопрос 6

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

  1.  Дополнение;
  2.  Декартово произведение;
  3.  Разность множеств;

Вопрос 7

Пусть задача A — «есть ли цикл в ненаправленном графе». Рассмотрим набор утверждений.


  • (1) Задача A — в P
  • (2) Задача A — в NP
  • (3) Если задача A — NP-полна, то существует НМТ, решающая A за полиномиальное время.

Что верно?

  1.  1, 2 и 3
  2.  1 и 2
  3.  Все остальные варианты — неверны.
  4.  2 и 3
  5.  1 и 3

Вопрос 8

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

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

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

  1.  X в NP, но не NP-полная.
  2.  P2 в NPC, P1 в P.
  3.  Обе в P
  4.  Обе в NPC
  5.  Все остальные варианты — неверны.
  6.  P1 в NPC, P2 в P.

Вопрос 9

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

  1.  Петля Нестерова
  2.  Наполеонов цикл
  3.  Эйлеров цикл
  4.  Цикл Нельсона
  5.  Гамильтонов цикл

Вопрос 10

Задача 2SAT:

  1.  NP-трудна, но не NP-полна.
  2.  разрешима за полиномиальное время, но не за константное время.
  3.  NP-полна
  4.  разрешима за константное время, т.к. любой вход для такой задачи выполним.
  5.  Все остальные варианты — неверны.
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-weekly»