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

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

Вариант 759973564.

Ваше имя*:

Вопрос 1

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


  1.  ;
  2.  
  3.  ;

Вопрос 2

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

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

Вопрос 3

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

Вопрос 4

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

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

Вопрос 5

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

Вопрос 6

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

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

Вопрос 7

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

  1.  Да;
  2.  Нет;

Вопрос 8

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


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

Что верно?

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

Вопрос 9

Пусть

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

Что верно?

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

Вопрос 10

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

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

Вопрос 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.  Только (I)
  2.  Все остальные варианты — неверны.
  3.  Только (I) и (IV)
  4.  Только (III)
  5.  Только (II)

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

  1.  
  2.  
  3.  
  4.  

Вопрос 16

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

Какой метод применялся в теме про подсчет выполняющих наборов для ДНФ?

  1.  Монте-Карло
  2.  Динамическое программирование
  3.  Вероятностное округление
  4.  Дерандомизация вероятностного округления
  5.  Полный перебор

Вопрос 21

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

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

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

называется:

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

Вопрос 22

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

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

Вопрос 23

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

Вопрос 24

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

Вопрос 25

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

Вопрос 26

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

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

Вопрос 27

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

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

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

Вопрос 31

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

  1.  3
  2.  
  3.  
  4.  

Вопрос 32

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

Вопрос 33

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

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

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

Вопрос 34

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

Вопрос 35

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

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

Вопрос 36

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

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

Вопрос 37

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

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

Вопрос 38

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

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

Вопрос 39

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

  1.  
  2.  
  3.  

Вопрос 40

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

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

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

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

  1.  Нет, полиномиального алгоритма нет
  2.  Да, есть полиномиальный алгоритм
  3.  Полиномиального нет, но есть квазиполиномиальный алгоритм
  4.  Полиномиального нет, но есть псевдополиномиальный алгоритм
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-exam»