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

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

Вариант 3300987596.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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


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

Что верно?

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

Вопрос 3

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

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

Вопрос 4

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

  1.   и ;
  2.   и ;
  3.   и ;

Вопрос 5

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

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

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

Вопрос 6

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


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

Вопрос 7

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


  1.  ;
  2.  ;
  3.  

Вопрос 8

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

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

Вопрос 9

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

  1.  Нет
  2.  Формально да, но никто не знает как именно это сделать (примерно как со вполне упорядочиванием );
  3.  Да, известно чёткое описание того, как это делать;

Вопрос 10

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

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

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-weekly»