Тест по курсу «Эффективные алгоритмы для труднорешаемых задач» — вопросы

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

Вариант 1507133924.


Ваше имя*:


Вопрос 1

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

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

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

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

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

Вопрос 2

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 3

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

  1.  
  2.  
  3.  
  4.  

Вопрос 4

Множество S является разрешимым, тогда и только тогда, когда существует такая машина Тьюринга T, что:

  1.  , то T останавливается и выводит 1, а если , то T останавливается и выводит 0
  2.  , то T останавливается и выводит 1
  3.  , то T останавливается и выводит 1, а если , то T зацикливается
  4.  , то T останавливается и выводит 0

Вопрос 5

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

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

Вопрос 6

У языков 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.  Только (I)
  4.  Только (II)
  5.  Только (III)

Вопрос 7

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

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

Вопрос 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

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

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

Вопрос 11

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

Вопрос 12

Пересечение двух каких классов окажется пустым, если окажется, что ?

  1.   и ;
  2.   и ;
  3.   и ;

Вопрос 13

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

Вопрос 14

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

Вопрос 15

Существует ли биекция между классами и ?

  1.  Нет, не существует;
  2.  Да, существует;
  3.  Ответ на этот вопрос нет, т.к. нам ничего неизвестно про равенство классов и ;

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

Вопрос 19

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

Вопрос 20

Задача 2SAT:

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

Вопрос 21

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

Вопрос 22

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

  1.  Нет;
  2.  Да;

Вопрос 23

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

  1.  Нет
  2.  Да

Вопрос 24

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

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

Вопрос 25

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

Вопрос 26

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

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

Вопрос 27

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

  1.  Да
  2.  Нет

Вопрос 28

Возможно ли сконструировать алгоритм , который для произвольной машины Тюринга и входа определит, остановится ли данная М.Т. на заданном входе?

  1.  Да, известно чёткое описание того, как это делать;
  2.  Формально да, но никто не знает как именно это сделать (примерно как со вполне упорядочиванием );
  3.  Нет

Вопрос 29

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

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

Вопрос 30

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

Вопрос 31

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


  1.  ;
  2.  ;
  3.  

Вопрос 32

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

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

Вопрос 33

  1.  
  2.  
  3.  
  4.  Quiz:Полиномиальный в среднем алгоритм для задачи упаковки
  5.  

Вопрос 34

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

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

Вопрос 35

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

Вопрос 36

Является ли пустое множество разрешимым?

  1.  Да;
  2.  Нет;

Вопрос 37

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

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

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

Вопрос 38

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

  1.  
  2.  
  3.  

Вопрос 39

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

Вопрос 40

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

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

Вопрос 41

Пусть

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

Что верно?

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

Вопрос 42

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

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

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


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

Вопрос 43

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

Вопрос 44

Пусть сводится по Карпу к . Выберите верное утверждение:

  1.  Если , то ;
  2.  Если , то ;
  3.  Если , то ;

Вопрос 45

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

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

Вопрос 46

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

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

Вопрос 47

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

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

Вопрос 48

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

Вопрос 49

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

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

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

Вопрос 50

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


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

Что верно?

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

Вопрос 51

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

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

Вопрос 52

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

Вопрос 53

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

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

Вопрос 54

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

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

Вопрос 55

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

  1.  
  2.  
  3.  
  4.  

Вопрос 56

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

Вопрос 57

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

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

Вопрос 58

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

  1.  
  2.  
  3.  
  4.  

Вопрос 59

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

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

Вопрос 60

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 61

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

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

Вопрос 62

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

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

Вопрос 63

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

Вопрос 64

Выберите верное следствие:

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

Вопрос 65

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

  1.  Разность множеств;
  2.  Дополнение;
  3.  Декартово произведение;

Вопрос 66

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

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

Вопрос 67

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

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

Вопрос 68

Какой из этих тестов на простоту не является рандомизированным:

  1.  Бейли — Померанца — Селфриджа — Уогстаффа
  2.  Все существующие тесты на простоту являются рандомизированными
  3.  Бейли — Померанца — Селфриджа — Уогстаффа,
  4.  Миллера-Рабина
  5.  Миллера

Вопрос 69

Какое утверждение неверно?

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

Вопрос 70

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


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

Вопрос 71

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

NPC-GQ08.png


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

Вопрос 72

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

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

Вопрос 73

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

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

Вопрос 74

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

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

Вопрос 75

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

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

Вопрос 76

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

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

Вопрос 77

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

  1.  3
  2.  
  3.  
  4.  

Вопрос 78

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

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

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

называется:

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

Вопрос 79

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 80

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