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

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

Вариант 821337849.

Ваше имя*:

Вопрос 1

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

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

Вопрос 7

Задача 2SAT:

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

Вопрос 12

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

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

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


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

Вопрос 13

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

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

Вопрос 14

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

Вопрос 15

Выберите верное следствие:

  1.  Ничего из этого не является верным;
  2.  Из разрешимости множества следует его ко-разрешимость;
  3.  Из перечислимости множества следует его ко-перечислимость;

Вопрос 16

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

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

Вопрос 17

Паросочетание, покрывающее все вершины графа, называется

  1.  совершенным
  2.  вершинным
  3.  сочетающим
  4.  покрывающим
  5.  максимальным

Вопрос 18

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 19

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

  1.  Нет
  2.  Да

Вопрос 20

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

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

Вопрос 21

Возможно ли сконструировать алгоритм , который для произвольной машины Тюринга и входа определит, остановится ли данная М.Т. на заданном входе?

  1.  Нет
  2.  Да, известно чёткое описание того, как это делать;
  3.  Формально да, но никто не знает как именно это сделать (примерно как со вполне упорядочиванием );

Вопрос 22

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

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

Вопрос 23

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

Вопрос 24

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 25

Какова сложность вероятностного алгоритма Фрейвалда для проверки тождества AB=C для матриц  ?

  1.  
  2.  
  3.  
  4.  

Вопрос 26

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 27

Цикл, проходящий через все ребра графа по одному разу, называется

  1.  Наполеонов цикл
  2.  Цикл Нельсона
  3.  Петля Нестерова
  4.  Гамильтонов цикл
  5.  Эйлеров цикл

Вопрос 28

Задачи 3SAT и 2SAT:

  1.  Обе NP-полны
  2.  Обе в P
  3.  Первая NP-полна и вторая в P.
  4.  Все остальные варианты — неверны.
  5.  Первая неразрешима и вторая — NP-полна.

Вопрос 29

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

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

Вопрос 30

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

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

Вопрос 31

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

Вопрос 32

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

  1.  Да;
  2.  Нет;

Вопрос 33

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

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

Вопрос 34

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

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

Вопрос 35

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

Вопрос 36

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

Вопрос 37

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

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

Вопрос 38

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

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

Вопрос 39

Пересечение двух каких классов окажется пустым, если окажется, что ?

  1.   и ;
  2.   и ;
  3.   и ;

Вопрос 40

  1.  NP
  2.  RP
  3.  coNP
  4.  coRP
  5.  PP
  6.  
  7.  ALL
  8.  ZPP
  9.  BPP
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-exam»