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

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

Вариант 2000374618.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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


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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

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

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

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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


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

Вопрос 12

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

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

Вопрос 13

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

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

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

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

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

Вопрос 14

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

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

Вопрос 15

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 26

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

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

Вопрос 27

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 28

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 29

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

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

Вопрос 30

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

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