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

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

Вариант 2493127602.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 3

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

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

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

называется:

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

Вопрос 4

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

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

Вопрос 5

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

  1.  Обе в P
  2.  Обе NP-полны
  3.  Первая NP-полна и вторая в P.
  4.  Все остальные варианты — неверны.
  5.  Первая неразрешима и вторая — NP-полна.
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras»