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

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

Вариант 2831027807.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

  1.  
  2.  
  3.  
  4.  3

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

  1.  Гамильтоновой
  2.  Евклидовой
  3.  Треугольной
  4.  Эйлеровой
  5.  Метрической

Вопрос 8

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

  1.  
  2.  
  3.  
  4.  

Вопрос 9

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

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

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

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

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

Вопрос 10

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

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

Вопрос 11

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


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

Вопрос 12

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

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

Вопрос 13

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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