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

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

Вариант 2953472219.

Ваше имя*:

Вопрос 1

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

  1.  метод условного спуска
  2.  PTAS-апроксимация
  3.  вероятностное округление
  4.  дерандомизация
  5.  округление коэффициентов

Вопрос 2

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

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

Вопрос 3

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 4

Вероятностные «zero-error»-алгоритмы:

  1.  Когда дают ответ он правильный, но могут отвечать «не знаю»
  2.  Всегда дают верный ответ в случае, если возвращают «0»
  3.  Могут ошибаться, но только в случае, если возвращают «0»
  4.  Всегда дают верный ответ

Вопрос 5

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 6

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

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

Вопрос 7

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


  1.  Форда-Фалкерсона
  2.  Немхаузера-Ульмана
  3.  Флойда-Уоршолла
  4.  Включений-Исключений
  5.  Беллмана-Форда

Вопрос 8

В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке рассматривался алгоритм, который оперирует множеством…

  1.  доминирующих наборов
  2.  набранных отборов
  3.  наборов максимальной стоимости для каждого веса
  4.  отборных наборов
  5.  наборов минимального веса для каждой стоимости
  6.  допустимых наборов
  7.  недопустимых наборов

Вопрос 9

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

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

Вопрос 10

Как называется задача оптимизации со следующей формулировкой:

  1.  Выпуклое программирование
  2.  Векторное программирование
  3.  Полуопределенное программирование
  4.  Положительное линейное программирование (ПЛП)
  5.  Линейное программирование
  6.  Целочисленное линейное программирование
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Эффективные_алгоритмы»