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

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

Вариант 1506830247.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

  1.  Да;
  2.  Нет;

Вопрос 4

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

Вопрос 5

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

Вопрос 6

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

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

Вопрос 7

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

Вопрос 8

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

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

Вопрос 9

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

Вопрос 10

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

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

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

Вопрос 11

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 12

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

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

Вопрос 13

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


  1.  ;
  2.  ;
  3.  

Вопрос 14

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 15

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

  1.  
  2.  
  3.  
  4.  

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

  1.  
  2.  
  3.  
  4.  

Вопрос 24

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


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

Что верно?

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

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

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

Вопрос 28

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

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

Вопрос 29

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

  1.  Нет
  2.  Да

Вопрос 30

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

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

Вопрос 31

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

  1.  Да;
  2.  Нет;

Вопрос 32

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

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

Вопрос 33

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

Вопрос 34

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

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

Вопрос 35

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

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

Вопрос 36

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

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

Вопрос 37

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

Вопрос 38

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

Вопрос 39

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

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

Вопрос 40

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

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

Вопрос 41

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

Вопрос 42

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

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

Вопрос 43

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

Вопрос 44

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

  1.  Да;
  2.  Нет;

Вопрос 45

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

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

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

называется:

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

Вопрос 46

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

NPC-GQ08.png


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

Вопрос 47

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

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

Вопрос 48

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


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

Вопрос 49

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

Вопрос 50

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

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

Вопрос 51

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

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

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

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

Вопрос 52

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

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

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

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

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

Вопрос 53

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 54

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

  1.  
  2.  
  3.  

Вопрос 55

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

  1.  
  2.  
  3.  3
  4.  

Вопрос 56

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

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

Вопрос 57

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

Вопрос 58

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

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

Вопрос 59

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

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

Вопрос 60

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

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

Вопрос 61

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

Вопрос 62

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

Вопрос 63

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

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

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

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

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

Вопрос 64

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

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

Вопрос 65

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


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

Вопрос 66

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

Вопрос 67

Задача 2SAT:

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

Вопрос 68

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

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

Вопрос 69

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

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

Вопрос 70

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

Вопрос 71

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

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

Вопрос 72

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

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

Вопрос 73

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

  1.  Нет
  2.  Да

Вопрос 74

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

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

Вопрос 75

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

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

Вопрос 76

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

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

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

Вопрос 77

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 78

Пусть

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

Что верно?

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

Вопрос 79

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

Вопрос 80

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

  1.  «дерандомизация»
  2.  «отладка вероятности»
  3.  «антирандомизация»
  4.  «вероятностная амплификация»
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-innopolis-exam»