Эффективные алгоритмы — вопросы

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

Вариант 2140777015.

Ваше имя*:

Вопрос 1

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

Вопрос 2

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

  1.  
  2.  
  3.  
  4.  

Вопрос 3

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

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

Вопрос 4

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

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

Вопрос 8

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

  1.  
  2.  
  3.  
  4.  

Вопрос 9

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

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

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


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

Вопрос 10

  1.  
  2.  
  3.  
  4.  
  5.  
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Эффективные_алгоритмы»