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

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

Вариант 3220750101.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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


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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

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

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

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

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

Вопрос 18

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

  1.  
  2.  
  3.  
  4.  

Вопрос 19

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

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

Вопрос 28

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 29

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

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

Вопрос 30

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

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