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

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

Вариант 1863811501.

Ваше имя*:

Вопрос 1

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

  1.  
  2.  
  3.  

Вопрос 2

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

Вопрос 3

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

Вопрос 4

Задача 2SAT:

  1.  NP-трудна, но не NP-полна.
  2.  NP-полна
  3.  разрешима за константное время, т.к. любой вход для такой задачи выполним.
  4.  разрешима за полиномиальное время, но не за константное время.
  5.  Все остальные варианты — неверны.

Вопрос 5

Предположим, разумеется, что Тогда что будет верно?

  1.  
  2.  
  3.  
  4.  

Вопрос 6

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

  1.  Да
  2.  Нет

Вопрос 7

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

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

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

Вопрос 8

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

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

Вопрос 9

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

  1.  Да;
  2.  Нет;

Вопрос 10

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