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

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

Вариант 755935364.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 3

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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


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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

  1.  
  2.  
  3.  3
  4.  

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

С какой точностью работает модифицированный жадный алгоритм для задачи о рюкзаке из соответствующей темы?

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

Вопрос 15

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

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

Вопрос 16

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

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

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

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

Вопрос 20

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

  1.  
  2.  
  3.  
  4.  

Вопрос 21

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

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

Вопрос 22

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

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

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

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

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

Вопрос 23

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

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

Вопрос 24

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

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

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