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

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

Вариант 4273436657.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

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

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

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

Вопрос 4

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

Вопрос 8

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

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

Вопрос 9

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

Вопрос 10

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

Пусть

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

Что верно?

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

Вопрос 14

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


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

Вопрос 15

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

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

Вопрос 16

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

  1.  Да
  2.  Нет

Вопрос 17

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 18

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

Вопрос 19

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 20

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

Вопрос 21

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

Вопрос 22

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

  1.  трехсторонние
  2.  односторонние (при ответе «0»)
  3.  односторонние (при ответе «1»)
  4.  двусторонние
  5.  никакие
  6.  «ZPP»-ошибки

Вопрос 23

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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

  1.  
  2.  
  3.  
  4.  

Вопрос 27

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

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

Вопрос 28

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

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

Вопрос 29

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

Вопрос 30

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

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

Вопрос 31

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

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

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


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

Вопрос 32

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

Вопрос 33

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

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

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

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

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

Вопрос 34

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

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

Вопрос 35

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

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

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

называется:

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

Вопрос 36

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

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

Вопрос 37

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

  1.  
  2.  
  3.  3
  4.  

Вопрос 38

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

Вопрос 39

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

Вопрос 40

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

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