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

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

Вариант 4099902102.


Ваше имя*:


Вопрос 1

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

  1.  жадный алгоритм для рюкзака
  2.  дерандомизация
  3.  алгоритм Кристофидеса
  4.  динамическое программирование с отбором наиболее легких наборов

Вопрос 2

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

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

Вопрос 3

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 4

У языков 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.  Только (I) и (IV)
  3.  Только (III)
  4.  Все остальные варианты — неверны.
  5.  Только (I)

Вопрос 5

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

Вопрос 6

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

  1.  двусторонние
  2.  односторонние (при ответе «0»)
  3.  трехсторонние
  4.  «ZPP»-ошибки
  5.  никакие
  6.  односторонние (при ответе «1»)

Вопрос 7

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

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

Вопрос 8

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 9

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

Вопрос 10

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

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

Вопрос 11

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

Вопрос 12

Задача 2SAT:

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

Вопрос 13

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

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

Вопрос 14

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

Вопрос 15

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

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

Вопрос 16

Пусть

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

Что верно?

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

Вопрос 17

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 18

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

NPC-GQ08.png


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

Вопрос 19

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

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

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


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

Вопрос 20

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

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

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

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

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

Вопрос 21

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

Вопрос 22

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

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

Вопрос 23

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


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

Что верно?

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

Вопрос 24

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

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

Вопрос 25

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

Вопрос 26

Аню и Колю попросили показать, что задача X — NP-полна. Аня показала полиномиальную сводимость по Карпу от 3SAT к X, а Коля показал полиномиальную сводимость по Карпу от X к 3SAT.

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

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

Вопрос 27

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

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

Вопрос 28

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

Вопрос 29

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

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

Вопрос 30

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

  1.  Да
  2.  Нет

Вопрос 31

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

Вопрос 32

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

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

Вопрос 33

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 34

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

Вопрос 35

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

Вопрос 36

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

Вопрос 37

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

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

Вопрос 38

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

Вопрос 39

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

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

Вопрос 40

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

  1.  Нет
  2.  Да