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

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

Вариант 28142162.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

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

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

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

Вопрос 13

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


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

Вопрос 14

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

  1.  
  2.  
  3.  
  4.  

Вопрос 18

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

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

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

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

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

Вопрос 19

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

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

Вопрос 20

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

  1.  
  2.  3
  3.  
  4.  

Вопрос 21

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

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

Вопрос 22

Для чего применяется «метод условных вероятностей»:

  1.  Метод Монте-Карло
  2.  Рандомизация
  3.  Шервудские алгоритмы
  4.  Метод Лас-Вегас
  5.  Дерандомизация
  6.  Демократизация
  7.  Дератизация

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 28

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

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

Вопрос 29

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


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

Вопрос 30

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

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