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

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

Вариант 421142406.

Ваше имя*:

Вопрос 1

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

  1.  полином, но степени больше 2
  2.  квадратичное
  3.  экспоненциальное
  4.  
  5.  линейное

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

Гамильтонов цикл в графе:

  1.  проходит через все ребра по одному разу
  2.  проходит через все вершины и ребра по одному разу
  3.  проходит через все вершины по одному разу

Вопрос 5

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

  1.  двусторонние
  2.  односторонние
  3.  «PP»-ошибки
  4.  трехсторонние

Вопрос 6

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

  1.  односторонние
  2.  «BP»-ошибки
  3.  трехсторонние
  4.  двусторонние

Вопрос 7

Какие условия на существование полиномиального в среднем алгоритма упаковки требуются в соответствующей теме?

m
элементов,
n
подмножеств
p
вероятность ненулевого элемента в матрице инцидентности
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  

Вопрос 8

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

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

Вопрос 9

Цикл, проходящий через все ребра графа по одному разу, называется

  1.  Наполеонов цикл
  2.  Петля Нестерова
  3.  Цикл Нельсона
  4.  Гамильтонов цикл
  5.  Эйлеров цикл

Вопрос 10

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

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

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

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

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

Вопрос 11

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

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

Вопрос 12

Какие условия на существование полиномиального в среднем алгоритма для «SAT» требуются в соответствующей теме?

Напомним, что у нас n переменных и m скобок, p — вероятность появления переменной в каждой скобке.


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 13

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 14

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


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

Вопрос 15

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

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

Вопрос 16

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

  1.  Миллера-Рабина
  2.  Бейли — Померанца — Селфриджа — Уогстаффа,
  3.  Миллера
  4.  Все существующие тесты на простоту являются рандомизированными
  5.  Бейли — Померанца — Селфриджа — Уогстаффа

Вопрос 17

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 18

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 19

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

  1.  Подсчитывал число невыполненных наборов
  2.  Заполнял таблицу «наиболее выполняющими» наборами
  3.  Вероятностно подсчитывал число невыполненных наборов
  4.  Точность решения в среднем —
  5.  Вероятностно подсчитывал число выполненных наборов
  6.  Находит приближенное решение, с точностью

Вопрос 20

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

  1.  динамическое программирование с отбором наиболее дорогих наборов
  2.  динамическое программирование с отбором наиболее легких наборов
  3.  алгоритм Немхаузера-Ульмана
  4.  алгоритм Беллмана-Форда
  5.  метод условного спуска

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 24

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

  1.  Каргера-Штейна
  2.  Форда-Фалкерсона
  3.  Беллмана-Форда
  4.  Флойда-Уоршелла
  5.  Эдмондса-Карпа
  6.  Немхаузера-Ульмана

Вопрос 25

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

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

Вопрос 26

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 27

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

  1.  
  2.  
  3.  
  4.  3

Вопрос 28

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

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

Вопрос 29

Метод многократного запуска вероятностного алгоритма, с целью уменьшения вероятности ошибки называется:

  1.  «отладка вероятности»
  2.  «антирандомизация»
  3.  «дерандомизация»
  4.  «вероятностная амплификация»

Вопрос 30

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

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