Эффективные алгоритмы — вопросы

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

Вариант 1571220309.


Ваше имя*:


Вопрос 1

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

  1.  
  2.  
  3.  
  4.  

Вопрос 5

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

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

Вопрос 6

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

Вопрос 7

Есть граф G=(V,E). Разбиение множества вершин V на непересекающиеся множества S и T называется:

  1.  Поток
  2.  Раскладка
  3.  Разбивка
  4.  Паросочетание
  5.  Клика
  6.  Разрез

Вопрос 8

Аню и Колю попросили показать, что задача X — NP-полна. Аня показала полиномиальную сводимость по Карпу от 3SAT к X, а Коля показал полиномиальную сводимость по Карпу от X к 3SAT.

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

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 14

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

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

Вопрос 15

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 16

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

Вопрос 17

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

Вопрос 18

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

  1.  динамическое программирование с отбором наиболее легких наборов
  2.  жадный алгоритм для рюкзака
  3.  дерандомизация
  4.  алгоритм Кристофидеса

Вопрос 19

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


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

Что верно?

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

Вопрос 20

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

NPC-GQ08.png


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

Вопрос 21

Задача 2SAT:

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

Вопрос 22

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

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

Вопрос 23

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

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

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

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

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

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

Как называется задача оптимизации со следующей формулировкой:

  1.  Полуопределенное программирование
  2.  Линейное программирование
  3.  Положительное линейное программирование (ПЛП)
  4.  Целочисленное линейное программирование
  5.  Векторное программирование
  6.  Выпуклое программирование

Вопрос 27

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

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

Вопрос 28

Вероятностный алгоритм A, который, получая

  • вход I
  • вещественное

за время, полиномиальное от , выдает в качестве выхода , такое, что

называется:

  1.  Полиномиальной рандомизированной аппроксимационной схемой
  2.  -полной рандомизированной аппроксимационной схемой
  3.  Полностью полиномиальной аппроксимационной схемой
  4.  Полностью полиномиальной рандомизированной аппроксимационной схемой

Вопрос 29

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

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

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

Вопрос 30

Пусть

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

Что верно?

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

Вопрос 31

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

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

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


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

Вопрос 32

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

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

Вопрос 33

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

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

Вопрос 34

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

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

Вопрос 35

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

Вопрос 36

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

Вопрос 37

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

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

Вопрос 38

Паросочетание, покрывающее все вершины графа, называется

  1.  максимальным
  2.  покрывающим
  3.  вершинным
  4.  совершенным
  5.  сочетающим

Вопрос 39

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

Вопрос 40

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