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

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

Вариант 2699502060.

Ваше имя*:

Вопрос 1

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

  1.  Нет
  2.  Да
  3.  Неизвестно, поскольку ответ на этот вопрос следует из истинности\ложности гипотезы Римана;

Вопрос 2

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

  1.  
  2.  
  3.  

Вопрос 3

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

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

Вопрос 4

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

  1.  Нет
  2.  Да

Вопрос 5

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

  1.  Нет;
  2.  Да;

Вопрос 6

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

  1.  Ничего не верно.
  2.  
  3.  Первой задачей с доказанной NP-полнотой была CircuitSAT, «the circuit satisfiability problem»
  4.  Все варианты, кроме «ничего не верно»
  5.  Если мы хотим доказать, что задача X — NP-трудна, мы берем известную NP-полную задачу Y и сводим ее полиномиально по Карпу к X.

Вопрос 7

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

NPC-GQ08.png


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

Вопрос 8

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

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

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  

Вопрос 9

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

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

Вопрос 10

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

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

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


  1.  P2 в NP, P1 в NP-hard
  2.  Обе в NP
  3.  Обе в NP-hard
  4.  P1 в NP, P2 в NP-hard
  5.  Все остальные варианты — неверны.
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-weekly»