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

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

Вариант 379966461.

Ваше имя*:

Вопрос 1

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

Вопрос 2

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

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

Вопрос 3

Пусть

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

Что верно?

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

Вопрос 4

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

Вопрос 5

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

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

Вопрос 6

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

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

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

называется:

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

Вопрос 7

Рассмотрим пару задач на графах.

P1
Для заданного графа, подтвердить или опровергнуть, что в нем есть цикл, которые посещает однократно все вершины, кроме первой, в которую надо вернутся, чтобы завершить цикл.
P2

Для заданного графа, подтвердить или опровергнуть, что в нем есть цикл, который проходит по каждому ребру точно один раз, без исключений.

  1.  P2 в NPC, P1 в P.
  2.  Все остальные варианты — неверны.
  3.  P1 в NPC, P2 в P.
  4.  X в NP, но не NP-полная.
  5.  Обе в NPC
  6.  Обе в P

Вопрос 8

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

Вопрос 9

Задача 2SAT:

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

Вопрос 10

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

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

Вопрос 11

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

Вопрос 12

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

Вопрос 16

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


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

Что верно?

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

Вопрос 17

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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

  1.  
  2.  
  3.  

Вопрос 25

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

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

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

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

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

Вопрос 26

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

Вопрос 27

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

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

Вопрос 28

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

Вопрос 29

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

  1.  
  2.  
  3.  
  4.  

Вопрос 30

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

  1.  
  2.  
  3.  3
  4.  

Вопрос 31

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

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

Вопрос 32

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

Вопрос 33

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

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

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

Вопрос 34

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

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

Вопрос 35

Для чего применяется «дерандомизация»:

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

Вопрос 36

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

NPC-GQ08.png


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

Вопрос 37

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

Вопрос 38

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 39

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

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

Вопрос 40

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

  1.  жадный алгоритм для рюкзака
  2.  динамическое программирование с отбором наиболее легких наборов
  3.  алгоритм Кристофидеса
  4.  дерандомизация
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-exam»