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

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

Вариант 2424633588.


Ваше имя*:


Вопрос 1

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

Вопрос 2

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

Вопрос 3

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

Вопрос 4

Найдите неверное утверждение:

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

Вопрос 5

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 6

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

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

Вопрос 7

Как называется задача оптимизации со следующей формулировкой:

  1.  Выпуклое программирование
  2.  Полуопределенное программирование
  3.  Линейное программирование
  4.  Целочисленное линейное программирование
  5.  Векторное программирование
  6.  Положительное линейное программирование (ПЛП)

Вопрос 8

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

Вопрос 9

С какой точностью работает модифицированный жадный алгоритм для задачи о рюкзаке из соответствующей темы?

  1.  0.878
  2.  
  3.  Этот алгоритм не гарантирует никакой точности решения;
  4.  2
  5.  3
  6.  

Вопрос 10

Для чего применяется «дерандомизация»:

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