Еженедельный по «сложности алгоритмов» для 6 курса МФТИ — вопросы

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
11121314151617181920
Еженедельный по «сложности алгоритмов» для 6 курса МФТИ

Вариант 4158870002.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

  1.  
  2.  
  3.  
  4.  

Вопрос 6

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

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

Вопрос 7

Какие из подходов к решению вычислительно трудных задач изучались в курсе?

  1.  Построение точных алгоритмов с субэкспоненциальными оценками сложности
  2.  Построение эффективных приближенных алгоритмов с оценками точности в худшем случае
  3.  Построение эффективных эвристических алгоритмов

Вопрос 8

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

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

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

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

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

Вопрос 9

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

  1.  3
  2.  
  3.  
  4.  

Вопрос 10

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 11

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


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

Вопрос 12

Какие из подходов к решению вычислительно трудных задач изучались в курсе?

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

  1.  
  2.  
  3.  
  4.  

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

Какие из подходов к решению вычислительно трудных задач изучались в курсе?

  1.  Построение эффективных вероятностных приближенных алгоритмов с оценками точности в худшем случае
  2.  Построение эффективных метаэвристик
  3.  Применение теории генетических алгоритмов

Вопрос 20

  1.  
  2.  
  3.  
  4.  
  5.  
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-6-course-ispras-weekly»