Эффективные алгоритмы — вопросы

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

Вариант 1839583808.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

Вероятностный алгоритм A, который, получая

  • вход I
  • вещественное

за время, полиномиальное от , выдает в качестве выхода , такое, что

называется:

  1.  -полной рандомизированной аппроксимационной схемой
  2.  Полностью полиномиальной рандомизированной аппроксимационной схемой
  3.  Полиномиальной рандомизированной аппроксимационной схемой
  4.  Полностью полиномиальной аппроксимационной схемой

Вопрос 3

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

Вопрос 4

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

  1.  
  2.  
  3.  
  4.  

Вопрос 5

Рассмотрим две задачи разрешения, P1 и P2, такие что

  • P1 сводится полиномиально по Карпу к 3SAT
  • 3SAT сводится полиномиально по Карпу к P2

Что можно утверждать?


  1.  Все остальные варианты — неверны.
  2.  P1 в NP, P2 в NP-hard
  3.  P2 в NP, P1 в NP-hard
  4.  Обе в NP
  5.  Обе в NP-hard

Вопрос 6

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

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

Вопрос 7

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

Вопрос 8

Рассмотрим модификацию задачи «Сумма размеров», разрешим даже отрицательные размеры.

Формально: Даны натуральные числа , , и число B.

Надо узнать, существует ли решение в 0/1 переменных уравнения .

Существует ли полиномиальный алгоритм для этой задачи?

  1.  Да, есть полиномиальный алгоритм
  2.  Нет, полиномиального алгоритма нет
  3.  Полиномиального нет, но есть квазиполиномиальный алгоритм

Вопрос 9

В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке рассматривался алгоритм, который оперирует множеством…

  1.  недопустимых наборов
  2.  отборных наборов
  3.  наборов максимальной стоимости для каждого веса
  4.  допустимых наборов
  5.  наборов минимального веса для каждой стоимости
  6.  доминирующих наборов
  7.  набранных отборов

Вопрос 10

Паросочетание, покрывающее все вершины графа, называется

  1.  вершинным
  2.  сочетающим
  3.  покрывающим
  4.  совершенным
  5.  максимальным