Тест по курсу «Эффективные алгоритмы для труднорешаемых задач» — вопросы

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

Вариант 994133364.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

  1.  Разность множеств;
  2.  Дополнение;
  3.  Декартово произведение;

Вопрос 3

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

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

Вопрос 4

Пусть

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

Что верно?

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

Вопрос 5

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

Вопрос 6

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

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

Вопрос 7

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


  1.  ;
  2.  ;
  3.  

Вопрос 8

Рассмотрим модификацию задачи «Сумма размеров», разрешим даже отрицательные размеры.

Формально: Даны натуральные числа , , и число B.

Надо узнать, существует ли решение в 0/1 переменных уравнения .

Существует ли полиномиальный алгоритм для этой задачи?

  1.  Полиномиального нет, но есть квазиполиномиальный алгоритм
  2.  Да, есть полиномиальный алгоритм
  3.  Нет, полиномиального алгоритма нет

Вопрос 9

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

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

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

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

Вопрос 15

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

Вопрос 16

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

Вопрос 17

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

  1.  Да
  2.  Нет

Вопрос 18

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

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

  1.  
  2.  
  3.  Quiz:Полиномиальный в среднем алгоритм для задачи упаковки
  4.  
  5.  

Вопрос 22

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

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

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

Вопрос 23

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

  1.  Нет
  2.  Да

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 27

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

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

Вопрос 28

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

Вопрос 29

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

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

Вопрос 30

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

Вопрос 31

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

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

Вопрос 32

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

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

Вопрос 33

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

NPC-GQ08.png


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

Вопрос 34

В работах по теории сложности алгоритм называется полиномиальным в среднем, если для входов длины n и времени работы алгоритма T, выполняется:

  1.  
  2.  
  3.  
  4.  

Вопрос 35

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 36

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

Вопрос 37

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

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

Вопрос 38

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

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

Вопрос 39

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

Вопрос 40

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

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

Вопрос 41

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

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

Вопрос 42

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

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

Вопрос 43

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

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

Вопрос 44

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

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

Вопрос 45

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

Вопрос 46

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 47

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

  1.  
  2.  
  3.  
  4.  

Вопрос 48

Рассмотрим модификацию задачи «Сумма размеров», разрешим даже отрицательные размеры.

Формально: Даны натуральные числа , , и число B.

Надо узнать, существует ли решение в 0/1 переменных уравнения .

Существует ли полиномиальный алгоритм для этой задачи?

  1.  Полиномиального нет, но есть квазиполиномиальный алгоритм
  2.  Да, есть полиномиальный алгоритм
  3.  Полиномиального нет, но есть псевдополиномиальный алгоритм
  4.  Нет, полиномиального алгоритма нет

Вопрос 49

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

Вопрос 50

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

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

Вопрос 51

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

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

Вопрос 52

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

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

Вопрос 53

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

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

Вопрос 54

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

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

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

называется:

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

Вопрос 55

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

  1.  3
  2.  
  3.  
  4.  

Вопрос 56

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

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

Вопрос 57

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

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

Вопрос 58

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

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

Вопрос 59

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

Вопрос 60

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

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

Вопрос 61

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

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

Вопрос 62

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


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

Что верно?

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

Вопрос 63

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

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

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

Вопрос 64

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

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

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


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

Вопрос 65

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

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

Вопрос 66

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

Вопрос 67

Цикл, проходящий через все ребра графа по одному разу, называется

  1.  Гамильтонов цикл
  2.  Цикл Нельсона
  3.  Эйлеров цикл
  4.  Петля Нестерова
  5.  Наполеонов цикл

Вопрос 68

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

Вопрос 69

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

Вопрос 70

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


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

Вопрос 71

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

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

Вопрос 72

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

  1.  
  2.  
  3.  
  4.  

Вопрос 73

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

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

Вопрос 74

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

  1.  Нет;
  2.  Да;

Вопрос 75

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

  1.  
  2.  
  3.  

Вопрос 76

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

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

Вопрос 77

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

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

Вопрос 78

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

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

Вопрос 79

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

Вопрос 80

  1.  RP
  2.  coZPP
  3.  PP
  4.  coRP
  5.  FPTAS
  6.  
  7.  BPP
  8.  ZPP
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-innopolis-exam»