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

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

Вариант 2940940471.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

Вопрос 3

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

NPC-GQ08.png


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

Вопрос 4

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

Вопрос 5

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


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

Что верно?

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

Вопрос 6

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

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

Вопрос 7

Найдите неверное утверждение:

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  

Вопрос 8

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

Вопрос 9

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

Вопрос 10

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

  1.  Если X можно решить за полиномиальное время на ДМТ, то P=NP
  2.  X может быть неразрешима
  3.  Нет полиномиального алгоритма для X
  4.  Все остальные варианты — неверны.
  5.  Если X — NP-hard, то она NP-полная
  6.  X — NP-трудная
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-weekly»