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

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

Вариант 368010678.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

  1.  Да
  2.  Нет

Вопрос 3

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

Вопрос 4

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

Вопрос 5

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

  1.  
  2.  
  3.  
  4.  

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

  1.  
  2.  
  3.  

Вопрос 9

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

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

Вопрос 10

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


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

Вопрос 11

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

Вопрос 12

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

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

Вопрос 13

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

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

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

Вопрос 14

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

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

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


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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 18

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

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

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

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

Вопрос 19

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

  1.  Да
  2.  Нет

Вопрос 20

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

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

Вопрос 21

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

Вопрос 22

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

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

Вопрос 23

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

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

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

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

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

Вопрос 24

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

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

Вопрос 25

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 26

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


  1.  Верного ответа нет
  2.  Из сводимости по Куку следует сводимость по Карпу
  3.  Из сводимости по Карпу следует сводимость по Куку

Вопрос 27

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

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

Вопрос 28

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

NPC-GQ08.png


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

Вопрос 29

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

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

Вопрос 30

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

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

Вопрос 31

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

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

Вопрос 32

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 33

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

Вопрос 34

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

  1.  3
  2.  
  3.  
  4.  

Вопрос 35

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

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

Вопрос 36

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

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

Вопрос 37

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

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

Вопрос 38

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

  1.  Нет;
  2.  Да;

Вопрос 39

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

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

Вопрос 40

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

  1.  
  2.  
  3.  
  4.  
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-exam»