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

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

Вариант 2427291627.

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

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

Вопрос 4

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

  1.  Нет;
  2.  Да;

Вопрос 5

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

Вопрос 6

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

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

Вопрос 7

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 8

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

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

Вопрос 9

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

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

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

Вопрос 10

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

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

Вопрос 11

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


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

Что верно?

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

Вопрос 12

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

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

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

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

Вопрос 13

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

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

  1.  
  2.  
  3.  
  4.  

Вопрос 17

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

Вопрос 18

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

Вопрос 19

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

  1.  
  2.  
  3.  
  4.  

Вопрос 20

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

Вопрос 21

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 22

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

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

Вопрос 23

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

Вопрос 24

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

Вопрос 25

Метод многократного запуска вероятностного алгоритма, с целью уменьшения вероятности ошибки называется:

  1.  «дерандомизация»
  2.  «вероятностная амплификация»
  3.  «отладка вероятности»
  4.  «антирандомизация»

Вопрос 26

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

  1.  Да
  2.  Нет

Вопрос 27

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

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

Вопрос 28

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

Вопрос 29

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

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

Вопрос 30

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

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

Вопрос 31

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

Вопрос 32

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

Вопрос 33

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

Вопрос 34

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

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

Вопрос 35

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

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

Вопрос 36

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 37

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

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

Вопрос 38

Пусть

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

Что верно?

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

Вопрос 39

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

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

Вопрос 40

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

  1.  PTAS-апроксимация
  2.  округление коэффициентов
  3.  вероятностное округление
  4.  метод условного спуска
  5.  дерандомизация
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-exam»