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

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

Вариант 277531534.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

  1.  
  2.  
  3.  
  4.  3

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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


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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

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

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

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

Вопрос 20

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

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

Вопрос 21

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 22

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

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

Вопрос 23

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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


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

Вопрос 27

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

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

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

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

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

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

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

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