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

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

Вариант 3499859954.

Ваше имя*:

Вопрос 1

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

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

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

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

Вопрос 2

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

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

Вопрос 3

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

Вопрос 7

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

Вопрос 8

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

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

Вопрос 9

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

Вопрос 10

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

  1.  
  2.  
  3.  
  4.  

Вопрос 14

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

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

Вопрос 15

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

  1.  
  2.  
  3.  
  4.  

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

Вопрос 19

Задача 2SAT:

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

Вопрос 20

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

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

Вопрос 21

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

NPC-GQ08.png


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

Вопрос 22

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

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

Вопрос 23

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

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

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

Вопрос 24

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

  1.  Да
  2.  Нет

Вопрос 25

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

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

Вопрос 26

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

Вопрос 27

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

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

Вопрос 28

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


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

Что верно?

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

Вопрос 29

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

Вопрос 30

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

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

Вопрос 31

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

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

Вопрос 32

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

Вопрос 33

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

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

Вопрос 34

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

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

Вопрос 35

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

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

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

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

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

Вопрос 36

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

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

Вопрос 37

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

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

Вопрос 38

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

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

Вопрос 39

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

  1.  
  2.  
  3.  
  4.  

Вопрос 40

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


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