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

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

Вариант 562871555.

Ваше имя*:

Вопрос 1

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 2

  1.  
  2.  
  3.  
  4.  
  5.  Quiz:Полиномиальный в среднем алгоритм для задачи упаковки

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

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