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

Материал из DISCOPAL
Перейти к: навигация, поиск
12345
Тест по курсу «Эффективные алгоритмы»

Вариант 3308622818.

Ваше имя*:

Вопрос 1

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


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

Вопрос 2

Для чего применяется «метод условных вероятностей»:

  1.  Дератизация
  2.  Дерандомизация
  3.  Демократизация
  4.  Рандомизация
  5.  Метод Монте-Карло
  6.  Шервудские алгоритмы
  7.  Метод Лас-Вегас

Вопрос 3

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

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

Вопрос 4

  1.  ZPP
  2.  BPP
  3.  PP
  4.  coZPP
  5.  NP
  6.  coRP
  7.  RP
  8.  PSPACE

Вопрос 5

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