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

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

Вариант 2340955144.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 5

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

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

Вопрос 6

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 7

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 8

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

  1.  
  2.  
  3.  
  4.  

Вопрос 9

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


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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

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

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

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

Вопрос 13

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

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

Вопрос 14

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

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

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

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

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

Вопрос 15

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

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

Вопрос 16

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

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

Вопрос 28

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

  1.  
  2.  
  3.  
  4.  

Вопрос 29

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

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

Вопрос 30

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

m
элементов,
n
подмножеств
p
вероятность ненулевого элемента в матрице инцидентности
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Эффективные_алгоритмы-Экзамен»