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

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

Вариант 3275197831.

Ваше имя*:

Вопрос 1

В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке полиномиальность в среднем доказана для следующего распределения входных данных:

  1.  и стоимости и веса выбираются случайно
  2.  стоимости произвольные, веса выбираются случайно
  3.  веса произвольные, стоимость выбираются случайно

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

  1.  MAX-CUT
  2.  MAX-SAT
  3.  Рюкзак-выполнимость
  4.  Рюкзак-оптимизация
  5.  TSP
  6.  MIN-CUT

Вопрос 7

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 8

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


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

Вопрос 9

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

  1.  
  2.  
  3.  
  4.  

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

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

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

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

Эйлеров цикл в графе:

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

Вопрос 19

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

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

Вопрос 20

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

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