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

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

Вариант 10476977.

Ваше имя*:

Вопрос 1

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


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

Вопрос 2

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

  1.  
  2.  
  3.  
  4.  

Вопрос 3

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

Вопрос 4

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

Вопрос 5

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

Вопрос 10

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

Вопрос 11

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

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

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

Вопрос 12

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

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

Вопрос 13

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

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

Вопрос 20

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


  1.  ;
  2.  ;
  3.  

Вопрос 21

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

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

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

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

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

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

Пусть

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

Что верно?

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

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

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

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

Вопрос 31

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

Вопрос 32

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

Вопрос 33

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

Вопрос 34

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

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

Вопрос 35

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

Вопрос 36

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

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

Вопрос 37

Задача 2SAT:

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

Вопрос 38

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

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

Вопрос 39

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

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

Вопрос 40

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

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