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

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

Вариант 3303792114.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 3

Является ли пустое множество разрешимым?

  1.  Да;
  2.  Нет;

Вопрос 4

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

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

Вопрос 5

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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


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

Вопрос 10

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

Вопрос 11

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

Вопрос 12

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

Вопрос 16

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

Вопрос 17

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

  1.  
  2.  
  3.  
  4.  3

Вопрос 18

У языков 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) и (IV)
  3.  Только (I)
  4.  Только (III)
  5.  Только (II)

Вопрос 19

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

Вопрос 20

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

Вопрос 24

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

  1.  Да;
  2.  Нет;

Вопрос 25

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

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

Вопрос 26

Существует ли биекция между классами и ?

  1.  Нет, не существует;
  2.  Ответ на этот вопрос нет, т.к. нам ничего неизвестно про равенство классов и ;
  3.  Да, существует;

Вопрос 27

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

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

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

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

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

Вопрос 28

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

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

Вопрос 29

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

Вопрос 30

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

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

Вопрос 31

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

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

Вопрос 32

  1.  
  2.  
  3.  Quiz:Полиномиальный в среднем алгоритм для задачи упаковки
  4.  
  5.  

Вопрос 33

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 34

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

  1.  
  2.  
  3.  

Вопрос 35

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

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

Вопрос 36

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

  1.  Поиск минимального остовного дерева
  2.  Поиск минимального разреза
  3.  Поиск минимального обхода вершин (TSP)
  4.  Поиск кратчайших путей
  5.  Рюкзак-оптимальность

Вопрос 37

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


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

Что верно?

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

Вопрос 38

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

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

Вопрос 39

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

NPC-GQ08.png


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

Вопрос 40

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

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