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

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

Вариант 2307652076.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

  1.  
  2.  3
  3.  
  4.  

Вопрос 3

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 4

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

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

Вопрос 5

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


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

Вопрос 6

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

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

Вопрос 7

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

  1.  
  2.  
  3.  
  4.  

Вопрос 8

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 17

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 18

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

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

Вопрос 19

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

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

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

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

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