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

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

Вариант 1148039780.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

  1.  
  2.  
  3.  
  4.  

Вопрос 5

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

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

Вопрос 6

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 7

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

  1.  
  2.  
  3.  3
  4.  

Вопрос 8

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

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

Вопрос 9

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

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

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

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

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

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

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

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

Вопрос 18

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


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

Вопрос 19

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

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

Вопрос 20

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

Напомним, что у нас n переменных и m скобок, p — вероятность появления переменной в каждой скобке.


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