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

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

Вариант 744292368.


Ваше имя*:


Вопрос 1

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

Вопрос 2

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 3

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

Вопрос 4

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

  1.  Да
  2.  Нет

Вопрос 5

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

  1.  
  2.  
  3.  

Вопрос 9

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

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

Вопрос 10

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 11

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

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

Вопрос 12

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

Вопрос 13

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

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

Вопрос 14

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

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

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

Вопрос 15

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

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

Вопрос 16

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

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

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

Вопрос 17

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

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

Вопрос 18

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

  1.  
  2.  
  3.  
  4.  

Вопрос 19

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

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

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

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

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

Вопрос 20

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

Вопрос 25

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

Вопрос 26

Пусть

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

Что верно?

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

Вопрос 27

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

Вопрос 28

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

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

Вопрос 29

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

  1.  
  2.  
  3.  3
  4.  

Вопрос 30

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

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

Вопрос 31

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

Вопрос 32

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

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

Вопрос 33

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 34

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

Вопрос 35

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

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

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


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

Вопрос 36

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

Вопрос 37

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

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

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

Вопрос 38

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

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

Вопрос 39

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


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

Что верно?

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

Вопрос 40

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