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

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

Вариант 2144721694.

Ваше имя*:

Вопрос 1

  1.  
  2.  
  3.  
  4.  Quiz:Полиномиальный в среднем алгоритм для задачи упаковки
  5.  

Вопрос 2

В работах по теории сложности алгоритм называется полиномиальным в среднем, если для входов длины n и времени работы алгоритма T, выполняется:

  1.  
  2.  
  3.  
  4.  

Вопрос 3

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

Вопрос 4

Формулировка (в виде ЦЛП) какой задачи приведена ниже:

  1.  MIN-SAT
  2.  MAX-3SAT
  3.  MIN-CUT
  4.  MAX-CUT
  5.  MAX-SAT

Вопрос 5

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