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

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

Вариант 3512429664.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

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

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

  1.  
  2.  
  3.  

Вопрос 8

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 9

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

Вопрос 10

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

Вопрос 11

Задача 2SAT:

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

Вопрос 12

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

  1.  Нет;
  2.  Да;

Вопрос 13

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

Вопрос 14

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

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

Вопрос 15

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

Вопрос 16

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

Вопрос 17

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

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

Вопрос 18

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

Вопрос 19

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

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

Вопрос 20

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

  1.  Да;
  2.  Нет;

Вопрос 21

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

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

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


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

Вопрос 22

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

Цикл, проходящий через все ребра графа по одному разу, называется

  1.  Гамильтонов цикл
  2.  Петля Нестерова
  3.  Наполеонов цикл
  4.  Эйлеров цикл
  5.  Цикл Нельсона

Вопрос 27

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

NPC-GQ08.png


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

Вопрос 28

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

Вопрос 29

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 30

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

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

Вопрос 31

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


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

Что верно?

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

Вопрос 32

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


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

Вопрос 33

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

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

Вопрос 34

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

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

Вопрос 35

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

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

Вопрос 36

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

  1.  Нет
  2.  Да

Вопрос 37

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

Вопрос 38

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

Вопрос 39

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

Вопрос 40

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