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

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

Вариант 1706472710.

Ваше имя*:

Вопрос 1

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 2

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


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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

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

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

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

Вопрос 6

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


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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

Паросочетание, покрывающее все вершины графа, называется

  1.  покрывающим
  2.  максимальным
  3.  совершенным
  4.  сочетающим
  5.  вершинным

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 13

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

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

Вопрос 14

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 26

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

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

Вопрос 27

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

  1.  
  2.  
  3.  
  4.  

Вопрос 28

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

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

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

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

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

Вопрос 29

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

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

Вопрос 30

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

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