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

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

Вариант 4078310549.


Ваше имя*:


Вопрос 1

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

  1.  Нет
  2.  Да

Вопрос 2

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

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

Вопрос 3

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


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

Вопрос 4

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

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

Вопрос 5

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

  1.  
  2.  
  3.  
  4.  

Вопрос 6

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

NPC-GQ08.png


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

Вопрос 7

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

Вопрос 8

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

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

Вопрос 9

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

Вопрос 10

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

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

Вопрос 11

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

Вопрос 12

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

Вопрос 13

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

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

Вопрос 14

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 15

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

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

Вопрос 16

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

  1.  
  2.  
  3.  
  4.  

Вопрос 17

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

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

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

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

Вопрос 18

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

  1.  
  2.  
  3.  
  4.  

Вопрос 19

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

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

Вопрос 20

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

  1.  
  2.  
  3.  

Вопрос 21

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

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

Вопрос 22

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

Вопрос 23

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

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

Вопрос 24

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

Вопрос 25

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

  1.  3
  2.  
  3.  
  4.  

Вопрос 26

Выберите общепринятое определение класса NPC (NP-полных задач).

тогда и только тогда, когда:

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

Вопрос 27

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

Вопрос 28

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

Вопрос 29

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

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

Вопрос 30

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

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

Вопрос 31

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

Вопрос 32

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

Вопрос 33

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

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

Вопрос 34

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 35

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

  1.  Нет
  2.  Да

Вопрос 36

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

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

Вопрос 37

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

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

Вопрос 38

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

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

Вопрос 39

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 40

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

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