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

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

Вариант 2060339449.

Прошло 00:00:04.
Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

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

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

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

Вопрос 3

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

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

Вопрос 4

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

Вопрос 5

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

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

Вопрос 6

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

Вопрос 7

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

Вопрос 8

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

Вопрос 9

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

  1.  
  2.  
  3.  
  4.  

Вопрос 13

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

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

Вопрос 14

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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


  1.  ;
  2.  ;
  3.  

Вопрос 23

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

  1.  динамическое программирование с отбором наиболее легких наборов
  2.  алгоритм Кристофидеса
  3.  дерандомизация
  4.  жадный алгоритм для рюкзака

Вопрос 24

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

Вопрос 25

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

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

Вопрос 26

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

  1.  
  2.  
  3.  
  4.  

Вопрос 27

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

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

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

Вопрос 28

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

Вопрос 29

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


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

Вопрос 30

Выберите верное верное утверждение из списка ниже, если верных вариантов ответа несколько, то выберите наиболее сильный из них:

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

Вопрос 31

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

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

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


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

Вопрос 32

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 33

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

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

Вопрос 34

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

  1.  
  2.  
  3.  

Вопрос 35

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

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

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

называется:

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

Вопрос 36

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

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

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

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

Вопрос 37

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

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

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

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

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

Вопрос 38

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

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

Вопрос 39

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

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

Вопрос 40

Задача 2SAT:

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