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

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

Вариант 138999911.


Ваше имя*:


Вопрос 1

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

  1.  округление коэффициентов
  2.  вероятностное округление
  3.  PTAS-апроксимация
  4.  метод условного спуска
  5.  дерандомизация

Вопрос 2

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

Вопрос 3

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

Вопрос 4

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

Вопрос 8

Задача 2SAT:

  1.  Все остальные варианты — неверны.
  2.  разрешима за полиномиальное время, но не за константное время.
  3.  NP-полна
  4.  NP-трудна, но не NP-полна.
  5.  разрешима за константное время, т.к. любой вход для такой задачи выполним.

Вопрос 9

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

  1.  
  2.  
  3.  
  4.  3

Вопрос 10

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

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

Вопрос 11

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 12

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

Вопрос 13

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

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

Вопрос 14

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 15

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

  1.  
  2.  
  3.  
  4.  

Вопрос 16

У языков 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)

Вопрос 17

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

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

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

Вопрос 18

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

NPC-GQ08.png


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

Вопрос 19

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 20

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

Вопрос 21

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

Вопрос 22

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

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

Вопрос 23

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

Вопрос 24

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

Вопрос 25

Пусть S — задача из NPC, а Q и R — тоже задачи, но про них известно только, что Q — полиномиально сводиться по Карпу к S, а S — к R.

Что будет верно?

  1.  Q — NP-трудная
  2.  R — NP-полная
  3.  R — NP-трудная
  4.  Q — NP-полная

Вопрос 26

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

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

Вопрос 27

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

Вопрос 28

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

  1.  Да
  2.  Нет

Вопрос 29

Гамильтонов цикл в графе:

  1.  проходит через все ребра по одному разу
  2.  проходит через все вершины по одному разу
  3.  проходит через все вершины и ребра по одному разу

Вопрос 30

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

  1.  
  2.  
  3.  
  4.  

Вопрос 31

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

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

Вопрос 32

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

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

Вопрос 33

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

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

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


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

Вопрос 34

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

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

Вопрос 35

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

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

Вопрос 36

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

Вопрос 37

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

Вопрос 38

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

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

Вопрос 39

Множество S является разрешимым, тогда и только тогда, когда существует такая машина Тьюринга T, что:

  1.  , то T останавливается и выводит 1, а если , то T зацикливается
  2.  , то T останавливается и выводит 0
  3.  , то T останавливается и выводит 1
  4.  , то T останавливается и выводит 1, а если , то T останавливается и выводит 0

Вопрос 40

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

  1.  
  2.  
  3.  
  4.  
  5.