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

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

Вариант 3032703501.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

Вопрос 3

Пусть

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

Что верно?

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

  1.  Да
  2.  Нет

Вопрос 7

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

Вопрос 11

Вероятностный алгоритм A, который, получая

  • вход I
  • вещественное

за время, полиномиальное от , выдает в качестве выхода , такое, что

называется:

  1.  -полной рандомизированной аппроксимационной схемой
  2.  Полностью полиномиальной аппроксимационной схемой
  3.  Полиномиальной рандомизированной аппроксимационной схемой
  4.  Полностью полиномиальной рандомизированной аппроксимационной схемой

Вопрос 12

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

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

Вопрос 13

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

  1.  Нет
  2.  Да

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

Вопрос 20

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

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

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

Вопрос 21

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

  1.  метод условного спуска
  2.  дерандомизация
  3.  вероятностное округление
  4.  округление коэффициентов
  5.  PTAS-апроксимация

Вопрос 25

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

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

Вопрос 26

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 27

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

  1.  
  2.  
  3.  

Вопрос 28

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

Вопрос 29

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


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

Вопрос 30

Задача 2SAT:

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

Вопрос 31

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

Вопрос 32

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

  1.  
  2.  
  3.  
  4.  

Вопрос 33

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

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

Вопрос 34

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

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

Вопрос 35

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

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

Вопрос 36

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

Вопрос 37

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

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

Вопрос 38

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

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

Вопрос 39

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

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

Вопрос 40

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

  1.  односторонние (при ответе «0»)
  2.  односторонние (при ответе «1»)
  3.  никакие
  4.  трехсторонние
  5.  «ZPP»-ошибки
  6.  двусторонние
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-exam»