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

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

Вариант 696207099.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

  1.  
  2.  
  3.  
  4.  

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

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

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

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 18

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

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

Вопрос 19

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


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

Вопрос 20

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

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

Вопрос 21

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

  1.  
  2.  
  3.  3
  4.  

Вопрос 22

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

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

Вопрос 23

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 27

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

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

Вопрос 28

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 29

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

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

Вопрос 30

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

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