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

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

Вариант 1642343394.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

  1.  
  2.  
  3.  
  4.  

Вопрос 11

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

  1.  
  2.  
  3.  
  4.  

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 27

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

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

Вопрос 28

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

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

Вопрос 29

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


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

Вопрос 30

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

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