Еженедельный по «сложности алгоритмов» для 3 курса ИСПРАН — вопросы

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
Еженедельный по «сложности алгоритмов» для 3 курса ИСПРАН

Вариант 1234527703.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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