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

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

Вариант 395976900.

Прошло 00:00:01.
Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

  1.  
  2.  
  3.  
  4.  

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

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

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

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

  1.  
  2.  
  3.  3
  4.  

Вопрос 16

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

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

Вопрос 17

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

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

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

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

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