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

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

Вариант 1626741692.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

  1.  Да;
  2.  Нет;

Вопрос 6

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

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

Вопрос 7

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

Вопрос 8

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

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

Вопрос 9

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

  1.  
  2.  
  3.  
  4.  

Вопрос 10

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

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

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

Вопрос 11

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


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

Вопрос 12

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

Вопрос 13

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

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

Вопрос 14

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

Вопрос 15

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

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

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

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 19

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

  1.  Нет
  2.  Да

Вопрос 20

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 21

Задача 2SAT:

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

Вопрос 22

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


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

Что верно?

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

Вопрос 23

Возможно ли сконструировать алгоритм , который для произвольной машины Тюринга и входа определит, остановится ли данная М.Т. на заданном входе?

  1.  Да, известно чёткое описание того, как это делать;
  2.  Формально да, но никто не знает как именно это сделать (примерно как со вполне упорядочиванием );
  3.  Нет

Вопрос 24

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

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

Вопрос 25

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

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

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


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

Вопрос 26

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

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

Вопрос 27

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

  1.  
  2.  
  3.  
  4.  

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

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

  1.  3
  2.  
  3.  
  4.  

Вопрос 31

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

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

Вопрос 32

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

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

Вопрос 33

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

Вопрос 34

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

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

Вопрос 35

Аню и Колю попросили показать, что задача X — NP-полна. Аня показала полиномиальную сводимость по Карпу от 3SAT к X, а Коля показал полиномиальную сводимость по Карпу от X к 3SAT.

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

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

Вопрос 36

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

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

Вопрос 37

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

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

Вопрос 38

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

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

Вопрос 39

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

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

Вопрос 40

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