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

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

Вариант 1403858258.

Ваше имя*:

Вопрос 1

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 2

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

  1.  
  2.  
  3.  
  4.  

Вопрос 3

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 4

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

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

Вопрос 5

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

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

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

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

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

Вопрос 6

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


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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 10

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

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

Вопрос 11

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

  1.  
  2.  
  3.  
  4.  3

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

  1.  линейное
  2.  квадратичное
  3.  экспоненциальное
  4.  полином, но степени больше 2
  5.  

Вопрос 20

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

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