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

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

Вариант 3810162098.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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


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