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

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

Вариант 2392401918.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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


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

Вопрос 3

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

Вопрос 4

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


  1.  ;
  2.  ;
  3.  

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

Вопрос 8

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 9

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

Вопрос 10

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

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

Вопрос 11

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

Вопрос 12

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

  1.  
  2.  
  3.  
  4.  

Вопрос 13

Задача 2SAT:

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

Вопрос 14

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

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

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


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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

  1.  Да;
  2.  Нет;

Вопрос 20

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

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

Вопрос 21

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

Пусть

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

Что верно?

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

Вопрос 26

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

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

Вопрос 27

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

Вопрос 28

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

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

Вопрос 29

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 30

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

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

Вопрос 31

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

  1.  Нет
  2.  Да

Вопрос 32

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

  1.  Да;
  2.  Нет;

Вопрос 33

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

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

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

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

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

Вопрос 34

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

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

Вопрос 35

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

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

Вопрос 36

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 37

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

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

Вопрос 38

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

Вопрос 39

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

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

Вопрос 40

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

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