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

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

Вариант 3288283671.

Прошло 00:00:02.
Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

  1.  
  2.  
  3.  

Вопрос 5

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

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

Вопрос 6

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


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

Что верно?

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

Вопрос 7

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

  1.  Нет
  2.  Да

Вопрос 8

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

Вопрос 9

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

  1.  
  2.  
  3.  
  4.  

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

Вопрос 13

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

  1.  Да;
  2.  Нет;

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

Вопрос 21

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


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

Вопрос 22

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

Вопрос 23

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

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

Вопрос 24

Пусть

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

Что верно?

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

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

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

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

Вопрос 31

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

  1.  Да
  2.  Нет

Вопрос 32

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 33

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

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

Вопрос 34

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

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

Вопрос 35

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

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

Вопрос 36

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

Вопрос 37

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

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

Вопрос 38

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

Вопрос 39

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

Вопрос 40

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

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

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

называется:

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