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

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

Вариант 1593460131.


Ваше имя*:


Вопрос 1

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

Вопрос 2

Предположим, разумеется, что Тогда что будет верно?

  1.  
  2.  
  3.  
  4.  

Вопрос 3

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

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

Вопрос 4

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

Вопрос 5

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

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

Вопрос 6

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 7

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

m
элементов,
n
подмножеств
p
вероятность ненулевого элемента в матрице инцидентности
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  

Вопрос 8

Выберите не NP-полную задачу

  1.  SAT
  2.  TSP-выполнимость
  3.  3SAT
  4.  Сумма множеств
  5.  2SAT
  6.  Клика (есть ли в графе клика больше заданной)
  7.  Вершинное покрытие

Вопрос 9

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 10

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

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

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

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

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