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

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

Вариант 3229097158.

Ваше имя*:

Вопрос 1

Является ли конкатенация двух разрешимых языков перечислимой?

  1.  Да;
  2.  Нет;

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

Вопрос 5

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

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

Вопрос 6

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

NPC-GQ08.png


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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

  1.  
  2.  
  3.  
  4.  

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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


  1.  ;
  2.  ;
  3.  

Вопрос 18

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

  1.  
  2.  
  3.  
  4.  

Вопрос 19

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

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

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

Вопрос 20

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

Вопрос 21

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

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

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

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

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

Вопрос 22

Пусть

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

Что верно?

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

Вопрос 23

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

Вопрос 24

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

Вопрос 25

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


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

Вопрос 26

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

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

Вопрос 27

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

Вопрос 28

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 29

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

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

Вопрос 30

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

  1.  
  2.  
  3.  

Вопрос 31

Пусть сводится по Карпу к . Выберите верное утверждение:

  1.  Если , то ;
  2.  Если , то ;
  3.  Если , то ;

Вопрос 32

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

Вопрос 33

Задача 2SAT:

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

Вопрос 34

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

Вопрос 35

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

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

Вопрос 36

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

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

Вопрос 37

Является ли разрешимым множество натуральных чисел, не превосходящих :

  1.  Нет
  2.  Неизвестно, поскольку ответ на этот вопрос следует из истинности\ложности гипотезы Римана;
  3.  Да

Вопрос 38

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

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

Вопрос 39

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

  1.  Да;
  2.  Нет;

Вопрос 40

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