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

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

Вариант 1641030485.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

  1.  
  2.  
  3.  
  4.  

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

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

  1.  
  2.  
  3.  
  4.  3

Вопрос 26

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

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

Вопрос 27

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

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

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

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

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