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

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

Вариант 1315478015.

Ваше имя*:

Вопрос 1

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

Вопрос 2

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

Вопрос 3

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

Вопрос 4

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

  1.  Нет;
  2.  Да;

Вопрос 8

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

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

Вопрос 9

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

Вопрос 10

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

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

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

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

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

Вопрос 16

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

  1.  
  2.  
  3.  

Вопрос 17

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

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

Вопрос 18

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 19

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

  1.  
  2.  
  3.  
  4.  

Вопрос 20

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

  1.  Разность множеств;
  2.  Декартово произведение;
  3.  Дополнение;

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

Выберите верное верное утверждение из списка ниже, если верных вариантов ответа несколько, то выберите наиболее сильный из них:

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

Вопрос 24

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

  1.  
  2.  
  3.  
  4.  

Вопрос 25

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

  1.  Да
  2.  Нет

Вопрос 26

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

  1.  
  2.  
  3.  
  4.  3

Вопрос 27

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

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

Вопрос 28

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

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

Вопрос 29

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

Вопрос 30

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

Вопрос 31

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


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

Вопрос 32

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

Вопрос 33

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

  1.  Да
  2.  Нет

Вопрос 34

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

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

Вопрос 35

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

Вопрос 36

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

Вопрос 37

Пересечение двух каких классов окажется пустым, если окажется, что ?

  1.   и ;
  2.   и ;
  3.   и ;

Вопрос 38

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

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

Вопрос 39

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

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

Вопрос 40

Задача 2SAT:

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