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

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

Вариант 2466210936.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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


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

Вопрос 3

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

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

Вопрос 4

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 13

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

  1.  
  2.  
  3.  
  4.  

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

Для чего применяется «метод условных вероятностей»:

  1.  Дерандомизация
  2.  Рандомизация
  3.  Дератизация
  4.  Шервудские алгоритмы
  5.  Метод Монте-Карло
  6.  Демократизация
  7.  Метод Лас-Вегас

Вопрос 23

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 24

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 25

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

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

Вопрос 26

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 27

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

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

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

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

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