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

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

Вариант 2026995031.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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

  1.  
  2.  
  3.  
  4.  

Вопрос 3

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

Вопрос 4

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

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

Вопрос 5

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

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

Вопрос 14

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

NPC-GQ08.png


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

Вопрос 15

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

Вопрос 16

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

  1.  Нет
  2.  Да

Вопрос 17

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 18

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 19

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

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

Задача 2SAT:

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

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 26

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

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

Вопрос 27

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

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

Вопрос 28

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

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

Вопрос 29

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

Вопрос 30

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

  1.  3
  2.  
  3.  
  4.  

Вопрос 31

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

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

Вопрос 32

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

Вопрос 33

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

  1.  
  2.  
  3.  
  4.  

Вопрос 34

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

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

Вопрос 35

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

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

Вопрос 36

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

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

Вопрос 37

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

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

Вопрос 38

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

Вопрос 39

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

Вопрос 40

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

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