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

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

Вариант 1420204755.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

  1.  
  2.  
  3.  

Вопрос 3

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

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

Вопрос 4

Пусть S — задача из NPC, а Q и R — тоже задачи, но про них известно только, что Q — полиномиально сводиться по Карпу к S, а S — к R.

Что будет верно?

  1.  Q — NP-полная
  2.  Q — NP-трудная
  3.  R — NP-трудная
  4.  R — NP-полная

Вопрос 5

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

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

Вопрос 6

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

NPC-GQ08.png


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

Вопрос 7

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

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

Вопрос 8

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

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

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

Вопрос 9

Существует ли биекция между классами и ?

  1.  Да, существует;
  2.  Нет, не существует;
  3.  Ответ на этот вопрос нет, т.к. нам ничего неизвестно про равенство классов и ;

Вопрос 10

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

  1.  Неизвестно, поскольку ответ на этот вопрос следует из истинности\ложности гипотезы Римана;
  2.  Да
  3.  Нет
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-weekly»