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

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

Вариант 2438987564.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

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

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

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

Вопрос 6

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

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

Вопрос 7

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


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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

  1.  
  2.  3
  3.  
  4.  

Вопрос 15

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


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

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

  1.  
  2.  
  3.  
  4.  

Вопрос 19

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

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

Вопрос 20

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

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

Вопрос 28

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 29

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

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

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

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

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

Вопрос 30

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

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