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

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

Вариант 3289764829.

Ваше имя*:

Вопрос 1

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

  1.  3
  2.  
  3.  
  4.  

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

  1.  
  2.  
  3.  
  4.  

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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


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

Вопрос 16

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 17

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


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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 28

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

  1.  
  2.  
  3.  
  4.  

Вопрос 29

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

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

Вопрос 30

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

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