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

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

Вариант 728386197.

Ваше имя*:

Вопрос 1

Какой прием используется в FPTAS-алгоритме для рюкзака?

  1.  округление коэффициентов
  2.  метод условного спуска
  3.  PTAS-апроксимация
  4.  вероятностное округление
  5.  дерандомизация

Вопрос 2

Метод многократного запуска вероятностного алгоритма, с целью уменьшения вероятности ошибки называется:

  1.  «вероятностная амплификация»
  2.  «антирандомизация»
  3.  «отладка вероятности»
  4.  «дерандомизация»

Вопрос 3

Какова наилучшая сложность алгоритма из темы про FPTAS-алгоритмы для рюкзака?

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 4

Выберите верное верное утверждение из списка ниже, если верных вариантов ответа несколько, то выберите наиболее сильный из них:

  1.  Перечислимые и разрешимые множества никак не пересекаются;
  2.  Из перечислимости множества следует его разрешимость;
  3.  Из разрешимости множества следует его перечислимость;
  4.  Нет верного ответа;

Вопрос 5

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

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