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

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

Вариант 1365776248.

Ваше имя*:

Вопрос 1

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


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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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

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

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

  1.  
  2.  
  3.  
  4.  

Вопрос 17

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

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

Вопрос 18

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

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

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

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

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

Вопрос 19

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

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

Вопрос 20

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

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

Вопрос 28

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 29

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

  1.  3
  2.  
  3.  
  4.  

Вопрос 30

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

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