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

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

Вариант 4248151907.

Ваше имя*:

Вопрос 1

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

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

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

Вопрос 10

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

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

Вопрос 11

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

Вопрос 12

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

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

Вопрос 13

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

Вопрос 14

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


  1.  ;
  2.  ;
  3.  

Вопрос 15

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

  1.  
  2.  
  3.  
  4.  3

Вопрос 16

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

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

Вопрос 17

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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

Вопрос 21

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

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

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

называется:

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

Вопрос 22

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 23

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

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

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

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

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

Вопрос 24

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

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

Вопрос 25

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

Вопрос 26

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

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

Вопрос 27

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

Вопрос 28

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 29

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

Вопрос 30

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

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

Вопрос 31

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

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

Вопрос 32

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

Вопрос 33

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

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

Вопрос 34

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

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

Вопрос 35

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

Вопрос 36

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

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

Вопрос 37

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

Вопрос 38

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

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

Вопрос 39

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

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

Вопрос 40

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

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