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

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

Вариант 4250524775.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

  1.  
  2.  
  3.  
  4.  

Вопрос 13

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

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

Вопрос 14

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

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

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

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

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

Вопрос 23

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

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

Вопрос 24

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


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

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

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

Вопрос 28

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

  1.  3
  2.  
  3.  
  4.  

Вопрос 29

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

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

Вопрос 30

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

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