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

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

Вариант 1445358679.

Ваше имя*:

Вопрос 1

Какой класс ошибок допускают алгоритмы решающие задачи из класса BPP?

  1.  «BP»-ошибки
  2.  односторонние
  3.  трехсторонние
  4.  двусторонние

Вопрос 2

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

Вопрос 3

Какие из подходов к решению вычислительно трудных задач изучались в курсе?

  1.  Применение эволюционных алгоритмов
  2.  Построение эффективных алгоритмов муравьиной колонии
  3.  Построение эффективных в среднем алгоритмов

Вопрос 4

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

Вопрос 5

Множество S является разрешимым, тогда и только тогда, когда существует такая машина Тьюринга T, что:

  1.  , то T останавливается и выводит 1, а если , то T останавливается и выводит 0
  2.  , то T останавливается и выводит 0
  3.  , то T останавливается и выводит 1
  4.  , то T останавливается и выводит 1, а если , то T зацикливается
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras»