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

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

Вариант 321458913.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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


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

Вопрос 14

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

  1.  
  2.  
  3.  
  4.  

Вопрос 15

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

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

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

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

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

Вопрос 16

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

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

Вопрос 17

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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


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