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

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

Вариант 2913009896.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

Эйлеров цикл в графе:

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 11

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

  1.  
  2.  
  3.  
  4.  

Вопрос 12

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

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

Вопрос 13

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 19

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

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

Вопрос 20

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

  1.  набранных отборов
  2.  доминирующих наборов
  3.  недопустимых наборов
  4.  допустимых наборов
  5.  отборных наборов
  6.  наборов максимальной стоимости для каждого веса
  7.  наборов минимального веса для каждой стоимости
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-6-course-ispras-weekly»