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

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

Вариант 2250030569.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

Какие условия на существование полиномиального в среднем алгоритма для «SAT» требуются в соответствующей теме?

Напомним, что у нас n переменных и m скобок, p — вероятность появления переменной в каждой скобке.


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 5

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

  1.  
  2.  
  3.  3
  4.  
  5.  
  6.  

Вопрос 6

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

  1.  квадратичное
  2.  линейное
  3.  
  4.  полином, но степени больше 2
  5.  экспоненциальное

Вопрос 7

Выберите общепринятое определение класса NPC (NP-полных задач).

тогда и только тогда, когда:

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  

Вопрос 8

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

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

Вопрос 9

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

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

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

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

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

Вопрос 10

  1.  NP
  2.  coNP
  3.  coRP
  4.  BPP
  5.  ZPP
  6.  
  7.  PP
  8.  ALL
  9.  RP