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

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

Вариант 2990959240.

Ваше имя*:

Вопрос 1

Какой класс ошибок допускают алгоритмы решающие задачи из класса ZPP?

  1.  односторонние (при ответе «1»)
  2.  трехсторонние
  3.  односторонние (при ответе «0»)
  4.  двусторонние
  5.  «ZPP»-ошибки
  6.  никакие

Вопрос 2

Рассмотрим модификацию задачи «Сумма размеров», разрешим даже отрицательные размеры.

Формально: Даны натуральные числа , , и число B.

Надо узнать, существует ли решение в 0/1 переменных уравнения .

Существует ли полиномиальный алгоритм для этой задачи?

  1.  Нет, полиномиального алгоритма нет
  2.  Полиномиального нет, но есть псевдополиномиальный алгоритм
  3.  Да, есть полиномиальный алгоритм
  4.  Полиномиального нет, но есть квазиполиномиальный алгоритм

Вопрос 3

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

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

Вопрос 4

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

  1.  
  2.  3
  3.  
  4.  

Вопрос 5

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

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

Вопрос 6

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


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

Вопрос 7

Задача Коммивояжера, в которой для матрицы расстояний выполнено неравенство треугольника, называется:

  1.  Гамильтоновой
  2.  Евклидовой
  3.  Треугольной
  4.  Метрической
  5.  Эйлеровой

Вопрос 8

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

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

Вопрос 9

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

  1.  алгоритм Кристофидеса
  2.  жадный алгоритм для рюкзака
  3.  дерандомизация
  4.  динамическое программирование с отбором наиболее легких наборов

Вопрос 10

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

  1.  Бейли — Померанца — Селфриджа — Уогстаффа
  2.  Миллера
  3.  Все существующие тесты на простоту являются рандомизированными
  4.  Бейли — Померанца — Селфриджа — Уогстаффа,
  5.  Миллера-Рабина
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Эффективные_алгоритмы»