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

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

Вариант 3660402617.


Ваше имя*:


Вопрос 1

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

  1.  Да
  2.  Нет

Вопрос 2

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


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

Что верно?

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

Вопрос 3

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

Вопрос 4

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

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

Вопрос 5

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 6

Пусть X — задача из NP. Что верно?

  1.  Если X можно решить за полиномиальное время на ДМТ, то P=NP
  2.  Нет полиномиального алгоритма для X
  3.  Если X — NP-hard, то она NP-полная
  4.  Все остальные варианты — неверны.
  5.  X может быть неразрешима
  6.  X — NP-трудная

Вопрос 7

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

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

Вопрос 8

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 9

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

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

Вопрос 10

Задача 2SAT:

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

Вопрос 11

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

  1.  
  2.  
  3.  

Вопрос 12

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 13

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

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

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

называется:

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

Вопрос 14

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

Вопрос 18

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

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

Вопрос 19

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

Вопрос 20

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

Вопрос 21

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

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

Вопрос 22

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

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

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

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

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

Вопрос 23

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

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

Вопрос 24

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

Вопрос 25

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

Вопрос 26

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

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

Вопрос 27

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

Вопрос 28

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

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

Вопрос 29

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

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

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

Вопрос 30

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

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

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

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

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

Вопрос 31

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

Вопрос 32

Метод многократного запуска вероятностного алгоритма, с целью уменьшения вероятности ошибки называется:

  1.  «дерандомизация»
  2.  «вероятностная амплификация»
  3.  «отладка вероятности»
  4.  «антирандомизация»

Вопрос 33

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

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

Вопрос 34

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

NPC-GQ08.png


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

Вопрос 35

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

  1.  
  2.  
  3.  
  4.  

Вопрос 36

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

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

Вопрос 37

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

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

Вопрос 38

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

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

Вопрос 39

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

  1.  
  2.  
  3.  
  4.  

Вопрос 40

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