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

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
11121314151617181920
21222324252627282930
31323334353637383940
Еженедельный по «сложности алгоритмов» для 3 курса ИСПРАН

Вариант 322061062.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке рассматривался алгоритм, который оперирует множеством…

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

Вопрос 3

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

  1.  Нет
  2.  Да

Вопрос 4

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

Вопрос 5

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

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

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


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

Вопрос 6

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

Вопрос 7

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 8

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

Вопрос 9

В теме про полиномиальный в среднем алгоритм для «SAT» мы применяли формулу…


  1.  Немхаузера-Ульмана
  2.  Форда-Фалкерсона
  3.  Включений-Исключений
  4.  Беллмана-Форда
  5.  Флойда-Уоршолла

Вопрос 10

Какие условия на существование полиномиального в среднем алгоритма для «SAT» требуются в соответствующей теме?

Напомним, что у нас n переменных и m скобок, p — вероятность появления переменной в каждой скобке.


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

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

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

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

Вопрос 14

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

Вопрос 15

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

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

Вопрос 16

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

Вопрос 17

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

  1.  алгоритм Немхаузера-Ульмана
  2.  динамическое программирование с отбором наиболее дорогих наборов
  3.  алгоритм Беллмана-Форда
  4.  метод условного спуска
  5.  динамическое программирование с отбором наиболее легких наборов

Вопрос 18

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

  1.  
  2.  
  3.  

Вопрос 19

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

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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


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

Вопрос 25

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

  1.  
  2.  
  3.  
  4.  3

Вопрос 26

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

Вопрос 27

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

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

Вопрос 28

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

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

Вопрос 29

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

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

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

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

Вопрос 30

Задача 2SAT:

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

Вопрос 31

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 32

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

Вопрос 33

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

Вопрос 34

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

Вопрос 35

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

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

Вопрос 36

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

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

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

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

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

Вопрос 37

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

Вопрос 38

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 39

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

Вопрос 40

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