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

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
11121314151617181920
21222324252627282930
31323334353637383940
Еженедельный по «сложности алгоритмов» для 3 курса ИСПРАН

Вариант 150115524.

Ваше имя*:

Вопрос 1

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 2

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

Вопрос 3

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

  1.  Да
  2.  Нет

Вопрос 4

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

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

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

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

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

Вопрос 5

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

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

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

Вопрос 6

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

Вопрос 11

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

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

Вопрос 12

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

  1.  Да
  2.  Нет

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

Какие условия на существование полиномиального в среднем алгоритма упаковки требуются в соответствующей теме?

m
элементов,
n
подмножеств
p
вероятность ненулевого элемента в матрице инцидентности
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  

Вопрос 16

В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке полиномиальность в среднем доказана для следующего распределения входных данных:

  1.  стоимости произвольные, веса выбираются случайно
  2.  и стоимости и веса выбираются случайно
  3.  веса произвольные, стоимость выбираются случайно

Вопрос 17

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

Вопрос 18

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

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

Вопрос 19

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 20

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

Вопрос 21

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

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

Вопрос 22

Если алгоритму из темы про полиномиальный в среднем алгоритм упаковки подать на вход единичную матрицу инцидентности, он, если считать от длины входа, затратит время …

  1.  экспоненциальное
  2.  квадратичное
  3.  линейное
  4.  
  5.  полином, но степени больше 2

Вопрос 23

Какие условия на существование полиномиального в среднем алгоритма для «SAT» требуются в соответствующей теме?

Напомним, что у нас n переменных и m скобок, p — вероятность появления переменной в каждой скобке.


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 24

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

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

Вопрос 25

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

  1.  
  2.  
  3.  

Вопрос 26

В теме про полиномиальный в среднем алгоритм для «SAT» наш алгоритм…

  1.  Вероятностно подсчитывал число выполненных наборов
  2.  Подсчитывал число невыполненных наборов
  3.  Находит приближенное решение, с точностью
  4.  Точность решения в среднем —
  5.  Заполнял таблицу «наиболее выполняющими» наборами
  6.  Вероятностно подсчитывал число невыполненных наборов

Вопрос 27

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

NPC-GQ08.png


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

Вопрос 28

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

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

Вопрос 29

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

Вопрос 30

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

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

Вопрос 31

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

Вопрос 32

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


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

Что верно?

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

Вопрос 33

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

Вопрос 34

Пусть

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

Что верно?

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

Вопрос 35

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

Вопрос 36

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

Вопрос 37

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

Вопрос 38

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

  1.  Построение эффективных алгоритмов муравьиной колонии
  2.  Построение эффективных в среднем алгоритмов
  3.  Применение эволюционных алгоритмов

Вопрос 39

В теме про полиномиальный в среднем алгоритм для «SAT» мы применяли формулу…


  1.  Форда-Фалкерсона
  2.  Включений-Исключений
  3.  Флойда-Уоршолла
  4.  Беллмана-Форда
  5.  Немхаузера-Ульмана

Вопрос 40

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