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

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

Вариант 3139238832.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

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

называется:

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

Вопрос 5

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

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

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

Вопрос 6

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

  1.  
  2.  
  3.  

Вопрос 7

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

  1.  Да;
  2.  Нет;

Вопрос 8

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

  1.  
  2.  
  3.  
  4.  

Вопрос 12

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

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

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


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

Вопрос 16

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

Вопрос 17

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

Вопрос 18

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

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

Вопрос 19

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

  1.  Нет
  2.  Да

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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


  1.  
  2.  ;
  3.  ;

Вопрос 27

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

Вопрос 28

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

Вопрос 29

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

Вопрос 30

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

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

Вопрос 31

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

  1.  
  2.  
  3.  
  4.  

Вопрос 32

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

Вопрос 33

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

  1.  Нет;
  2.  Да;

Вопрос 34

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

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

Вопрос 35

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

Вопрос 36

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

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

Вопрос 37

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

Вопрос 38

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

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

Вопрос 39

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


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

Что верно?

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

Вопрос 40

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

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