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

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

Вариант 2965036474.


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


Вопрос 1

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

NPC-GQ08.png


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

Вопрос 2

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 3

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

  1.  
  2.  
  3.  

Вопрос 4

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

  1.  Да;
  2.  Нет;

Вопрос 5

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

Вопрос 6

Существует ли биекция между классами и ?

  1.  Ответ на этот вопрос нет, т.к. нам ничего неизвестно про равенство классов и ;
  2.  Нет, не существует;
  3.  Да, существует;

Вопрос 7

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

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

Вопрос 8

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

Вопрос 9

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

Вопрос 10

В работах по теории сложности алгоритм называется полиномиальным в среднем, если для входов длины n и времени работы алгоритма T, выполняется:

  1.  
  2.  
  3.  
  4.  

Вопрос 11

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

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

Вопрос 12

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


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

Что верно?

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

Вопрос 13

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


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

Вопрос 14

Является ли разрешимым множество натуральных чисел, не превосходящих :

  1.  Да
  2.  Нет
  3.  Неизвестно, поскольку ответ на этот вопрос следует из истинности\ложности гипотезы Римана;

Вопрос 15

Предположим, разумеется, что Тогда что будет верно?

  1.  
  2.  
  3.  
  4.  

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

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


  1.  ;
  2.  ;
  3.  

Вопрос 22

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

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

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

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

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

  1.  Нет;
  2.  Да;

Вопрос 26

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

  1.  
  2.  
  3.  
  4.  

Вопрос 27

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


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

Вопрос 28

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

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

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


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

Вопрос 29

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

  1.  Да;
  2.  Нет;

Вопрос 30

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

Вопрос 31

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

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

Вопрос 32

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

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

Вопрос 33

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

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

Вопрос 34

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

Вопрос 35

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

Вопрос 36

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

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

Вопрос 37

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

Вопрос 38

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

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

Вопрос 39

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

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

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

Вопрос 40

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

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