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

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

Вариант 729386397.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

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

Вопрос 7

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

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

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


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

Вопрос 8

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

NPC-GQ08.png


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

Вопрос 9

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

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

Вопрос 10

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

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