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

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

Вариант 1530184242.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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

Вопрос 3

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

  1.  Построение эффективных в среднем алгоритмов
  2.  Применение эволюционных алгоритмов
  3.  Построение эффективных алгоритмов муравьиной колонии

Вопрос 4

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

Вопрос 5

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

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

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

Вопрос 6

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

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

Вопрос 7

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

Аню и Колю попросили показать, что задача X — NP-полна. Аня показала полиномиальную сводимость по Карпу от 3SAT к X, а Коля показал полиномиальную сводимость по Карпу от X к 3SAT.

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

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

Вопрос 11

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

  1.  
  2.  
  3.  3
  4.  

Вопрос 12

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

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

Вопрос 13

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 14

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

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

Вопрос 15

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

Вопрос 16

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

Вопрос 17

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

Вопрос 18

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

  1.  Нет
  2.  Да

Вопрос 19

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

  1.  Заполнял таблицу «наиболее выполняющими» наборами
  2.  Вероятностно подсчитывал число невыполненных наборов
  3.  Находит приближенное решение, с точностью
  4.  Вероятностно подсчитывал число выполненных наборов
  5.  Подсчитывал число невыполненных наборов
  6.  Точность решения в среднем —

Вопрос 20

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

NPC-GQ08.png


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