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

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

Вариант 3074965732.

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

Вопрос 1

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

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

Вопрос 2

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

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

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

называется:

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

Вопрос 3

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

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

Вопрос 4

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

Вопрос 5

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

Вопрос 6

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

  1.  Нет
  2.  Да

Вопрос 7

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

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

Вопрос 8

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

Вопрос 9

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

  1.  Да;
  2.  Нет;

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

Вопрос 16

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

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

Вопрос 17

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

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

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

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

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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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

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

Вопрос 21

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

  1.  Нет;
  2.  Да;

Вопрос 25

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

Вопрос 26

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


  1.  ;
  2.  
  3.  ;

Вопрос 27

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 28

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

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

Вопрос 29

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

Вопрос 30

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

Вопрос 31

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 32

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

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

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

Вопрос 33

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

  1.  Нет;
  2.  Да;

Вопрос 34

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

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

Вопрос 35

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

Вопрос 36

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

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

Вопрос 37

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

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

Вопрос 38

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

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

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

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

Вопрос 39

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

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

Вопрос 40

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