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

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

Вариант 4226047962.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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


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

Вопрос 8

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


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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 18

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

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

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

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

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

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

  1.  3
  2.  
  3.  
  4.  

Вопрос 23

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

  1.  
  2.  
  3.  
  4.  

Вопрос 24

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

  1.  
  2.  
  3.  
  4.  

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

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

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

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

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