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

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

Вариант 2293128718.

Ваше имя*:

Вопрос 1

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

Вопрос 2

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

  1.  
  2.  
  3.  
  4.  

Вопрос 9

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

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

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

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

Вопрос 13

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

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

Вопрос 14

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


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

Что верно?

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

Вопрос 15

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

  1.  
  2.  3
  3.  
  4.  

Вопрос 16

В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке рассматривался алгоритм…

  1.  Беллмана-Форда
  2.  Эдмондса-Карпа
  3.  Форда-Фалкерсона
  4.  Немхаузера-Ульмана
  5.  Каргера-Штейна
  6.  Флойда-Уоршелла

Вопрос 17

Рассмотрим пару задач на графах.

P1
Для заданного графа, подтвердить или опровергнуть, что в нем есть цикл, которые посещает однократно все вершины, кроме первой, в которую надо вернутся, чтобы завершить цикл.
P2

Для заданного графа, подтвердить или опровергнуть, что в нем есть цикл, который проходит по каждому ребру точно один раз, без исключений.

  1.  P1 в NPC, P2 в P.
  2.  Все остальные варианты — неверны.
  3.  X в NP, но не NP-полная.
  4.  Обе в NPC
  5.  Обе в P
  6.  P2 в NPC, P1 в P.

Вопрос 18

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 19

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

  1.  
  2.  
  3.  

Вопрос 20

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

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

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


  1.  Обе в NP
  2.  Все остальные варианты — неверны.
  3.  P2 в NP, P1 в NP-hard
  4.  Обе в NP-hard
  5.  P1 в NP, P2 в NP-hard
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-weekly»