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

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

Вариант 2896819388.


Ваше имя*:


Вопрос 1

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

  1.  
  2.  
  3.  
  4.  

Вопрос 2

Пусть задача A — «есть ли цикл в ненаправленном графе». Рассмотрим набор утверждений.


  • (1) Задача A — в P
  • (2) Задача A — в NP
  • (3) Если задача A — NP-полна, то существует НМТ, решающая A за полиномиальное время.

Что верно?

  1.  2 и 3
  2.  1 и 2
  3.  1 и 3
  4.  Все остальные варианты — неверны.
  5.  1, 2 и 3

Вопрос 3

Что верно для NP-полных и NP-трудных задач:

  1.  Если мы хотим доказать, что задача X — NP-трудна, мы берем известную NP-полную задачу Y и сводим ее полиномиально по Карпу к X.
  2.  
  3.  Первой задачей с доказанной NP-полнотой была CircuitSAT, «the circuit satisfiability problem»
  4.  Ничего не верно.
  5.  Все варианты, кроме «ничего не верно»

Вопрос 4

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

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

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


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

Вопрос 5

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

Вопрос 6

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

Вопрос 7

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

Вопрос 8

Существует ли алгоритм, который выписывает одну за другой все машины Тьюринга, которые не останавливаются, будучи запущенными на пустой ленте?

  1.  Да
  2.  Нет

Вопрос 9

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

Вопрос 10

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

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

Вопрос 11

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

  1.  алгоритм Немхаузера-Ульмана
  2.  метод условного спуска
  3.  алгоритм Беллмана-Форда
  4.  динамическое программирование с отбором наиболее легких наборов
  5.  динамическое программирование с отбором наиболее дорогих наборов

Вопрос 12

Какое утверждение неверно?

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

Вопрос 13

Сложность алгоритма динамического программирования для задачи о рюкзаке, который «помнит» о наиболее «легких» допустимых решениях:

  1.  
  2.  
  3.  
  4.  Нет правильного ответа
  5.  

Вопрос 14

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

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

Вопрос 15

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

Вопрос 16

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

Вопрос 17

Паросочетание, это подмножество...


  1.  связных подграфов
  2.  циклов
  3.  вершин
  4.  ребер

Вопрос 18

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

Вопрос 19

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

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

Вопрос 23

У языков L1-L4 доказаны следующие полиномиальные сводимости по Карпу: «L1→L2», «L3→L2→L4» Рассмотрим утверждения:

I
Если L4 в P, то L2 в P
II
Если L1 или L3 в P, то L2 в P
III
L1 в P, тогда и только тогда, когда L3 в P
IV
Если L4 в P, то L1 в P и L3 в P.


  1.  Только (II)
  2.  Все остальные варианты — неверны.
  3.  Только (I)
  4.  Только (III)
  5.  Только (I) и (IV)

Вопрос 24

Вероятностные «zero-error»-алгоритмы:

  1.  Всегда дают верный ответ в случае, если возвращают «0»
  2.  Когда дают ответ он правильный, но могут отвечать «не знаю»
  3.  Всегда дают верный ответ
  4.  Могут ошибаться, но только в случае, если возвращают «0»

Вопрос 25

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 26

Выберите корректное утверждение:

  1.  
  2.  
  3.  

Вопрос 27

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

Вопрос 28

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

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

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

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

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

Вопрос 29

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

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

Вопрос 30

Какой метод применялся в теме про подсчет выполняющих наборов для ДНФ?

  1.  Динамическое программирование
  2.  Полный перебор
  3.  Вероятностное округление
  4.  Монте-Карло
  5.  Дерандомизация вероятностного округления

Вопрос 31

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

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

Вопрос 32

Существует ли алгоритм, который выписывает одну за другой все машины Тьюринга, которые останавливаются, будучи запущенными на пустой ленте?

  1.  Да
  2.  Нет

Вопрос 33

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 34

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

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

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

называется:

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

Вопрос 35

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 36

Пусть

  • — задача поиска гамильтонового цикла в графе , где V — делиться на 3.
  • — задача подтверждения наличия гамильтонового цикла в таком графе.

Что верно?

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

Вопрос 37

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

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

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

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

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

Вопрос 38

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

  1.  
  2.  
  3.  
  4.  

Вопрос 39

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

Вопрос 40

Сложность алгоритма динамического программирования для задачи о рюкзаке, который «помнит» о наиболее «дорогих» допустимых решениях:

  1.  
  2.  
  3.  
  4.  
  5.