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

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

Вариант 394840305.

Ваше имя*:

Вопрос 1

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

Вопрос 2

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

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

Вопрос 3

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

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

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

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

Вопрос 4

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


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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

Вопрос 8

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

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

Вопрос 9

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

NPC-GQ08.png


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

Вопрос 10

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

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

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

называется:

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

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

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

Вопрос 17

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

Вопрос 18

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

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

Вопрос 19

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

Вопрос 20

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

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

Вопрос 21

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

  1.  
  2.  
  3.  
  4.  

Вопрос 22

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

Вопрос 23

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 24

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


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

Что верно?

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

Вопрос 25

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

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

Вопрос 26

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

  1.  
  2.  
  3.  

Вопрос 27

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

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

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

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

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

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

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

  1.  Нет;
  2.  Да;

Вопрос 31

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

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

Вопрос 32

Пусть

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

Что верно?

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

Вопрос 33

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

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

Вопрос 34

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

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

Вопрос 35

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

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

Вопрос 36

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

  1.  Да;
  2.  Нет;

Вопрос 37

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

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

Вопрос 38

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

Вопрос 39

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

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

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

Вопрос 40

Задача 2SAT:

  1.  разрешима за полиномиальное время, но не за константное время.
  2.  разрешима за константное время, т.к. любой вход для такой задачи выполним.
  3.  NP-трудна, но не NP-полна.
  4.  NP-полна
  5.  Все остальные варианты — неверны.
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-exam»