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

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

Вариант 100445498.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

Вопрос 3

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

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

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

Вопрос 8

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

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

Вопрос 9

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

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

Вопрос 13

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

  1.  
  2.  
  3.  

Вопрос 14

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

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

Вопрос 15

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


  1.  Из сводимости по Куку следует сводимость по Карпу
  2.  Из сводимости по Карпу следует сводимость по Куку
  3.  Верного ответа нет

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

Вопрос 20

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

  1.  
  2.  
  3.  
  4.  3

Вопрос 24

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

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

Вопрос 25

Задача 2SAT:

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

Вопрос 26

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

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

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


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

Вопрос 27

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

Вопрос 28

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

Вопрос 29

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

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

Вопрос 30

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

Вопрос 31

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

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

Вопрос 32

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

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

Вопрос 33

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

Вопрос 34

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 35

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

Вопрос 36

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

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

Вопрос 37

Паросочетание, покрывающее все вершины графа, называется

  1.  сочетающим
  2.  максимальным
  3.  вершинным
  4.  совершенным
  5.  покрывающим

Вопрос 38

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


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

Что верно?

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

Вопрос 39

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 40

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

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