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

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

Вариант 3971682636.

Ваше имя*:

Вопрос 1

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

Напомним, что у нас n переменных и m скобок, p — вероятность появления переменной в каждой скобке.


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

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

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

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

Вопрос 5

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

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

Вопрос 6

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 24

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

  1.  
  2.  3
  3.  
  4.  

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

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

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

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

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