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

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

Вариант 2215241943.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

  1.  
  2.  
  3.  3
  4.  

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

Задача 2SAT:

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

Вопрос 10

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

  1.  Нет
  2.  Да

Вопрос 14

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

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

Вопрос 15

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

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

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

Вопрос 16

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

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

Вопрос 17

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 18

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

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

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


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

Что верно?

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

Вопрос 22

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

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

Вопрос 23

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

Вопрос 24

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

  1.  Нет;
  2.  Да;

Вопрос 25

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

Вопрос 26

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

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

Вопрос 27

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

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

Вопрос 28

Пусть

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

Что верно?

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

Вопрос 29

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


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

Вопрос 30

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

Вопрос 31

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

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

Вопрос 32

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

Вопрос 33

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

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

Вопрос 34

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

Вопрос 35

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


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

Вопрос 36

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

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

Вопрос 37

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

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

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

называется:

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

Вопрос 38

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

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

Вопрос 39

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

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

Вопрос 40

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

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