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

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

Вариант 3890378669.


Ваше имя*:


Вопрос 1

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

Вопрос 6

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


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

Что верно?

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

Вопрос 7

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

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

Вопрос 8

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 9

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

Вопрос 10

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

  1.  
  2.  
  3.  
  4.  

Вопрос 11

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

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

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

Вопрос 12

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

  1.  Да
  2.  Нет

Вопрос 13

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

Вопрос 14

Аню и Колю попросили показать, что задача X — NP-полна. Аня показала полиномиальную сводимость по Карпу от 3SAT к X, а Коля показал полиномиальную сводимость по Карпу от X к 3SAT.

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

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

Пусть

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

Что верно?

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

Вопрос 18

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

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

Вопрос 19

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

NPC-GQ08.png


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

Вопрос 20

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

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

Вопрос 21

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

Вопрос 22

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

  1.  
  2.  
  3.  

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

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

  1.  
  2.  
  3.  
  4.  3

Вопрос 26

Задача 2SAT:

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

Вопрос 27

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

  1.  Да
  2.  Нет

Вопрос 28

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

Вопрос 29

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

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

Вопрос 30

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 31

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

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

Вопрос 32

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

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

Вопрос 33

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

Вопрос 34

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

Вопрос 35

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

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

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

называется:

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

Вопрос 36

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

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

Вопрос 37

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

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

Вопрос 38

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

Вопрос 39

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

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

Вопрос 40

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

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