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

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

Вариант 3582188075.

Ваше имя*:

Вопрос 1

Паросочетание, это подмножество...


  1.  ребер
  2.  циклов
  3.  связных подграфов
  4.  вершин

Вопрос 2

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

  1.  Выпуклое программирование
  2.  Целочисленное линейное программирование
  3.  Полуопределенное программирование
  4.  Линейное программирование
  5.  Векторное программирование
  6.  Положительное линейное программирование (ПЛП)

Вопрос 3

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

Какова сложность вероятностного алгоритма Фрейвалда для проверки тождества AB=C для матриц  ?

  1.  
  2.  
  3.  
  4.  

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

В работах по теории сложности алгоритм называется полиномиальным в среднем, если для входов длины n и времени работы алгоритма T, выполняется:

  1.  
  2.  
  3.  
  4.  

Вопрос 10

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

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

Вопрос 11

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 12

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

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

Вопрос 13

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 14

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

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

Вопрос 15

В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке полиномиальность в среднем доказана для следующего распределения входных данных:

  1.  веса произвольные, стоимость выбираются случайно
  2.  и стоимости и веса выбираются случайно
  3.  стоимости произвольные, веса выбираются случайно

Вопрос 16

Для чего применяется «дерандомизация»:

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

Вопрос 17

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

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

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

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

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

Вопрос 18

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

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

Вопрос 19

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 20

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

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

Вопрос 21

Есть граф G=(V,E). Разбиение множества вершин V на непересекающиеся множества S и T называется:

  1.  Разбивка
  2.  Поток
  3.  Разрез
  4.  Раскладка
  5.  Паросочетание
  6.  Клика

Вопрос 22

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

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

Вопрос 23

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

  1.  Линейное программирование
  2.  Целочисленное линейное программирование
  3.  Векторное программирование
  4.  Полуопределенное программирование
  5.  Положительное линейное программирование (ПЛП)
  6.  Выпуклое программирование

Вопрос 24

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

  1.  
  2.  
  3.  
  4.  
  5.  Нет правильного ответа

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

  1.  3
  2.  
  3.  
  4.  
  5.  
  6.  

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

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

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