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

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

Вариант 1166846517.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 4

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

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

Вопрос 5

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

  1.  
  2.  
  3.  
  4.  

Вопрос 9

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

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

Вопрос 10

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

  1.  
  2.  
  3.  
  4.  

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

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

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

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

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

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

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

Вопрос 28

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

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

Вопрос 29

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


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

Вопрос 30

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

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