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

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

Вариант 1918472992.

Ваше имя*:

Вопрос 1

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 2

Для какой задачи в курсе использовался "метод условных вероятностей" с последовательным определением значения переменных:

  1.  Рюкзак-оптимизация
  2.  MAX-SAT
  3.  Рюкзак-выполнимость
  4.  TSP
  5.  MAX-CUT
  6.  MIN-CUT

Вопрос 3

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

Вопрос 4

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

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

Вопрос 5

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

  1.  Да;
  2.  Нет;
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras»