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

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

Вариант 640095207.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

Вопрос 3

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

  1.  
  2.  
  3.  
  4.  

Вопрос 4

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

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

Вопрос 5

Пусть

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

Что верно?

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

Вопрос 6

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

  1.  
  2.  
  3.  
  4.  

Вопрос 7

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

  1.  
  2.  
  3.  

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

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

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

Вопрос 15

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


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

Вопрос 16

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

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

Вопрос 17

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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

  1.  Да
  2.  Нет

Вопрос 21

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

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

Вопрос 22

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

Вопрос 23

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

NPC-GQ08.png


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

Вопрос 24

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

Вопрос 25

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

  1.  
  2.  
  3.  
  4.  3

Вопрос 26

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

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

Вопрос 27

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

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

Вопрос 28

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

  1.  Да
  2.  Нет

Вопрос 29

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

  1.  Нет;
  2.  Да;

Вопрос 30

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

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

Вопрос 31

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

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

Вопрос 32

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

Вопрос 33

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 34

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

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

Вопрос 35

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

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

Вопрос 36

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 37

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

  1.  Да;
  2.  Нет;

Вопрос 38

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

Вопрос 39

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

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

Вопрос 40

Какое утверждение неверно?

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