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

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

Вариант 4276257649.

Ваше имя*:

Вопрос 1

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

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

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

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

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

Вопрос 2

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

  1.  3
  2.  
  3.  
  4.  

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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


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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 13

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

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

Вопрос 14

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 15

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

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

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

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

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

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 23

Цикл, проходящий через все ребра графа по одному разу, называется

  1.  Наполеонов цикл
  2.  Цикл Нельсона
  3.  Эйлеров цикл
  4.  Гамильтонов цикл
  5.  Петля Нестерова

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

  1.  
  2.  
  3.  
  4.  

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

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

  1.  Флойда-Уоршелла
  2.  Эдмондса-Карпа
  3.  Беллмана-Форда
  4.  Каргера-Штейна
  5.  Форда-Фалкерсона
  6.  Немхаузера-Ульмана
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Эффективные_алгоритмы-Экзамен»