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

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

Вариант 1612875007.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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


  1.  Из сводимости по Карпу следует сводимость по Куку
  2.  Верного ответа нет
  3.  Из сводимости по Куку следует сводимость по Карпу

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

Вопрос 7

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

Вопрос 13

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

Вопрос 14

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

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

Вопрос 15

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

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

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

Вопрос 16

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

NPC-GQ08.png


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

Вопрос 17

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

Вопрос 18

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

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

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

Вопрос 19

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

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

Вопрос 20

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

  1.  Да;
  2.  Нет;

Вопрос 21

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


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

Вопрос 22

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

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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


  1.  ;
  2.  
  3.  ;

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

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

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

Вопрос 31

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

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

Вопрос 32

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

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

Вопрос 33

Пусть

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

Что верно?

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

Вопрос 34

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

Вопрос 35

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

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

Вопрос 36

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

Вопрос 37

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

  1.  Да;
  2.  Нет;

Вопрос 38

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

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

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

называется:

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

Вопрос 39

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

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

Вопрос 40

Задача 2SAT:

  1.  разрешима за полиномиальное время, но не за константное время.
  2.  NP-трудна, но не NP-полна.
  3.  Все остальные варианты — неверны.
  4.  разрешима за константное время, т.к. любой вход для такой задачи выполним.
  5.  NP-полна
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-exam»