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

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

Вариант 2317568984.

Ваше имя*:

Вопрос 1

Пусть

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

Что верно?

  1.   — NP-hard, но не .
  2.  Они обе не NP-hard.
  3.  Все остальные варианты — неверны.
  4.   и — NP-трудны.
  5.   — NP-hard, но не .

Вопрос 2

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

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

Вопрос 3

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


  1.  Из сводимости по Куку следует сводимость по Карпу
  2.  Верного ответа нет
  3.  Из сводимости по Карпу следует сводимость по Куку

Вопрос 4

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

  1.  Фундаментальная теорема Сэвича строго доказывает, что детерминированная и недетерминированная память эквивалентны с точностью до квадрата, что в итоге и дает экспоненциальный рост по времени.
  2.  Машина, использующая полиномиальную память , имеет экспоненциальное количество уникальных конфигураций. Если она сделает больше шагов, то неизбежно повторит конфигурацию и зациклится.
  3.  В теории асимптотической сложности алгоритмов полином, возведенный в степень произвольной константы, всегда растет асимптотически медленнее, чем экспоненциальная функция от того же полинома.
  4.  Любую вычислительную задачу, требующую для своего решения полиномиальной памяти, всегда можно тривиально решить полным обходом дерева всех возможных вариантов за экспоненциальное время.

Вопрос 5

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


  1.  ;
  2.  ;
  3.  

Вопрос 6

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

  1.  Если , то ;
  2.  Если , то ;
  3.  Если , то ;

Вопрос 7

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

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

Вопрос 8

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

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

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

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

Вопрос 9

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

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

Вопрос 10

Задача 2SAT:

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