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

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

Вариант 3278386354.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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


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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

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

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

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

Вопрос 13

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

  1.  
  2.  
  3.  
  4.  

Вопрос 14

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

  1.  Построение эффективных алгоритмов муравьиной колонии
  2.  Построение эффективных в среднем алгоритмов
  3.  Применение эволюционных алгоритмов

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

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

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

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

Вопрос 20

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

  1.  MAX-CUT
  2.  Рюкзак-выполнимость
  3.  MIN-CUT
  4.  TSP
  5.  MAX-SAT
  6.  Рюкзак-оптимизация
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-6-course-ispras-weekly»