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

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

Вариант 1848617068.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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


  1.  Включений-Исключений
  2.  Форда-Фалкерсона
  3.  Флойда-Уоршолла
  4.  Беллмана-Форда
  5.  Немхаузера-Ульмана

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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


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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

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

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

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

Вопрос 14

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

  1.  дерандомизация
  2.  алгоритм Кристофидеса
  3.  динамическое программирование с отбором наиболее легких наборов
  4.  жадный алгоритм для рюкзака

Вопрос 15

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

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

Вопрос 16

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 17

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 18

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

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

Вопрос 19

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 20

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

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