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

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

Вариант 3287951010.

Ваше имя*:

Вопрос 1

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

  1.  
  2.  
  3.  
  4.  

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

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

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 9

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 10

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

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

Вопрос 11

Метод многократного запуска вероятностного алгоритма, с целью уменьшения вероятности ошибки называется:

  1.  «дерандомизация»
  2.  «отладка вероятности»
  3.  «антирандомизация»
  4.  «вероятностная амплификация»

Вопрос 12

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


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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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


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

Вопрос 16

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

  1.  
  2.  3
  3.  
  4.  

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

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

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

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

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 27

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

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

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

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

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