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

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

Вариант 3437501001.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

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

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

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

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

Вопрос 17

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


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

Вопрос 18

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

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

Вопрос 19

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

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

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

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

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

Вопрос 20

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

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

Вопрос 21

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

  1.  
  2.  
  3.  3
  4.  

Вопрос 22

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

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

Вопрос 23

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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

  1.  
  2.  
  3.  
  4.  

Вопрос 27

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

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

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

  1.  
  2.  
  3.  
  4.  
  5.